Interior-Point Algorithms for Monotone Linear Complementarity Problem Based on Different Predictor Directions

Marianna E.-Nagy, Tibor Illés, Yurii Nesterov, Petra Renáta Rigó · 2025

Read Interior-Point Algorithms for Monotone Linear Complementarity Problem Based on Different Predictor Directions by Marianna E.-Nagy, Tibor Illés, Yurii Nesterov, Petra Renáta Rigó (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-22185.txt.

Introduction

Marianna Nagy and co-authors introduce two interior point algorithms for monotone linear complementarity problems, in a paper from 2025. Surname only is used for the lead author because the head prints the name with an initial gap. The first method follows a universal tangent direction borrowed from linear optimization.

That method carries the best known worst case complexity bound for the problem class. A self correcting version is added and shown to converge quadratically near the answer, under a mild assumption. Computer tests compare the new methods with a recent general solver for weighted versions of the problem. The authors present the pair as both provably fast and locally rapid.

Catalog record

CREATORMarianna E.-Nagy, Tibor Illés, Yurii Nesterov, Petra Renáta Rigó
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE68 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-22185

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Interior-Point Algorithms for Monotone Linear Complementarity Problem Based on Different Predictor Directions Marianna E.-Nagy, Tibor Illés, Yurii Nesterov, Petra Renáta Rigó Abstract Abstract. In this paper, we introduce two parabolic target-space interior-point algorithms for solving monotone linear complementarity problems. The first algorithm is based on a universal tangent direction, which has been recently proposed for linear optimization problems [ 3 ] . We prove that this method has the best known worst-case complexity bound. We extend onto LCP its auto-correcting version [ 11 ] , and prove its local quadratic convergence under a non-degeneracy assumption. In our numerical experiments, we compare the new algorithms with a general method, recently developed for weighted monotone linear complementarity problems [ 4 ] . Keywords. Interior-point algorithm, Parabolic target-space, Monotone linear complementarity problems, Universal tangent direction, Polynomial complexity MSC Classification. 90C51, 90C33 1 Introduction Linear complementarity problems (LCPs) have applications in several fields, see [ 2 ] . It is well-known that linear programming (LP) and linearly constrained (convex) quadratic programming problems are special cases of LCPs. The monographs written by Cottle et al. [ 2 ] and Kojima et al. [ 7 ] contain the most important classical results for LCPs. General LCPs are NP-complete problems, see [ 1 ] . However, it is known that if the problem’s matrix is skew-symmetric (LP) [ 15 , 16 ] or positive semidefinite (monotone LCP) [ 8 ] , interior-point algorithms (IPAs) can find an approximate solution of LCPs in polynomial time. Starting from a properly selected \varepsilon -complementary feasible solution, an exact solution can be obtained using the rounding procedure in strongly polynomial time, which follows for monotone LCPs as a special case of [ 5 ] . Note that for monotone LCPs there are several results about quadratic convergence of the IPAs using Euclidean proximity measures, see [ 7 , 17 , 13 ] . Furthermore, it is also known that some versions of Newton’s method have local quadratic convergence for the Nonlinear Complementarity Problem under some non-degeneracy assumptions [ 14 ] . In 2008, Nesterov [ 9 ] presented a new target-following approach for LP, which can start at an arbitrary strictly feasible solution. It is based on embedding the problem into a higher-dimensional one, and introducing modeling variables according to the parabolic target space (PTS). The new parabolic barrier function plays a key role in this algorithm. In [ 4 ] , we generalized this algorithm for weighted monotone LCPs. In [ 3 ] , we presented a new PTS IPA for LP problems, which is based on a universal tangent direction. In [ 11 ] , it was shown that the algorithm appeared in [ 3 ] has favorable local behavior under some non-degeneracy assumptions. After that, two new PTS IPAs have been introduced using different search directions in the predictor stage. In this paper, we propose two new PTS IPAs for solving monotone LCPs based on the universal tangent direction proposed in [ 3 ] and on an auto-correcting version of it based on [ 11 ] . We show that the complexity of the new PTA IPAs coincides with the best-known bounds in the theory of IPAs. We present preliminary numerical results, where we compare the two new variants of IPAs with the general method from [ 4 ] for weighted monotone LCPs. In the algorithms [ 4 ] , the search directions are obtained by Newton’s method as applied to the barrier function, which needs inversion of the Hessians. However, the universal tangent direction and auto-correcting predictor direction used in this paper are less expensive. Another advantage of the auto-correcting IPA is that, although the method operates in a lifted space and it is based on the so-called functional proximity measure, we can prove its local quadratic convergence under the non-degeneracy assumption. Throughout the paper, we use the following notations. We use \mathbb{R}^{n}_{\oplus} and \mathbb{R}^{n}_{+} for the positive orthant and its interior. We denote by \mathbf{e} the vector of all ones of the corresponding size, while \bar{\mathbf{e}} stands for a vector of all ones extended by one additional entry. In general, the boldface small letters denote finite-dimensional vectors, while the real numbers and coordinates of vectors are denoted by small letters. All arithmetic operations and relations involving vectors, like \sqrt{\mathbf{x}} , \mathbf{x}\mathbf{s} , \mathbf{x}/\mathbf{s} for \mathbf{x},\mathbf{s}\in\mathbb{R}^{n} , are understood in the component-wise sense. The scalar products and the norms are defined in the standard way: \mathbf{x}^{T}\mathbf{s}=\sum\limits_{i=1}^{n}x_{i}\,s_{i},\;\|\mathbf{x}\|^{2}=\mathbf{x}^{T}\mathbf{x},\;\|\mathbf{x}\|_{1}=\sum\limits_{i=1}^{n}|x_{i}|,\;\|\mathbf{x}\|_{\infty}=\max\limits_{1\leq i\leq n}|x_{i}|,\mathbf{x},\mathbf{s}\in\mathbb{R}^{n}. Note that X denotes the diagonal matrix containing the components of the vector \mathbf{x} on the main diagonal. In our analysis, we often use the following functions [ 12 , 10 ] : \omega(t)=t-\ln(1+t):\;\mathbb{R}_{+}\to\mathbb{R},\qquad\omega_{*}(t)=-t-\ln(1-t):\;[0,1)\to\mathbb{R}. (1) 2 Parabolic target space Consider the LCPs -M\mathbf{x}+\mathbf{s}=\mathbf{q},\quad\mathbf{x},\mathbf{s}\geq\mathbf{0},\quad\mathbf{x}\,\mathbf{s}=\mathbf{0}, ( LCP ) where M\in\mathbb{R}^{n\times n} is a given matrix, \mathbf{q}\in\mathbb{R}^{n} is a given vector and n is a natural number. We assume that the matrix M is positive semidefinite. Denote by {\mathcal{F}}=\{(\mathbf{x},\mathbf{s})\in\mathbb{R}_{\oplus}^{n}\times\mathbb{R}_{\oplus}^{n}:-M\mathbf{x}+\mathbf{s}=\mathbf{q}\},\quad\mathcal{F}^{+}=\{(\mathbf{x},\mathbf{s})\in\mathbb{R}_{+}^{n}\times\mathbb{R}_{+}^{n}:-M\mathbf{x}+\mathbf{s}=\mathbf{q}\} and {\mathcal{F}^{*}}=\{(\mathbf{x},\mathbf{s})\in\mathcal{F}:\mathbf{x}\,\mathbf{s}={\mathbf{0}}\} the sets of feasible, strictly feasible, and optimal solutions to LCP. Our main assumption is {\cal F}^{+}\neq\emptyset . Following [ 4 ] , we relax the nonlinear equation of ( ⁢ L C P ) and define the following c onvex feasibility problem -M\mathbf{x}+\mathbf{s}=\mathbf{q},\quad\mathbf{x},\mathbf{s}\geq\mathbf{0},\quad\mathbf{x}\,\mathbf{s}\geq\mathbf{v}^{2}\quad\hbox{and}\quad v_{0}\geq\mathbf{x}^{T}\mathbf{s}. ( CFP ) When (\mathbf{x},\mathbf{s}) is a solution of ( ⁢ C F P ), then v_{0}\geq\|\mathbf{v}\|^{2} . Therefore, as in [ 9 , 4 , 3 ] , we introduce the variables \mathbf{w}=(v_{0},\mathbf{v})\in\mathbb{R}^{1+n} from the p arabolic target space (PTS) {\mathcal{F}_{w}}=\{\mathbf{w}=(v_{0},\mathbf{v})\in\mathbb{R}^{1+n}:v_{0}\geq\|\mathbf{v}\|^{2}\}. Clearly, \mathcal{F}_{w} is a convex set. We will use notation \mathcal{F}_{w}^{+} to denote its interior. The main idea of our approach is taking a sequence from \mathcal{F}_{w}^{+} which tends to the origin, and solving approximately the corresponding ( ⁢ C F P ) problems. Let us denote the set of all vectors satisfying the system of convex inequalities ( ⁢ C F P ) by \mathcal{F}_{z}=\left\{\mathbf{z}=(\mathbf{x},\mathbf{s},\mathbf{w})\in\mathcal{F}\times\mathcal{F}_{w}:\;\mathbf{x}\,\mathbf{s}\geq\mathbf{v}^{2},\;\mathbf{x}^{T}\mathbf{s}\leq v_{0}\right\}. Since M is a positive semidefinite matrix, the restriction of function \mathbf{x}^{T}\mathbf{s} onto the set \mathcal{F} is convex in \mathbf{x} : \mathbf{x}^{T}\mathbf{s}=\mathbf{x}^{T}(M\mathbf{x}+\mathbf{q})=\mathbf{x}^{T}M\mathbf{x}+\mathbf{q}^{T}\mathbf{x}. Therefore, the set \mathcal{F}_{z} is convex. From \mathcal{F}^{+}\neq\emptyset follows that the relative interior of \mathcal{F}_{z} , denoted by \mathcal{F}_{z}^{+} , is nonempty. It admits a standard self-concordant barrier F(\mathbf{z})\,=\,F(\mathbf{x},\mathbf{s},\mathbf{w})=-\ln\left(v_{0}-\mathbf{x}^{T}\mathbf{s}\right)-\sum_{i=1}^{n}\,\ln\left(x_{i}s_{i}-v^{2}_{i}\right),\quad\mathbf{z}\in\mathcal{F}_{z}^{+} (2) with barrier parameter \nu_{F}=2n+1 . Let us define the following residuals: r_{0}(\mathbf{z})=v_{0}-\mathbf{x}^{T}\mathbf{s},\quad r_{i}(\mathbf{z})\;=\;x_{i}\,s_{i}-v^{2}_{i},\quad i=1,\dots,n. (3) Hence, \mathbf{r}(\mathbf{z})\in\mathbb{R}^{1+n}_{\oplus} . Note that \frac{\bar{\mathbf{e}}^{T}\mathbf{r}(\mathbf{z})}{n+1}=\frac{v_{0}-\|\mathbf{v}\|^{2}}{n+1}=:\rho(\mathbf{w}). (4) With notation ( 3 ), the self-concordant barrier ( 2 ) can be written as F(\mathbf{z})=-\sum\limits_{i=0}^{n}\ln(r_{i}(\mathbf{z})). (5) Let us define now the control barrier function \phi(\mathbf{w})=\min\limits_{(\mathbf{x},\mathbf{s}):(\mathbf{x},\mathbf{s},\mathbf{w})\in\mathcal{F}_{z}}F(\mathbf{x},\mathbf{s},\mathbf{w})\;:\quad\mathbb{R}^{1+n}\to\mathbb{R}, (6) with notation \mathbf{z}(\mathbf{w})=\left(\mathbf{x}(\mathbf{w}),\mathbf{s}(\mathbf{w}),\mathbf{w}\right) for the optimal solution of ( 6 ). As in [ 9 , 4 ] , it has a closed form representation. Theorem 2.1 (Theorem 3.2 in [ 4 ] ) . Let M be positive semidefinite and \mathcal{F}^{+}\neq\emptyset . Then {\rm dom}\,\phi=\mathcal{F}_{w}^{+}\neq\emptyset and the optimization problem ( 6 ) has a unique solution. The optimal vector (\mathbf{x}(\mathbf{w}),\mathbf{s}(\mathbf{w})) is the unique solution of the following system: \begin{array}[]{rl}-M\mathbf{x}+\mathbf{s}&=\mathbf{q},\quad\mathbf{x},\mathbf{s}\geq\mathbf{0},\\ \mathbf{x}\,\mathbf{s}&=\mathbf{v}^{2}+\frac{v_{0}-\|\mathbf{v}\|^{2}}{n+1}\,\mathbf{e}.\end{array} (7) Moreover, for all \mathbf{w}\in\mathcal{F}_{w}^{+} , we have \phi(v_{0},\mathbf{v})=-(n+1)\,\ln\frac{v_{0}-\|\mathbf{v}\|^{2}}{n+1}. Corollary 2.2 . Under assumptions of Theorem 2.1 , the set {\cal F}^{*} is nonempty and bounded. Proof. Proof. Indeed, let (\hat{\mathbf{x}},\hat{\mathbf{s}})\in{\cal F}^{+} . For for any z=(\mathbf{x},\mathbf{s},(v_{0},\mathbf{v}))\in{\cal F}_{z} , we have 0\leq(\hat{\mathbf{x}}-\mathbf{x})^{T}(\hat{\mathbf{s}}-\mathbf{s})\leq\hat{\mathbf{x}}^{T}\hat{\mathbf{s}}-\mathbf{x}^{T}\hat{\mathbf{s}}-\hat{\mathbf{x}}^{T}\mathbf{s}+v_{0}. Therefore, for any sequence \mathbf{w}_{k}\in{\cal F}_{w}^{+} converging to the origin, the sequence (\mathbf{x}(\mathbf{w_{k}}),\mathbf{s}(\mathbf{w_{k}}))

Read the complete text