Study On Complexity Of Some Interior-point Algorithms In Symmetric Cone Complementarity Problem

Since the 1960 s, lots of theory and practice have shown that the interior point method(IPM) is one of the most effective methods for solving linear complementarity problems(LCP) and optimization problems. This thesis devotes to designing and analyzing the IPMs for symmetric cone linear complementarity problems(SCLCP), including LCPs, semidefinite linear complementarity problems(SDLCPs), and studies the algorithm complexity and the numerical results.First, three IPMs were proposed for the non-monotone LCPs, which worked in the wide neighborhoods of the central path. The first two algorithms belong to "safeguard" type Mehrotra predictor-corrector IPM. Compared with the first algorithm, the second method uses a new updating strategy of the centering parameter, which not only simplifies the complexity analysis and ensures that the algorithm is polynomial, but also has better practical efficiency. These algorithms enjoy the O((1 +k)n L) polynomial time complexity. Further, by LCP and a feasible initial iterate, we construct a disturbance of the LCP. Based on it, a second-order infeasible predictor corrector IPM for LCPs was proposed. The algorithm constructs strictly feasible iterates for the perturbations of the given problem, and keeps the iterates in the 1-norm neighborhood of the central path. The corrector is also different from that of the traditional IPM. The algorithm enjoys the O((1 +k)n L) polynomial complexity, which is consistent with the best complexity of IPM so far. Then, the algorithm is extended to SDLCPs, and it also enjoys the same complexity as for LCP.Second, we take further research on the infeasible predictor-corrector IPMs for Cartesian-*P(k) symmetric cone LCPs(SCLCPs). It contains two parts. One is for designing the new algorithm and the other is for analyzing the complexity. It is a characteristic feature of the Mehrotra type IPM that the product of the predictor vectors is used to calculate the corrector vectors. First, under the hypothesis of strictly feasible solution existence, through different weights to the components of the product of the corrector direction vectors, a Mehrotra-type predictor-corrector IPM for Cartesian ( )*P k-SCLCPs is proposed. In order to decrease the residual, the corrector of the algorithm is different from that of the traditional IPMs. It enjoys the complexity (( ) )2 1O1 krlog e-+ for NT-direction. Then by a positive definite initial iterate, we construct the disturbation of the Cartesian ( )*P k-SCLCP. By a second order infeasible IPM for the disturbation, the Cartesian ( )*P k-SCLCP is solved. It enjoys the complexity (( ) )2 1O1 krlog e-+ for NT-direction.Although the LCPs and the horizontal LCPs are equivalent, it is an open problem for SCLCPs. This thesis studies the existence of the central path of the Cartesian ? ?*P ? horizontal SCLCPs. Then a second order infeasible IPM is proposed for the Cartesian ? ?*P ? horizontal SCLCPs. The algorithm aims for the point near the central path to solve the corrector vector, and works in the symmetric neighborhood of the central path to strengthen the centricity of the iterates. It enjoys the complexity ? ?3/ 2 1O rlog ??for NT direction. Some numerical results are provided as well.