Non-interior continuation algorithm for solving system of inequalities over symmetric cones

Abstract

As a basic mathematical structure, the system of inequalities over symmetric cones and its solution can provide an effective method for solving the startup problem of interior point method which is used to solve many optimization problems. In this paper, a non-interior continuation algorithm is proposed for solving the system of inequalities under the order induced by a symmetric cone. It is shown that the proposed algorithm is globally convergent and well-defined. Moreover, it can start from any point and only needs to solve one system of linear equations at most at each iteration. Under suitable assumptions, global linear and local quadratic convergence is established with Euclidean Jordan algebras. Numerical results indicate that the algorithm is efficient. The systems of random linear inequalities were tested over the second-order cones with sizes of 10,100, ...,1 000 respectively and the problems of each size were generated randomly for 10 times. The average iterative numbers show that the proposed algorithm can generate a solution at one step for solving the given linear class of problems with random initializations. It seems possible that the continuation algorithm can solve larger scale systems of linear inequalities over the second-order cones quickly. Moreover, a system of nonlinear inequalities was also tested over Cartesian product of two simple second-order cones, and numerical results indicate that the proposed algorithm can deal with the nonlinear cases.

Keywords

system of inequalities / symmetric cone / non-interior continuation algorithm / global linear convergence / local quadratic convergence

References

[1] Daniel J. W. Newton’s method for nonlinear inequalities [J]. Numerische Mathematik, 1973, 21(5): 381-387.

[2] Mayne D. Q., Polak E., Heunis A. J. Solving nonlinear inequalities in a finite number of iterations[J]. Journal of Optimization Theory and Applications, 1981, 33(2): 207-221.

[3] Macconi M., Morini B., Porcelli M. Trust-region quadratic methods for nonlinear systems of mixed equalities and inequalities[J]. Applied Numerical Mathematics, 2009, 59(5): 859-876.

[4] Morini B, Porcelli M. TRESNEI, a Matlab trust-region solver for systems of nonlinear equalities and inequalities[J]. Computational Optimization and Applications. DOI:10. 1007/s10589-010-9327-5.

[5] Huang Z. H., Zhang Y., Wu W. A smoothing-type algorithm for solving system of inequalities[J]. Journal of Computational and Applied Mathematics, 2008, 220(1/2): 355-363.

[6] Zhang Y., Huang Z. H. A nonmonotone smoothing-type algorithm for solving a system of equalities and inequalities[J]. Journal of Computational and Applied Mathematics, 2010, 233(9): 2312-2321.

[7] Zhu J. G., Liu H. W., Li X. L. A regularized smoothing-type algorithm for solving a system of inequalities with a P ₀-function[J]. Journal of Computational and Applied Mathematics, 2010, 233(10): 2611-2619.

[8] Burke J., Xu S. A non-interior predictor-corrector path following algorithm for the monotone linear complementarity problem[J]. Mathematical Programming, 2000, 87(1): 113-130.

[9] Chen B. T., Chen X. J. A global and local superlinear continuation-smoothing method for P ₀ and R ₀ NCP or monotone NCP[J]. SIAM Journal on Optimization, 1999, 9(3): 624-645.

[10] Chen B. T., Xiu N. H. A global linear and local quadratic non-interior continuation method for nonlinear complementarity problems based on Chen-Mangasarian smoothing functions[J]. SIAM Journal on Optimization, 1999, 9(3): 605-623.

[11] Chen X., Tseng P. Non-interior continuation methods for solving semidefinite complementarity problems[J]. Mathematical Programming, 2003, 95(3): 431-474.

[12] Lu N., Huang Z. H. Convergence of a non-interior continuation algorithm for the monotone SCCP[J]. Acta Mathematicae Applicatae Sinica(English Series), 2010, 26(4): 543-556.

[13] Faraut J., Koranyi A. Analysis on Symmetric Cones[M]. 1994, Oxford, UK: Oxford University Press.

[14] Gowda M. S., Sznajder R., Tao J. Some P-properties for linear transformation on Euclidean Jordan algebras[J]. Linear Algebra and Its Applications, 2004, 393(1): 203-232.

[15] Pan S. H., Chen J. S. A one-parametric class of metric functions for the symmetric cone complementarity problem[J]. Journal of Mathematical Analysis and Applications, 2009, 355(1): 195-215.

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