Abstract
In this paper, a variant of Mehrotra-type predictor–corrector algorithm is proposed for \(P_{*}(\kappa )\) linear complementarity problems. In this algorithm, a safeguard step is used to avoid small step sizes and a new corrector direction is adopted. The algorithm has polynomial iteration complexity and the iteration bound is \(O ((14\kappa +11)\sqrt{(1+4 \kappa )(1+2\kappa )}~n\log \frac{(x^{0})^{T}s^{0}}{\varepsilon } )\). Some numerical results are reported as well.
Similar content being viewed by others
1 Introduction
A \(P_{*}(\kappa )\) linear complementarity problem (LCP) is to find vectors \(x \in \mathbb{R}^{n}\) and \(s \in \mathbb{R}^{n}\) such that
where \(M\in \mathbb{R}^{n\times n}\) is a \(P_{*}(\kappa )\) matrix and \(q\in \mathbb{R}^{n}\).
LCPs are closely associated with linear programming and quadratic programming. It is well known that a differentiable convex quadratic programming can be formulated as a monotone LCP by exploiting the first-order optimality conditions, and vice versa [1]. Transportation planning and game theory also have a close connection with LCPs [2, 3].
Interior point algorithms for LCPs have been widely studied in the last few decades [4]. In 1991, Kojima et al. [5] extended all the previously known results to \(P_{*}(\kappa )\) LCPs and unified the theory of LCPs from the view point of interior point methods. Since then, many interior point algorithms for linear programming have been extended to \(P_{*}(\kappa )\) LCPs. Illés and Nagy [6], and Miao [7] studied the Mizuno-Todd-Ye type interior point algorithms on \(P_{*}(\kappa )\) LCPs. Cho [8], and Cho and Kim [9] proposed two interior point polynomial algorithms based on kernel functions for \(P_{*}(\kappa )\) LCPs. Using a new updating strategy of the centering parameter, Liu et al. [10] extended two Mehrotra-type predictor–corrector algorithms to sufficient LCPs.
Predictor–corrector algorithms are practical interior point methods for linear programming, quadratic programming and LCPs, variants of which have become backbones of several optimization software packages [11, 12]. Mehrotra [13] proposed a predictor–corrector algorithm for linear programming, in which the coefficient matrices in both predictor steps and corrector steps are the same, and it needs less computational efforts than other methods. After that, several variants of this algorithm have been studied. Jarre and Wechs [14] studied a new primal–dual interior point method in which the search directions are based on corrector directions of Mehrotra-type algorithm. Zhang and Zhang [15] presented a second order Mehrotra-type predictor–corrector algorithm without updating the central path. Salahi et al. [16] found that in a variant of Mehrotra’s algorithm, in order to keep iterates in a large neighborhood of the central path, some steps are very small. To avoid small or zero steps, Salahi et al. introduced some safeguards in the corrector steps [16] and a new criterion on predictor step sizes [17], moreover, they proved that the two algorithms have polynomial complexity and practical efficiency. Infeasible versions of Mehrotra-type algorithms are studied by Liu et al. [18], and Yang et al. [19].
In this paper, a new variant of Mehrotra-type predictor–corrector algorithm is proposed for \(P_{*}(\kappa )\) LCPs. In this algorithm, the corrector step is different from other Mehrotra-type predictor–corrector algorithms [16, 17]. If (Δx, Δs) is the search direction of a \(P_{*}(\kappa )\) LCP, then \(\Delta x^{T}\Delta s \neq 0 \), while \(\Delta x^{T}\Delta {s}=0 \) if (Δx, Δs) is the search direction of linear programming. So the analysis is different from that in linear programming. If an iteration \((x,s)\) takes a step along the corrector direction \((\Delta x,\Delta s)\), the parameter \(\mu _{g}(\alpha )=(1-\alpha )\mu _{g}+\alpha \mu -\alpha \alpha _{a}^{2} \frac{{\Delta x^{a}}^{T}\Delta s^{a}}{n}+{\alpha ^{2}}\frac{{\Delta x}^{T}\Delta s}{n}\), where \(\alpha _{a}\) is the predictor step size and \((\Delta x^{a},\Delta s ^{a})\) is the predictor search direction. In order to reduce the dual gap \(x^{T}s\), the corrector step size α should be chosen such that \(\mu _{g}(\alpha ) \leq \mu _{g}\), that is to say, α should have an upper bound. If α is larger than a given threshold, then the threshold is chosen as the corrector step size. The iteration complexity of the new algorithm is \(O ((14\kappa +11)\sqrt{(1+4 \kappa )(1+2\kappa )}~n\log \frac{(x^{0})^{T}s^{0}}{\varepsilon } )\), which is analogous to that of linear programming.
This paper is organized as follows. In Sect. 2, a new Mehrotra-type predictor–corrector algorithm for \(P_{*}(\kappa )\) LCPs is introduced. In Sect. 3, the polynomial iteration complexity is provided. Some illustrative numerical results are reported in Sect. 4. Finally, some concluding remarks are given in Sect. 5.
We use the following notations throughout the paper: \(\|\cdot \|\) denotes the 2-norm of vectors, e is the n-dimensional vector of ones. For any two n-dimensional vectors x and s, xs is the componentwise product of the two vectors. We also use the following notations.
2 Mehrotra-type predictor–corrector algorithm
A matrix \(M\in \mathbb{R}^{n\times n}\) is a \(P_{*}(\kappa )\) matrix [5] if
or
where \(\kappa \geq 0\), \(J_{+}=\{j|j\in I, x_{j}(Mx)_{j}\geq 0\}\), and \(J_{-}=\{j|j\in I, x_{j}(Mx)_{j}<0\}\).
Noting that the positive semi-definite matrix is a \(P_{*}(0)\) matrix, thus the class of \(P_{*}(\kappa )\) matrices includes the class of positive semi-definite matrices. Other properties of \(P_{*}(\kappa )\) matrices can be found in [5].
Without loss of generality [5], we assume that the \(P_{*}(\kappa )\) LCP (1) satisfies the interior point condition, that is, there exists a point \((x^{0},s^{0})\) such that
To find an approximate solution of (1), the following parameterized system is established:
where \(\mu >0\).
If the \(P_{*}(\kappa )\) LCP (1) satisfies the interior point condition, then the system (4) has a unique solution for any \(\mu > 0\). For a given μ, the solution, denoted by \((x(\mu ),s(\mu ))\), is called a μ-center of (1). The set of all μ-centers gives the central path of (1). A primal–dual interior point algorithm follows the central path \(\{(x(\mu ),s(\mu ))|\mu >0\}\) approximately and approaches the solution of (1) as μ goes to zero.
Most interior point algorithms work in the neighborhood \(N_{\infty } ^{-}(\gamma )\) defined by
where \(\gamma \in (0,1)\) is a constant independent of n and \(\mu _{g}=\frac{x^{T}s}{n}\).
Now, based on [16], a new variant of Mehrotra-type predictor–corrector algorithm for \(P_{*}(\kappa )\) LCPs will be described.
The predictor search direction (\(\Delta x^{a}\), \(\Delta s^{a}\)) is determined by the following equations:
The predictor step size \(\alpha _{a}\) is defined by
However, this algorithm does not take a step along the direction \((\Delta x^{a},\Delta s^{a})\). Using information of the predictor step, the algorithm computes the corrector search direction \((\Delta x, \Delta s)\) by solving the following system:
where
with \(g_{a}=(x+\alpha _{a}\Delta x^{a})^{T}(s+\alpha _{a}\Delta s^{a})\) and \(g=x^{T}s\). The second equation of (7) is different from that in [16], where it is \(s\Delta x+x \Delta s =\mu e-xs-\Delta x^{a}\Delta s^{a}\).
The next iterate is denoted by
where α is the corrector step size defined by
In order to avoid small steps, we combine Mehrotra’s updating strategy of the centering parameter with a safeguard step at each iteration. The new Mehrotra-type predictor–corrector algorithm for \(P_{*}(\kappa )\) LCPs is stated as Algorithm 1.
3 Complexity analysis
The polynomial complexity of Algorithm 1 will be discussed in this section. Firstly, we present three important lemmas which will be used in convergence analysis.
Lemma 1
([16])
Let \((\Delta x^{a},\Delta s^{a})\) be the solution of (5). Then
Lemma 2
Let M be a \(P_{*}(\kappa )\) matrix and \((\Delta x^{a},\Delta s^{a})\) be the solution of (5). Then
Proof
Since M is a \(P_{*}(\kappa )\) matrix, we have
where the last inequality is due to the third conclusion of Lemma 1. Furthermore, from (3), we get
This completes the proof. □
Lemma 3
Let M be a \(P_{*}(\kappa )\) matrix and \((\Delta x,\Delta s)\) be the solution of (7) with \(\mu >0\). Then
Proof
The proof is similar to that of Lemma 8 in [6], and it is omitted. □
According to (8) and Lemma 2, it can be found that
Consequently, \(\frac{\mu }{\mu _{g}} \leq (1-\frac{3}{4}\alpha _{a} )^{3}\) if \(\mu = (\frac{g_{a}}{g} )^{2}\frac{g _{a}}{n}\).
The following theorem shows that the predictor step size has a lower bound.
Theorem 4
Let the current iterate \((x,s)\in N_{\infty }^{-}(\gamma )\), \((\Delta x^{a},\Delta s^{a})\) be the solution of (5) and \(\alpha _{a}\) be the predictor step size. Then
Proof
According to (5), we get
Following from Lemma 2, we have \(\Delta x_{i}^{a} \Delta s_{i}^{a} \geq 0\) if \(i \in I_{+}\) and \(\Delta x_{i}^{a}\Delta s_{i}^{a} \geq -\frac{4\kappa +1}{4}x^{T}s\) if \(i \in I_{-}\). Therefore, for all \(i \in I\),
Noting that \((x,s)\in N_{\infty }^{-}(\gamma )\) implies \(x_{i}s_{i} \geq \gamma \mu _{g}\), we have
Thus, to show \((x+\alpha \Delta x^{a},s+\alpha \Delta s^{a})\in {F} _{+}\), one has to prove the following inequality:
Clearly, inequality (11) is true if
Therefore, the predictor step size \(\alpha _{a}\) satisfies
Since \(0<\frac{\gamma }{(4\kappa +1)n}<\frac{1}{4\kappa +1}\frac{1}{4 \kappa +5}\frac{1}{n}<\frac{1}{2}\), it can be found that
This completes the proof. □
In what follows, the lower bound of \(\alpha _{a}\) is used as the default predictor step size with the notation
Lemma 5
If \((x,s)\in {N}_{\infty }^{-}(\gamma )\), and \((\Delta x,\Delta s)\) is the solution of (7) with \(\mu \geq 0\), then
and
where \(\omega =\frac{n\mu ^{2}}{\gamma \mu _{g}} -2n\mu +\frac{n\mu \alpha _{a}^{2}(4\kappa +1)}{2\gamma }+\frac{\alpha _{a}^{4}+8\alpha _{a}^{2}+4\alpha _{a}^{2}(4\kappa +1)(1-\alpha _{a})+16}{16}n\mu _{g}\).
Proof
From Lemma 3, we have
and
where
Since \(x_{i}s_{i}\geq \gamma \mu _{g}\) for all \(i\in {I}\), we have
From Lemma 1 and Lemma 2, it follows that
Since \((x,s)\in {N}_{\infty }^{-}(\gamma )\) and \(\sum_{i\in I _{-}}|\Delta x_{i}^{a}\Delta s_{i}^{a}|\leq \frac{4\kappa +1}{4}x^{T}s\), we obtain
As \(\sum_{i\in I_{+}}\Delta x_{i}^{a}\Delta s_{i}^{a}\leq \frac{x ^{T}s}{4}\), we get
Combining the above inequalities yields the result of this lemma. □
Corollary 6
If \((x,s)\in {N}_{\infty }^{-}(\gamma )\), \(\gamma \in (0,\frac{1}{4 \kappa +5} )\), and \((\Delta x,\Delta s)\) is the solution of (7) with \(\mu =\frac{\gamma }{1-\gamma }\mu _{g}\), then
where \(p=\frac{14\kappa +11}{16}\sqrt{(1+4\kappa )(2+4\kappa )}\) and \(q=\frac{14\kappa +11}{16}\).
Proof
Since \(0<\gamma <\frac{1}{4\kappa +5}\leq \frac{1}{5}\), we have \(\frac{\gamma }{(1-\gamma )^{2}} \leq \frac{5}{16}\) and \(\frac{\alpha _{a}^{2}(4\kappa +1)-4\gamma }{2(1-\gamma )} \leq \frac{5\alpha _{a} ^{2}(4\kappa +1)}{8}\).
If \(\mu =\frac{\gamma }{1-\gamma }\mu _{g}\), then
where the second inequality follows from \(0<\alpha _{a}\leq 1\).
From Lemma 5, it follows that
Similarly, the second result can easily be verified. □
For simplicity, the following notation is used in the rest of this paper:
Obviously, \(\Delta x_{i}^{a}\Delta s_{i}^{a} \leq tx_{i}s_{i}\) and \(t\leq \frac{1}{4}\).
Theorem 7
Let \((x,s)\in N_{\infty }^{-}(\gamma )\), \((\Delta x,\Delta s)\) be the solution of (7) with \(\mu =\frac{\gamma }{1- \gamma }\mu _{g}\) and α be the corrector step size. Then
Proof
The corrector step size is the maximum α such that \(\alpha \in (0,1]\) and
After a simple computation, we get
where the inequality is due to \(\Delta x_{i}^{a}\Delta s_{i}^{a} \leq tx_{i}s_{i}\) and \(\|\Delta x\Delta s\|\leq pn\mu _{g}\). Clearly, \(1+t\alpha _{a}^{2} \leq 1+\frac{1}{4}\alpha _{a}^{2}\). Thus, for \(0 \leq \alpha \leq \frac{1}{1+\frac{1}{4}\alpha _{a}^{2}}\), we have
Applying Lemma 2 and Corollary 6 yields
To prove \(x_{i}(\alpha )s_{i}(\alpha )\geq \gamma \mu _{g}(\alpha )\), one has to show that
If \(\mu =\frac{\gamma }{1-\gamma }\mu _{g}\), then the above inequality is equivalent to
Since \(\alpha _{a}=\sqrt{\frac{\gamma }{(4\kappa +1)n}}\), \(\gamma <1\) and \(t\leq \frac{1}{4}\), we have
Noting that \(pn>q\gamma \), then inequality (14) is true if \(0 \leq \alpha \leq \frac{7\gamma }{16pn}\). We can conclude that the corrector step size α satisfies
□
In Algorithm 1, the corrector step size α has an upper bound \(\alpha _{1}\), that is,
The next theorem means that the upper bound is well defined.
Theorem 8
Let \(\alpha _{a}\) be the default predictor step size and \(\gamma \in (0,\frac{1}{4\kappa +5} )\). Then \(\frac{7\gamma }{16pn}<\frac{1-2\gamma -(1-\gamma )\kappa \alpha _{a} ^{2}}{2q(1-\gamma )}<1\).
Proof
Since \(q=\frac{14\kappa +11}{16}>\frac{1}{2}\), it is clear that \(\frac{1-2\gamma -(1-\gamma )\kappa \alpha _{a}^{2}}{2q(1-\gamma )}<1\). As \(n\geq 2\) and \(p>q>\frac{1}{2}\), we have
According to (12), one has \(\kappa \alpha _{a}^{2}=\frac{ \kappa \gamma }{n(4\kappa +1)}\leq \frac{\gamma }{8}\), thus
From \(\gamma <\frac{1}{4\kappa +5}\leq \frac{1}{ 5}\), it follows that
Therefore
which completes the proof. □
In the following theorem, we obtain an upper bound of the iteration number.
Theorem 9
Algorithm 1 stops after at most
iterations with a solution for which \(x^{T}s\leq \varepsilon \).
Proof
If \(\alpha _{a}\geq 0.3\) and \(\alpha \geq \frac{7\gamma }{16pn}\), then Algorithm 1 adopts Mehrotra’s strategy in the corrector step, i.e., \(\mu = (\frac{g_{a}}{g} )^{2}\frac{g_{a}}{n}\). Based on (13), we have
where the second inequality follows from (10) and (15), the third inequality is due to \(\kappa \alpha _{a}^{2}\leq 0.025\) and \(1-\frac{3}{4}\alpha _{a}\leq \frac{31}{40}\), and the fourth inequality comes from \(1-0.0125-0.47 \geq \frac{1}{2}\).
If \(\alpha _{a}<0.3\) or \(\alpha <\frac{7\gamma }{16pn}\), then Algorithm 1 adopts the safeguard strategy in the corrector step, that is, \(\mu =\frac{\gamma }{1-\gamma }\mu _{g}\). In this case, from \(\frac{7\gamma }{16pn} \leq \alpha \leq \frac{1-2\gamma -(1-\gamma ) \kappa \alpha _{a}^{2}}{2q(1-\gamma )}\), we get
where the last inequality follows from \(\kappa \alpha _{a}^{2}\leq 0.025\) and \(\alpha \geq \frac{7\gamma }{16pn}\). This completes the proof by Theorem 3.2 of [1]. □
4 Numerical results
In this section, some numerical results are reported. The results are obtained by using MATLAB R2014a.
The algorithm presented in this paper is compared with a Mizuno–Todd–Ye (MTY) type predictor–corrector algorithm [6], Cho’s algorithm [8] and an interior point algorithm based on the classical kernel function \(\varphi (t)= \frac{t^{2}-1}{2}-\log {t}\) (IPMCKF) [20]. We consider the following two problems.
Problem 1
([21])
Problem 2
([22])
Problem 1 is a \(P_{*}(\frac{1}{4})\) LCP, and Problem 2 is a \(P_{*}(0)\) LCP. We solve the two problems by using the above-mentioned algorithms. For all algorithms we set the accuracy parameter \(\epsilon =10^{-8}\). In Algorithm 1, we set \(\gamma =0.01\).
Table 1 shows the iteration numbers of Algorithm 1, MTY algorithm, Cho’s algorithm and IPMCKF algorithm for Problem 1. From the results we conclude that Algorithm 1 reduced the iteration numbers.
Table 2 gives the iteration numbers of the four algorithms for Problem 2 with \(n \in \{10,20,30,40,50,100,150,200\}\). The numerical results illustrate that Algorithm 1 has the least iteration numbers. Since the safeguard step helps Algorithm 1 to avoid small steps, Algorithm 1 is efficient.
5 Concluding remarks
In this paper, a Mehrotra-type predictor–corrector algorithm for \(P_{*}(\kappa )\) LCPs is studied. Since \(P_{*}(\kappa )\) LCPs are the generalization of linear programming, the search directions Δx and Δs are not orthogonal, therefore the analysis is different from that in linear programming. The iteration bound of our algorithm is \(O ((14\kappa +11) \sqrt{(1+4\kappa )(1+2\kappa )}~n\log \frac{(x^{0})^{T}s^{0}}{\varepsilon } )\). Numerical results show that this algorithm is efficient.
References
Wright, S.J.: Primal–Dual Interior-Point Methods. Society for Industrial and Applied Mathematics, Philadelphia (1997)
Billups, S.C., Murty, K.G.: Complementarity problems. J. Comput. Appl. Math. 124(1), 303–318 (2000)
Cottle, R.W., Pang, J.S., Stone, R.E.: The Linear Complementarity Problem. Academic Press, New York (1992)
Roos, C., Terlaky, T., Vial, J.P.: Interior Point Methods for Linear Optimization. Springer, Boston (2006)
Kojima, M., Megiddo, N., Noma, T., Yoshise, A.: A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems. Springer, Berlin (1991)
Illes, T., Nagy, M.: A Mizuno–Todd–Ye type predictor–corrector algorithm for sufficient linear complementarity problems. Eur. J. Oper. Res. 181(3), 1097–1111 (2007)
Miao, J.: A quadratically convergent \(O((1+\kappa )\sqrt {n}{L})\)-iteration algorithm for the \(P_{*}(\kappa )\)-matrix linear complementarity problem. Math. Program. 69(1), 355–368 (1995)
Cho, G.M.: A new large-update interior point algorithm for \(P_{*}(\kappa )\) linear complementarity problems. J. Comput. Appl. Math. 216(1), 265–278 (2008)
Cho, G.M., Kim, M.K.: A new large-update interior point algorithm for \(P_{*}(\kappa )\) LCPs based on kernel functions. Appl. Math. Comput. 182(2), 1169–1183 (2006)
Liu, H., Liu, X., Liu, C.: Mehrotra-type predictor–corrector algorithms for sufficient linear complementarity problem. Appl. Numer. Math. 62(12), 1685–1700 (2012)
Czyzyk, J., Mehrotra, S., Wagner, M., Wright, S.: Pcx: an interior-point code for linear programming. Optim. Methods Softw. 11(1–4), 397–430 (1999)
Zhang, Y.: Solving large-scale linear programs by interior-point methods under the Matlab environment. Optim. Methods Softw. 10(1), 1–31 (1998)
Mehrotra, S.: On finding a vertex solution using interior point methods. Linear Algebra Appl. 152(91), 233–253 (1991)
Jarre, F., Wechs, M.: Extending Mehrotra’s corrector for linear programs. Adv. Model. Optim. 1(2), 38–60 (1999)
Zhang, Y., Zhang, D.: On polynomiality of the Mehrotra-type predictor–corrector interior-point algorithms. Math. Program. 68(1), 303–318 (1995)
Salahi, M., Peng, J., Terlaky, T.: On Mehrotra-type predictor–corrector algorithms. SIAM J. Optim. 18(4), 1377–1397 (2007)
Salahi, M., Terlaky, T.: Mehrotra-type predictor–corrector algorithm revisited. Optim. Methods Softw. 23(2), 259–273 (2008)
Liu, X., Liu, H., Wang, W.: Polynomial convergence of Mehrotra-type predictor–corrector algorithm for the Cartesian \(P_{*}(\kappa )\)-LCP over symmetric cones. Optimization 64(4), 815–837 (2015)
Yang, X., Liu, H., Dong, X.: Polynomial convergence of Mehrotra-type prediction-corrector infeasible-IPM for symmetric optimization based on the commutative class directions. Appl. Math. Comput. 230(2), 616–628 (2014)
Lesaja, C., Roos, C.: Unified analysis of kernel-based interior-point methods for \(P_{*}(\kappa )\)-linear complementarity problems. SIAM J. Optim. 20(6), 3014–3039 (2010)
Lee, Y.-H., Cho, Y.-Y., Cho, G.-M.: Interior-point algorithms for \(P_{*}(\kappa )\) LCP based on a new class of kernel functions. J. Glob. Optim. 58, 137–149 (2014)
Harker, P.T., Pang, J.-S.: A damped-Newton method for the linear complementarity problem. Lect. Appl. Math. 26, 265–284 (1990)
Funding
This work was supported by the National Natural Science Foundation of China (71471102, 71561022 and 71771025).
Author information
Authors and Affiliations
Contributions
All authors contributed equally to this work. All authors read and approved the final manuscript.
Corresponding author
Ethics declarations
Competing interests
The authors declare that they have no competing interests.
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Zhou, Y., Zhang, M. & Huang, Z. On complexity of a new Mehrotra-type interior point algorithm for \(P_{*}(\kappa )\) linear complementarity problems. J Inequal Appl 2019, 6 (2019). https://doi.org/10.1186/s13660-019-1954-5
Received:
Accepted:
Published:
DOI: https://doi.org/10.1186/s13660-019-1954-5