TL;DR
This paper introduces a new interior-point algorithm for solving linear complementarity problems (LCPs) that is guaranteed to converge from any positive starting point and achieves polynomial complexity. The algorithm is also shown to be readily extendable to mixed LCPs, linear programming (LP), and convex quadratic programming (QP) problems, offering a unified approach to these important optimization tasks.
What Problem Does This Paper Address?
The paper tackles the problem of solving the Linear Complementarity Problem (LCP), which is a fundamental problem in optimization with applications in economics, engineering, and game theory. An LCP seeks to find a pair of vectors $(x, y)$ that satisfy a set of linear equations and inequalities, specifically:
$y = Mx + q$ $x \ge 0, y \ge 0$ $x^T y = 0$
where $M$ is a positive semidefinite matrix and $q$ is a vector. A key challenge in solving LCPs is the "complementarity" condition ($x^T y = 0$), which means that for each index $i$, at least one of $x_i$ or $y_i$ must be zero. This condition makes standard linear system solvers insufficient. Furthermore, many existing algorithms require a "strictly feasible" starting point (where $x > 0$ and $y > 0$), which is often not available in practice. The paper also addresses the more general Mixed Linear Complementarity Problem (MLCP) and its relation to LP and QP problems.
Methods
The core of the paper is a novel "path-following interior-point algorithm." Interior-point methods work by staying strictly within the feasible region (in this case, $x > 0$ and $y > 0$) and following a "central path" towards the solution. The key innovations of this algorithm include:
- Convergence from any positive starting point: Unlike some previous methods, this algorithm does not require a strictly feasible starting point, making it more robust.
- "Fast" and "Safe" Steps: The algorithm employs two types of steps. A "fast step" aims for rapid progress using an affine scaling direction, while a "safe step" uses a centering parameter to ensure progress and avoid numerical issues. The algorithm prioritizes fast steps but reverts to safe steps if they don't yield sufficient improvement.
- Unified Framework: The algorithm is designed to handle not only LCPs but also MLCPs, LP, and QP problems by reformulating them as LCPs. This provides a single algorithmic framework for a broad class of optimization problems.
- Matrix Factorization and Triangular Solves: Like many interior-point methods, the computational core of each iteration involves matrix factorizations and solving triangular systems, which are standard but efficient operations.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Generality through LCP: The paper strongly advocates for the LCP as a unifying framework for LP and QP. By showing that LP and QP optimality conditions can be expressed as LCPs, it suggests that LCP algorithms can be applied to these problems with little loss of efficiency, especially if the underlying linear algebra exploits the specific structure of LP/QP.
- Robustness to Infeasibility: The ability to start from any positive point (not necessarily feasible) is a significant practical advantage, as finding strictly feasible starting points can be difficult for many real-world problems.
- "Fast" vs. "Safe" Step Trade-off: The algorithm's strategy of attempting aggressive "fast" steps and falling back to more conservative "safe" steps is a clever way to balance speed and convergence guarantees. This is a common theme in interior-point methods, but the specific formulation here is novel.
- Subquadratic Convergence: For problems with a "strictly complementary" solution (a desirable property where $x_i > 0$ and $y_i > 0$ for some indices), the algorithm exhibits superlinear convergence, which is quite fast.
Key Results
- Global Convergence: The algorithm is proven to converge globally to the solution set of the LCP from any strictly positive starting point.
- Polynomial Complexity: Under certain assumptions on the starting point, the algorithm achieves polynomial complexity, meaning the number of iterations grows polynomially with the problem size.
- Superlinear Convergence: When a strictly complementary solution exists, the algorithm converges superlinearly (specifically, Q-order 2), meaning the rate of convergence accelerates as it approaches the solution.
- Extension to MLCP, LP, and QP: The paper demonstrates that the algorithm can be readily extended to solve mixed LCPs, and consequently, all standard formulations of linear and convex quadratic programming problems.
Limitations and Future Work
- Assumption of Feasibility: The analysis relies on the assumption that the LCP (or MLCP) is feasible. While the paper notes that LP/QP problems typically have feasible primal-dual points, it acknowledges that some LPs can be primal or dual infeasible. The authors mention that techniques exist to reformulate such problems to satisfy this assumption, allowing their algorithm to be applied with confidence.
- Nondegeneracy Assumption: The local convergence analysis requires the existence of a "strictly complementary" solution, which is a form of nondegeneracy. While this is a common assumption in the field, the paper notes that dropping it would likely sacrifice superlinear convergence.
- Future Work: The paper implicitly suggests future work in exploring the practical performance of this unified algorithm across its various applications (LCP, MLCP, LP, QP) and potentially refining the step selection strategy for even faster convergence in practice. The extension to more general nonlinear complementarity problems is also a natural avenue for future research.
Summary updated