Global convergence of an inexact interior-point method for convex quadratic‎ ‎symmetric cone programming‎

Document Type : Research Paper

Authors

1 Department of Applied Mathematics‎, ‎Faculty of‎ ‎Mathematical Sciences‎, ‎Shahrekord University‎, ‎P.O‎. ‎Box 115‎, ‎Shahrekord‎, ‎Iran.

2 Department of Applied Mathematics‎, ‎Faculty of ‎Mathematical Sciences‎, ‎Shahrekord University‎, ‎P.O‎. ‎Box 115‎, ‎Shahrekord‎, ‎Iran.

Abstract

‎In this paper‎, ‎we propose a feasible interior-point method for‎ ‎convex quadratic programming over symmetric cones‎. ‎The proposed algorithm relaxes the‎ ‎accuracy requirements in the solution of the Newton equation system‎, ‎by using an inexact Newton direction‎. ‎Furthermore‎, ‎we obtain an‎ ‎acceptable level of error in the inexact algorithm on convex‎ ‎quadratic symmetric cone programming (CQSCP)‎. ‎We also prove that the iteration‎ ‎bound for the feasible short-step method is‎ ‎$O(\sqrt{n}\log\frac{1}{\varepsilon})$‎, ‎and‎ ‎$O(n\log\frac{1}{\varepsilon})$ for the large-step method which coincide with the currently best‎ ‎known iteration bounds for CQSCPs.

Keywords

Main Subjects

References

F. Alizadeh, Interior point methods in semidednite programming with applications to combinatorial optimization, SIAM J. Optim. 5 (1995), no. 1, 13--51.
S. Bellavia, Inexact interior point method, J. Optim. Theory Appl. 96 (1998) 109--121.
L. Bergamaschi, J. Gondzio and G. Zilli, Preconditioning indefnite systems in interior point methods for optimization, Comput. Optim. Appl. 28 (2004) 149--171.
S. Cafieri, M. Dapuzzo, V. De Simone, D. di Serafino and G. Toraldo, Convergence analysis of an inexact potential reduction method for convex quadratic programming, J. Optim. Theory Appl. 135 (2007) 355--366.
J. S. Chai and K. C. Toh, Preconditioning and iterative solution of symmetric indefinite linear systems arising from interior point methods for linear programming, Comput. Optim. Appl. 36 (2007) 221--247.
J. Faraut and A. Koranyi, Analysis on Symmetric Cones, Oxford Math. Monogr. Oxford Univ. Press, New York, 1994.
L. Faybusovich, Euclidean Jordan algebras and interior-point algorithms, Positivity 1 (1997), no. 4, 331--357.
L. Faybusovich, Linear systems in Jordan algebras and primal-dual interior-point algorithms, J. Comput. Appl. Math. 86 (1997), no. 1, 149--175.
R. W. Freund, F. Jarre and S. Mizuno, Convergence of a class of inexact interior-point algorithms for linear programs, Math. Oper. Res. 24 (1999) 50--71.
L. Faybusovich and R. Arana, A long-step primal-dual algorithm for the symmetric programming problem, Systems Control Lett. 43 (2001), no. 1, 3--7.
L. Faybusovich, A Jordan-algebraic approach to potential-reduction algorithms, Mathematische Zeitschrift. 239 (2002), no. 1, 117--129.
O. Guler, Barrier functions in interior point methods, Math. Oper. Res. 21 (1996), no. 4, 860--885.
G. Gu, Full-step interior point methods for symmetric optimization, PhD thesis, Faculty of Mathematics and Computer Science, TU Delft, NL--2628 CD Delft, The Netherlands, 2009.
G. Gu, M. Zangiabadi and C. Roos, Full Nesterov-Todd step infeasible interior-point method for symmetric optimization, European J. Oper. Res. 214 (2011), no. 3, 473--484.
J. Gondzio, Convergence Analysis of an Inexact Feasible Interior Point Method for Convex Quadratic Programming, SIAM J. Optim. 23 (2013), no. 3, 1510--1527.
S. H. Schmieta and F. Alizadeh, Extension of primal-dual interior-point algorithms tosymmetric cones, Math. Program. Ser. A 96 (2003), no. 3, 409--438.
M. Kojima, N. Megiddo, T. Noma and A. Yoshise, A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems, Lecture Notes in Comput. Sci. 538, NewYork, 1991.
M. Kojima, N. Megiddo and S. Mizuno, A primal-dual infeasible-interior-point algorithm for linear programming, Math. Program. 61 (1993) 263--280.
N. Karmarkar, New polynomial-time algorithm for linear programming, Combinatorica 4 (1984) 373--395.
Y. Lim, Geometric means on symmetric cones, Arch. Math. 75 (2000), no. 1, 39--56.
Z. Lu, R. D. C. Monteiro and J. W. Oneal, An iterative solver-based infeasible primaldual path-following algorithm for convex quadratic programming, SIAM J. Optim. 17 (2006) 287--310.
S. Mizuno and F. Jarre, Global and polynomial-time convergence of an infeasible-interior point algorithm using inexact computation, Math. Program. 84 (1999) 105--122.
G. Q. Wang, C. J. Yu and K. L. Teo, A new full Nesterov-Todd step feasible interiorpoint method for convex quadratic symmetric cone optimization, Appl. Math. Comput. 221 (2013) 329--343.
S. J. Wright, Primal-Dual Interior-Point Methods, SIAM, Philadelphia, 1996.
Bulletin of the Iranian Mathematical Society
Volume 42, Issue 6
December 2016
Pages 1363-1385

Files

History

  • Receive Date: 02 December 2014
  • Revise Date: 24 August 2015
  • Accept Date: 03 September 2015

Share

How to cite

Statistics