Local and Global Convergence of Greedy Parabolic Target-Following Methods for Linear Programming
Yurii Nesterov · 2024
Read Local and Global Convergence of Greedy Parabolic Target-Following Methods for Linear Programming by Yurii Nesterov (2024) 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-2412-14934.txt.
Introduction
Yurii Nesterov, a solo author, studies fast optimization methods for linear programming in a 2024 paper. Linear programming solves problems with linear goals and limits, central to logistics and economics. The methods studied chase a curved central path toward the solution, using a greedy parabolic strategy with a polynomial time guarantee.
Nesterov proves three versions with faster and faster local behavior near the solution. The first reaches a super linear rate when the path is followed closely. A second version with a self correcting predictor switches automatically to quadratic convergence near the end. A third, following quadratic curves, achieves an unusual cubic local rate at little extra cost. Finite termination tricks for spotting the optimal basis are also discussed.
Catalog record
| CREATOR | Yurii Nesterov |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 83 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-14934
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Local and Global Convergence of Greedy Parabolic Target-Following Methods for Linear Programming Yurii Nesterov Abstract In the first part of this paper, we prove that, under some natural non-degeneracy assumptions, the Greedy Parabolic Target-Following Method [ 7 ] , based on universal tangent direction [ 6 ] has a favorable local behavior. In view of its global complexity bound of the order O ( n ln 1 ϵ ) O(\sqrt{n}\ln{1\over\epsilon}) , this fact proves that the functional proximity measure, used for controlling the closeness to Greedy Central Path, is large enough for ensuring a local super-linear rate of convergence, provided that the proximity to the path is gradually reduced. This requirement is eliminated in our second algorithm, which is based on a new auto-correcting predictor direction. This method, besides the best-known polynomial-time complexity bound, ensures an automatic switching onto the local quadratic convergence in a small neighborhood of the solution. We present also the third algorithm, which approximates the path by quadratic curves. On the top of the best known global complexity bound, this method benefits from an unusual local cubic rate of convergence. It is important that this amelioration needs no serious increase in the cost of one iteration. Finally, we compare the advantages of these local accelerations with possibilities of finite termination. As we will see, the conditions allowing the optimal basis detection sometimes are even weaker than those required for the local superlinear convergence. Hence, it is important to endow the practical optimization schemes with both abilities. To the best of our knowledge, the proposed methods have a very interesting combination of favorable properties, which can be hardly found in the most of existing Interior-Point schemes. As all other parabolic target-following schemes, the new methods can start from an arbitrary strictly feasible primal-dual pair and go directly towards the optimal solution of the problem in a single phase. The preliminary computational experiments confirm the advantage of the second-order prediction. Keywords: Linear optimization, interior-point methods, polynomial-time methods, local quadratic convergence, finite termination. 1 Introduction Motivation. In the mid-eighties, starting from the seminal papers by Karmarkar [ 2 ] , Renegar [ 9 ] , and Gonzaga [ 1 ] , the Interior-Point Methods (IPM) for Linear Programming became the most active research direction in Optimization. The new methods, supported by very attractive worst-case polynomial-time complexity bounds, presented a serious competition for the traditional Simplex Method. Today, the most advanced versions of IPM are primal-dual predictor-corrector schemes, which follow the primal-dual central path in a large neighborhood, defined by some proximity measure (e.g. [ 4 ] ). However, despite to the excellent complexity bounds, in the last years these methods are not very popular among practitioners. The reason is that the new problems of Machine Learning and Artificial Intelligence usually have a big dimension and a very special structure, which looks more suitable for the cheap first-order methods. However, the first-order methods are slow and suffer from the absence of polynomial-time complexity bounds. Hence, there is always a chance for adapting IPM to the new reality and getting even more efficient optimization schemes. This paper presents one of the first steps in this direction. The main drawback of the classical theory of IPMs consists in the necessity of performing several stages of the minimization process (for explanations, see for example, Section 5.3.6 in [ 8 ] ). For the primal-dual pair of Linear Optimization Problems \begin{array}[]{rcl}\min\limits_{x\in\mathbb{R}^{n}_{+}}\{\langle c,x\rangle:\;Ax=b\}&=&\max\limits_{y\in\mathbb{R}^{m},s\in\mathbb{R}^{n}_{+}}\{\langle b,y\rangle:\;s+A^{T}y=c\},\end{array} (1.1) the standard methods follows the central path u_{\mu}=(x_{\mu},s_{\mu},y_{\mu}) defined by the following system of equations: \begin{array}[]{rcl}x_{\mu}s_{\mu}&=&\mu e,\quad Ax_{\mu}=b,\quad s_{\mu}+A^{T}y_{\mu}=c,\quad\mu>0,\end{array} where e\in\mathbb{R}^{n} is the vector of all ones. Even if a feasible starting point \begin{array}[]{rcl}u_{0}=(x_{0},s_{0},y_{0})&\in&{\cal F}_{0}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\{(x,s,y):\;Ax=b,\;s+A^{T}y=c,\;x,s\in\mathbb{R}^{n}_{++}\},\end{array} is known, we still need an initial stage for finding an approximation to the point u_{\mu_{0}} for some \mu_{0}>0 . This stage can be eliminated in the framework of weighted barriers [ 10 ] , where the weighted central path is defined by control variable \bar{v}\in\mathbb{R}^{n}_{++} as follows: \begin{array}[]{rcl}x_{\bar{v}}s_{\bar{v}}&=&\bar{v},\quad Ax_{\bar{v}}=b,\quad s_{\bar{v}}+A^{T}y_{\bar{v}}=c,\quad\bar{v}>0.\end{array} (1.2) However, it appears that the worst-case complexity bound in this approach depends on the condition number of the weights: \begin{array}[]{rcl}\kappa(\bar{v})&=&\max\limits_{1\leq i,j\leq n}{\bar{v}^{(i)}\over\bar{v}^{(j)}},\end{array} and this destroys the polynomial-time complexity bounds of the schemes. The latter difficulty was eliminated in [ 7 ] , where the nonlinear equalities in ( 1.2 ) were replaced by convex inequalities : \begin{array}[]{rcl}xs&\geq&v^{2},\quad Ax=b,\quad s+A^{T}y=c,\quad\langle c,x\rangle-\langle b,y\rangle\leq v^{0},\end{array} (1.3) with w=(v^{0},v)\in\mathbb{R}^{n+1} being a vector of control parameters. The main advantage of this approach is related to the fact that the natural barrier function for the feasible set( 1.3 ), \begin{array}[]{rcl}F(u,w)&=&-\sum\limits_{i=1}^{n}\ln(x^{(i)}s^{(i)}-(v^{(i)})^{2})-\ln(v^{0}-\langle c,x\rangle+\langle b,y\rangle)\end{array} admits a close-form solution for the problem \begin{array}[]{rcl}\min\limits_{u\in{\cal F}_{0}}F(u,w)&=&-(n+1)\ln{v^{0}-\|v\|^{2}\over n+1}.\end{array} Thus, it is possible to measure the closeness of any point u\in{\cal F}_{0} to the analytic center of the set ( 1.3 ) by a simple functional proximity measure (FPM). The components of the control variable w in this approach must satisfy the inequality v^{0}>\|v\|^{2} , which explains the name Parabolic Target Space . This idea was elaborated in [ 7 ] in the framework of self-concordant functions (see, for example, Chapter 5 in [ 8 ] ). However, the corresponding machinery of Linear Algebra was quite heavy: instead of inverting at each iteration one m\times m -matrix, as it was done in the standard IPMs for Linear Optimization, it is necessary to invert (2m)\times(2m) -matrices. This was the reason for revisiting this approach in the recent papers [ 5 , 6 ] . In the second paper, we proposed a new Universal Tangent Direction , which is computationally cheap and which ensures the best-known worst-case complexity bound of O(\sqrt{n}\ln{n\over\epsilon}) for the number of Newton steps required for computing an \epsilon -solution of the problem ( 1.1 ). The corresponding method can start from any point u_{0}\in{\cal F}_{0} and travel towards the optimal solution in a single stage. In this paper, we start from further investigation of the properties of method [ 6 ] . In particular, we prove for it a local linear convergence to the non-degenerate solution of the problem ( 1.1 ) with coefficient depending only on the level of functional proximity level. If this level vanishes, then we can get a super-linear convergence rate. However, a slight modification of the search direction gives us already a scheme with local quadratic convergence. Moreover, it is possible to replace the line-search strategy at the predictor step by a parabolic search . In this case, we get a local cubic rate of convergence. On the top of these results, we provide all our methods with a finite-termination criterion, which is based on the new indicator functions. The classical results on local convergence and finite termination of IPMs for Linear Optimization are mainly based on Euclidean proximity measure [ 3 , 11 , 12 , 13 , 15 , 16 , 14 ] . Hence, our developments seem to be new. We confirm our theoretical results by encouraging computational experiments, which confirm a superiority of the second-order prediction. Contents. The paper is organized as follows. In Section 2 , we introduce the framework of Parabolic Target Space [ 7 ] and present a predictor-corrector method for the Greedy Strategy, based on the Universal Tangent Direction (UTD) [ 6 ] . Our method ( 2.14