New complexity analysis of full Nesterov-Todd step infeasible interior point method for second-order cone optimization
DOI:
https://doi.org/10.2298/YJOR161217017KKeywords:
second-order cone optimization, infeasible interior-point method, full Nesterov-Todd step, polynomial complexityAbstract
We present a full Nesterov-Todd (NT) step infeasible interior-point algorithm for second-order cone optimization based on a different way to calculate feasibility direction. In each iteration of the algorithm we use the largest possible barrier parameter value θ. Moreover, each main iteration of the algorithm consists of a feasibility step and a few centering steps. The feasibility step differs from the feasibility step of the other existing methods. We derive the complexity bound which coincides with the best known bound for infeasible interior point methods.References
Adler, I., and Alizadeh, F., “Primal-dual interior point algorithms for convex quadratically constrained and semidefinite optimization problems”, Technical Report RRR-111-95, Rutger Center for Operations Research, Brunswick, NJ, 1995.
Bouali, S., and Kabbaj, S., “Full-NT step infeasible interior-point method for SOCO based on a specific kernel function”, Afrika Matematika, 25 (2014) 549–565.
Darvay, Z., “New interior point algorithms in linear programming”, Advanced Modeling and Optimization, 5 (2003) 51–92.
Faybusovich, L., “Linear systems in Jordan algebras and primal-dual interior point algorithms”, Journal of Computational and Applied Mathematics, 86 (1997) 149–175.
Kheirfam, B., “A full NT-step infeasible interior-point algorithm for semidefinite optimization based on a self-regular proximity”, The ANZIAM Journal, 53 (2011) 48–67.
Kheirfam, B., “Simplified infeasible interior-point algorithm for SDO using full Nesterov-Todd step”, Numerical Algorithms, 59 (2012) 589–606.
Kheirfam, B., and Mahdavi-Amiri, N., “A full Nesterov-Todd step infeasible interior-point algorithm for symmetric cone linear complementarity problem”, Bulletin of the Iranian Mathematical Society, 40 (2014) 541–564.
Kojima, M., Megiddo, N., and Mizuno, S., “A primal-dual infeasible-interior-point algorithm for linear programming”, Mathematical Programming, 61 (1993) 263–280.
Lim, Y., “Geometric means on symmetric cones”, Archiv der Mathematik, 75 (2000) 39–45.
Lustig, I.J., “Feasible issues in a primal-dual interior-point method”, Mathematical Programming, 67 (1990) 145–162.
Mansouri, H., and Roos, C., “Simplified O(nL) infeasible interior-point algorithm for linear optimization using full-Newton step”, Optimization Methods and Software, 22 (2007) 519–530.
Mizuno, S., “Polynomiality of infeasible-interior-point algorithms for linear programming”, Mathematical Programming, 67 (1994) 109–119.
Nesterov, Y.E., and Todd, M.J., “Self-scaled barriers and interior-point methods for convex programming”, Mathematics of Operations Research, 22 (1997) 1–42.
Roos, C., Terlaky, T., and Vial, J.-Ph., Theory and Algorithms for Linear Optimization. An Interior-Point Approach, John Wiley and Sons, Chichester, UK, 1997.
Roos, C., “A full-Newton step O(n) infeasible interior-point algorithm for linear optimization”, SIAM Journal on Optimization, 16 (2006) 1110–1136.
Schmieta, S.H., and Alizadeh, F., “Extension of primal-dual interior-point algorithms to symmetric cones”, Mathematical Programming, 96 (2003) 409–438.
Vieira, M.V.C., “Jordan algebraic approach to symmetric optimization”, Ph.D. thesis, Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, The Netherlands, 2007.
Wang, G. Q., and Bai, Y. Q., “A primal-dual interior-point algorithm for second-order cone optimization with full Nesterov-Todd step”, Applied Mathematics and Computation, 215 (2009) 1047–1061.
Wright, S. J., Primal-Dual interior-point methods, SIAM, Philadelphia, USA, 1997.
Zangiabadi, M., Gu, G., and Roos, C., “A full Nesterov-Todd step infeasible interior-point method for second-order cone optimization”, Journal of Optimization Theory and Applications, 158 (2013) 816–858.
Zhang, Y., “On the convergence of a class of infeasible interior point methods for the horizontal linear complementary problem”, SIAM Journal on Optimization, 4 (1994) 208–227.
Downloads
Published
Issue
Section
License
Copyright (c) 2018 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
