Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
semidefinite optimization; infeasible interior-point method; primal-dual method; polynomial complexity; Newton-step; optimal solutions
semidefinite optimization; infeasible interior-point method; primal-dual method; polynomial complexity; Newton-step; optimal solutions
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.
References:
[1] Alizadeh, F.: Interior-point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5 (2006), 13-51. DOI 10.1137/0805002 | MR 1315703 | Zbl 0833.90087
[2] Helmberg, C.: Semidefinite Programming for Combinatorial Optimization. Technical Report 00-34, Konrad-Zuse-Zentrum für Informationstechink Berlin 2000.
[3] Horn, R. A., Johnson, C. R.: Topics in Matrix Analysis. Cambridge University Press, Cambridge 1991. MR 1091716 | Zbl 0801.15001
[4] Klerk, E. de: Aspects of Semidefinite Programming. Kluwer Academic Publishers, Dordrecht 2002. MR 2064921 | Zbl 0991.90098
[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. DOI 10.1007/BF01581723 | MR 1489167
[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. DOI 10.1007/3-540-54509-3 | MR 1226025 | Zbl 0745.90069
[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. DOI 10.1137/S1052623496299187 | MR 1617436 | Zbl 0910.90229
[8] Lustig, I. J.: Feasible issues in a primal-dual interior point method for linear programming. Math. Program. 49 (1990/1991), 145-162. DOI 10.1007/BF01588785 | MR 1087451
[9] Lütkepohl, H.: Handbook of Matrices. John Wiley \& Sons, Chichester 1996. MR 1433592 | Zbl 0856.15001
[10] Mansouri, H.: Full-Newton Step Interior-Point Methods for Conic Optimization. Ph.D. Thesis, Faculty of Mathematics and Computer Science, TU Delft, 2008.
[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. DOI 10.1007/s11075-009-9270-7 | MR 2563703 | Zbl 1180.65079
[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
[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.
[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. DOI 10.1287/moor.22.1.1 | MR 1436572 | Zbl 0871.90064
[15] Nesterov, Y. E., Todd, M. J.: Primal-dual interior-point methods for self-scaled cones. SIAM J. Optim. 8 (1998), 2, 324-364. DOI 10.1137/S1052623495290209 | MR 1618802 | Zbl 0922.90110
[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. DOI 10.1007/s101070200296 | MR 1912271 | Zbl 1007.90037
[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. DOI 10.1137/S1052623495294955 | MR 1646116 | Zbl 0917.65058
[18] Roos, C.: A full-Newton step $O(n)$ infeasible interior-point algorithm for linear optimization. SIAM J. Optim. 16 (2006), 4, 1110-1136. DOI 10.1137/050623917 | MR 2219135 | Zbl 1131.90029
[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.) MR 1450094 | Zbl 0954.65041
[20] Wolkowicz, H., Saigal, R., Vandenberghe, L.: Handbook of Semidefinite Programming, Theory, Algorithms, and Applications. Kluwer Academic Publishers, Dordrecht 2000. MR 1778223 | Zbl 0962.90001
[21] 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
