A New Inexact Non-Interior Continuation Algorithm for Second-Order Cone Programming

  • Liang Fang Taishan University
Keywords: Second-order cone programming, non-interior continuation method, interior-point method, smoothing function, Euclidean Jordan algebra

Abstract

Second-order cone programming has received considerable attention in the past decades because of its wide range of applications. Non-interior continuation method is one of the most popular and efficient methods for solving second-order cone programming partially due to its superior numerical performances. In this paper, a new smoothing form of the well-known Fischer-Burmeister function is given. Based on the new smoothing function, an inexact non-interior continuation algorithm is proposed. Attractively, the new algorithm can start from an arbitrary point, and it solves only one system of linear equations inexactly and performs only one line search at each iteration. Moreover, under a mild assumption, the new algorithm has a globally linear and locally Q-quadratical convergence. Finally, some preliminary numerical results are reported which show the effectiveness of the presented algorithm.

Author Biography

Liang Fang, Taishan University

College of Mathematics and Statistics, Taishan University, 271021, Tai'an

References

Liu, D., Li, L. & Chen, X., Pattern synthesis of a practical conformal hydrophone array via second-order cone programming, Cluster Comput (2018), 1-18. https://doi.org/10.1007/s10586-018-1836-5.

Kanno, Y. & Yamada, H., A note on truss topology optimization under self-weight load: mixed-integer second-order cone programming approach, Structural and Multidisciplinary Optimization, 56(1): 221-226, 2017.

Ukritchon, B. & Keawsawasvong, S., Stability of Retained Soils Behind Underground Walls with an Opening Using Lower Bound Limit Analysis and Second-Order Cone Programming,1-17, 2018 Geotechnical and Geological Engineering, https://doi.org/10.1007/s10706-018-0710-9.

Zhang, Y., A projected-based neural network method for second-order cone programming, International Journal of Machine Learning and Cybernetics, 8(6):1907–1914, 2017.

F. Alizadeh, D. Goldfarb, Second-order cone programming, Mathematical Programming, 95(1)(2003), 3-51.

M.S. Lobo, L. Vandenberghe, S. Boyd, H. Lebret, Applications of second-order cone programming, Linear Algebra and its Applications, 284(1-3)(1998), 193-228.

S.H. Schmieta, F. Alizadeh, Extension of primal-dual interior point algorithms to symmetric cones, Mathematical Programming, Series A., 96(3)(2003), 409-438.

P. Tseng, Second-order cone programming relaxation of sensor network localization, SIAM Journal on Optimization, 18(1)(2007), 156-185.

R.D.C. Monteiro, T. Tsuchiya, Polynomial Convergence of Primal-Dual Algorithms for the Second-Order Cone Program Based on the MZ-Family of Directions, Mathematical Programming, 88(1)(2000), 61-83.

B.K. Rangarajan, Polynomial Convergence of Infeasible-Interior-Point Methods over Symmetric Cones, SIAM J. OPTIM., 16(4)(2006), 1211-1229.

J. Faraut, A. Koranyi, Analysis on symmetric cones, Oxford University Press, London and New York, 1994.

M. Fukushima, Z. Luo, P. Tseng, Smoothing functions for second order cone complimentarity problems, SIAM J. Optim., 2(2)(2001), 436-460.

J. Faraut, A. Koranyi, Analysis on symmetric cones, Oxford University Press, London and New York, 1994.

M.S. Gowda, R. Sznajder, J. Tao, Some P-properties for linear transformations on Euclidean Jordan algebras, Linear Algebra Appl., 393(2004), 203-232.

L. Qi, J. Sun, A nonsmooth version of Newton’s method, Mathematical Programming, 58(1-3)(1993), 353-367.

S. Hayashi, N. Yamashita, M. Fukushima, A combined smoothing and regularized method for monotone second-order cone complementarity problems, SIAM Journal on Optimization, 15(2)(2005), 593-615.

K.C. Toh, R.H. Tütüncü, M.J. Todd, On the implementation of SDPT3 (version 3.1) - a Matlab software package for semidefinite-quadratic-linear programming, Invited Paper, 2004 IEEE Conference on Computer-Aided Control System Design, Taipei, Taiwan.

Published
2019-02-28
How to Cite
Fang, L. (2019). A New Inexact Non-Interior Continuation Algorithm for Second-Order Cone Programming. JOURNAL OF ADVANCES IN MATHEMATICS, 16, 8297-8316. https://doi.org/10.24297/jam.v16i0.8152
Section
Articles