An infeasible interior point methods for convex quadratic problems
DOI:
https://doi.org/10.33993/jnaat472-1147Keywords:
Convex quadratic programs, Infeasible interior-point method, Newton stepAbstract
In this paper, we deal with the study and implementation of an infeasible interior point method for convex quadratic problems (CQP). The algorithm uses a Newton step and suitable proximity measure for approximately tracing the central path and guarantees that after one feasibility step, the new iterate is feasible and suciently close to the central path. For its complexity analysis, we reconsider the analysis used by the authors for linear optimisation (LO) and linear complementarity problems (LCP).
We show that the algorithm has the best known iteration bound, namely \(n log (n+1)\).
Finally, to measure the numerical performance of this algorithm, it was tested on convex quadratic and linear problems.
Downloads
References
M. Achache, M. Goutal, A primal-dual interior point algorithm for convex quadratic programs, Studia Univ. Babes Bolyai Informatica.LVII (2012) no. 1, pp. 48–58.
Zs. Darvay, I.-M. Papp, P.-R. Takacs, An infeasible full-Newton step algorithm for linear optimization with one centering step in major iteration, Studia Univ. Babes-Bolyai Informatica, 59 (2014), pp. 28-45.
G. Gu, M. Zangiabadi, C. Roos, Full Nesterov-Todd step infeasible interior-point methods for symmetric optimization, European J. Oper. Res, 214 (2011) no. 3, pp. 473-484, https://doi.org/10.1016/j.ejor.2011.02.022 DOI: https://doi.org/10.1016/j.ejor.2011.02.022
N.K. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, 4 (1984) no. 4, pp. 373-395, https://doi.org/10.1007/bf02579150 DOI: https://doi.org/10.1007/BF02579150
H. Mansouri, C. Roos, A simplified O(nL) infeasible interior-point algorithm for linear optimization using full Newton steps, Optim. Methods Softw, 22 (2007) no. 3, pp. 519-530, https://doi.org/10.1080/10556780600816692 DOI: https://doi.org/10.1080/10556780600816692
H. Mansouri, M. Zangiabad, An adaptive infeasible interior-point algorithm with full-Newton step for linear optimization, Optimization, 62 (2013) no. 2, pp. 285-297, https://doi.org/10.1080/02331934.2011.611881 DOI: https://doi.org/10.1080/02331934.2011.611881
H. Mansouri, M. Zangiabadi, M. Arzani, A modified infeasible-interior-point algorithm for linear optimization problems, J. Optim. Theory Appl., 166 (2015) no. 2, pp. 605-618, https://doi.org/10.1007/s10957-015-0719-7 DOI: https://doi.org/10.1007/s10957-015-0719-7
H. Mansouri, M. Zangiabadi, M. Pirhaji, A full-Newton step O(n) infeasible interior-point algorithm for linear complementarity problems, Nonlinear Anal. Real World Appl. 12 (2011) no. 1, pp. 545-561, https://doi.org/10.1016/j.nonrwa.2010.06.039 DOI: https://doi.org/10.1016/j.nonrwa.2010.06.039
C. Roos, A full-Newton step O(n) infeasible interior-point algorithm for linear optimization, SIAM J. Optim, 16 (2006) no. 4, pp. 1110-1136, https://doi.org/10.1137/050623917 DOI: https://doi.org/10.1137/050623917
C. Roos, An improved and simplified full-Newton step O(n) infeasible interior-point method for linear optimization, SIAM J. Optim, 25 (2015) no. 1, pp. 102-114, https://doi.org/10.1137/140975462 DOI: https://doi.org/10.1137/140975462
Gy. Sonnevend, An Analytic Center for Polyhedrons and New Classes of Global Algorithms for Linear (Smooth, Convex) Programming, Lecture Notes in Control and Information Sciences, Springer, Berlin, 84 (1985), pp.866-876, https://doi.org/10.1007/bfb0043914 DOI: https://doi.org/10.1007/BFb0043914
G.Q. Wang, Y.Q. Ba, A new full Nesterov-Todd step primal-dual path-following interior-point algorithm for symmetric optimization, J. Optim. Theory Appl., 154 (2012) no. 3, pp. 966-985, https://doi.org/10.1007/s10957-012-0013-x DOI: https://doi.org/10.1007/s10957-012-0013-x
G.Q. Wang, Y.Q. Bai, X.Y. Gao, D.Z. Wang, Improved complexity analysis of full Nesterov-Todd step interior point methods for semidefinite optimization, J. Optim. Theory Appl.,165(2014) no. 1, pp. 242-262, https://doi.org/10.1007/s10957-014-0619-2 DOI: https://doi.org/10.1007/s10957-014-0619-2
G.Q. Wang, G. Lesaja, Full Nesterov-Todd step feasible interior-point method for the Cartesian P(*)-SCLCP, Optim. Methods Softw, 28 (2013) no. 3, pp. 600-618, http://doi.org/10.1080/10556788.2013.781600 DOI: https://doi.org/10.1080/10556788.2013.781600
Published
How to Cite
Issue
Section
License
Copyright (c) 2019 Journal of Numerical Analysis and Approximation Theory
This work is licensed under a Creative Commons Attribution 4.0 International License.
Open Access. This article is distributed under the terms of the Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
