A globally convergent non-interior point algorithm with full Newton step for second-order cone programming. (English) Zbl 1212.90299
Summary: A non-interior point algorithm based on projection for second-order cone programming problems is proposed and analyzed. The main idea of the algorithm is that we cast the complementary equation in the primal-dual optimality conditions as a projection equation. By using this reformulation, we only need to solve a system of linear equations with the same coefficient matrix \(A\) and compute two simple projections at each iteration, without performing any line search. This algorithm can start from an arbitrary point, and does not require the row vectors of \(A\) to be linearly independent. We prove that our algorithm is globally convergent under weak conditions. Preliminary numerical results demonstrate the effectiveness of our algorithm.
MSC:
| 90C25 | Convex programming |
| 90C30 | Nonlinear programming |
| 90C51 | Interior-point methods |
| 65K05 | Numerical mathematical programming methods |
| 65Y20 | Complexity and performance of numerical algorithms |
Keywords:
non-interior point algorithm; second-order cone programming; Jordan product; optimality condition; central pathSoftware:
SDPT3References:
| [1] | F. Alizadeh, D. Goldfarb: Second-order cone programming. Math. Program. 95 (2003), 3–51. · Zbl 1153.90522 · doi:10.1007/s10107-002-0339-5 |
| [2] | H. Y. Benson, R. J. Vanderbei: Solving problems with semidefinite and related constraints using interior-point methods for nonlinear programming. Math. Program. Ser. B 95 (2003), 279–302. · Zbl 1030.90138 · doi:10.1007/s10107-002-0350-x |
| [3] | A. Ben-Tal, A. Nemirovski: On polyhedral approximations of the second order cone. Math. Oper. Res. 26 (2001), 193–205. · Zbl 1082.90133 · doi:10.1287/moor.26.2.193.10561 |
| [4] | X. D. Chen, D. Sun, J. Sun: Complementarity functions and numerical experiments on some smoothing Newton methods for second-order-cone complementarity problems. Comput. Optim. Appl. 25 (2003), 39–56. · Zbl 1038.90084 · doi:10.1023/A:1022996819381 |
| [5] | I. C. Choi, C. L. Monma, D. Shanno: Further developments of primal-dual interior point methods. ORSA J. Comput. 2 (1990), 304–311. · Zbl 0757.90051 |
| [6] | J. Faraut, A. Korányi: Analysis on Symmetric Cones. Oxford University Press, Oxford, 1994. |
| [7] | L. Faybusovich: Euclidean Jordan algebras and interior-point algorithms. Positivity 1 (1997), 331–357. · Zbl 0973.90095 · doi:10.1023/A:1009701824047 |
| [8] | L. Faybusovich: Linear systems in Jordan algebras and primal-dual interior point algorithms. J. Comput. Appl. Math. 86 (1997), 149–175. · Zbl 0889.65066 · doi:10.1016/S0377-0427(97)00153-2 |
| [9] | M. Fukushima, Z.-Q. Luo, P. Tseng: Smoothing functions for second-order cone complementarity problems. SIAM J. Optim. 12 (2002), 436–460. · Zbl 0995.90094 · doi:10.1137/S1052623400380365 |
| [10] | Q. M. Han: Projection and contraction methods for semidefinite programming. Appl. Math. Comput. 95 (1998), 275–289. · Zbl 0938.90054 · doi:10.1016/S0096-3003(97)10113-8 |
| [11] | S. Hayashi, N. Yamashita, M. Fukushima: A combined smoothing and regularization method for monotone second-order cone complementarity problems. SIAM J. Optim. 15 (2005), 593–615. · Zbl 1114.90139 · doi:10.1137/S1052623403421516 |
| [12] | B. S. He, L. Z. Liao, D. R. Han, H. Yang: A new inexact alternating directions method for monotone variational inequality. Math. Program. 92 (2002), 103–118. · Zbl 1009.90108 · doi:10.1007/s101070100280 |
| [13] | Z. Huang, W. Gu: A smoothing-type algorithm for solving linear complementarity problems with strong convergence properties. Appl. Math. Optim. 57 (2008), 17–29. · Zbl 1190.90236 · doi:10.1007/s00245-007-9004-y |
| [14] | S. Kim, M. Kojima: Second order cone programming relaxations of nonconvex quadratic optimization problems. Optim. Methods Softw. 15 (2001), 201–224. · Zbl 1109.90327 · doi:10.1080/10556780108805819 |
| [15] | Y. J. Kuo, H. D. Mittelmann: Interior point methods for second-order cone programming and OR applications. Comput. Optim. Appl. 28 (2004), 255–285. · Zbl 1084.90046 · doi:10.1023/B:COAP.0000033964.95511.23 |
| [16] | Y. Liu, L. Zhang, Y. Wang: Analysis of a smoothing method for symmetric conic linear programming. J. Appl. Math. Comput. 22 (2006), 133–148. · Zbl 1132.90353 · doi:10.1007/BF02896466 |
| [17] | M. S. Lobo, L. Vandenberghe, S. Boyd, H. Lebret: Applications of second order cone programming. Linear Algebra Appl. 284 (1998), 193–228. · Zbl 0946.90050 · doi:10.1016/S0024-3795(98)10032-0 |
| [18] | R. D. C. Monteiro, T. Tsuchiya: Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions. Math. Program. 88 (2000), 61–83. · Zbl 0967.65077 · doi:10.1007/PL00011378 |
| [19] | R. D. C. Monteiro, Y. Zhang: A unified analysis for a class of path-following primal-dual interior-point algorithms for semidefinite programming. Math. Program. 81 (1998), 281–299. · Zbl 0919.90109 |
| [20] | Yu. E. Nesterov, A. S. Nemirovskii: Interior-Point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia, 1994. · Zbl 0824.90112 |
| [21] | B. K. Rangarajan: Polynomial convergence of infeasible-interior-point methods over symmetric cones. SIAM J. Optim. 16 (2006), 1211–1229. · Zbl 1131.90043 · doi:10.1137/040606557 |
| [22] | B. Rangarajan, M. J. Todd: Convergence of infeasible-interior-point methods for self-scaled conic programming. Technical Report 1388. School of OR & IE, Cornell University. |
| [23] | S. H. Schmieta, F. Alizadeh: Extension of primal-dual interior-point algorithm to symmetric cones. Math. Program. 96 (2003), 409–438. · Zbl 1023.90083 · doi:10.1007/s10107-003-0380-z |
| [24] | S. H. Schmieta, F. Alizadeh: Associative and Jordan algebras, and polynomial time interior-point algorithms for symmetric cones. Math. Oper. Res. 26 (2001), 543–564. · Zbl 1073.90572 · doi:10.1287/moor.26.3.543.10582 |
| [25] | S. H. Schmieta, F. Alizadeh: Extension of commutative class of primal-dual interior point algorithms to symmetric cones. Technical Report RRR 13-99, RUTCOR. Rutgers University, August 1999. |
| [26] | D. Sun, J. Sun: Strong semismoothness of the Fischer-Burmeister SDC and SOC complementarity functions. Math. Program., Ser. A 103 (2005), 575–581. · Zbl 1099.90062 · doi:10.1007/s10107-005-0577-4 |
| [27] | M. Todd: Semidefinite optimization. Acta Numerica 10 (2001), 515–560. · Zbl 1105.65334 · doi:10.1017/S0962492901000071 |
| [28] | K. C. Toh, M. J. Todd, R. H. Tütüncü: SDPT3-A Matlab software package for semidefinite programming. Version 2.1. Optim. Methods Softw. 11 (1999), 545–581. · Zbl 0997.90060 · doi:10.1080/10556789908805762 |
| [29] | T. Tsuchiya: A convergence analysis of the scaling-invariant primal-dual path-following algorithms for second-order cone programming. Optim. Methods Softw. 11 (1999), 141–182. · Zbl 0957.90129 · doi:10.1080/10556789908805750 |
| [30] | T. Tsuchiya: A polynomial primal-dual path-following algorithm for second-order cone programming. Technical Report No. 649. The Institute of Statistical Mathematics, Tokyo, 1997. |
| [31] | S. L. Wang, H. Yang, B. S. He: Solving a class of asymmetric variational inequalities by a new alternating direction method. Comput. Math. Appl. 40 (2000), 927–937. · Zbl 0959.49009 · doi:10.1016/S0898-1221(00)85004-X |
| [32] | S. J. Wright: Primal-Dual Interior Point Methods. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, 1997. · Zbl 0863.65031 |
| [33] | G. L. Xue, Y. Y. Ye: An efficient algorithm for minimizing a sum of Euclidean norms with applications. SIAM J. Optim. 7 (1997), 1017–1036. · Zbl 0885.68074 · doi:10.1137/S1052623495288362 |
| [34] | Y. Zhang: On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming. SIAM J. Optim. 8 (1998), 365–386. · Zbl 0913.65050 · doi:10.1137/S1052623495296115 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
