| Title:
|
Full-Newton step infeasible interior-point algorithm for SDO problems (English) |
| Author:
|
Mansouri, Hossein |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
48 |
| Issue:
|
5 |
| Year:
|
2012 |
| Pages:
|
907-923 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
In this paper we propose a primal-dual path-following interior-point algorithm for semidefinite optimization. The algorithm constructs strictly feasible iterates for a sequence of perturbations of the given problem and its dual problem. Each main step of the algorithm consists of a feasibility step and several centering steps. At each iteration, we use only full-Newton step. Moreover, we use a more natural feasibility step, which targets at the $\mu^+$-center. The iteration bound of the algorithm coincides with the currently best iteration bound for semidefinite optimization problems. (English) |
| Keyword:
|
semidefinite optimization |
| Keyword:
|
infeasible interior-point method |
| Keyword:
|
primal-dual method |
| Keyword:
|
polynomial complexity |
| Keyword:
|
Newton-step |
| Keyword:
|
optimal solutions |
| MSC:
|
90C05 |
| MSC:
|
90C51 |
| idMR:
|
MR3086859 |
| . |
| Date available:
|
2012-12-17T13:31:54Z |
| Last updated:
|
2013-09-24 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/143089 |
| . |
| Reference:
|
[1] Alizadeh, F.: Interior-point methods in semidefinite programming with applications to combinatorial optimization..SIAM J. Optim. 5 (2006), 13-51. Zbl 0833.90087, MR 1315703, 10.1137/0805002 |
| Reference:
|
[2] Helmberg, C.: Semidefinite Programming for Combinatorial Optimization..Technical Report 00-34, Konrad-Zuse-Zentrum für Informationstechink Berlin 2000. |
| Reference:
|
[3] Horn, R. A., Johnson, C. R.: Topics in Matrix Analysis..Cambridge University Press, Cambridge 1991. Zbl 0801.15001, MR 1091716 |
| Reference:
|
[4] Klerk, E. de: Aspects of Semidefinite Programming..Kluwer Academic Publishers, Dordrecht 2002. Zbl 0991.90098, MR 2064921 |
| Reference:
|
[5] Kojima, M., Shida, M., Shindoh, S.: Local convergence of predictor-corrector infeasible interior-point algorithm for SDPs and SDLCPs..Math. Program. 80 (1998), 129-160. MR 1489167, 10.1007/BF01581723 |
| Reference:
|
[6] Kojima, M., Megiddo, N., Noma, T., Yoshise, A.: A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems..Lecture Notes in Comput. Sci. 538, Springer, Berlin 1991. Zbl 0745.90069, MR 1226025, 10.1007/3-540-54509-3 |
| Reference:
|
[7] Luo, Z. Q., Sturm, J., Zhang, S. Z.: Superlinear convergence of a symmetric primal-dual path following algorithm for semidefinite programming..SIAM J. Optim. 8 (1998), 59-81. Zbl 0910.90229, MR 1617436, 10.1137/S1052623496299187 |
| Reference:
|
[8] Lustig, I. J.: Feasible issues in a primal-dual interior point method for linear programming..Math. Program. 49 (1990/1991), 145-162. MR 1087451, 10.1007/BF01588785 |
| Reference:
|
[9] Lütkepohl, H.: Handbook of Matrices..John Wiley \& Sons, Chichester 1996. Zbl 0856.15001, MR 1433592 |
| Reference:
|
[10] Mansouri, H.: Full-Newton Step Interior-Point Methods for Conic Optimization..Ph.D. Thesis, Faculty of Mathematics and Computer Science, TU Delft, 2008. |
| Reference:
|
[11] Mansouri, H., Roos, C.: A new full-Newton step $o(n)$ infeasible interior-point algorithm for semidefinite optimization..J. Numer. Algorithms 52 (2009), 2, 225-255. Zbl 1180.65079, MR 2563703, 10.1007/s11075-009-9270-7 |
| Reference:
|
[12] Mansouri, H., Zangiabadi, M.: New complexity analysis of full Nesterov-Todd steps for semidefinite optimization..Bull. Iranian Math. Soc. 1 (2011), 269-286. MR 2850119 |
| Reference:
|
[13] Mansouri, H., Siyavash, T., Zangiabadi, M.: A path-following infeasible interior-point algorithm for semidefinite programming..Iranian J. Oper. Res. 3 (2012), 1, 11-30. |
| Reference:
|
[14] Nesterov, Y. E., Todd, M. J.: Self-scaled barriers and interior-point methods for convex programming..Math. Oper. Res. 22 (1997), 1, 1-42. Zbl 0871.90064, MR 1436572, 10.1287/moor.22.1.1 |
| Reference:
|
[15] Nesterov, Y. E., Todd, M. J.: Primal-dual interior-point methods for self-scaled cones..SIAM J. Optim. 8 (1998), 2, 324-364. Zbl 0922.90110, MR 1618802, 10.1137/S1052623495290209 |
| Reference:
|
[16] Peng, J., Roos, C., Terlaky, T.: Self-regular functions and new search directions for linear and semidefinite optimization..Math. Program. 93 (2002), 129-171. Zbl 1007.90037, MR 1912271, 10.1007/s101070200296 |
| Reference:
|
[17] Potra, F. A., Sheng, R.: A superlinearly convergent primal-dual infeasible-interior-point algorithm for semidefinite programming..SIAM J. Optim. 8 (1998), 1007-1028. Zbl 0917.65058, MR 1646116, 10.1137/S1052623495294955 |
| Reference:
|
[18] Roos, C.: A full-Newton step $O(n)$ infeasible interior-point algorithm for linear optimization..SIAM J. Optim. 16 (2006), 4, 1110-1136. Zbl 1131.90029, MR 2219135, 10.1137/050623917 |
| Reference:
|
[19] Roos, C., Terlaky, T., Vial, J.-Ph.: Theory and Algorithms for Linear Optimization. An Interior-Point Approach..John Wiley and Sons, Chichester 1997. (Second Edition Springer 2005.) Zbl 0954.65041, MR 1450094 |
| Reference:
|
[20] Wolkowicz, H., Saigal, R., Vandenberghe, L.: Handbook of Semidefinite Programming, Theory, Algorithms, and Applications..Kluwer Academic Publishers, Dordrecht 2000. Zbl 0962.90001, MR 1778223 |
| Reference:
|
[21] 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 |
| . |
