| Title:
|
A globally convergent non-interior point algorithm with full Newton step for second-order cone programming (English) |
| Author:
|
Fang, Liang |
| Author:
|
He, Guoping |
| Author:
|
Sun, Li |
| Language:
|
English |
| Journal:
|
Applications of Mathematics |
| ISSN:
|
0862-7940 (print) |
| ISSN:
|
1572-9109 (online) |
| Volume:
|
54 |
| Issue:
|
5 |
| Year:
|
2009 |
| Pages:
|
447-464 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
non-interior point algorithm |
| Keyword:
|
second-order cone programming |
| Keyword:
|
Jordan product |
| Keyword:
|
optimality condition |
| Keyword:
|
central path |
| MSC:
|
65K05 |
| MSC:
|
65Y20 |
| MSC:
|
90C25 |
| MSC:
|
90C30 |
| MSC:
|
90C51 |
| idZBL:
|
Zbl 1212.90299 |
| idMR:
|
MR2545411 |
| DOI:
|
10.1007/s10492-009-0029-1 |
| . |
| Date available:
|
2010-07-20T13:22:53Z |
| Last updated:
|
2020-07-02 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/140378 |
| . |
| Reference:
|
[1] Alizadeh, F., Goldfarb, D.: Second-order cone programming.Math. Program. 95 (2003), 3-51. Zbl 1153.90522, MR 1971381, 10.1007/s10107-002-0339-5 |
| Reference:
|
[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. Zbl 1030.90138, MR 1976482, 10.1007/s10107-002-0350-x |
| Reference:
|
[3] Ben-Tal, A., Nemirovski, A.: On polyhedral approximations of the second order cone.Math. Oper. Res. 26 (2001), 193-205. Zbl 1082.90133, MR 1895823, 10.1287/moor.26.2.193.10561 |
| Reference:
|
[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. Zbl 1038.90084, MR 1996662, 10.1023/A:1022996819381 |
| Reference:
|
[5] Choi, I. C., Monma, C. L., Shanno, D.: Further developments of primal-dual interior point methods.ORSA J. Comput. 2 (1990), 304-311. 10.1287/ijoc.2.4.304 |
| Reference:
|
[6] Faraut, J., Korányi, A.: Analysis on Symmetric Cones.Oxford University Press Oxford (1994). MR 1446489 |
| Reference:
|
[7] Faybusovich, L.: Euclidean Jordan algebras and interior-point algorithms.Positivity 1 (1997), 331-357. Zbl 0973.90095, MR 1660399, 10.1023/A:1009701824047 |
| Reference:
|
[8] Faybusovich, L.: Linear systems in Jordan algebras and primal-dual interior point algorithms.J. Comput. Appl. Math. 86 (1997), 149-175. Zbl 0889.65066, MR 1491432, 10.1016/S0377-0427(97)00153-2 |
| Reference:
|
[9] Fukushima, M., Luo, Z.-Q., Tseng, P.: Smoothing functions for second-order cone complementarity problems.SIAM J. Optim. 12 (2002), 436-460. MR 1885570, 10.1137/S1052623400380365 |
| Reference:
|
[10] Han, Q. M.: Projection and contraction methods for semidefinite programming.Appl. Math. Comput. 95 (1998), 275-289. Zbl 0938.90054, MR 1633814, 10.1016/S0096-3003(97)10113-8 |
| Reference:
|
[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. Zbl 1114.90139, MR 2144183, 10.1137/S1052623403421516 |
| Reference:
|
[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. MR 1892298, 10.1007/s101070100280 |
| Reference:
|
[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. Zbl 1190.90236, MR 2373004, 10.1007/s00245-007-9004-y |
| Reference:
|
[14] Kim, S., Kojima, M.: Second order cone programming relaxations of nonconvex quadratic optimization problems.Optim. Methods Softw. 15 (2001), 201-224. MR 1892585, 10.1080/10556780108805819 |
| Reference:
|
[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. Zbl 1084.90046, MR 2080003, 10.1023/B:COAP.0000033964.95511.23 |
| Reference:
|
[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. Zbl 1132.90353, MR 2248446, 10.1007/BF02896466 |
| Reference:
|
[17] Lobo, M. S., Vandenberghe, L., Boyd, S., Lebret, H.: Applications of second order cone programming.Linear Algebra Appl. 284 (1998), 193-228. Zbl 0946.90050, MR 1655138 |
| Reference:
|
[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. Zbl 0967.65077, MR 1765893, 10.1007/PL00011378 |
| Reference:
|
[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. MR 1617748, 10.1007/BF01580085 |
| Reference:
|
[20] Nesterov, Yu. E., Nemirovskii, A. S.: Interior-Point Polynomial Algorithms in Convex Programming.SIAM Philadelphia (1994). Zbl 0824.90112, MR 1258086 |
| Reference:
|
[21] Rangarajan, B. K.: Polynomial convergence of infeasible-interior-point methods over symmetric cones.SIAM J. Optim. 16 (2006), 1211-1229. Zbl 1131.90043, MR 2219140, 10.1137/040606557 |
| Reference:
|
[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. |
| Reference:
|
[23] Schmieta, S. H., Alizadeh, F.: Extension of primal-dual interior-point algorithm to symmetric cones.Math. Program. 96 (2003), 409-438. MR 1993457, 10.1007/s10107-003-0380-z |
| Reference:
|
[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. Zbl 1073.90572, MR 1849884, 10.1287/moor.26.3.543.10582 |
| Reference:
|
[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. |
| Reference:
|
[26] Sun, D., Sun, J.: Strong semismoothness of the Fischer-Burmeister SDC and SOC complementarity functions.Math. Program., Ser. A 103 (2005), 575-581. Zbl 1099.90062, MR 2166550, 10.1007/s10107-005-0577-4 |
| Reference:
|
[27] Todd, M.: Semidefinite optimization.Acta Numerica 10 (2001), 515-560. Zbl 1105.65334, MR 2009698, 10.1017/S0962492901000071 |
| Reference:
|
[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. MR 1778429, 10.1080/10556789908805762 |
| Reference:
|
[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. Zbl 0957.90129, MR 1777456, 10.1080/10556789908805750 |
| Reference:
|
[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). |
| Reference:
|
[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. Zbl 0959.49009, MR 1781888, 10.1016/S0898-1221(00)85004-X |
| Reference:
|
[32] Wright, S. J.: Primal-Dual Interior Point Methods.Society for Industrial and Applied Mathematics (SIAM) Philadelphia (1997). Zbl 0863.65031, MR 1422257 |
| Reference:
|
[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. Zbl 0885.68074, MR 1479612, 10.1137/S1052623495288362 |
| Reference:
|
[34] Zhang, Y.: On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming.SIAM J. Optim. 8 (1998), 365-386. Zbl 0913.65050, MR 1618806, 10.1137/S1052623495296115 |
| . |
