Article
MSC:
65K05,
65Y20,
90C25,
90C30,
90C51 | MR 2545411 | Zbl 1212.90299 | DOI: 10.1007/s10492-009-0029-1
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
non-interior point algorithm; second-order cone programming; Jordan product; optimality condition; central path
non-interior point algorithm; second-order cone programming; Jordan product; optimality condition; central path
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 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.
References:
[1] Alizadeh, F., Goldfarb, D.: Second-order cone programming. Math. Program. 95 (2003), 3-51. DOI 10.1007/s10107-002-0339-5 | MR 1971381 | Zbl 1153.90522
[2] Benson, H. Y., Vanderbei, R. J.: Solving problems with semidefinite and related constraints using interior-point methods for nonlinear programming. Math. Program. Ser. B 95 (2003), 279-302. DOI 10.1007/s10107-002-0350-x | MR 1976482 | Zbl 1030.90138
[3] Ben-Tal, A., Nemirovski, A.: On polyhedral approximations of the second order cone. Math. Oper. Res. 26 (2001), 193-205. DOI 10.1287/moor.26.2.193.10561 | MR 1895823 | Zbl 1082.90133
[4] Chen, X. D., Sun, D., Sun, J.: Complementarity functions and numerical experiments on some smoothing Newton methods for second-order-cone complementarity problems. Comput. Optim. Appl. 25 (2003), 39-56. DOI 10.1023/A:1022996819381 | MR 1996662 | Zbl 1038.90084
[5] Choi, I. C., Monma, C. L., Shanno, D.: Further developments of primal-dual interior point methods. ORSA J. Comput. 2 (1990), 304-311. DOI 10.1287/ijoc.2.4.304
[6] Faraut, J., Korányi, A.: Analysis on Symmetric Cones. Oxford University Press Oxford (1994). MR 1446489
[7] Faybusovich, L.: Euclidean Jordan algebras and interior-point algorithms. Positivity 1 (1997), 331-357. DOI 10.1023/A:1009701824047 | MR 1660399 | Zbl 0973.90095
[8] Faybusovich, L.: Linear systems in Jordan algebras and primal-dual interior point algorithms. J. Comput. Appl. Math. 86 (1997), 149-175. DOI 10.1016/S0377-0427(97)00153-2 | MR 1491432 | Zbl 0889.65066
[9] Fukushima, M., Luo, Z.-Q., Tseng, P.: Smoothing functions for second-order cone complementarity problems. SIAM J. Optim. 12 (2002), 436-460. DOI 10.1137/S1052623400380365 | MR 1885570
[10] Han, Q. M.: Projection and contraction methods for semidefinite programming. Appl. Math. Comput. 95 (1998), 275-289. DOI 10.1016/S0096-3003(97)10113-8 | MR 1633814 | Zbl 0938.90054
[11] Hayashi, S., Yamashita, N., Fukushima, M.: A combined smoothing and regularization method for monotone second-order cone complementarity problems. SIAM J. Optim. 15 (2005), 593-615. DOI 10.1137/S1052623403421516 | MR 2144183 | Zbl 1114.90139
[12] He, B. S., Liao, L. Z., Han, D. R., Yang, H.: A new inexact alternating directions method for monotone variational inequality. Math. Program. 92 (2002), 103-118. DOI 10.1007/s101070100280 | MR 1892298
[13] Huang, Z., Gu, W.: A smoothing-type algorithm for solving linear complementarity problems with strong convergence properties. Appl. Math. Optim. 57 (2008), 17-29. DOI 10.1007/s00245-007-9004-y | MR 2373004 | Zbl 1190.90236
[14] Kim, S., Kojima, M.: Second order cone programming relaxations of nonconvex quadratic optimization problems. Optim. Methods Softw. 15 (2001), 201-224. DOI 10.1080/10556780108805819 | MR 1892585
[15] Kuo, Y. J., Mittelmann, H. D.: Interior point methods for second-order cone programming and OR applications. Comput. Optim. Appl. 28 (2004), 255-285. DOI 10.1023/B:COAP.0000033964.95511.23 | MR 2080003 | Zbl 1084.90046
[16] Liu, Y., Zhang, L., Wang, Y.: Analysis of a smoothing method for symmetric conic linear programming. J. Appl. Math. Comput. 22 (2006), 133-148. DOI 10.1007/BF02896466 | MR 2248446 | Zbl 1132.90353
[17] Lobo, M. S., Vandenberghe, L., Boyd, S., Lebret, H.: Applications of second order cone programming. Linear Algebra Appl. 284 (1998), 193-228. MR 1655138 | Zbl 0946.90050
[18] Monteiro, R. D. C., Tsuchiya, T.: 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. DOI 10.1007/PL00011378 | MR 1765893 | Zbl 0967.65077
[19] Monteiro, R. D. C., Zhang, Y.: A unified analysis for a class of path-following primal-dual interior-point algorithms for semidefinite programming. Math. Program. 81 (1998), 281-299. DOI 10.1007/BF01580085 | MR 1617748
[20] Nesterov, Yu. E., Nemirovskii, A. S.: Interior-Point Polynomial Algorithms in Convex Programming. SIAM Philadelphia (1994). MR 1258086 | Zbl 0824.90112
[21] Rangarajan, B. K.: Polynomial convergence of infeasible-interior-point methods over symmetric cones. SIAM J. Optim. 16 (2006), 1211-1229. DOI 10.1137/040606557 | MR 2219140 | Zbl 1131.90043
[22] Rangarajan, B., Todd, M. J.: Convergence of infeasible-interior-point methods for self-scaled conic programming. Technical Report 1388. School of OR & IE, Cornell University.
[23] Schmieta, S. H., Alizadeh, F.: Extension of primal-dual interior-point algorithm to symmetric cones. Math. Program. 96 (2003), 409-438. DOI 10.1007/s10107-003-0380-z | MR 1993457
[24] Schmieta, S. H., Alizadeh, F.: Associative and Jordan algebras, and polynomial time interior-point algorithms for symmetric cones. Math. Oper. Res. 26 (2001), 543-564. DOI 10.1287/moor.26.3.543.10582 | MR 1849884 | Zbl 1073.90572
[25] Schmieta, S. H., Alizadeh, F.: Extension of commutative class of primal-dual interior point algorithms to symmetric cones. Technical Report RRR 13-99, RUTCOR. Rutgers University, August 1999.
[26] Sun, D., Sun, J.: Strong semismoothness of the Fischer-Burmeister SDC and SOC complementarity functions. Math. Program., Ser. A 103 (2005), 575-581. DOI 10.1007/s10107-005-0577-4 | MR 2166550 | Zbl 1099.90062
[27] Todd, M.: Semidefinite optimization. Acta Numerica 10 (2001), 515-560. DOI 10.1017/S0962492901000071 | MR 2009698 | Zbl 1105.65334
[28] Toh, K. C., Todd, M. J., Tütüncü, R. H.: SDPT3-A Matlab software package for semidefinite programming. Version 2.1. Optim. Methods Softw. 11 (1999), 545-581. DOI 10.1080/10556789908805762 | MR 1778429
[29] Tsuchiya, T.: A convergence analysis of the scaling-invariant primal-dual path-following algorithms for second-order cone programming. Optim. Methods Softw. 11 (1999), 141-182. DOI 10.1080/10556789908805750 | MR 1777456 | Zbl 0957.90129
[30] Tsuchiya, T.: A polynomial primal-dual path-following algorithm for second-order cone programming. Technical Report No. 649. The Institute of Statistical Mathematics Tokyo (1997).
[31] Wang, S. L., Yang, H., He, B. S.: Solving a class of asymmetric variational inequalities by a new alternating direction method. Comput. Math. Appl. 40 (2000), 927-937. DOI 10.1016/S0898-1221(00)85004-X | MR 1781888 | Zbl 0959.49009
[32] Wright, S. J.: Primal-Dual Interior Point Methods. Society for Industrial and Applied Mathematics (SIAM) Philadelphia (1997). MR 1422257 | Zbl 0863.65031
[33] Xue, G. L., Ye, Y. Y.: An efficient algorithm for minimizing a sum of Euclidean norms with applications. SIAM J. Optim. 7 (1997), 1017-1036. DOI 10.1137/S1052623495288362 | MR 1479612 | Zbl 0885.68074
[34] Zhang, Y.: On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming. SIAM J. Optim. 8 (1998), 365-386. DOI 10.1137/S1052623495296115 | MR 1618806 | Zbl 0913.65050
Search
Partner of
