A full Nesterov-Todd step interior-point method for circular cone optimization

Document Type : Original paper


Azarbaijan Shahid Madani University


In this paper, we present a full Newton step feasible interior-point method for circular cone optimization by using Euclidean Jordan algebra. The search direction is based on the Nesterov-Todd scaling scheme, and only full-Newton step is used at each iteration. Furthermore, we derive the iteration bound that coincides with the currently best known iteration bound for small-update methods.


Main Subjects

[1] M. Achache and M. Goutali, Complexity analysis and numerical implementation of a full-newton step interior-point algorithm for lcco, Numer. Algorithms 70 (2015), no. 2, 393–405.
[2] F. Alizadeh and D. Goldfarb, Second-order cone programming, Math. Program. Ser. B 95 (2003), 3–51.
[3] B. Alzalg, The jordan algebraic structure of the circular cone, Technical report, Optimization online, http:// www.optimizationonline.org/DB−HTML/2015/07/5027.html, (2015).
[4] B. Alzalg, Primal-dual path-following algorithm for circular programming, Technical report, Optimization online,http://www.optimization-online.org /DB−FILE/2015/07/4998.pdf (2015).
[5] A. Ben-Tal and A. Nemirovski, Lectures on modern convex optimization., MPS/SIAM Series on Optimization. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, Algorithms, and Engineering Applications, 2001.
[6] Zs. Darvay, New interior point algorithms in linear programming, Adv. Model. Optim. 5 (2003), no. 1, 51–92.
[7] L. Faybusovich, Euclidean jordan algebras and interior-point algorithms, Positivity 1 (1997), no. 4, 331–357.
[8] G. Gu, Full-step interior-point methods for symmetric optimization, Ph.D. Thesis, TU Delft, 2009.
[9] T. Illés and M. Nagy, A mizuno-todd-ye type predictor-corrector algorithm for sufficient linear complementarity problems, Eur. J. Oper. Res. 181(2007), no. 3, 1097–1111.
[10] N.K. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica 4 (1984), 375–395.
[11] B. Kheirfam, An interior-point method for cartesian $p_∗(κ)$-linear complementarity problem over symmetric cones, ORiON 30 (2014), no. 1, 41–58.
[12] B. Kheirfam, predictor-corrector interior-point algorithm for $p_∗(κ)$-horizontal linear complementarity problem, Numer. Algorithms 66 (2014), no. 2, 349–361.
[13] B. Kheirfam and N. Mahdavi-Amiri, A new interior-point algorithm based on modified nesterov-todd direction for symmetric cone linear complementarity problem, Optim. Letters 8 (2014), no. 3, 1017–1029.
[14] E. De Klerk, Aspects of semidefinite programming. applied optimization, vol. 65, Kluwer Academic, Dordrecht, 2002.
[15] C.H. Ko and J.S. Chen, ptimal grasping manipulation for multifingered robots using semismooth newton method, Math. Probl. Eng. 2013 (2013), article ID 681710, 9 pages.
[16] P.F. Ma, Y.Q. Bai, and J.-S. Chen, A self-concordant interior point algorithm for nonsymmetric circular cone programming, J. Nonlinear Conv. Analysis 17 (2016), no. 2, 225–241.
[17] R.D.C. Monteiro and Y. Zhang, A unified analysis for a class of longstep primal-dual path-following interior-point algorithms for semidefinite programming, Math. Program. 81 (1998), 281–299.
[18] Y.E. Nesterov and M.J. Todd, Self-scaled barriers and interior-point methods for convex programming, Math. Oper. Res. 22 (1997), 1–42.
[19] Y.E. Nesterov and M.J. Todd, Primal-dual interior-point methods for self-scaled cones, SIAM J. Optim. 8 (1998), 324–364.
[20] F. Permenter, H.A. Friberg, and E.D. Andersen, Solving conic optimization problems via self-dual embedding and facial reduction: a unified approach, Optimization-online.org/DBHTML/2015/09/5104.html.
[21] C. Roos, T. Terlaky, and J-Ph. Vial, Theory and algorithms for linear optimization. an interior-point approach, John Wiley and Sons, Chichester, UK, 1997.
[22] S.H. Schmieta and F. Alizadeh, Extension of primal-dual interior point methods to symmetric cones, Math. Program. Ser. A 96 (2003), 409–438.
[23] M.V.C. Vieira, Jordan algebraic approach to symmetric optimization, Ph.D. Thesis, Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, The Netherlands, 2007.
[24] G. Q. Wang and G. Lesaja, Full nesterov-todd step feasible interior-point method for the cartesian $p_∗(κ)$-sclcp, Optim. Methods & Softw. 28 (2013), no. 3, 600–618.
[25] G.Q. Wang, L.C. Kong, J.Y. Tao, and G. Lesaja, Improved complexity analysis of full nesterov-todd step feasible interior-point method for symmetric optimization, J. Optim. Theory Appl. 166 (2015), no. 2, 588–604.
[26] G.Q. Wang, C.J. Yu, and K.L. Teo, A new full nesterov-todd step feasible interior-point method for convex quadratic symmetric cone optimization, Appl. Math. Comput. 221 (2013), 329–343.