Multiconic Optimization for Symmetric Cones and Hyperbolic Coupling

Marianna E.-Nagy, Yurii Nesterov, Petra Renáta Rigó · 2026

Read Multiconic Optimization for Symmetric Cones and Hyperbolic Coupling by Marianna E.-Nagy, Yurii Nesterov, Petra Renáta Rigó (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-2605-12658.txt.

Introduction

Nagy, Nesterov and Rigó develop a new algorithm for multiconic optimisation using the parabolic target approach. The cone is a direct product of many small cones. Their approach rests on hyperbolic coupling, giving linked primal-dual pairs whose conduct is much more tame. They justify all main steps in the cost analysis and prove overall cost like the best known cost for linear programs of the same size.

Catalog record

CREATORMarianna E.-Nagy, Yurii Nesterov, Petra Renáta Rigó
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE87447
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.12658

Browse the full library · About the Tower of Babel

Full text

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

Multiconic Optimization for Symmetric Cones and Hyperbolic Coupling Marianna E.-Nagy, Yurii Nesterov, Petra Renáta Rigó Abstract Abstract. We develop a new interior-point algorithm for solving multiconic optimization problems using the parabolic target space approach. The feasible cone in these problems is composed as a direct product of many small-dimensional cones. Our approach is based on a new concept, called the hyperbolic coupling. This provides a new framework that has an advantage of interdependent pairs of primal-dual variables. In this way, their behaviour is much more controllable. We justify all main steps in the complexity analysis of the algorithm and prove that the overall complexity of solving this type of large-scale nonlinear problems by our algorithm is comparable with the best known complexity for solving linear programming problems of the same dimension. Keywords. Multiconic optimization, hyperbolic coupling, interior-point algorithm, functional proximity measure. MSC Classification. 90C51 1 Introduction The development of interior-point algorithms (IPAs) for linear programming (LP) originated with the seminal work of Karmarkar [ 7 ] , who introduced a novel projective method. Later on, several IPAs have been published for different classes of problems, see from [ 9 , 13 , 15 ] . The most important results related to IPAs are summarized in the monographs of Roos et al. [ 16 ] and Ye [ 17 ] . In multiconic optimization, we consider a direct product of small-dimensional symmetric cones. Hence, LP is a special case of multiconic optimization, where all cones are one-dimensional. Multiconic optimization often arises in practical applications, see [ 8 ] . Note that in 2016, the horizontal linear complementarity problem over Cartesian product of symmetric cones has been introduced by Asadi et al. [ 2 ] . Later on, several IPAs have been proposed for solving these types of problems, see [ 1 , 3 ] . Nesterov and Nemirovskii [ 18 ] introduced the framework of self-concordant functions, which is a key element to extend several classes of IPAs from LP to nonlinear settings. Nesterov and Todd [ 11 , 12 ] provided a theoretical foundation for the study of efficient IPAs for problems that are extensions of LP. They considered self-scaled cones, which include as special cases the cone of positive semidefinite matrices, the second-order cone, and the nonnegative orthant. Güler [ 6 ] showed that the family of self-scaled cones is identical to the symmetric cones. Nesterov [ 19 ] introduced the so-called parabolic target space (PTS) approach for LP, which can start at an arbitrary strictly feasible solution. He embedded the problem into a higher-dimensional one and introduced modeling variables according to the PTS. The proposed method is based on a parabolic barrier function, which plays a key role in the algorithm. In [ 4 ] , we extended this IPA for weighted monotone LCPs. In [ 5 ] , we proposed a new PTS IPA for LP problems based on a new direction, called the universal tangent direction. In [ 14 ] , Nesterov showed that the IPA presented in [ 5 ] has favorable local behavior under some non-degeneracy assumptions. In this paper, we propose a new IPA in the PTS framework for solving multiconic optimization problems. We introduce a new concept, called hyperbolic coupling . This gives a new framework, which has an advantage that the primal-dual variables are interdependent between the cones. In this way, their behaviour is much more controllable. We also propose the new inequality ( 2.13 ), which plays a key role in the complexity analysis of the new IPA. The paper is organized as follows. In Section 2 we present the notations used in the paper, and give the definition of the self-concordant functions and barriers, respectively. Section 3 presents the theory of self-scaled barriers, while Section 4 contains the new concept of hyperbolic coupling. In Section 5 we present the multiconic optimization problem [ 10 ] and the new PTS approach. In Section 6 we show how the search directions are computed in the new algorithm. Section 7 presents the functional proximity measure and the main parts of the complexity analysis of the algorithm. In Section 8 we present the strategy for choosing the initial point. After that, the concluding remarks and further research topics are presented. In Appendix, we show how to compute the scaling point for the Lorentz cone, which seems to be absent in the literature. 2 Notations and Generalities Let \mathbb{E} be a finite-dimensional space and \mathbb{E}^{*} be the space of linear functions on \mathbb{E} . For x\in\mathbb{E} and s\in\mathbb{E}^{*} , denote by \langle s,x\rangle the value of function s at x . We use the same notation \langle\cdot,\cdot\rangle for different spaces. Thus, its actual meaning is defined by the context. For a linear operator A:\mathbb{E}_{1}\to\mathbb{E}^{*}_{2} , we denote by A^{*} its adjoint operator : \langle Ax,y\rangle=\langle A^{*}y,x\rangle,\quad x\in\mathbb{E}_{1},\;y\in\mathbb{E}_{2}. Thus, A^{*}:\mathbb{E}_{2}\to\mathbb{E}_{1}^{*} . The operator A:\mathbb{E}\to\mathbb{E}^{*} is positive semidefinite (notation A\succeq 0 ) if \langle Ax,x\rangle\geq 0 for all x\in\mathbb{E} . We write A\succeq B if A-B\succeq 0 . In case of \mathbb{E}=\mathbb{R}^{n} , we have \mathbb{E}^{*}=\mathbb{R}^{n} and \langle s,x\rangle\;=\;\sum\limits_{i=1}^{n}s^{(i)}x^{(i)},\quad\|x\|\;\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\;\langle x,x\rangle^{1/2},\quad s,x\in\mathbb{R}^{n}. Vector e\in\mathbb{R}^{n} is the vector of all ones, and e_{i} , i=1,\dots,n , are coordinate vectors in \mathbb{R}^{n} . For function f(\cdot) with open domain {\rm dom\,}f\subseteq\mathbb{E} , we denote by \begin{array}[]{rcl}D^{k}f(x)[h_{1},\dots,h_{k}],\quad x\in{\rm dom\,}f,\;h_{i}\in\mathbb{E},\;i=1,\dots,k,\end{array} its k th directional derivative at x along k directions. It is a symmetric k -linear form. If all directions are the same, we use notation D^{k}f(x)[h]^{k} . Thus, under the mild assumptions, for the gradient and the Hessian of function f(\cdot) , we have the following relations: \begin{array}[]{rcl}Df(x)[h]&=&\langle\nabla f(x),h\rangle,\quad D^{2}f(x)[h]^{2}\;=\;\langle\nabla^{2}f(x)h,h\rangle.\end{array} Using the third derivative, we can define the following objects: \displaystyle D^{3}f(x)[h_{1},h_{2},h_{3}] \displaystyle\equiv \displaystyle\langle D^{3}f(x)[h_{1},h_{2}],h_{3}\rangle (2.1) \displaystyle\equiv \displaystyle\langle D^{3}f(x)[h_{1}]h_{2},h_{3}\rangle,\quad h_{1},h_{2},h_{3}\in\mathbb{E}. Thus, D^{3}f(x)[h_{1},h_{2}]\in\mathbb{E}^{*} and D^{3}f(x)[h_{1}] is a self-adjoint linear operator from \mathbb{E} to \mathbb{E}^{*} . Note that D^{3}f(x)[h_{1},h_{2}]=D^{3}f(x)[h_{1}]h_{2},\quad h_{1},h_{2}\in\mathbb{E}. Self-concordant functions Let us recall some facts from the theory of self-concordant functions (e.g. [ 20 , 18 ] ). Definition 2.1 . Let a closed convex function f\in{\cal C}^{3}(\mathbb{E}) have an open domain. It is called self-concordant (SCF) if its third directional derivative is bounded by an appropriate power of the second one: \begin{array}[]{rcl}D^{3}f(x)[h]^{3}&\leq&2\Big(D^{2}f(x)[h]^{2}\Big)^{3/2},\quad x\in{\rm dom\,}f,\;h\in\mathbb{E}.\end{array} (2.2) If {\rm dom\,}f contains no straight line, then its Hessian is positive definite at any x\in{\rm dom\,}f . In this paper, we mainly deal with such functions. However, {\rm dom\,}f still can be unbounded. In this case, the following relation is important: \langle\nabla^{2}f(x)d,d\rangle^{1/2}\leq-\langle\nabla f(x),d\rangle for any x\in{\rm int\,}{\rm dom\,}f and any recession direction d of the set {\rm dom\,}f . The dual function f_{*}(s)=\max\limits_{x\in{\rm dom\,}f}[-\langle s,x\rangle-f(x)] for any SCF is also self-concordant. Note that -\nabla f(x)\in{\rm dom\,}f_{*} for all x\in{\rm dom\,}f , and \begin{array}[]{rcl}\nabla f_{*}(s)&=&-x(s)\;\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\;-\arg\max\limits_{x\in{\rm dom\,}f}[-\langle s,x\rangle-f(x)],\quad s\in{\rm dom\,}f_{*}.\end{array} For any x\in{\rm dom\,}f and s\in{\rm dom\,}f_{*} , we have \displaystyle f(-\nabla f_{*}(s)) \displaystyle=\langle s,\nabla f_{*}(s)\rangle-f_{*}(s), \displaystyle f_{*}(-\nabla f(x)) \displaystyle=\langle\nabla f(x),x\rangle-f(x), \displaystyle\nabla f(-\nabla f_{*}(s)) \displaystyle=-s, \displaystyle\nabla f_{*}(-\nabla f(x)) \displaystyle=-x, (2.3) \displaystyle\nabla^{2}f(-\nabla f_{*}(s)) \displaystyle=[\nabla^{2}f_{*}(s)]^{-1}, \displaystyle\nabla^{2}f_{*}(-\nabla f(x)) \displaystyle=[\nabla^{2}f(x)]^{-1}. One of the main properties of SCF is that the Dikin Ellipsoid defined as \begin{array}[]{rcl}W^{f}_{r}(x)&=&\{y\in\mathbb{E}:\;\langle\nabla^{2}f(x)(y-x),y-x\rangle\leq r^{2}\},\quad x\in{\rm dom\,}f,\end{array} belongs to {\rm dom\,}f for any r\in[0,1) . In this paper, we often use the local norms defined by the Hessians of SCF. For x\in{\rm dom\,}f , s\in{\rm dom\,}f_{*} , u\in\mathbb{E}

Read the complete text