An interior-point algorithm for semidefinite least-squares problems

Chafia Daili; Mohamed Achache

Applications of Mathematics (2022)

  • Volume: 67, Issue: 3, page 371-391
  • ISSN: 0862-7940

Abstract

top
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 β which defines the size of the neighborhood of the central-path and of the parameter θ 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, 𝒪 ( n log ( n / ϵ ) ) . Finally, we report some numerical results to illustrate the efficiency of our proposed algorithm.

How to cite

top

Daili, Chafia, and Achache, Mohamed. "An interior-point algorithm for semidefinite least-squares problems." Applications of Mathematics 67.3 (2022): 371-391. <http://eudml.org/doc/297924>.

@article{Daili2022,
abstract = {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.},
author = {Daili, Chafia, Achache, Mohamed},
journal = {Applications of Mathematics},
keywords = {semidefinite least-squares problem; interior-point method; polynomial complexity},
language = {eng},
number = {3},
pages = {371-391},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {An interior-point algorithm for semidefinite least-squares problems},
url = {http://eudml.org/doc/297924},
volume = {67},
year = {2022},
}

TY - JOUR
AU - Daili, Chafia
AU - Achache, Mohamed
TI - An interior-point algorithm for semidefinite least-squares problems
JO - Applications of Mathematics
PY - 2022
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 67
IS - 3
SP - 371
EP - 391
AB - 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.
LA - eng
KW - semidefinite least-squares problem; interior-point method; polynomial complexity
UR - http://eudml.org/doc/297924
ER -

References

top
  1. Achache, M., 10.1590/S0101-82052006000100005, Comput. Appl. Math. 25 (2006), 97-110. (2006) Zbl1213.90187MR2267615DOI10.1590/S0101-82052006000100005
  2. Achache, M., 10.1007/s10114-015-1314-4, Acta Math. Sin., Engl. Ser. 31 (2015), 543-556. (2015) Zbl1308.65086MR3306664DOI10.1007/s10114-015-1314-4
  3. Achache, M., 10.1007/s13370-015-0363-2, Afr. Mat. 27 (2016), 591-601. (2016) Zbl1378.90089MR3500476DOI10.1007/s13370-015-0363-2
  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. (2011) Zbl1274.90371MR3059815
  5. Achache, M., Guerra, L., 10.1016/j.amc.2013.12.070, Appl. Math. Comput. 231 (2014), 581-590. (2014) Zbl1410.90230MR3174056DOI10.1016/j.amc.2013.12.070
  6. Achache, M., Roumili, H., Keraghel, A., 10.1016/j.amc.2006.07.135, Appl. Math. Comput. 186 (2007), 1472-1479. (2007) Zbl1117.65082MR2316940DOI10.1016/j.amc.2006.07.135
  7. Achache, M., Tabchouche, N., 10.1007/s11590-018-1328-9, Optim. Lett. 13 (2019), 1039-1057. (2019) Zbl1425.90116MR3956989DOI10.1007/s11590-018-1328-9
  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). (1994) MR1636549
  9. Alzalg, B., 10.1007/s11590-019-01404-1, Optim. Lett. 14 (2020), 729-746. (2020) Zbl1442.90177MR4075446DOI10.1007/s11590-019-01404-1
  10. Boyd, S., Vandenberghe, L., 10.1017/CBO9780511804441, Cambridge University Press, Cambridge (2004). (2004) Zbl1058.90049MR2061575DOI10.1017/CBO9780511804441
  11. Boyd, S., Xiao, L., 10.1137/040609902, SIAM J. Matrix Anal. Appl. 27 (2005), 532-546. (2005) Zbl1099.65039MR2179687DOI10.1137/040609902
  12. Cherif, L. B., Merikhi, B., 10.1051/ro/2018061, RAIRO, Oper. Res. 53 (2019), 29-38. (2019) Zbl1414.90264MR3899028DOI10.1051/ro/2018061
  13. Davies, P. I., Higham, N. J., 10.1023/A:1022384216930, BIT 40 (2000), 640-651. (2000) Zbl0969.65036MR1799307DOI10.1023/A:1022384216930
  14. Klerk, E. de, Interior Point Methods for Semidefinite Programming: Thesis Technische Universiteit Delf, (1997). (1997) 
  15. Helmberg, C., Rendl, F., Vanderbei, R. J., Wolkowicz, H., 10.1137/0806020, SIAM J. Optim. 6 (1996), 342-361. (1996) Zbl0853.65066MR1387330DOI10.1137/0806020
  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). (2009) 
  17. Higham, N. J., 10.1093/imanum/22.3.329, IMA J. Numer. Anal. 22 (2002), 329-343. (2002) Zbl1006.65036MR1918653DOI10.1093/imanum/22.3.329
  18. Kettab, S., Benterki, D., 10.1051/ro/2014055, RAIRO, Oper. Res. 49 (2015), 555-568. (2015) Zbl1327.90179MR3349134DOI10.1051/ro/2014055
  19. Kojima, M., Shindoh, S., Hara, S., 10.1137/S1052623494269035, SIAM J. Optim. 7 (1997), 86-125. (1997) Zbl0872.90098MR1430559DOI10.1137/S1052623494269035
  20. Krislock, N. G. B., Numerical Solution of Semidefinite Constrained Least Squares Problems: A Thesis, University of British Columbia, Vancouver (2003). (2003) 
  21. Malick, J., 10.1137/S0895479802413856, SIAM J. Matrix Anal. Appl. 26 (2004), 272-284. (2004) Zbl1080.65027MR2112861DOI10.1137/S0895479802413856
  22. Malick, J., Applications of SDP least-squares in finance and combinatorics, CNRS, Lab. J. Kuntzmann, Grenoble CORE Math. Prog. Seminar-11 March (2008). (2008) 
  23. Monteiro, R. D. C., 10.1137/S1052623495293056, SIAM J. Optim. 7 (1997), 663-678. (1997) Zbl0913.65051MR1462060DOI10.1137/S1052623495293056
  24. Nesterov, Y. E., Todd, M. J., 10.1287/moor.22.1.1, Math. Oper. Res. 22 (1997), 1-42. (1997) Zbl0871.90064MR1436572DOI10.1287/moor.22.1.1
  25. Nesterov, Y. E., Todd, M. J., 10.1137/S1052623495290209, SIAM J. Optim. 8 (1998), 324-364. (1998) Zbl0922.90110MR1618802DOI10.1137/S1052623495290209
  26. Qian, X., Continuous Methods for Convex Programming and Convex Semidefinite Programming: PhD. Thesis, Hong Kong Baptist University, Hong Kong (2017). (2017) 
  27. Todd, M. J., 10.1080/10556789908805745, Optim. Methods Softw. 11 (1999), 1-46. (1999) Zbl0971.90109MR1777451DOI10.1080/10556789908805745
  28. Toh, K. C., Todd, M. J., Tütüncü, R. H., 10.1080/10556789908805762, Optim. Methods Softw. 11 (1999), 545-581. (1999) Zbl0997.90060MR1778429DOI10.1080/10556789908805762
  29. Ye, Y., 10.1002/9781118032701, Wiley-Interscience Series in Discrete Mathematics and Optimization. John-Wiley & Sons, Chichester (1997). (1997) Zbl0943.90070MR1481160DOI10.1002/9781118032701
  30. Zhang, Y., 10.1137/S1052623495296115, SIAM J. Optim. 8 (1998), 365-386. (1998) Zbl0913.65050MR1618806DOI10.1137/S1052623495296115

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.