Primal-dual path-following algorithms for circular programming

Document Type : Original paper

Authors

1 The University of Jordan

2 Shahrekord University

Abstract

Circular programming problems are a new class of convex optimization problems that include second-order cone programming problems as a special case. Alizadeh and Goldfarb [Math. Program. Ser. A 95 (2003) 3-51] introduced primal-dual path-following algorithms for solving second-order cone programming problems. In this paper, we generalize their work by using the machinery of Euclidean Jordan algebras associated with the circular cones to derive primal-dual path-following interior point algorithms for circular programming problems. We prove polynomial convergence of the proposed algorithms by showing that the circular logarithmic barrier is a strongly self-concordant barrier. The numerical examples show the path-following algorithms are simple and efficient.

Keywords

Main Subjects

References

[1] F. Alizadeh and D. Goldfarb, Second-order cone programming, Math. Program. Ser. B 95 (2003), no. 1, 3–51.
[2] B. Alzalg, Decomposition-based interior point methods for stochastic quadratic second-order cone programming, Appl. Math. Comput. 249 (2014), 1–18.
[3] B. Alzalg, Volumetric barrier decomposition algorithms for stochastic quadratic second-order cone programming, Appl. Math. Comput. 265 (2015), 494–508.
[4] B. Alzalg, The jordan algebraic structure of the circular cone, Oper. Matrices 11 (2017), no. 1, 1–21.
[5] B. Alzalg and K.A. Ariyawansa, Logarithmic barrier decomposition-based interior point methods for stochastic symmetric programming, J. Math. Anal. Appl. 409 (2014), no. 2, 973–995.
[6] Y.Q. Bai, P.F. Ma, and J. Zhang, A polynomial-time interior-point method for circular cone programming based on kernel functions, J. Indust. Manag. Optim 12 (2016), no. 2, 739–756.
[7] H.H. Bauschke, Projection algorithms and monotone operators, Ph.D. thesis, Theses (Dept. of Mathematics and Statistics)/Simon Fraser University, 1996.
[8] J.F. Bonnans and H.R. Cabrera, Perturbation analysis of second-order cone programming problems, Math. Program. Ser. B 104 (2005), no. 2, 205–227.
[9] S.P. Boyd and B. Wegbreit, Fast computation of optimal contact forces, IEEE Trans. Robot. 23 (2007), no. 6, 1117–1132.
[10] X. Chi, Z. Wan, Z. Zhu, and L. Yuan, A nonmonotone smoothing newton method for circular cone programming, Optimization 65 (2016), no. 12, 2227–2250.
[11] J. Faraut and A. Kor´anyi, Analysis on symmetric cones, Oxford University Press, Oxford, UK, 1994.
[12] C. Helmberg, F. Rendl, R.J. Vanderbei, and H. Wolkowicz, An interior-point methods for stochastic semidefinite programming, SIAM J. Optim. 6 (1996), no. 2, 342–361.
[13] T. Ill´es 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.
[14] B. Kheirfam, An interior-point method for cartesian p?(κ)-linear complementarity problem over symmetric cones, ORiON 30 (2014), no. 1, 41–58.
[15] B. Kheirfam, A full nesterov-todd step interior-point method for circular cone optimization, Commun. Comb. Optim. 1 (2016), no. 2, 83–102.
[16] B. Kheirfam and G.Q. Wang, An infeasible full nt-step interior point method for circular optimization, Numer. Alg. Cont. Optim. 7 (2017), no. 2, 171–184.
[17] C.H. Ko and J.S. Chen, Optimal grasping manipulation for multifingered robots using semismooth newton method, Math. Probl. Eng. 2013 (2013), 1–7.
[18] M. Kojima, S. Shindoh, and S. Hara, Interior-point methods for the monotone linear complementarity problem in symmetric matrices, SIAM J. Optim. 7 (1997), no. 1, 86–125.
[19] B. Leon, A. Morales, and J. Sancho-Bru, Robot grasping foundations, in from robot to human grasping simulation, Springer International Publishing, 2014.
[20] R.D. Monteiro, Primal–dual path-following algorithms for semidefinite programming, SIAM J. Optim. 7 (1997), no. 3, 663–678.
[21] Y. Nesterov and A. Nemirovskii, Interior-point polynomial algorithms in convex programming, SIAM Publications, Philadelphia, PA, 1994.
[22] Yu.E. Nesterov and M.J. Todd, Self-scaled barriers and interior-point methods for convex programming, Math. Oper. Res. 22 (1997), no. 1, 1–42.
[23] , Primal-dual interior-point methods for self-scaled cones, SIAM J. Optim. 8 (1998), no. 2, 324–364.
[24] S.H. Schmieta and F. Alizadeh, Extension of primal-dual interior point algorithms to symmetric cones, Math. Program. Ser. A 96 (2003), no. 3, 409–438.
[25] M.J. Todd, Semidefinite optimization, Acta Numer. 10 (2001), 515–560. 
[26] Y. Zhang, On extending some primal–dual interior-point algorithms from linear programming to semidefinite programming, SIAM J. Optim. 8 (1998), no. 2, 365–386.
[27] J.C. Zhou and J.S. Chen, Properties of circular cone and spectral factorization associated with circular cone, J. Nonlinear Convex Anal. 14 (2013), no. 4, 807–816.
[28] J.C. Zhou, J.S. Chen, and H. Hung, Circular cone convexity and some inequalities associated with circular cones, J. Ineq. Appl. 2013 (2013), no. 1, 571.
[29] J.C. Zhou, J.S. Chen, and B.S. Mordukhovich, Variational analysis of circular cone programs, Optimization 64 (2015), no. 1, 113–147.
 
Communications in Combinatorics and Optimization
Volume 2, Issue 2
September 2017
Pages 65-85

Files

Share

How to cite

Statistics