Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
semidefinite least-squares problem; interior-point method; polynomial complexity
semidefinite least-squares problem; interior-point method; polynomial complexity
Summary:
We propose a feasible primal-dual path-following interior-point algorithm for semidefinite least squares problems (SDLS). At each iteration, the algorithm uses only full Nesterov-Todd steps with the advantage that no line search is required. Under new appropriate choices of the parameter $\beta $ which defines the size of the neighborhood of the central-path and of the parameter $\theta $ which determines the rate of decrease of the barrier parameter, we show that the proposed algorithm is well defined and converges to the optimal solution of SDLS. Moreover, we obtain the currently best known iteration bound for the algorithm with a short-update method, namely, $\mathcal {O}(\sqrt {n}\log (n/\epsilon ))$. Finally, we report some numerical results to illustrate the efficiency of our proposed algorithm.
References:
[1] Achache, M.: A new primal-dual path-following method for convex quadratic programming. Comput. Appl. Math. 25 (2006), 97-110. DOI 10.1590/S0101-82052006000100005 | MR 2267615 | Zbl 1213.90187
[2] Achache, M.: Complexity analysis of an interior point algorithm for the semidefinite optimization based on a kernel function with a double barrier term. Acta Math. Sin., Engl. Ser. 31 (2015), 543-556. DOI 10.1007/s10114-015-1314-4 | MR 3306664 | Zbl 1308.65086
[3] Achache, M.: A new parameterized kernel function for LO yielding the best known iteration bound for a large-update interior point algorithm. Afr. Mat. 27 (2016), 591-601. DOI 10.1007/s13370-015-0363-2 | MR 3500476 | Zbl 1378.90089
[4] Achache, M., Boudiaf, N.: Complexity analysis of primal-dual algorithms for the semidefinite linear complementarity problem. Rev. Anal. Numér. Théor. Approx. 40 (2011), 95-106. MR 3059815 | Zbl 1274.90371
[5] Achache, M., Guerra, L.: A full Nesterov-Todd-step feasible primal-dual interior point algorithm for convex quadratic semi-definite optimization. Appl. Math. Comput. 231 (2014), 581-590. DOI 10.1016/j.amc.2013.12.070 | MR 3174056 | Zbl 1410.90230
[6] Achache, M., Roumili, H., Keraghel, A.: A numerical study of an infeasible primal-dual path-following algorithm for linear programming. Appl. Math. Comput. 186 (2007), 1472-1479. DOI 10.1016/j.amc.2006.07.135 | MR 2316940 | Zbl 1117.65082
[7] Achache, M., Tabchouche, N.: A full-Newton step feasible interior-point algorithm for monotone horizontal linear complementarity problems. Optim. Lett. 13 (2019), 1039-1057. DOI 10.1007/s11590-018-1328-9 | MR 3956989 | Zbl 1425.90116
[8] Alizadeh, F., Haeberly, J.-P. A., Overton, M. L.: A New Primal-Dual Interior-Point Methods for Semidefinite Programming. Technical Report 659. Computer Science Department, Courant Institute of Mathematical Sciences, New York University, New York (1994). MR 1636549
[9] Alzalg, B.: A logarithmic barrier interior-point method based on majorant functions for second-order cone programming. Optim. Lett. 14 (2020), 729-746. DOI 10.1007/s11590-019-01404-1 | MR 4075446 | Zbl 1442.90177
[10] Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004). DOI 10.1017/CBO9780511804441 | MR 2061575 | Zbl 1058.90049
[11] Boyd, S., Xiao, L.: Least-squares covariance matrix adjustment. SIAM J. Matrix Anal. Appl. 27 (2005), 532-546. DOI 10.1137/040609902 | MR 2179687 | Zbl 1099.65039
[12] Cherif, L. B., Merikhi, B.: A penalty method for nonlinear programming. RAIRO, Oper. Res. 53 (2019), 29-38. DOI 10.1051/ro/2018061 | MR 3899028 | Zbl 1414.90264
[13] Davies, P. I., Higham, N. J.: Numerically stable generation of correlation matrices and their factors. BIT 40 (2000), 640-651. DOI 10.1023/A:1022384216930 | MR 1799307 | Zbl 0969.65036
[14] Klerk, E. de: Interior Point Methods for Semidefinite Programming: Thesis Technische Universiteit Delf. (1997).
[15] Helmberg, C., Rendl, F., Vanderbei, R. J., Wolkowicz, H.: An interior-point method for semidefinite programming. SIAM J. Optim. 6 (1996), 342-361. DOI 10.1137/0806020 | MR 1387330 | Zbl 0853.65066
[16] Henrion, D., Malick, J.: SDLS: A Matlab package for solving conic least-squares problems. Version 1.2. Available at https://homepages.laas.fr/henrion/software/sdls/ (2009).
[17] Higham, N. J.: Computing the nearest correlation matrix - a problem from finance. IMA J. Numer. Anal. 22 (2002), 329-343. DOI 10.1093/imanum/22.3.329 | MR 1918653 | Zbl 1006.65036
[18] Kettab, S., Benterki, D.: A relaxed logarithmic barrier method for semidefinite programming. RAIRO, Oper. Res. 49 (2015), 555-568. DOI 10.1051/ro/2014055 | MR 3349134 | Zbl 1327.90179
[19] Kojima, M., Shindoh, S., Hara, S.: Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices. SIAM J. Optim. 7 (1997), 86-125. DOI 10.1137/S1052623494269035 | MR 1430559 | Zbl 0872.90098
[20] Krislock, N. G. B.: Numerical Solution of Semidefinite Constrained Least Squares Problems: A Thesis. University of British Columbia, Vancouver (2003).
[21] Malick, J.: A dual approach to semidefinite least-squares problems. SIAM J. Matrix Anal. Appl. 26 (2004), 272-284. DOI 10.1137/S0895479802413856 | MR 2112861 | Zbl 1080.65027
[22] Malick, J.: Applications of SDP least-squares in finance and combinatorics. CNRS, Lab. J. Kuntzmann, Grenoble CORE Math. Prog. Seminar-11 March (2008).
[23] Monteiro, R. D. C.: Primal-dual path-following algorithms for semidefinite programming. SIAM J. Optim. 7 (1997), 663-678. DOI 10.1137/S1052623495293056 | MR 1462060 | Zbl 0913.65051
[24] Nesterov, Y. E., Todd, M. J.: Self-scaled barriers and interior-point methods for convex programming. Math. Oper. Res. 22 (1997), 1-42. DOI 10.1287/moor.22.1.1 | MR 1436572 | Zbl 0871.90064
[25] Nesterov, Y. E., Todd, M. J.: Primal-dual interior-point methods for self-scaled cones. SIAM J. Optim. 8 (1998), 324-364. DOI 10.1137/S1052623495290209 | MR 1618802 | Zbl 0922.90110
[26] Qian, X.: Continuous Methods for Convex Programming and Convex Semidefinite Programming: PhD. Thesis. Hong Kong Baptist University, Hong Kong (2017).
[27] Todd, M. J.: A study of search directions in primal-dual interior-point methods for semidefinite programming. Optim. Methods Softw. 11 (1999), 1-46. DOI 10.1080/10556789908805745 | MR 1777451 | Zbl 0971.90109
[28] Toh, K. C., Todd, M. J., Tütüncü, R. H.: SDPT3 - a MATLAB package for semidefinite programming, version 1.3. Optim. Methods Softw. 11 (1999), 545-581. DOI 10.1080/10556789908805762 | MR 1778429 | Zbl 0997.90060
[29] Ye, Y.: Interior Point Algorithms: Theory and Analysis. Wiley-Interscience Series in Discrete Mathematics and Optimization. John-Wiley & Sons, Chichester (1997). DOI 10.1002/9781118032701 | MR 1481160 | Zbl 0943.90070
[30] 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
