| Title:
|
An interior-point algorithm for semidefinite least-squares problems (English) |
| Author:
|
Daili, Chafia |
| Author:
|
Achache, Mohamed |
| Language:
|
English |
| Journal:
|
Applications of Mathematics |
| ISSN:
|
0862-7940 (print) |
| ISSN:
|
1572-9109 (online) |
| Volume:
|
67 |
| Issue:
|
3 |
| Year:
|
2022 |
| Pages:
|
371-391 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
semidefinite least-squares problem |
| Keyword:
|
interior-point method |
| Keyword:
|
polynomial complexity |
| MSC:
|
65K05 |
| MSC:
|
90C22 |
| MSC:
|
90C25 |
| MSC:
|
90C51 |
| idZBL:
|
Zbl 07547200 |
| idMR:
|
MR4409311 |
| DOI:
|
10.21136/AM.2021.0217-20 |
| . |
| Date available:
|
2022-04-14T13:37:40Z |
| Last updated:
|
2024-07-01 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/150320 |
| . |
| Reference:
|
[1] Achache, M.: A new primal-dual path-following method for convex quadratic programming.Comput. Appl. Math. 25 (2006), 97-110. Zbl 1213.90187, MR 2267615, 10.1590/S0101-82052006000100005 |
| Reference:
|
[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. Zbl 1308.65086, MR 3306664, 10.1007/s10114-015-1314-4 |
| Reference:
|
[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. Zbl 1378.90089, MR 3500476, 10.1007/s13370-015-0363-2 |
| Reference:
|
[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. Zbl 1274.90371, MR 3059815 |
| Reference:
|
[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. Zbl 1410.90230, MR 3174056, 10.1016/j.amc.2013.12.070 |
| Reference:
|
[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. Zbl 1117.65082, MR 2316940, 10.1016/j.amc.2006.07.135 |
| Reference:
|
[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. Zbl 1425.90116, MR 3956989, 10.1007/s11590-018-1328-9 |
| Reference:
|
[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 |
| Reference:
|
[9] Alzalg, B.: A logarithmic barrier interior-point method based on majorant functions for second-order cone programming.Optim. Lett. 14 (2020), 729-746. Zbl 1442.90177, MR 4075446, 10.1007/s11590-019-01404-1 |
| Reference:
|
[10] Boyd, S., Vandenberghe, L.: Convex Optimization.Cambridge University Press, Cambridge (2004). Zbl 1058.90049, MR 2061575, 10.1017/CBO9780511804441 |
| Reference:
|
[11] Boyd, S., Xiao, L.: Least-squares covariance matrix adjustment.SIAM J. Matrix Anal. Appl. 27 (2005), 532-546. Zbl 1099.65039, MR 2179687, 10.1137/040609902 |
| Reference:
|
[12] Cherif, L. B., Merikhi, B.: A penalty method for nonlinear programming.RAIRO, Oper. Res. 53 (2019), 29-38. Zbl 1414.90264, MR 3899028, 10.1051/ro/2018061 |
| Reference:
|
[13] Davies, P. I., Higham, N. J.: Numerically stable generation of correlation matrices and their factors.BIT 40 (2000), 640-651. Zbl 0969.65036, MR 1799307, 10.1023/A:1022384216930 |
| Reference:
|
[14] Klerk, E. de: Interior Point Methods for Semidefinite Programming: Thesis Technische Universiteit Delf.(1997). |
| Reference:
|
[15] Helmberg, C., Rendl, F., Vanderbei, R. J., Wolkowicz, H.: An interior-point method for semidefinite programming.SIAM J. Optim. 6 (1996), 342-361. Zbl 0853.65066, MR 1387330, 10.1137/0806020 |
| Reference:
|
[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). |
| Reference:
|
[17] Higham, N. J.: Computing the nearest correlation matrix - a problem from finance.IMA J. Numer. Anal. 22 (2002), 329-343. Zbl 1006.65036, MR 1918653, 10.1093/imanum/22.3.329 |
| Reference:
|
[18] Kettab, S., Benterki, D.: A relaxed logarithmic barrier method for semidefinite programming.RAIRO, Oper. Res. 49 (2015), 555-568. Zbl 1327.90179, MR 3349134, 10.1051/ro/2014055 |
| Reference:
|
[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. Zbl 0872.90098, MR 1430559, 10.1137/S1052623494269035 |
| Reference:
|
[20] Krislock, N. G. B.: Numerical Solution of Semidefinite Constrained Least Squares Problems: A Thesis.University of British Columbia, Vancouver (2003). |
| Reference:
|
[21] Malick, J.: A dual approach to semidefinite least-squares problems.SIAM J. Matrix Anal. Appl. 26 (2004), 272-284. Zbl 1080.65027, MR 2112861, 10.1137/S0895479802413856 |
| Reference:
|
[22] Malick, J.: Applications of SDP least-squares in finance and combinatorics.CNRS, Lab. J. Kuntzmann, Grenoble CORE Math. Prog. Seminar-11 March (2008). |
| Reference:
|
[23] Monteiro, R. D. C.: Primal-dual path-following algorithms for semidefinite programming.SIAM J. Optim. 7 (1997), 663-678. Zbl 0913.65051, MR 1462060, 10.1137/S1052623495293056 |
| Reference:
|
[24] Nesterov, Y. E., Todd, M. J.: Self-scaled barriers and interior-point methods for convex programming.Math. Oper. Res. 22 (1997), 1-42. Zbl 0871.90064, MR 1436572, 10.1287/moor.22.1.1 |
| Reference:
|
[25] Nesterov, Y. E., Todd, M. J.: Primal-dual interior-point methods for self-scaled cones.SIAM J. Optim. 8 (1998), 324-364. Zbl 0922.90110, MR 1618802, 10.1137/S1052623495290209 |
| Reference:
|
[26] Qian, X.: Continuous Methods for Convex Programming and Convex Semidefinite Programming: PhD. Thesis.Hong Kong Baptist University, Hong Kong (2017). |
| Reference:
|
[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. Zbl 0971.90109, MR 1777451, 10.1080/10556789908805745 |
| Reference:
|
[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. Zbl 0997.90060, MR 1778429, 10.1080/10556789908805762 |
| Reference:
|
[29] Ye, Y.: Interior Point Algorithms: Theory and Analysis.Wiley-Interscience Series in Discrete Mathematics and Optimization. John-Wiley & Sons, Chichester (1997). Zbl 0943.90070, MR 1481160, 10.1002/9781118032701 |
| Reference:
|
[30] 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 |
| . |
