Non-interior continuation algorithm for solving system of inequalities over symmetric cones |
| |
Authors: | Ying Zhang Nan Lu |
| |
Institution: | (School of Sciences,Tianjin University,Tianjin 300072,China) |
| |
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 |
本文献已被 CNKI 维普 万方数据 SpringerLink 等数据库收录! |
|