A Homogeneous Model for Mixed Complementarity Problems over Symmetric Cones

Yedong Lin (linsk.tsukuba.ac.jp)
Akiko Yoshise (yoshisesk.tsukuba.ac.jp)

Abstract: In this paper, we propose a homogeneous model for solving monotone mixed complementarity problems over symmetric cones, by extending the results in \cite{YOSHISE04} for standard form of the problems. We show that the extended model inherits the following desirable features: (a) A path exists, is bounded and has a trivial starting point without any regularity assumption concerning the existence of feasible or strictly feasible solutions. (b) Any accumulation point of the path is a solution of the homogeneous model. (c) If the original problem is solvable, then every accumulation point of the path gives us a finite solution. (d) If the original problem is strongly infeasible, then every accumulation point of the path gives us a finite certificate proving infeasibility. We also show that the homogeneous model is directly applicable to the primal-dual convex quadratic problems over symmetric cones.

Keywords: Complementarity problem, nonlinear optimization, optimality condition, symmetric cone, homogeneous algorithm, interior point method, detecting infeasibility.

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Complementarity and Variational Inequalities

Category 3: Nonlinear Optimization

Citation: Vietnam Journal of Mathematics 35 (2007) 541-562

Download: [Postscript][Compressed Postscript][PDF]

Entry Submitted: 09/22/2005
Entry Accepted: 09/22/2005
Entry Last Modified: 04/11/2010

Modify/Update this entry