B.Г. Жадан. Вариант аффинно-масштабирующего метода для задачи конического программирования на конусе второго порядка ... С. 114-124.

УДК 519.856

MSC: 90С22  

DOI:  10.21538/0134-4889-2017-23-3-114-124  

Полная версия статьи

Работа выполнена при поддержке РФФИ, грант 15-01-08259, а также при содействии Программы ведущих научных школ (НШ-8860.2016.1).

Рассматривается линейная задача конического программирования, в которой конус является прямым произведением конусов второго порядка (конусов Лоренца). Для ее решения предлагается прямой метод аффинно-масштабирующего типа, обобщающий соответствующий метод для линейного программирования. Метод можно рассматривать как специальный способ решения системы необходимых и достаточных условий оптимальности для пары взаимно двойственных задач конического программирования. На основании этих условий выводится зависимость двойственных переменных от прямых, которая подставляется в условие дополнительности. Получившаяся система уравнений относительно прямых переменных решается с помощью метода простой итерации. Стартовые точки в методе принадлежат конусу, но не обязательно должны удовлетворять линейным ограничениям типа равенства. При предположении о невырожденности решений прямой и двойственной задач и их строгой дополнительности доказывается локальная сходимость метода с линейной скоростью.  

Ключевые слова: задача конического программирования, конус второго порядка, аффинно-масштабирующий метод, локальная сходимость.  

Список литературы

 1. Alizadeh F., Goldfarb D. Second-order cone programming // Math. Program., Ser. B.  2003. Vol. 95.  P. 3-51. doi:  10.1016/j.ifacol.2015.11.079.  

2. Applications of second order cone programming  M.S. Lobo, L. Vandenberghe, S. Boyd, H. Lebret // Linear Algebra Appl. 1998. Vol.284. P.193-228. doi: 10.1016/S0024-3795(98)10032-0.  

3. Anjos M.F., Lasserre J.B., eds. Handbook on semidefinite, cone and polynomial optimization: theory, algorithms, software and applications. New York: Springer, 2011. 960 p. doi: 10.1007/978-1-4614-0769-0.  

4.  Nesterov Y.E., Todd M.J. Primal-dual interior-point methods for self-scaled cones // SIAM J. Optim. 1998. Vol. 8, no. 2. P. 324-364. doi: 10.1137/S1052623495290209.  

5. Monteiro R.D.C., Tsuchia T. Polynomial convergence of primal-dual algorithms for the second-order cone program bazed on MZ-family directions // Math. Program. 2000. Vol. 88. P. 61-83. doi:  10.1007/s101070000137.  

6. Muramatsu M. A pivoting procedure for a class of second-order cone programming // Optim. Methods Softw. 2006. Vol. 21, № 2. P. 295-315. doi: /10.1080/10556780500094697.  

7. Evtushenko Yu., Zhadan V. Stable barrier-projection and barrier-newton methods in linear programming // Comput. Optimiz. and Appl. 1994. Vol. 3, no. 4. P. 289-304.  

8. Бабынин М.С., Жадан В.Г. Прямой метод внутренней точки для линейной задачи полуопределенного программирования // Журн. вычисл. математики и мат. физики. 2008. Т. 48, № 10. С. 1780-1801.  

9. Pataki G. Cone-LP's and semidefinite programs: geometry and simplex-type method // Proc. Conf. on Integer Programming and Combinatorial Optimization (IPCO5), 1996. P. 1-13.  

10. Ортега Дж., Рейнболдт В. Итерационные методы решения систем нелинейных уравнений со многими неизвестными. М.: Мир, 1975. 560 c.  

Поступила  31.05.2017  

Жадан Виталий Григорьевич  
д-р физ.-мат. наук, профессор, главный науч. сотрудник  
Вычислительный центр им.А.А. Дородницына, ФИЦ Информатика и управление РАН, г. Москва 
e-mail: zhadan@ccas.ru

English

V.G. Zhadan. A variant of the affine-scaling method for a cone programming problem on a second-order cone.  

A linear cone programming problem in which the cone is the direct product of second-order cones (Lorentz cones) is considered. For its solution we propose a direct affine-scaling type method generalizing the corresponding method used in linear programming. The method can be considered as a special way to solve a system of necessary and sufficient optimality conditions for a pair of mutually dual cone programming problems. These conditions are used to derive the dependence of the dual variables on the primal variables, and the dependence is substituted into the complementarity condition. The obtained system of equations is solved with respect to the primal variables by the simple iteration method. The starting points in the method belong to the cone but do not necessarily satisfy the linear equality-type constraints. The local linear convergence of the method is proved under the assumption that the solutions of the primal and dual problems are nondegenerate and strictly complementary.  

Keywords: cone programming, second-order cone, affine-scaling method, local convergence.  

The paper was received by the Editorial Office on May 31, 2017.

Vitalii Grigor'evich Zhadan, Dr. Phys.-Math. Sci., Prof., Dorodnicyn Computing Centre, FRC CSC RAS,  Moscow, 119333 Russia, e-mail: zhadan@ccas.ru .