Fast Solutions to Projective Monotone Linear Complementarity Problems

Geoffrey J. GordonarXiv 2012 · OpenReview

TL;DR

This paper introduces a new, faster algorithm for a specific type of optimization problem called Linear Complementarity Problems (LCPs). By exploiting a special structure in the problem's matrix, the algorithm achieves significant speedups compared to existing methods, making it practical for larger-scale problems.

What Problem Does This Paper Address?

Linear Complementarity Problems (LCPs) are a fundamental problem in optimization with applications ranging from economics to engineering. An LCP involves finding non-negative vectors $x$ and $y$ that satisfy a system of linear equations and a complementarity condition ($x_i y_i = 0$ for all $i$). While general monotone LCPs can be solved efficiently using interior-point methods, these methods typically require solving large systems of linear equations in each iteration, which can be computationally expensive for large problem sizes ($n$). This paper focuses on a subclass of LCPs, termed "projective LCPs," where the matrix $M$ has a specific low-rank structure ($M = \Phi U + \Pi_0$). The challenge is to develop an algorithm that leverages this structure to reduce the computational cost per iteration without sacrificing the overall convergence rate.

Methods

The paper proposes a novel interior-point potential-reduction algorithm. This approach builds upon existing potential-reduction methods for LCPs but introduces a key innovation to handle the projective structure. The core idea is to avoid directly solving large $n \times n$ systems of linear equations. Instead, the algorithm works with a lower-dimensional representation of the problem, specifically using vectors of length $k$ (where $k$ is the rank of the special structure).

The algorithm maintains a strictly feasible point $(x, y)$ and iteratively reduces a potential function. The potential function is designed to guide the iterates towards the central path of the LCP, which is a curve of solutions with a constant complementarity gap. The novelty lies in how the Newton-like steps are computed. By exploiting the low-rank structure of $M$, the algorithm reformulates the problem such that the most computationally intensive part of each iteration involves solving a $k \times k$ system, rather than an $n \times n$ system. This is achieved by introducing an auxiliary variable $w$ and deriving a system of equations that can be solved efficiently using block Gaussian elimination.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithm development and analysis rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Exploiting Low-Rank Structure: The paper demonstrates that a specific low-rank decomposition of the LCP matrix ($M = \Phi U + \Pi_0$) can be leveraged for significant computational gains. This is a crucial insight for accelerating solutions to this class of problems.
  • Dimensionality Reduction: The core algorithmic innovation is the ability to perform most computations in a $k$-dimensional space instead of the original $n$-dimensional space, where $k \ll n$. This is achieved by cleverly reformulating the update steps.
  • Surprising Complexity Result: It's surprising that even though the solution to a projective LCP isn't restricted to a low-rank subspace, an algorithm with significantly reduced iteration complexity ($O(nk^2)$ flops per iteration) can still be developed. This contrasts with linear equations, where low-rank structure directly implies low-rank solutions.
  • Potential Function for Convergence: The use of a potential function is a standard technique in interior-point methods, but its application here, combined with the new update mechanism, guarantees convergence and a specific error reduction rate.

Key Results

The main result is a new algorithm for solving monotone projective LCPs that achieves:

  • Iteration Complexity: $O(\sqrt n \ln(1/\epsilon))$ iterations to reach a relative accuracy of $\epsilon$. This is comparable to general monotone LCP solvers.
  • Flops per Iteration: $O(nk^2)$ flops. This is a significant improvement over general interior-point methods, which require $O(n^3)$ or $O(n^\omega)$ flops per iteration (where $\omega$ is the matrix multiplication exponent) to solve an $n \times n$ system. The speedup is particularly pronounced when $k \ll n$.
  • Guaranteed Strict Feasibility: The algorithm maintains strict feasibility throughout its execution.
  • Guaranteed Potential Reduction: Each step of the algorithm guarantees a reduction in the potential function, ensuring convergence.

Limitations and Future Work

  • Specific Structure Required: The algorithm's efficiency relies heavily on the matrix $M$ having the specific projective structure ($M = \Phi U + \Pi_0$ with $\text{rank}(\Phi) = k < n$). It does not apply to general LCPs.
  • Strict Feasibility Assumption: The algorithm assumes the existence of a strictly feasible initial point. While the paper mentions that constructing one is possible, it's an upfront requirement.
  • Future Work: The paper implicitly suggests that exploring similar low-rank decomposition techniques for other classes of optimization problems could lead to further algorithmic advancements. Further empirical validation on real-world problems with this specific structure would also be valuable.

Summary updated

Abstract

We present a new interior-point potential-reduction algorithm for solving monotone linear complementarity problems (LCPs) that have a particular special structure: their matrix $M\in{\mathbb R}^{n\times n}$ can be decomposed as $M=\Phi U + \Pi_0$, where the rank of $\Phi$ is $k<n$, and $\Pi_0$ denotes Euclidean projection onto the nullspace of $\Phi^\top$. We call such LCPs projective. Our algorithm solves a monotone projective LCP to relative accuracy $\epsilon$ in $O(\sqrt n \ln(1/\epsilon))$ iterations, with each iteration requiring $O(nk^2)$ flops. This complexity compares favorably with interior-point algorithms for general monotone LCPs: these algorithms also require $O(\sqrt n \ln(1/\epsilon))$ iterations, but each iteration needs to solve an $n\times n$ system of linear equations, a much higher cost than our algorithm when $k\ll n$. Our algorithm works even though the solution to a projective LCP is not restricted to lie in any low-rank subspace.
BibTeX
@misc{gordon2012fast,
  author = {Geoffrey J. Gordon},
  title = {{Fast Solutions to Projective Monotone Linear Complementarity Problems}},
  year = {2012},
  eprint = {1212.6958},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1212.6958},
}
Figure