Theorem of Alternative for Extended Homogeneous Linear System and its Application in Conic Optimization
Yurii Nesterov · 2026
Read Theorem of Alternative for Extended Homogeneous Linear System and its Application in Conic Optimization by Yurii Nesterov (2026) 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-2603-21500.txt.
Introduction
Nesterov develops a new route to infeasible-start primal-dual methods for conic optimization. The approach grows out of Gordan's theorem of the alternative. Given only a target duality gap, he forms an auxiliary convex problem: minimize a barrier function under linear equality constraints. Its solution converts easily into the desired output. He analyzes two solvers for that problem, a damped Newton method and a short-step path-following scheme. Both get polynomial-time complexity proofs, and both can exploit hot starts.
Catalog record
| CREATOR | Yurii Nesterov |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 52966 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.21500
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Theorem of Alternative for Extended Homogeneous Linear System and its Application in Conic Optimization Yurii Nesterov Abstract In this paper, we develop a new framework for constructing infeasible-start primal-dual methods for Conic Optimization. Our approach can be seen as a straightforward consequence of Gordan Theorem of Alternative. Given by the target upper bound ϵ > 0 \epsilon>0 for the duality gap as the only input parameter, we form an auxiliary convex problem of minimizing barrier function with linear equality constraints. Its solution can be easily transformed to the requested output. This function can be minimized by different schemes of Unconstrained Optimization, with possible quadratic convergence in the end of the process. In our paper, we analyze the Damped Newton Method and a short-step path-following scheme. For both of them, we prove polynomial-time complexity results. Our methods are able to benefit from the hot-start opportunities. We can ensure the residual of the linear equality constraints in the primal and dual problems to be at the level of machine accuracy, independently on the accuracy parameter ϵ \epsilon . Keywords: Conic Optimization, Primal-Dual Problem, Interior-Point Methods, Self-Concordant Barriers, Infeasible-Start Methods. 1 Introduction Motivation. As it is widely recognized now, theorems of alternatives play an important role in Optimization Theory (e.g. [ 2 ] ). One of the first theorems of this type was proved in 1873 by Gordan [ 6 ] for homogeneous systems of linear inequalities coupled with a positive orthant. Later on in 1902, Farkas [ 4 ] published a non-homogeneous version of this result, which became one of the fundamentals of Convex Analysis (see [ 17 ] ). These theorems are usually applied to resolve some questions related to existence and boundedness of optimal sets of different optimization problems. Hence, in the more recent years, there are still publications proposing new variants of these results (e.g. [ 9 ] ) and finding new ways for their justifications (e.g. [ 10 ] ). Further developments are also focused on extensions of the initial theorems onto general nonlinear cones (e.g. [ 18 ] ). In this paper, we present a variant of Gordan Theorem for general cones, where a part of variables is free. As we will see, this is exactly the format suitable for development of Infeasible-Start primal-dual Interior-Point Methods (IPMs) for general convex cones. Such a development is the main goal of this paper. Infeasible start IPMs are the most powerful modern methods for solving the problems of Conic Optimization. They can start from an arbitrary interior point inside the convex cone and generate a sequence of iterates, for which both the duality gap and the residual in the primal-dual system of linear equality constraints are vanishing. For that, they introduce additional projective variables (one or two) and let the minimization sequence go to infinity. If the problem is feasible, then the projective variable goes to infinity too. The final output is obtained by dividing the current primal-dual point by one of the projective variables. This operation explains the main drawback of this approach: in the output, both the accuracy in function value and the residual of linear equality constraints are always of the same order. However, in many practical problems we do not need an extremely high accuracy in the function value. At the same time, very often, the linear constraints must be satisfied with the machine accuracy. Another drawback of these two approaches is impossibility to use the advantages of hot start. Even if our primal-dual starting point is close somehow to the solution, the global complexity bounds of these schemes remain unchanged. In our paper, we are going to address both these issues. In order to position properly our results, let us explain two existing homogenization approaches for constructing infeasible start IPMs (see [ 7 ] for reviewing other techniques). Both of them are applied to the following primal-dual pair of Conic Problems: \begin{array}[]{rcl}f^{*}&=&\min\limits_{x\in K}\{\langle c,x\rangle:\;Ax=b\}\;=\;\max\limits_{y\in\mathbb{E}_{y},\,s\in K^{*}}\{\langle b,y\rangle:\;s+A^{*}y=c\},\end{array} (1.1) where c\in\mathbb{E}^{*}_{x} , b\in\mathbb{E}^{*}_{y} , and A:\mathbb{E}_{x}\to\mathbb{E}_{y}^{*} (see Section 2 for notation). The optimal solution (x^{*},s^{*},y^{*}) is characterized by the following conditions: \begin{array}[]{rclrcl}s^{*}+A^{*}y^{*}&=&c,&Ax^{*}&=&b,\\ \\ \langle c,x^{*}\rangle-\langle b,y^{*}\rangle&=&0,&x&\in&K,\quad s\in K^{*}.\end{array} (1.2) In the first approach [ 11 ] , we introduce a single projective variable t\in\mathbb{R} and form the following shifted feasible set: {\cal F}_{1}=\left\{(x,s,y,t):\begin{array}[]{rclrcl}s+A^{*}y&=&\bar{s}+tc,&Ax&=&A\bar{x}+tb,\\ \langle c,x\rangle-\langle b,y\rangle&=&\langle c,\bar{x}\rangle,&x&\in&K,\quad s\in K^{*}\end{array}\right\}. (1.3) where \bar{x}\in{\rm int\,}K and \bar{s}\in{\rm int\,}K^{*} are the initial reference points in the primal-dual cone. It is clear that if (\hat{x},\hat{s},\hat{y},\hat{t}) is a recession direction of the set {\cal F} with \hat{t}>0 , then the point (\hat{x}/\hat{t},\hat{s}/\hat{t},\hat{y}/\hat{t}) satisfies conditions ( 1.2 ). On the other hand, it is well known that the recession directions of an unbounded convex set can be found by minimizing its self-concordant barrier. This simple observation leads to several infeasible-start IPMs [ 11 ] . All of them solve the following optimization problem: \inf\limits_{(x,s,y,t)\in{\cal F}_{1}}\Big\{F(x)+F_{*}(s)\Big\}. (1.4) The second approach is based on so-called self-dual embedding (see [ 19 ] for the initial version for Linear Optimization and [ 1 , 3 , 8 , 16 ] for further extensions). In this framework, in the case of general convex cones, it is necessary to find a recession direction of the following set [ 15 ] : \begin{array}[]{c}{\cal F}_{2}=\Big\{\{(x,s,y,t,\kappa):\;s+A^{*}y=\bar{s}+A^{*}\bar{y}-\bar{t}c+tc,\quad Ax=A\bar{x}-\bar{t}b+tb,\\ \langle c,x\rangle-\langle b,y\rangle+\kappa=\bar{\kappa}+\langle c,\bar{x}\rangle-\langle b,\bar{y}\rangle,\\ x\in K,\quad s\in K^{*},\quad t\geq 0,\quad\kappa\geq 0\Big\},\end{array} (1.5) where \bar{x}\in{\rm int\,}K , \bar{s}\in{\rm int\,}K^{*} , \bar{y}\in\mathbb{R}^{m} , \bar{t}>0 , and \bar{\kappa}>0 are the reference points in the corresponding sets. For finding this direction, we can solve the following minimization problem: \inf\limits_{(x,s,y,t,\kappa)\in{\cal F}_{2}}\Big\{F(x)+F_{*}(s)-\ln t-\ln\kappa\Big\}, (1.6) which is below unbounded provided that our initial problem ( 1.1 ) has nonempty interior. Same as for problem ( 1.4 ), the output is generated by dividing the last iterate by the projective variable t>0 . Hence, the accuracy in linear equality constraints is proportional to that of duality gap. Our approach can be seen as a mixture of these two approaches. We derive it from one fundamental fact in Convex Analysis, a version of Gordan Theorem of Alternative for extended linear systems and convex cones. Contents. The paper is organized as follows. In Section 2 , we introduce notation and present some general results used in the paper. In Section 3 , we prove a modified version of Gordan Theorem of Alternative for an extended system of linear equality constraints and a general convex cone. This theorem is used in Section 4 in order to derive a convex optimization problem ( 4.8 ) with equality constraints. Its solution can be transformed to a strictly feasible \epsilon -solution of the initial problem. In all our methods, accuracy \epsilon>0 plays a role of input parameter. In Section 5 , we analyze behavior of Damped Newton Method as applied to problem ( 4.8 ). For this method, we prove a polynomial-time complexity bound of the order O(\nu\ln{1\over\epsilon}) , where \nu is the parameter of self-concordant barrier for the feasible cone. In Section 6 , we analyze performance of a short-step path-following scheme. We show that it achieves the region of quadratic convergence in O(\nu^{1/2}\ln{1\over\epsilon}) iterations. In Section 7 , we show that our methods benefit from using a hot-start reference points. We finish the paper with Conclusion in Section 8 and Appendix in Section 9 , where