A numerical study of an infeasible interior-point algorithm for convex quadratic semi-definite optimization

Yasmina Bendaas; Mohamed Achache

doi:10.33993/jnaat532-1442

Authors

Yasmina Bendaas Setif 1 Ferhat Abbas University, Algeria
Mohamed Achache Setif 1 Ferhat Abbas University, Algeria

DOI:

https://doi.org/10.33993/jnaat532-1442

Keywords:

Convex quadratic semidefinite optimization, Interior-point methods, Primal-dual algorithm, Newton method.

Abstract views: 0

Abstract

The focus of this research is to apply primal-dual interior-point pathfollowing methods, specifically those derived from Newton’s method for solving convex quadratic semidefinite optimization (CQSDO) problems. In this paper, we present a numerical study of an infeasible primal-dual interior-point method for tackling this class of optimization problems. Unlike the feasible interior-point algorithms, the proposed algorithm can be start with any initial positive definite matrix and does not require the strictly feasible initial points. Under certain conditions, the Newton system is well defined and its Jacobian is nonsingular at the solution. For computing an iteration throughout the algorithm, a Newton direction and a step-size are determined. Here, our search direction is based on Alizadeh-Haeberly-Overton (AHO) symmetrization. However, for the step size along this direction an efficient procedure is suggested. Preliminary numerical results demonstrate the efficiency of our algorithm.

Downloads

Download data is not yet available.

References

J. S. Jacob, J. H. Priya and A. Karthika, Applications of fractional calculus in science and engineering, J. Crit. Rev, 7 (2020) no. 13, pp. 4385–4394. https://www.jcreview.com/admin/Uploads/Files/624890460526e8.90194993.pdf

H. M. Nasir and K. Nafa, Algebraic construction of a third order difference approximation for fractional derivatives and applications, ANZIAM Journal, 59 (2018) no. EMAC2017, pp. C231–C245. https://doi.org/10.21914/anziamj.v59i0.12592 DOI: https://doi.org/10.21914/anziamj.v59i0.12592

H. M. Nasir and K. Nafa, A new second order approximation for fractional derivatives with applications, SQU Journal of Science, 23 (2018) no. 1, pp. 43-55. https://doi.org/10.24200/squjs.vol23iss1pp43-55 DOI: https://doi.org/10.24200/squjs.vol23iss1pp43-55

C. Lubich, Discretized fractional calculus, SIAM J. Math. Anal., 17 (1986) no. 3, pp. 704–719. https://doi.org/10.1137/0517050 DOI: https://doi.org/10.1137/0517050

I. Podlubny, Fractional differential equations: an introduction to fractional derivatives, fractional differential equations, to methods of their solution and some of their applications, Elsevier, 1998.

A. Akg¨ul and S. H. A. Khoshnaw , Application of fractional derivative on non-linear biochemical reaction models, Int. J. Intell. Netw., 1 (2020), pp. 52–58. https://doi.org/10.1016/j.ijin.2020.05.001 DOI: https://doi.org/10.1016/j.ijin.2020.05.001

M. M. Meerschaert and C. Tadjeran, Finite difference approximations for fractional advection–dispersion flow equations, J. Comput. Appl. Math., 172 (2004) no. 1, pp. 65–77. https://doi.org/10.1016/j.cam.2004.01.033 DOI: https://doi.org/10.1016/j.cam.2004.01.033

W.A. Gunarathna, H.M. Nasir and W.B. Daundasekera, An explicit form for higher order approximations of fractional derivatives, Appl. Numer. Math., 143 (2019), pp. 51–60. https://doi.org/10.1016/j.apnum.2019.03.017 DOI: https://doi.org/10.1016/j.apnum.2019.03.017

F. Mainardi, Fractional relaxation-oscillation and fractional diffusion-wave phenomena, Chaos Solitons Fractals, 7 (1996) no. 9, pp. 1461–1477. https://doi.org/10.1016/0960-0779(95)00125-5 DOI: https://doi.org/10.1016/0960-0779(95)00125-5

R.L. Bagley and P.J. Torvik, A theoretical basis for the application of fractional calculus to viscoelasticity, J. Rheol., 27 (1983) no. 3, pp. 201–210. https://doi.org/10.1122/1.549724 DOI: https://doi.org/10.1122/1.549724

B.M. Vinagre, I. Podlubny, A. Hernandez and V Feliu, Some approximations of fractional order operators used in control theory and applications, Fractional calculus and applied analysis, 3 (2000) no. 3, pp. 231–248.

R. Metzler and J. Klafter, The restaurant at the end of the random walk: recent developments in the description of anomalous transport by fractional dynamics, J. Phys. A Math. Gen., 37 (2004) no. 31, pp. R161. http://dx.doi.org/10.1088/0305-4470/37/31/R01 DOI: https://doi.org/10.1088/0305-4470/37/31/R01

W. A. Gunarathna, H. M. Nasir and W. B. Daundasekara, Quasi-compact fourth-order approximations for fractional derivatives and applications, Ceylon J. Sci., 51 (2022) no. 5, pp. 589-595. https://doi.org/10.4038/cjs.v51i5.8085 DOI: https://doi.org/10.4038/cjs.v51i5.8085

H.G. Sun, Y. Zhang, D. Baleanu, W. Chen and YQ Chen, A new collection of real world applications of fractional calculus in science and engineering, Commun. Nonlinear Sci. Numer. Simul., 64 (2018), pp. 213–231. https://doi.org/10.1016/j.cnsns.2018.04.019 DOI: https://doi.org/10.1016/j.cnsns.2018.04.019

Y. Zhang, H.G. Sun, H.H. Stowell, M. Zayernouri and S.E. Hansen, A review of applications of fractional calculus in Earth system dynamics, Chaos Solitons Fractals, 102 (2017), pp. 29–46. https://doi.org/10.1016/j.chaos.2017.03.051 DOI: https://doi.org/10.1016/j.chaos.2017.03.051

M. Achache, Complexity analysis and numerical implementation of a short-step primal-dual algorithm for linear complementarity problems, Appl. Math. Comput., 216 (2010), pp. 1889–1895. https://doi.org/10.1016/j.amc.2010.03.015 DOI: https://doi.org/10.1016/j.amc.2010.03.015

M. Achache, L Guerra, A full Nesterov Todd-step feasible primal dual interior point algorithm for convex quadratic semi-definite optimization, Appl. Math. Comput. 231 (2014), pp. 581–590. https://doi.org/10.1016/j.amc.2013.12.070 DOI: https://doi.org/10.1016/j.amc.2013.12.070

M. Achache, N. Tabchouche, A full-Newton step feasible interior-point algorithm for monotone horizontal linear complementarity problems, Optim. Lett., 13 (2019), pp. 1039–1057. https://doi.org/10.1007/s11590-018-1328-9 DOI: https://doi.org/10.1007/s11590-018-1328-9

F. Alizadeh, J.P.A. Haeberly, M.L. Overton, Primal-dual interior-point methods for semidefinite programming. Convergence rates, stability and numerical results, SIAM J. Optim., 8 (1998) 3, pp. 746–768. https://doi.org/10.1137/S1052623496304700 DOI: https://doi.org/10.1137/S1052623496304700

Y.Q. Bai, F.Y. Wang, X.W. Luo, A polynomial time interior point algorithm for convex quadratic semidefinite optimization, RAIRO, Oper. Res., 44 (2010), pp. 251–265. https://doi.org/10.1051/ro/2010016 DOI: https://doi.org/10.1051/ro/2010016

Zs. Darvay, New interior-point algorithms for linear optimization, Advanced Modeling Optimization, 5 (1), 51-92 (2003).

E. De Klerk, Interior point methods for semidefinite programming. Master of Science in the Faculty of Engineering University of Pretoria, (1997). https://pure.uvt.nl/ws/portalfiles/portal/844453/thesis.pdf

C. Helmberg, F. Rendl, R.J. Vanderbei, H. Wolkowicz, An interior-point method for semidefinite programming, SIAM J. Optim., 6 (1996) 2, pp. 342–361. https://doi.org/10.1137/0806020 DOI: https://doi.org/10.1137/0806020

M. Seetharama Gowda, Yoon Song, On semidefinite linear complementarity problems, Math. Progr., 88 (2000), pp. 575–587. https://doi.org/10.1007/PL00011387 DOI: https://doi.org/10.1007/PL00011387

W. Grimes, Path-following interior-point algorithm for monotone linear complementarity problems, Asian-Eur. J. Math., 15 (2021) 9, https://doi.org/10.1142/S1793557122501704 DOI: https://doi.org/10.1142/S1793557122501704

L. Guerra, A class of new search directions for full-NT step feasible interior point method in semidefinite optimization, RAIRO Oper. Res., 56 (2022), pp. 3955–3971. https://doi.org/10.1051/ro/2022192 DOI: https://doi.org/10.1051/ro/2022192

M. Kojima, M. Shida, S. Shindoh, Search directions in the SDP and monotone SDLCP: Generalization and inexact computation, Math. Progr., 85 (1999), pp. 51–80. DOI: https://doi.org/10.1007/s101070050046

B. Krislock, Numerical solution of semidefinite constrained least squares problems, University Regina, (2000). http://hdl.handle.net/2429/14126

N. Moussaoui, M. Achache, A weighted-path following interior-point algorithm for convex quadratic optimization based on modified search directions, Stat. Optim. Inf. Comput, 10 (2022) 3, pp. 873–889. https://doi.org/10.19139/soic-2310-5070-1385 DOI: https://doi.org/10.19139/soic-2310-5070-1385

Y.E. Nesterov, M.J. Todd, Primal-dual interior-point methods for self-scaled cones, SIAM J. Optim., 8 (1998), pp. 324–364. https://doi.org/10.1137/S1052623495290209 DOI: https://doi.org/10.1137/S1052623495290209

J.W. Nie, Y.X. Yuan, A potential reduction algorithm for an extended SDP problem, Sci. China A, Math., 43 (2000) 1, pp. 35–46. DOI: https://doi.org/10.1007/BF02903846

X. Quian, Comparison between an infeasible interior point algorithm and a homogeneous self dual algorithm for semidefinite programming, New Mexico Institute of Mining and Technology. Socorro, New Mexico (2006).

K.C. Toh, M.J. Todd, R.H. T¨ut¨uncu, SDPT3-a MATLAB package for semidefinite programming, Optim. Methods Softw., 11 (1999), pp. 545–581. https://doi.org/10.1080/10556789908805762 DOI: https://doi.org/10.1080/10556789908805762

I. Touil, D. Benterki, A. Yassine, A feasible primal–dual interior point method for linear semidefinite programming, J. Comput. Appl. Math., 312 (2017), pp. 216–230. https://doi.org/10.1016/j.cam.2016.05.008 DOI: https://doi.org/10.1016/j.cam.2016.05.008

S. Wright, Primal-Dual Interior-Point Methods, SIAM, Philadelphia, PA, 1997. https://epubs.siam.org/doi/pdf/10.1137/1.9781611971453.bm DOI: https://doi.org/10.1137/1.9781611971453

Y. Ye, Interior point algorithms: Theory and Analysis, 44, John Wiley & Sons, 2011.

F. Zhang, Matrix theory basic results and techniques, Springer, ISBN 0-387-98696-0.

Y. Zhang, On the convergence of a class of infeasible interior-point methods for horizontal linear complementarity problem, SIAM J. Optim., 4 (1994) 1, pp. 208–227. https://doi.org/10.1137/0804012 DOI: https://doi.org/10.1137/0804012