Previous |  Up |  Next

Article

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
.

Files

Files Size Format View
AplMat_67-2022-3_6.pdf 280.2Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo