Theorem 2. Suppose Assumption 1 holds. Recall the definition of \(r(\mu)\) from ?? . Then, 1 terminates after at most \[\begin{align} K \le 1 + \frac{\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_1) -\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} ^\star}{C\gamma\mu} \left( \frac{8 L_G^{2/3}}{(1 - C)^{2/3} \eta_1^{4/3}}{} \mu^{-2/3} + r(\mu) \right) \end{align}\] iterations with a \(\mu\)-approximate first-order SIP, i.e., 1 holds.
An adaptive interior-point method with backtracking line search for convex constrained optimization
July 14, 2026
Abstract
Interior-point methods (IPMs) are widely adopted due to their high practical efficiency in solving linear, convex, and nonconvex optimization problems. For convex optimization, this performance is theoretically well-supported: there are strong complexity guarantees for self-concordant barrier setups [1], which cover linear and conic optimization. On the other hand, unconstrained convex optimization is well-studied. However, there is limited analysis of constrained convex optimization methods without the self-concordance assumption. We develop and analyze a regularized Newton method with line search applied to the log barrier function in the setting that the objective and constraints are thrice differentiable and have Lipschitz continuous first and second derivatives. Starting from a strictly feasible point, our method finds an \(\epsilon\)-approximately optimal solution in \(\tilde{O}(\epsilon^{-2/3})\) iterations.
1 Introduction↩︎
This paper studies the constrained convex optimization problem \[\begin{align} \label{eq:optimization-constrained-problem} \min_{x \in \mathcal{X}}{~f(x)} \text{ where } \mathcal{X}:= \{ x \in {\boldsymbol{R}}^{n} : a(x) \ge \mathbf{0}\} \end{align}\tag{1}\] where \(f: \mathbf{R}^{n} \rightarrow \mathbf{R}\) is convex, and \(a: \mathbf{R}^{n} \rightarrow \mathbf{R}^{q}\) is concave. We assume that both functions are thrice differentiable with Lipschitz continuous first and second derivatives. Additionally, we assume Slater’s condition holds, i.e., there exists a strictly feasible point \(x_1\) such that \(a(x_1) > \mathbf{0}\), which we use as the starting point of our algorithm. Under these assumptions, we aim to find an approximately optimal solution, i.e., a point \(\tilde{x}\) such that \[f(\tilde{x}) \le \epsilon + \min_{x \in \mathcal{X}}{~f(x)}\] for some small \(\epsilon > 0\). To solve this problem, we move the constraints into the objective by using a log barrier function: \[\begin{align} \label{barrier-problem} \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x) := f(x) - \mu \sum_{i=1}^{q} \log(a_i(x)) \end{align}\tag{2}\] where the barrier parameter \(\mu\) is positive. This transforms the constrained optimization problem 1 into an unconstrained problem 2 , allowing us to use methods from unconstrained optimization such as damped Newton’s method [1]. More specifically, we employ a regularized Newton method with line search, i.e., \[x_{k+1} = x_{k} + \alpha_k d^{x}_k\] where \(\delta_k\) is a carefully selected regularization parameter, \(d^{x}_k := -(\grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) + \delta_k \boldsymbol{I})^{-1} \grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k)\) is the regularized Newton direction, and \(\alpha_k \in [0,1]\) is the step size, e.g., selected via a backtracking line search. This is a popular practical strategy for solving constrained nonlinear optimization problems [2], [3] (also, see [4]). However, there are no known worst-case complexity bounds for this type of method.
A natural approach would be to apply standard trust-region or cubic regularization methods to solve this problem [5]–[8]. Unfortunately, these methods require that the Hessian is Lipschitz continuous. However, the Hessian of the log barrier is not Lipschitz continuous. Moreover, even if we only require that the Hessian of the log barrier is Lipschitz continuous on the initial level set, \(\{ x \in \mathcal{X}: \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x) \le \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_1) \}\), the corresponding Lipschitz constant can grow exponentially with the inverse of the barrier parameter \(\mu\), leading to extraordinarily large worst-case iteration bounds [9].
1.0.0.1 Our contributions:
We provide the first worst-case bound for regularized Newton with line search on log barriers for general convex constrained optimization problems. To prove this result we develop a new proof technique based by carefully constructing a dynamic lower bound on our method’s step size.
We establish an \(\tilde{O}(\epsilon^{-2/3})\) bound on the number of iterations of our method.
Despite its simplicity, our method shows strong potential in preliminary comparisons with IPOPT [3], a state-of-the-art interior point method.
Our techniques build on ideas from [10], which provides an algorithm that, while impractical because it requires knowledge of problem parameters such as the Lipschitz constant, provides an \(O(\mu^{-7/4})\) iteration bound for log barrier methods on general nonconvex constrained optimization problems to find \(\mu\)-approximate KKT points.
1.1 Related work↩︎
1.1.0.1 Second-order methods for unconstrained convex optimization with Lipschitz assumptions.
While this paper is unique because it develops an implementable and adaptive second-order method for constrained convex optimization with Lipschitz continuous derivatives, there is a substantial line of work for unconstrained convex optimization under such assumptions. The cubically regularized Newton method of [5] established the first global complexity bounds in this setting under Lipschitz continuity of the Hessian, achieving an \(O(1/k^2)\) rate for convex problems, which was subsequently accelerated to \(O(1/k^3)\) by [11]. [12] proposed the accelerated hybrid proximal extragradient (A-HPE) framework and a corresponding accelerated Newton proximal extragradient (A-NPE) method with an improved \(\tilde{O}(1/k^{7/2})\) rate, which was later shown to be optimal up to logarithmic factors by the lower bounds of [13] and [14]. Lipschitz continuity of higher derivatives was exploited by [15] to obtain an \(O(1/k^4)\) convergence rate. More recently, [16] develop an adaptive regularized Newton method for convex optimization with excellent practical performance.
1.1.0.2 Worst-case guarantees for general constrained convex optimization via variational inequalities.
One technique for solving general convex optimization problems is to reformulate the problem in terms of the optimality conditions and use variational inequality methods to solve them [17]. Under the assumption that the gradient is Lipschitz, mirror-prox uses a first-order oracle to obtain an \(O(\epsilon^{-1})\) convergence rate [18]. Under the assumption of Lipschitz continuous Hessians, [19] introduced a Newton proximal extragradient method and obtained a \(\tilde{O}(\epsilon^{-2/3})\) iteration complexity for monotone variational inequalities. This \(\tilde{O}(\epsilon^{-2/3})\) rate has since been recovered by a number of more recent methods [20]–[23]; [23] also provide matching upper and lower bounds showing that \(O(\epsilon^{-2/3})\) is the optimal oracle complexity. A key caveat is that these are oracle rates. In particular, each iteration involves finding an approximate solution of a variational inequality derived from a second-order Taylor model. Solving these subproblems reduces to a few linear system solves in the unconstrained setting but once even simple constraints such as the nonnegative orthant are imposed, this subproblem becomes more expensive. For example, the subproblem of [19] reduces to a monotone linear complementarity problem, which can be solved by interior point methods [24], [25] at higher expense than a linear system solve. Our work obtains a similar \(\tilde{O}(\epsilon^{-2/3})\) rate2 for general constrained convex problems but with cheaper and more practical iterations: each iteration of our method only requires a logarithmic number of linear system solves and evaluations of \(\mathcal{L}\), \(\grad \mathcal{L}\), and \(\grad^2 \mathcal{L}\), where \(\mathcal{L}(x,y) := f(x) - y^\top a(x)\) is the Lagrangian.
1.1.0.3 Interior-point methods
Interior-point methods (IPMs) are a very popular second-order method to solve constrained optimization problems, including in linear, conic, convex, and nonconvex settings [3], [26]–[33]. The main theoretical complexity result in the convex setting for IPMs states that they require \(O(\sqrt{c}\log(1/\epsilon))\) iterations to find an \(\epsilon\)-global minimum [1], where \(c\) is the self-concordance parameter of the barrier function and \(\epsilon\) stands for the desired accuracy or duality gap. However, this theoretical foundation is restrictive: for general nonlinear convex problems the log barrier is not self-concordant and, while the universal barrier exists for arbitrary convex bodies, it is computationally intractable [1], [34].
1.1.0.4 Quasi-self-concordance
Quasi-self-concordance is a variant of classical self-concordance introduced by [35] in the context of logistic regression. Within this class, [36] obtain accelerated rates via a ball optimization oracle, and [37] show that gradient-regularized Newton methods can also obtain similar rates. While this structure is well-suited to certain machine learning problems, it cannot accommodate barrier functions such as \(-\log(x)\), whose curvature diverges at the boundary, and is therefore not applicable to interior point methods for general constrained problems.
1.1.0.5 Adaptive second-order methods for nonconvex optimization
While this paper is focused on developing an adaptive method for convex optimization, there is a large body of work studying adaptive methods for nonconvex optimization both in the unconstrained [6]–[8], [38], [39] and constrained settings [40]–[42]. However, [10] is the only paper studying log barrier methods with general (nonconvex) constraints, but it requires knowledge of problem parameters such as the Lipschitz constant, making it nonadaptive and impractical.
1.2 Outline and notation↩︎
1.2.0.1 Outline
The paper is structured as follows. In 2, we introduce and analyze our adaptive line search method for minimizing the log barrier with a fixed barrier parameter showing that it can find a \(\mu\)-approximate stationary interior point in \(O(\mu^{-5/3})\) iterations; proving this result involves developing a novel proof technique that reasons about the minimum step size thresholds relative to the predicted reduction in the log barrier for a unit regularized Newton step. In 3 we apply a standard scheme for annealing the barrier parameter to our method from 2, yielding our main result, which collapses our \(O(\mu^{-5/3})\) iteration bound into a \(O(\epsilon^{-2/3})\) iteration bound for finding an \(\epsilon\)-approximately optimal solution. In 4, we provide the numerical results. Finally, 5 provides a discussion.
1.2.0.2 Notation
Let \(\mathbf{N}\) be the set of natural numbers (starting from one), \(\boldsymbol{I}\) be the identity matrix, \(\mathbf{R}\) be the set of real numbers, and \(\mathbf{R}_{+}\) be the set of nonnegative real numbers. Let \(\mathop{\boldsymbol{d}iag}(v)\) be a diagonal matrix with entries composed of the vector \(v\). Let \(CONVEX\{u, v\} = \{\theta u + (1-\theta) v : \theta \in [0, 1]\}\). Let \(\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} ^{\star} := \inf_{x \in \mathcal{X}} \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x)\), and \(f_{\star} := \inf_{x \in \mathcal{X}} f(x)\). Unless otherwise specified, \(\log(\cdot)\) is the natural logarithm. Let \(\mathbf{interior}(\mathcal{X}) := \{ x \in \mathbf{R}^{n} : a(x) > \mathbf{0}\}\). Let \(\mathbf{diam}(\mathcal{X}) = \sup_{u,v \in \mathcal{X}} \| u - v \|_2\).
2 A log barrier method with fixed barrier parameter↩︎
In this section, we detail our adaptive line search log barrier method (1). To compute the next iterate \(x_{k+1}\), we first carefully select a regularized Newton search direction \(d^{x}_k\) (Condition 1), and then determine a step size \(\alpha_k \in (0, 1]\) via a line search (Condition 2).
To generate the search direction, we consider the second-order Taylor series approximation of the function at the current iterate: \[\begin{align} \label{eq:newton-direction-IPM-unconstrained} \mathcal{M}_k(d) := \grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k)^\top d + \frac{1}{2} d^\top \grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) d. \end{align}\tag{3}\] When generating our search direction, instead of taking a full Newton step and minimizing 3 , we take a regularized Newton step: \[\begin{align} d^{x}_k := -(\grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) + \delta_k \boldsymbol{I})^{-1} \grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k). \end{align}\] We require our search direction \(d^{x}_k\) to satisfy Condition 1. For brevity, we denote \(M_k= \mathcal{M}_k(d^{x}_k)\).
Condition 1. Let \(\eta_1\) and \(\eta_2\) be problem-independent constants with \(\eta_1 \in (0, 1/2)\) and \(\eta_2 \in (\eta_1, 1/2)\). Let \(\varepsilon_k > 0\) be a sequence of scalars with \(\| \grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) \|_2 > \varepsilon_k\). The search direction \(d^{x}_k\) and regularization parameter \(\delta_k \ge 0\) satisfy \[\begin{align} (\grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) + \delta_k \boldsymbol{I}) d^{x}_k =& -\grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) \label{eq:search-direction} \\ \eta_1 \le & ~\frac{-M_k}{\varepsilon_k \|d^{x}_k\|_2} \label{eq:direction-condition-eta1} \\ \text{either }\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k + d^{x}_k) > \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) + C\cdot M_k, ~\text{ or }~ &\frac{\| d^{x}_k \|_2 \delta_k}{2 \varepsilon_k} \le \eta_2 \label{eq:direction-condition-eta2} \end{align}\] {#eq: sublabel=eq:eq:search-direction,eq:eq:direction-condition-eta1,eq:eq:direction-condition-eta2} where \(\varepsilon_k := \mu \sqrt{1 + \| y_k \|_1}\).
In 7 we show it is always possible to satisfy Condition 1 with at most \[O\left( 1 +\log_2\log_2 \left(\frac{\| \grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) \|_2}{\tilde{\delta}} + \frac{\tilde{\delta}(\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) - \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} ^\star)}{C\varepsilon_k^2} \right) \right)\] factorizations and function evaluations where \(\tilde{\delta}\) is some initial estimate of the regularization parameter. The key idea is that it suffices to find a regularizer \(\delta\) such that \[\begin{align} \label{eq:bisection-scheme} \phi_k(\delta) \in [\eta_1, \eta_2] \text{ where } \phi_k(\delta) := \varepsilon_k^{-1} \delta \| (\grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) + \delta \boldsymbol{I})^{-1} \grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) \| . \end{align}\tag{4}\] We find such a regularizer by applying a bisection search to \(\phi_k\) on a log-scale. To find a search interval for the bisection routine we devise a simple doubling scheme on a log-scale that leverages several important facts we can prove about \(\phi_k\), for all \(\delta > 0\): \((i)\) for \(\delta' \ge \delta\), \(\phi_k(\delta) \le \phi_k(\delta')\) and \(\delta \phi_k(\delta') \le \delta' \phi_k(\delta)\), \((ii)\) for \(\delta \ge \frac{\eta_1}{1 - \eta_1} \| \grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) \|_2\) we have \(\phi_k(\delta) \ge \eta_1\), \((iii)\) for \(\delta \le \eta_2^2 C\varepsilon_k^2 (\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) - \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} ^\star)^{-1}\) we have \(\phi_k(\delta) \le \eta_2\) or \(\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k + d(\delta)) > \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) + C\mathcal{M}_k(d(\delta))\). These facts allow us not only to efficiently find an initial interval but that the endpoint of the interval will be sufficiently close for the bisection search to be efficient.
Given a search direction satisfying Condition 1, we now find a step size such that the sufficient decrease condition holds but for larger step size it fails (Condition 2). There are many line search methods that one could use to satisfy such a condition but the particular method we use in our implementation is a variant of the standard backtracking method. See Appendix 8 for details and guarantees on the number of function evaluations of this routine.
Condition 2 (Step size condition). Let \(C\in (0, 1/2)\) and \(\gamma\in (0, 1)\) be problem-independent constants. Suppose that \(\alpha_k \in (0,1]\) provides sufficient objective reduction, i.e., \[\begin{align}\label{eq:sufficient-decrease} \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k + \alpha_k d^{x}_k) \leq \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) + C\cdot \mathcal{M}_k(\alpha_k d^{x}_k) \end{align} and either \alpha_k = 1 or the larger step size \hat{\alpha}_k = \min\{1, \alpha_k / \gamma\} has insufficient objective reduction, i.e., \begin{align}\label{eq:sufficient-decrease-fails-for-larger-step-size} \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k + \hat{\alpha}_k d^{x}_k) > \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) + C\cdot \mathcal{M}_k(\hat{\alpha}_k d^{x}_k). \end{align}\] {#eq: sublabel=eq:eq:sufficient-decrease,eq:eq:sufficient-decrease-fails-for-larger-step-size}
Similar to the termination criteria in [10], we consider 1 converged when it reaches an approximate first-order stationary interior point (SIP). Note that Definition 2 of [10] also includes terms \(\tau_l\) and \(\tau_c\) to trade the tolerance of the complementarity conditions and duality gap, we omit these for simplicity.
Definition 1. [10]A \(\mu\)-approximate first-order stationary interior point (SIP) is a point \((x, y)\) defined by \[\begin{align} (a(x), y) &> \mathbf{0} \label{eq:first-order-SIP-full:feasible} \\ \abs{y_i a_i(x) - \mu} &\le \frac{\mu}{2} \quad \forall i \in [ q] \label{eq:first-order-SIP-full:centrality} \\ \norm{\grad_{x} \mathcal{L}(x,y) }_{2} &\le \mu \sqrt{\norm{y}_{1} + 1} \label{eq:first-order-SIP-full:grad-lag}. \end{align}\] {#eq: sublabel=eq:eq:first-order-SIP-full:feasible,eq:eq:first-order-SIP-full:centrality,eq:eq:first-order-SIP-full:grad-lag}
While our method is a log barrier method, we do use a dual variable for termination. We either use \(y_k\) (Termination check I) or \(\hat{y}_{k+1}\) (Termination check II) where \[\tag{5} \begin{align} &s_k := a(x_k), \quad y_k := \mu S_k^{-1} \mathbf{1}, \quad S_k := \mathop{\boldsymbol{d}iag}(s_k), \quad Y_k = \mathop{\boldsymbol{d}iag}(y_k) \\ &d^{s}_k := \grad a(x_k) d^{x}_k, \quad d^{y}_k :=-Y_k S_k^{-1} d^{s}_k \\ &\hat{y}_{k+1} := y_k + d^{y}_k. \tag{6} \end{align}\] Note that \(y_k=\mu S_k^{-1}\mathbf{1}\) is the standard dual multiplier estimate induced by the log-barrier KKT conditions, since the barrier stationarity conditions imply \(Sy=\mu\mathbf{1}\) [4]. The search directions given in 5 satisfy the classical linear system for computing the search directions of primal-dual interior point methods [4]: \[\label{eq:primal-dual-interior-point-search-direction} \begin{align} (\grad_{xx}^2 \mathcal{L}(x_k,y_k) + \delta_k \boldsymbol{I}) d^{x}_k - \grad a(x_k)^\top d^{y}_k &= -\grad_x \mathcal{L}(x_k,y_k) \\ \grad a(x_k) d^{x}_k - d^{s}_k &= \mathbf{0}\\ S_k d^{y}_k + Y_k d^{s}_k &= \mu \mathbf{1}- S_k y_k . \end{align}\tag{7}\] These two termination checks play different roles. Termination check I is equivalent to checking if \(\| \grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) \| \le \varepsilon_k\) and is needed to establish that \(\| \grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) \| > \varepsilon_k\) so we can satisfy Condition 1; on the other hand, termination check II is used in our convergence analysis to establish that the algorithm always reduces the log barrier or terminates.
We will use 1, which is a well-known fact about convex functions, in our analysis.
Fact 1 (Well-known). If \(\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}}\) is convex and \(d^{x}_k\) satisfies ?? with \(\delta_k \ge 0\), then for all \(\alpha \in [0,1]\), \(\mathcal{M}_k(\alpha d^{x}_k) \le \alpha \mathcal{M}_k(d^{x}_k) \le \frac{1}{2}\mathcal{M}_k( \alpha d^{x}_k)\).
Proof. By convexity we have \(\mathcal{M}_k(\alpha d^{x}_k) = \alpha \grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k)^\top d^{x}_k + \frac{\alpha^2}{2} (d^{x}_k)^\top \grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) d^{x}_k \le \alpha \grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k)^\top d^{x}_k + \frac{\alpha}{2} (d^{x}_k)^\top \grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) d^{x}_k = \alpha \mathcal{M}_k(d^{x}_k)\). Moreover, \(\grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k)^\top d^{x}_k = - (d^{x}_k)^\top \grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) d^{x}_k - \delta_k \|d^{x}_k\|^2\). Thus, \(\frac{1}{2}\mathcal{M}_k(\alpha d^{x}_k)-\alpha\mathcal{M}_k(d^{x}_k) = \frac{\alpha\delta_k}{2}\|d^{x}_k\|^2+\frac{\alpha^2}{4} (d^{x}_k)^\top \grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k)d^{x}_k \ge 0\) where the inequality uses \(\delta_k\ge 0\) and convexity of \(\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}}\). ◻
2.1 A warm-up: analysis for unconstrained convex optimization↩︎
This section analyzes 1 in the unconstrained setting. We obtain slightly stronger results in this special setting than we do in 2.3 which analyzes the constrained setting. This section also serves as a “warm-up” to exhibit the basic idea of our minimum step size threshold proof technique before proceeding to the more technically involved constrained setting analyzed in 2.3. Dropping the constraints from 1 gives \(\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} = f\) and therefore the problem is simply to find a stationary point of \(f\). Moreover, in the absence of constraints, the norm of dual variables in the formula \(\varepsilon_k =\mu\sqrt{1+\|y_k\|_1}\) is set to zero, i.e., \(\varepsilon_k =\mu\). For our analysis, we will assume that the Hessian of \(f\) is \(L_H\)-Lipschitz. A well-known fact [5] that we will find useful is that, if the Hessian of \(f\) is \(L_H\)-Lipschitz, then \[\begin{align} \| \grad f(x_k+d^{x}_k) \|_2 &\le \| \grad \mathcal{M}_k(d^{x}_k) \|_2 + \frac{L_H}{2} \| d^{x}_k \|_2^2 \tag{8}\\ f(x_k + \alpha d^{x}_k) &\le f(x_k) + \mathcal{M}_k(\alpha d^{x}_k) + \frac{L_H\alpha^3}{6} \| d^{x}_k \|_2^3 \quad \forall \alpha \in [0,1] \tag{9} \end{align}\] for some \(L_H\in (0,\infty)\).
2.1.0.1 Minimum step size threshold.
Our proof revolves around the following minimum step size threshold, \[\begin{align} \underaccent{\bar}{\alpha}_{k} := \sqrt{\frac{\eta_1^2 \mu^{3} \min\{6 (1 - C) \eta_1, 2(1-2\eta_2) \}}{L_H(-M_k)^2}}. \label{alpha-min-def-IPM-unconstrained} \end{align}\tag{10}\] Our proof strategy is as follows. First, in 1 we show that any step size below this threshold will trigger the sufficient decrease condition (?? ), allowing us to conclude that if \(\underaccent{\bar}{\alpha}_{k} \ge 1\) then \(\alpha_k=1\) and if \(\underaccent{\bar}{\alpha}_{k} < 1\) then \(\alpha_k \ge \gamma\cdot \underaccent{\bar}{\alpha}_{k}\). For iterations where \(\underaccent{\bar}{\alpha}_{k} < 1\), 2 uses the sufficient decrease condition to show the function value reduction per iteration is at least \(-\alpha_{k} CM_k\ge -\gamma\underaccent{\bar}{\alpha}_{k} CM_k= \Omega(\mu^{3/2})\). Finally, in 3 we show if \(\underaccent{\bar}{\alpha}_{k} \ge 1\) then the algorithm terminates on iteration \(k\). From here, 1 uses a standard argument to obtain an \(O(\mu^{-3/2})\) bound on the number of iterations of the method.
We emphasize this proof technique differs from the standard analysis of adaptive second-order methods [6]–[8], [43], [44]. Standard methods control the norm of the search direction, i.e., \(\| d^{x}_k \|_2\) using either regularization or a trust region radius, and ensure sufficient function value reduction at accepted iterates. In contrast, our method does not directly control the size of the search direction and relies on a line search to ensure sufficient progress at each iteration. Thus, it is more natural for us to lower bound the search direction size.
Lemma 1. Suppose that the problem is unconstrained, i.e., \(\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x) = f(x)\) and \(\grad^2 f\) is \(L_H\)-Lipschitz. Then, if \(\underaccent{\bar}{\alpha}_{k} \ge 1\) then \(\alpha_k=1\) and if \(\underaccent{\bar}{\alpha}_{k} < 1\) then \(\alpha_k \ge \gamma\cdot \underaccent{\bar}{\alpha}_{k}\).
Proof. Suppose that \(\alpha \in (0,1]\) satisfies \(\alpha \leq \underaccent{\bar}{\alpha}_{k}\). Then, \[\frac{\alpha^3 L_H\|d^{x}_k\|_2 ^ 3}{6} \le \frac{\alpha \underaccent{\bar}{\alpha}_{k}^2 L_H\|d^{x}_k\|_2 ^ 3}{6} \underset{(a)}{\le} \alpha \frac{L_H\underaccent{\bar}{\alpha}_{k}^2 (\eta_1 \mu)^{-3} (-M_k)^3}{6} \underset{(b)}{\le} (1- C) \alpha (-M_k) \underset{(c)}{\le} (1 - C) (-\mathcal{M}_k( \alpha d^{x}_k))\] where \((a)\) uses ?? , \((b)\) uses 10 , and \((c)\) uses 1. Combining this inequality with 9 it follows that \[f(x_k + \alpha d^{x}_k) - f(x_k) \le \mathcal{M}_k(\alpha d^{x}_k) + \frac{\alpha ^ 3L_H}{6} \| d^{x}_k \|_2^3 \le C\cdot \mathcal{M}_k(\alpha d^{x}_k),\] i.e., the sufficient progress condition (?? ) holds. We conclude that \(\alpha \in (0,1]\) and \(\alpha \leq \underaccent{\bar}{\alpha}_{k}\) implies ?? holds.
This conclusion allows us to deduce the desired result. If \(\underaccent{\bar}{\alpha}_{k}\ge 1\), then the step size \(\alpha=1\) satisfies Condition 2, and so \(\alpha_k=1\). If \(\underaccent{\bar}{\alpha}_{k}<1\), then \(\alpha_k \ge \gamma\underaccent{\bar}{\alpha}_{k}\); otherwise \(\alpha = \alpha_k/\gamma<\underaccent{\bar}{\alpha}_{k}\) would also satisfy ?? , contradicting the second part of Condition 2. ◻
Lemma 2. Suppose that the problem is unconstrained, i.e., \(\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x) = f(x)\) and \(\grad^2 f\) is \(L_H\)-Lipschitz. If \(\underaccent{\bar}{\alpha}_{k} < 1\) then \[\begin{align} f(x_k) - f(x_{k+1}) \geq \hat{C} \cdot L_H^{-1/2} \mu^{3/2} \end{align}\] where \(\hat{C} := \gamma C\eta_1 \cdot \min\{ \sqrt{6(1- C) \eta_1} , \sqrt{2(1-2\eta_2)}\}\) is a problem-independent constant.
Proof. By \((a)\) equation ?? and 1, \((b)\), 1 with \(\underaccent{\bar}{\alpha}_{k} < 1\), we get \[\begin{align} f(x_k) - f(x_{k+1}) &\underset{(a)}{\ge} -C\cdot \alpha_{k} M_k \underset{(b)}{\ge} -\gamma C\underaccent{\bar}{\alpha}_{k} M_k = \gamma C\sqrt{\frac{\eta_1^2 \mu^{3} \min\{6 (1 - C) \eta_1, 2(1-2\eta_2) \}}{L_H(-M_k)^2}} \cdot (-M_k) \\ &= \hat{C} L_H^{-1/2} \mu^{3/2}. \end{align}\] ◻
Lemma 3. Suppose that the problem is unconstrained, i.e., \(\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x) = f(x)\) and \(\grad^2 f\) is \(L_H\)-Lipschitz. If \(\underaccent{\bar}{\alpha}_{k} \ge 1\) then \(\| \grad f(x_{k+1}) \|_2 \le \mu\).
Proof. Since \(\underaccent{\bar}{\alpha}_{k} \ge 1\), 1 implies \(\alpha_k=1\). Moreover, \[\begin{align} \| \grad f(x_{k+1}) \|_2 &= \| \grad f(x_k + d^{x}_k) \|_2 \underset{(a)}{\le} \| \grad \mathcal{M}_k(d^{x}_k) \|_2 + \frac{L_H}{2} \| d^{x}_k \|_2^2 \underset{(b)}{=} \delta_k \|d^{x}_k\|_2 + \frac{L_H}{2} \| d^{x}_k \|_2^2 \\ &\underset{(c)}{\le} 2\eta_2 \mu + \frac{L_H}{2} \| d^{x}_k \|_2^2 \underset{(d)}{\le} 2\eta_2 \mu + \frac{L_H}{2} (\eta_1 \mu)^{-2} \cdot (-M_k)^2 \le 2\eta_2 \mu + \frac{L_H}{2} (\eta_1 \mu)^{-2} \cdot (-M_k)^2 \underaccent{\bar}{\alpha}_{k}^2 \\ &\le 2 \eta_2 \mu + \frac{L_H}{2} (\eta_1 \mu)^{-2} \cdot (-M_k)^2 \cdot \frac{\eta_1^2 \mu^{3} 2(1-2\eta_2)}{L_H(-M_k)^2} \le \mu \end{align}\] where inequality \((a)\) uses 8 , equality \((b)\) uses \(\| \grad \mathcal{M}_k(d^{x}_k) \|_2 = \delta_k \|d^{x}_k\|_2\), inequality \((c)\) uses ?? from Condition 1 and the fact that \(\alpha_k = 1\), and inequality \((d)\) uses the upper bound on \(\| d^{x}_k \|\) given in ?? . ◻
Theorem 1. Suppose that the problem is unconstrained, i.e., \(\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x) = f(x)\) and \(\grad^2 f\) is \(L_H\)-Lipschitz. Let \(\hat{C} := \gamma C\eta_1 \cdot \min\{ \sqrt{6(1- C) \eta_1} , \sqrt{2(1-2\eta_2)}\}\) be a problem-independent constant. Then, 1 terminates after at most \[\begin{align} K \le 1+\hat{C} ^ {-1} \cdot \frac{(f(x_1) - f_\star) L_H^ {1/2}}{\mu ^ {3/2}} \end{align}\] iterations.
Proof. Consider some iteration \(K\) of the algorithm, since the algorithm has not terminated across iterations \(k = 1, \dots, K-1\), by the contrapositive of 3 we deduce that \(\underaccent{\bar}{\alpha}_{k} < 1\) for \(k \in [1,K-1]\). Thus, by 2 and a telescoping sum, we get: \[\begin{align} f(x_1) - f(x_{K}) \ge \sum_{k=1}^{K-1} (f(x_k) - f(x_{k+1})) \geq \sum_{k=1}^{K-1} \hat{C} \cdot L_H^{-1/2} \mu^{3/2} = (K-1) \cdot \hat{C} \cdot L_H^{-1/2} \mu^{3/2}. \end{align}\] Rearranging the above inequality and using \(f(x_{K}) \ge f_\star\) gives the desired result. ◻
Remark 1. In convex optimization, it is well known that if the initial sublevel set is bounded by \(D\), i.e., \(D = \mathbf{diam}(\{ x \in \mathbf{R}^{n} : f(x) \le f(x_1) \})\) then the iteration bound for cubic regularized Newton to find an \(\epsilon\)-approximate minimizer is \(O(L_H^{1/2} D^{3/2} \epsilon^{-1/2})\) [5]. This may be preferable to 1 which obtains a worse \(\mu^{-3/2}\) scaling3. However, in 3 we show we can match this bound of cubic regularized Newton by annealing \(\mu\). Additionally, it is well-known that many methods [5], [6], [8] can achieve a similar result to 1 without a convexity assumption.
2.2 Lemmas on local approximations and direction sizes↩︎
This section lists a series of useful lemmas from [10] for analyzing log barrier methods. They depend on the following assumption.
Assumption 1 (Lipschitz derivatives). The functions \(f\) and each \(a_i\) for \(i \in [m]\) are thrice differentiable on \({\boldsymbol{R}}^{n}\). Let \(L_G, L_H\in (0,\infty)\). On the set \(\mathcal{X}\), \(f\) and each \(a_i\) have \(L_G\)-Lipschitz first derivatives and \(L_H\)-Lipschitz second derivatives.
4 bounds the gap between the predicted reduction from the second order model \(\mathcal{M}_k\) and the actual reduction of the log barrier \(\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}}\). This allows us to establish a lower bound on the actual reduction in the log barrier similar to 2 in the unconstrained setup. Recall from 5 that \[\begin{align} &s_k := a(x_k), \quad y_k := \mu S_k^{-1} \mathbf{1}, \quad S_k := \mathop{\boldsymbol{d}iag}(s_k), \quad Y_k = \mathop{\boldsymbol{d}iag}(y_k), \\ &d^{s}_k := \grad a(x_k) d^{x}_k, \quad d^{y}_k :=-Y_k S_k^{-1} d^{s}_k \end{align}\] and that \(S_k y_k + S_k d^{y}_k + Y_k d^{s}_k = \mu \mathbf{1}\). Also, by definition of 1 we have \(x_k \in \mathbf{interior}(\mathcal{X})\).
Lemma 4. [10]Suppose Assumption 1 holds (Lipschitz derivatives). Let \(\alpha \in [0,1]\), and \[\begin{align} \label{eq:kappa-requirement} \kappa_{\alpha} := \| S_k^{-1} d^{s}_k \|_{2} \alpha + \frac{L_G\| d^{x}_k \|_2^2 \| y_k \|_2 \alpha^2}{\mu}. \end{align}\qquad{(1)}\] If \(\kappa_{\alpha} \in (0, 1/4]\) then \(CONVEX\{ x_k, x_k + \alpha d^{x}_k \} \subseteq \mathcal{X}\) and \[\begin{align} \label{eq:progress-barrier-error} | \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) + \mathcal{M}_k(\alpha d^{x}_k) - \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k + \alpha d^{x}_k) | \le \frac{L_H( 1 + 2 \| y_k \|_1 ) \| d^{x}_k \|_2^3 \alpha^3}{6} + {\frac{4 L_G\| d^{x}_k \|_2^2 \| y_k \|_1 \kappa_{\alpha} \alpha^2 }{3}} + \frac{5 \mu \kappa_{\alpha}^3}{3}. \end{align}\qquad{(2)}\]
5 allows us to establish when we have found an approximate stationary interior point, i.e., 1 holds.
Lemma 5. [10]Suppose Assumption 1 holds (Lipschitz derivatives). Let \(\hat{x}_{k+1} = x_{k} + d^{x}_k\), \(\hat{y}_{k+1} = y_k + d^{y}_k\), \(CONVEX\{x_k, \hat{x}_{k+1} \} \subseteq \mathcal{X}\), \(\hat{S}_{k+1} = \mathop{\boldsymbol{d}iag}(a(\hat{x}_{k+1}))\), then \[\begin{align} \| \hat{S}_{k+1} \hat{y}_{k+1} - \mu \mathbf{1}\|_{2} &\le \mu \| S_k^{-1} d^{s}_k \|_{2}^2 + \frac{L_G}{2} \| y_k \|_{2} (1 + \| S_k^{-1} d^{s}_k \|_{2}) \| d^{x}_k \|_2^2. \label{eq:new-general-comp-bound} \end{align}\qquad{(3)}\] Moreover, \[\label{eq:LagError} \begin{align} &\| \grad_{x} \mathcal{L}( x_k , y_k ) + \grad_{xx}^2 \mathcal{L}(x_k, y_k)^\top d^{x}_k - (\grad a(x_k))^\top d^{y}_k - \grad_{x} \mathcal{L}(\hat{x}_{k+1}, \hat{y}_{k+1}) \|_{2} \\ &\le L_G\| y_k \|_2 \| d^{x}_k \|_2 \| S_k^{-1} d^{s}_k \|_2 + \frac{L_H}{2} (\| y_k \|_1 + 1) \| d^{x}_k \|^2_2. \end{align}\qquad{(4)}\]
Finally, we will finish this section with 6. This is a key result that allows us to bound the direction size of the slack variables, i.e, \(\|S_k^{-1} d^{s}_k\|_2\). Combining 6 with the above lemmas will allow us to give concrete bounds on the reduction of the log barrier at each iteration.
Lemma 6. [10]Suppose Assumption 1 holds (Lipschitz derivatives). Then the following inequality holds:\[\begin{align} \label{eq:bound-slack-variable} \| S_k^{-1} d^{s}_k \|_2 \leq \sqrt{\frac{-2M_k}{\mu}}. \end{align}\qquad{(5)}\]
Proof. As discussed immediately after Lemma 9 of [10] one has \(\| S^{-1}_k d^{s}_k \|_2 \le \sqrt{ \frac{ -(d^{x}_k)^\top \grad_{xx}^2 \mathcal{L}(x_k,y_k) d^{x}_k - 2 M_k}{\mu} }\). Since \(\grad_{xx}^2 \mathcal{L}(x_k,y_k) \succeq 0\) by convexity we get the desired result. ◻
2.3 Analysis of our log barrier method with fixed barrier parameter↩︎
In this subsection, we prove that 1 finds an approximate stationary interior point in at most \(O(\mu^{-5/3})\) iterations. This proof shares a similar structure to the proof in 2.1 for the unconstrained setup but is more technical. In particular, we show that there is a threshold representing the minimum step size that the algorithm must take as a function of the expected progress \(-M_k\). Although this step size threshold decays as \(-M_k\) grows, this is balanced out because, by the sufficient decrease condition (?? ) and 1, the function value is reduced by at least \(\alpha_k CM_k\) at each iteration. On the other hand, we show if this step threshold exceeds one then \(\alpha_k=1\) and the algorithm will terminate at the next iteration. While the high-level structure is similar to 2.1, the threshold and exact analysis is much more involved due to the presense of the log barrier.
2.3.0.1 Step size thresholds that guarantee feasibility.
\[\begin{align} \label{def:alpha-feas-threshold} \underaccent{\bar}{\alpha}_{k}^{(1)} := \frac{1}{8} \sqrt{\frac{\mu}{-2M_k}}, \qquad \underaccent{\bar}{\alpha}_{k}^{(2)} := \frac{1}{2\sqrt{2 L_G}} \cdot \frac{\mu ^ {3/2} \cdot \eta_1}{-M_k}. \end{align}\tag{11}\] In 7 we show that for any step size \(\alpha \in (0,1]\) below these thresholds, \(\kappa_{\alpha} \in (0,1/4]\) and therefore, by 4 the candidate iterate \(x_{k} + \alpha d^{x}_k\) is feasible.
Lemma 7. Suppose Assumption 1 holds (Lipschitz derivatives). Then, for any step size \(\alpha \in [0,1]\) with \(\alpha \le \min\{ 1, \underaccent{\bar}{\alpha}_{k}^{(1)}, \underaccent{\bar}{\alpha}_{k}^{(2)} \}\), we have \(\kappa_{\alpha} \in [0,1/4]\) where \(\kappa_{\alpha}\) is defined in 4.
Proof. Using equation ?? from 4, we will show that if the step size \(\alpha\) satisfies the inequality \(\alpha \leq \min \{1, \underaccent{\bar}{\alpha}_{k}^{(1)}, \underaccent{\bar}{\alpha}_{k}^{(2)} \}\) then \(\kappa_{\alpha} \in [0,1/4]\).
Denote \(S_k = \mathop{\boldsymbol{d}iag}(a(x_k))\), \(d^{s}_k = \grad a(x_k) d^{x}_k\), and \(y_k = \mu S_k^{-1} \mathbf{1}\). First, we will show that \(\alpha \| S_k^{-1} d^{s}_k \|_{2} \leq \frac{1}{8}\). Note that: \[\begin{align} \alpha \| S_k^{-1} d^{s}_k \|_{2} &\underset{(a)}{\le} \frac{1}{8} \cdot \sqrt{\frac{\mu}{-2M_k}} \cdot \| S_k^{-1} d^{s}_k \|_{2} \\ &\underset{(b)}{\le} \frac{1}{8} \cdot \sqrt{\frac{\mu}{-2M_k}} \cdot \sqrt{\frac{-2M_k}{\mu}} = \frac{1}{8} \end{align}\] where inequality \((a)\) uses \(\alpha \leq \min \{\underaccent{\bar}{\alpha}_{k}^{(1)}, \underaccent{\bar}{\alpha}_{k}^{(2)}\} \leq \underaccent{\bar}{\alpha}_{k}^{(1)}\) and the definition of \(\underaccent{\bar}{\alpha}_{k}^{(1)}\) from 11 and inequality \((b)\) uses \(\| S_k^{-1} d^{s}_k \|_2 \leq \sqrt{\frac{-2M_k}{\mu}}\) from ?? .
Next, we will show that \(\frac{L_G\| d^{x}_k \|_2^2 \| y_k \|_2 \alpha ^ 2}{\mu} \le \frac{1}{8}\). Note that: \[\begin{align} \frac{L_G\|d^{x}_k \|_2^2 \| y_k \|_2 \alpha^2}{\mu} &\underset{(a)}{\le} \frac{L_G\|d^{x}_k \|_2^2 \| y_k \|_2}{\mu} \cdot \left(\frac{1}{2\sqrt{2 L_G}} \cdot \frac{\mu ^ {3/2} \cdot \eta_1}{-M_k}\right) ^ 2 \\ &= \frac{\| y_k \|_2}{8} \cdot \|d^{x}_k \|_2^2 \cdot \frac{\mu ^ 2 \eta_1 ^ 2}{(-M_k)^2} \\ &\underset{(b)}{\le} \frac{1}{8} \cdot \|d^{x}_k \|_2^2 \cdot \mu ^ 2 \eta_1 ^ 2 \cdot \frac{\|y_k\|_2}{\eta_1 ^ 2 \mu ^ 2 \|d^{x}_k\|_2^2 (\|y_k\|_1 + 1)} = \frac{1}{8} \cdot \frac{\|y_k\|_2}{\|y_k\|_1 + 1} \le \frac{1}{8} \end{align}\] where inequality \((a)\) uses \(\alpha \leq \min \{\underaccent{\bar}{\alpha}_{k}^{(1)}, \underaccent{\bar}{\alpha}_{k}^{(2)}\} \leq \underaccent{\bar}{\alpha}_{k}^{(2)}\) and the definition of \(\underaccent{\bar}{\alpha}_{k}^{(2)}\) from 11 and inequality \((b)\) uses ?? from Condition 1 with \(\varepsilon_k = \mu \sqrt{\|y_k\|_1 + 1}\).
Therefore \(\kappa_{\alpha} = \alpha \| S_k^{-1} d^{s}_k \|_{2} + \frac{L_G\| d^{x}_k \|_2^2 \| y_k \|_2 \alpha ^ 2}{\mu} \leq \frac{1}{4}\) as desired. ◻
2.3.0.2 Step size thresholds that guarantee sufficient decrease.
\[\begin{align} \label{def:alpha-sufficient-decrease-threshold} \begin{aligned} \underaccent{\bar}{\alpha}_{k}^{(3)} := \frac{(1 - C)^{1/2} \mu^{3/2} \eta_1^{3/2}}{L_H^{1/2} (-M_k)}, \qquad \underaccent{\bar}{\alpha}_{k}^{(4)} := \frac{(1 - C)^{1/2} \mu^{5/4} \eta_1}{(8\sqrt{2})^{1/2} L_G^{1/2} (-M_k)^{3/4}}, \qquad\quad\qquad\quad \\[2ex] \underaccent{\bar}{\alpha}_{k}^{(5)} := \frac{(1 - C)^{1/3} \mu^{5/3} \eta_1^{4/3}}{2 L_G^{2/3} (-M_k)}, \quad \underaccent{\bar}{\alpha}_{k}^{(6)} := \frac{(1 - C)^{1/2} \mu^{1/4}}{(80\sqrt{2})^{1/2} (-M_k)^{1/4}}, \quad \underaccent{\bar}{\alpha}_{k}^{(7)} := \frac{(1 - C)^{1/5} \mu^{8/5} \eta_1^{6/5}}{40^{1/5} L_G^{3/5} (-M_k)}. \end{aligned} \end{align}\tag{12}\] 8 uses these thresholds and the thresholds defined in 11 to lower bound the step size \(\alpha_k\) taken by our method. The proof of 8 shows that for any step size \(\alpha \in (0,1]\) below these thresholds and the thresholds defined in 11 , the sufficient decrease condition given in the first part of Condition 2 is satisfied. Combining this fact with the second part of Condition 2 which requires that larger step sizes violate the sufficient decrease condition, allows us to obtain our desired lower bounds on the step size.
The analog of 8 in the unconstrained setting is 1.
Lemma 8. Suppose Assumption 1 holds (Lipschitz derivatives). Then, if \(\min_{i \in [7]} \underaccent{\bar}{\alpha}_{k}^{(i)} \ge 1\) then \(\alpha_k=1\) and if \(\min_{i \in [7]} \underaccent{\bar}{\alpha}_{k}^{(i)} < 1\) then \(\alpha_k > \gamma\cdot \min_{i \in [7]} \underaccent{\bar}{\alpha}_{k}^{(i)}\).
To prove 8 we first prove Claim 1. We then recast the Taylor series error bounds from 4 in the form of ?? using 7 and ?? , allowing us to mechanically derive 8 using Claim 1.
Claim 1. Let the premise of 8 hold. Additionally, suppose that there exists constants \(t_k, \zeta_{k,1}, \dots, \zeta_{k,P} \in (0,\infty)\) and \(\theta_{1}, \dots, \theta_{P} \in (1,\infty)\) such that for all \(\alpha \in [0, t_k]\) \[\begin{align} \label{eq:structured-error-bound} \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k + \alpha d^{x}_k) \le \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) + \mathcal{M}_k(\alpha d^{x}_k) + \max_{p \in [P]} \zeta_{k,p} \alpha^{\theta_{p}}. \end{align}\qquad{(6)}\] Let \[\tau_k := \min\left\{ t_k , \min_{p \in [P]} \left( \frac{-M_k(1 - C)}{\zeta_{k,p}} \right)^{\frac{1}{\theta_{p}-1}} \right\}.\] Then, if \(\tau_k \ge 1\) then \(\alpha_k=1\) and if \(\tau_k < 1\) then \(\alpha_k > \gamma\tau_k\).
Proof. By the Claim statement and 1, for the sufficient decrease condition, ?? , to hold, it suffices for \[\max_{p \in [P]} \zeta_{k,p} \alpha^{\theta_{p}} \le \alpha (C- 1) \cdot M_k.\] Dividing both sides by \(\alpha\) gives: \[\max_{p \in [P]} \zeta_{k,p} \alpha^{\theta_{p} - 1} \le (C- 1) \cdot M_k.\] Since \(\theta_{p} > 1\), solving for \(\alpha\) gives that the sufficient decrease condition (?? ) is satisfied for all \[\alpha \le \min\left\{ t_k, \min_{p \in [P]} \left( \frac{- M_k(1 - C)}{\zeta_{k,p}} \right)^{\frac{1}{\theta_{p} - 1}} \right\} = \tau_k.\] Therefore if \(\tau_k \ge 1\), then ?? fails for all \(\hat{\alpha}_k \le 1\), so Condition 2 is satisfied only for \(\alpha_k = 1\). Otherwise, if \(\tau_k < 1\), then by the requirement in ?? that the larger step size \(\hat{\alpha}_k = \min\{ \alpha_k / \gamma, 1 \}\) fails to obtain sufficient decrease we deduce that \(\alpha_k / \gamma> \tau_k\) and thus \(\alpha_k > \gamma\tau_k\). ◻
Proof of 8. We proceed to obtain a bound in the form of ?? so we can employ Claim 1. For simplicity, let \(\sigma_k= \sqrt{\| y_k \|_1 + 1}\) where \(y_k = \mu S_k^{-1} \mathbf{1}\) and \(S_k = \mathop{\boldsymbol{d}iag}(a(x_k))\). Using ?? from Condition 1 with \(\varepsilon_k = \mu \sigma_k\), we get: \[\|d^{x}_k\|_2 \le \frac{-M_k}{\varepsilon_k \eta_1} = \frac{-M_k}{\sigma_k\mu \eta_1}.\] Also, using ?? from 4 as well as 6, for any \(\alpha \in [0,1]\) we get: \[\kappa_{\alpha} \le 2 \max\left\{ \sqrt{\frac{-2 M_k}{\mu}} \alpha, \frac{L_G\| d^{x}_k \|_2^2 \sigma_k^2}{\mu} \alpha^2 \right\} \le 2 \max\left\{ \sqrt{\frac{-2 M_k}{\mu}} \alpha, \frac{L_G(-M_k)^2}{\mu^3 \eta_1^2} \alpha^2 \right\}.\] Moreover, using 1 and ?? from 4, for any \(\alpha \in [0,\min\{1,\underaccent{\bar}{\alpha}_{k}^{(1)},\underaccent{\bar}{\alpha}_{k}^{(2)}\}]\) we have \[\begin{align} &\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k + \alpha d^{x}_k) - \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) - \mathcal{M}_k(\alpha d^{x}_k) \le 3 \max\left\{ \frac{2 L_H\sigma_k^2 \| d^{x}_k \|_2^3 \alpha^3}{6} , {\frac{4 L_G\| d^{x}_k \|_2^2 \sigma_k^2 \kappa_{\alpha} \alpha^2 }{3}} , \frac{5 \mu \kappa_{\alpha}^3}{3} \right\} \\ &\underset{(a)}{\le} \max\left\{ \frac{L_H\alpha^3 (-M_k)^3}{\sigma_k\mu^3 \eta_1^3} , \frac{4 L_G\kappa_{\alpha} \alpha^2 (-M_k)^2}{\mu^2 \eta_1^2} , 5 \mu \kappa_{\alpha}^3 \right\} \\ &\underset{(b)}{\le} \max\left\{ \frac{L_H(-M_k)^3}{\sigma_k\mu^3 \eta_1^3} \alpha^3, \frac{8\sqrt{2} L_G(-M_k)^{5/2}}{\mu^{5/2} \eta_1^2} \alpha^3, \frac{8 L_G^2 (-M_k)^4}{\mu^5 \eta_1^4} \alpha^4, \frac{80\sqrt{2} (-M_k)^{3/2}}{\mu^{1/2}} \alpha^3 , \frac{40 L_G^3 (-M_k)^6}{\mu^8 \eta_1^6} \alpha^6 \right\}. \end{align}\] where inequality \((a)\) uses our upper bound on \(\| d^{x}_k \|_2\) and \((b)\) substitutes for our upper bound on \(\kappa_{\alpha}\). Thus, by 7 and Claim 1 with \(t_k = \min\{ 1, \underaccent{\bar}{\alpha}_{k}^{(1)}, \underaccent{\bar}{\alpha}_{k}^{(2)} \}\) we get that \[\begin{align} \tau_k = \min\Bigg\{ &t_k, \frac{(1 - C)^{1/2} \sigma_k^{1/2} \mu^{3/2} \eta_1^{3/2}}{L_H^{1/2} (-M_k)}, \frac{(1 - C)^{1/2} \mu^{5/4} \eta_1}{(8\sqrt{2})^{1/2} L_G^{1/2} (-M_k)^{3/4}}, \frac{(1 - C)^{1/3} \mu^{5/3} \eta_1^{4/3}}{2 L_G^{2/3} (-M_k)}, \\ &\frac{(1 - C)^{1/2} \mu^{1/4}}{(80\sqrt{2})^{1/2} (-M_k)^{1/4}}, \frac{(1 - C)^{1/5} \mu^{8/5} \eta_1^{6/5}}{40^{1/5} L_G^{3/5} (-M_k)} \Bigg\} \ge \min\left\{1, \min_{i \in [7]} \underaccent{\bar}{\alpha}_{k}^{(i)} \right\}. \end{align}\] ◻
8 showed that the step size \(\alpha_k\) taken by the method is one if \(\min_{i \in [7]} \underaccent{\bar}{\alpha}_{k}^{(i)} \ge 1\) and otherwise greater than \(\gamma\min_{i \in [7]} \underaccent{\bar}{\alpha}_{k}^{(i)}\). 9 shows in the case that \(\min_{i \in [7]} \underaccent{\bar}{\alpha}_{k}^{(i)} < 1\) that there is significant reduction in the barrier function. The analog of 9 in the unconstrained setting is 2.
Lemma 9. Suppose Assumption 1 holds. If \(\min_{i \in [7]} \underaccent{\bar}{\alpha}_{k}^{(i)} < 1\) then \[\begin{align} \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) - \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_{k+1}) \ge C\gamma\mu \left( \frac{8 L_G^{2/3}}{(1 - C)^{2/3} \eta_1^{4/3}}{} \mu^{-2/3} + r(\mu) \right)^{-1} \end{align}\] where \[\begin{align} \begin{aligned} \label{eq:formula-for-remainder} r(\mu) := 128 &+ \frac{12800}{(1-C)^2} + \left(\frac{2\sqrt{2 L_G}}{\eta_1} + \frac{L_H^{1/2}}{(1-C)^{1/2}\eta_1^{3/2}} \right) \mu^{-1/2} + \frac{40^{1/5}L_G^{3/5}}{(1-C)^{1/5}\eta_1^{6/5}} \mu^{-3/5}. \end{aligned} \end{align}\qquad{(7)}\]
To prove 9 we first prove Claim 2 which recasts the \(\underaccent{\bar}{\alpha}_{k}\) as a generic formula, allowing us to produce a generic bound on \(\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) - \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_{k+1})\). We can then use Claim 2 to mechanically derive 9.
Claim 2. Suppose that there exists constants \(\zeta_{k,1}, \dots, \zeta_{k,P} \in (0,\infty)\) and \(\theta_{1}, \dots, \theta_{P} \in (0,1]\) such that \(\min_{p \in [P]} \;\frac{\zeta_{k,p}}{(-M_k)^{\theta_{p}}} < 1\) then, if \(\alpha_k \ge \gamma\min_{p \in [P]} \frac{\zeta_{k,p}}{(-M_k)^{\theta_{p}}}\), we have: \[\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) - \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_{k+1}) \ge \gamma C\cdot \min_{p \in [P]} \zeta_{k,p} ^ \frac{1}{\theta_{p}}.\]
Proof. Let \(p^* = \arg\min_{p \in [P]} \frac{\zeta_{k,p}}{(-M_k)^{\theta_{p}}}\). Since \(\frac{\zeta_{k,p^*}}{(-M_k)^{\theta_{p^*}}} < 1\), we have: \[-M_k> \zeta_{k,p^*}^{1/\theta_{p^*}}.\] Using 1 and the sufficient decrease condition (?? ): \[\begin{align} \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) - \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_{k+1}) = \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) - \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k + \alpha_k d^{x}_k) &\geq -C\cdot \mathcal{M}_k(\alpha_k d^{x}_k) \ge C\cdot \alpha_k (-M_k) \\ &\ge \gamma C\cdot \frac{\zeta_{k,p^*}}{(-M_k)^{\theta_{p^*}}} \cdot (-M_k) \\ &= \gamma C\cdot \zeta_{k,p^*} \cdot (-M_k)^{1-\theta_{p^*}}. \end{align}\] Since \(0 < \theta_{p^*} \le 1\), we have \(1 - \theta_{p^*} \ge 0\). Rearranging \(\frac{\zeta_{k,p}}{(-M_k)^{\theta_{p}}} < 1\) gives \(-M_k> \zeta_{k,p^*}^{1/\theta_{p^*}}\) and thus \[\frac{\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) - \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_{k+1})}{\gamma C} \ge \zeta_{k,p^*} \cdot (-M_k)^{1-\theta_{p^*}} \ge \zeta_{k,p^*} \cdot \left(\zeta_{k,p^*}^{1/\theta_{p^*}}\right)^{1-\theta_{p^*}} \ge \zeta_{k,p^*} \cdot \zeta_{k,p^*}^{(1-\theta_{p^*})/\theta_{p^*}} = \zeta_{k,p^*}^{1/\theta_{p^*}}\] as desired. ◻
Proof of 9. Using Claim 2, we will derive the reduction in the log barrier function for all the lower bound on the step size \(\alpha_k\) from Lemma 8, i.e, \(\alpha_k \ge \gamma\min_{i \in [7]} \underaccent{\bar}{\alpha}_{k}^{(i)}\). Note that by our definition of \(\underaccent{\bar}{\alpha}_{k}^{(i)} \text{ } \forall i \in [7]\), we can write each \(\underaccent{\bar}{\alpha}_{k}^{(i)}\) in the format \(\frac{\zeta_{k,i}}{(-M_k)^{\theta_{i}}}\) with \(\theta_{i} \le 1\). Therefore, by Claim 2, we get: \[\begin{align} \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) - \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_{k+1}) \ge C\gamma\cdot \min\Bigg\{ &\frac{\mu}{128}, \frac{\mu^{3/2} \eta_1}{2\sqrt{2 L_G}}, \frac{(1 - C)^{1/2} \mu^{3/2} \eta_1^{3/2}}{L_H^{1/2}}, \frac{(1 - C)^{2/3} \mu^{5/3} \eta_1^{4/3}}{(8\sqrt{2})^{2/3} L_G^{2/3}}, \\ &\frac{(1 - C)^{1/3} \mu^{5/3} \eta_1^{4/3}}{2 L_G^{2/3}}, \frac{(1 - C)^{2} \mu}{12800}, \frac{(1 - C)^{1/5} \mu^{8/5} \eta_1^{6/5}}{40^{1/5} L_G^{3/5}} \Bigg\}. \end{align}\] ◻
Recall that 9 shows that if \(\min_{i \in [7]} \underaccent{\bar}{\alpha}_{k}^{(i)} < 1\) then there is significant reduction in the barrier function. 10 complements 9 by showing if \(\min_{i \in [7]} \underaccent{\bar}{\alpha}_{k}^{(i)} \ge 1\) then the algorithm terminates. The analog of 10 in the unconstrained setting is 3.
Lemma 10. Suppose Assumption 1 holds. If \(\min_{i \in [7]} \underaccent{\bar}{\alpha}_{k}^{(i)} \ge 1\) then, \((x_{k+1}, \hat{y}_{k+1})\) is a \(\mu\)-approximate first-order SIP where \(\hat{y}_{k+1}\) is defined in 6 .
Proof. Recall \(d^{s}_k := \grad a(x_k) d^{x}_k\). By our assumption that \(\min_{i \in [7]} \underaccent{\bar}{\alpha}_{k}^{(i)} \ge 1\), 8 implies that \(\alpha_k = 1\) and thus \(x_{k+1} = x_k + d^{x}_k \in \mathbf{interior}(\mathcal{X})\). For brevity, denote \(\hat{y}_{k+1} = y_k + d^{y}_k\), and \(s_{k+1} = a(x_{k+1})\). Also, using \(\min\{\underaccent{\bar}{\alpha}_{k}^{(1)},\underaccent{\bar}{\alpha}_{k}^{(2)}\}\ge 1\) and ?? , we have \[\begin{align} \label{eq:Sinv-bound-by-constant} \|S_k^{-1}d^{s}_k\|_2 \underset{(a)}{\le} \sqrt{\frac{-2M_k}{\mu}} \underset{(b)}{\le} \frac{1}{8} \end{align}\tag{13}\] where \((a)\) uses 6 and \((b)\) uses \(-M_k\le \mu / 128\) from \(\underaccent{\bar}{\alpha}_{k}^{(1)} \ge 1\). Next note that using \(S_k d^{y}_k + Y_k d^{s}_k + S_k y_k = \mu \mathbf{1}\) and \(S_k y_k=\mu\mathbf{1}\), we have \[\begin{align} \label{eq:dir-y-formula} d^{y}_k=-Y_k S_k^{-1} d^{s}_k \end{align}\tag{14}\] Thus \(\| Y_k^{-1} d^{y}_k \|_{\infty} \le \| Y_k^{-1} d^{y}_k \|_2 = \|S_k^{-1}d^{s}_k\|_2 \le 1/8\) and using 13 we conclude \(Y_k^{-1} (y_{k} + d^{y}_k) > 0\) and therefore ?? holds. The remainder of the proof establishes that ?? and ?? hold.
We first show the complementarity condition ?? holds. Observe that \[\begin{align} \| \mathop{\boldsymbol{d}iag}(\hat{y}_{k+1}) s_{k+1} - \mu \mathbf{1}\|_2 &\underset{(a)}{\le} \mu \|S_k^{-1} d^{s}_k\|_2^2 + \frac{L_G}{2} \| y_k \|_{2} (1 + \|S_k^{-1} d^{s}_k\|_2) \| d^{x}_k \|_2^2 \\ &\underset{(b)}{\le} \frac{\mu}{64} + \frac{9 L_G}{16} \| y_k \|_{2} \| d^{x}_k \|_2^2 \\ &\underset{(c)}{\le} \frac{\mu}{64} + \frac{9 L_G}{16} \| y_k \|_{2} \left(\frac{-M_k}{\eta_1 \mu \sqrt{\|y_k\|_1 + 1}}\right)^2 \\ &\underset{(d)}{\le} \frac{\mu}{64} + \frac{L_G}{2} \left(1 + \frac{1}{8} \right) \cdot \frac{\mu}{8L_G} \cdot \frac{\| y_k \|_2}{1 + \| y_k \|_1} \le \frac{\mu}{64} + \frac{9}{128}\mu = \frac{11}{128}\mu < \frac{1}{2}\mu, \end{align}\] where inequality \((a)\) uses ?? , inequality \((b)\) uses 13 , \((c)\) uses ?? with \(\varepsilon_k = \mu \sqrt{1 + \| y_k \|_1}\), and \((d)\) uses \(-M_k\le \frac{\eta_1 \mu^{3/2}}{2\sqrt{2}\,L_G^{1/2}}\) from \(\underaccent{\bar}{\alpha}_{k}^{(2)} \ge 1\). Since \(\|\cdot\|_\infty\le \|\cdot\|_2\), the complementarity condition ?? holds.
Now we show that the gradient of the Lagrangian is small, i.e., ?? holds. Substituting 14 and \(d^{s}_k = \grad a(x_k) d^{x}_k\) into \((\grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) + \boldsymbol{I}\delta_k)d^{x}_k = -\grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k)\) gives \[\grad_{x} \mathcal{L}(x_k, y_k) + \grad_{xx}^2 \mathcal{L}(x_k, y_k)^\top d^{x}_k - \grad a(x_k)^\top d^{y}_k = -\delta_k d^{x}_k.\] Combining this with ?? yields \[\begin{align} \| \delta_k d^{x}_k + \grad_{x} \mathcal{L}(x_{k+1}, \hat{y}_{k+1}) \| &\le \frac{L_H}{2}(\|y_k\|_1 + 1)\|d^{x}_k\|_2^2 + L_G\|y_k\|_2 \|d^{x}_k\|_2 \|S_k^{-1}d^{s}_k\|_2. \end{align}\] Therefore, \[\begin{align} \|\grad_{x}\mathcal{L}(x_{k+1}, \hat{y}_{k+1})\| &\le \|\delta_k d^{x}_k\| + \frac{L_H}{2}(\|y_k\|_1+1)\|d^{x}_k\|_2^2 + L_G\|y_k\|_2 \|d^{x}_k\|_2 \|S_k^{-1}d^{s}_k\|_2 \\ &\underset{(a)}{\le} 2\mu\eta_2\sqrt{\|y_k\|_1+1} + \frac{L_H}{2}(\|y_k\|_1+1)\|d^{x}_k\|_2^2 + L_G\|y_k\|_2 \|d^{x}_k\|_2 \|S_k^{-1}d^{s}_k\|_2 \\ &\underset{(b)}{\le} 2\mu\eta_2\sqrt{\|y_k\|_1+1} + \frac{L_H}{2}\left(\frac{-M_k}{\mu\eta_1}\right)^2 + L_G\|y_k\|_2\cdot\frac{2^{1/2}(-M_k)^{3/2}}{\mu^{3/2}\eta_1\sqrt{\|y_k\|_1+1}} \\ &\underset{(d)}{\le} 2\mu\eta_2\sqrt{\|y_k\|_1+1} + \frac{L_H}{2\eta_1^2}\left(\frac{-M_k}{\mu}\right)^2 + \frac{2^{1/2}L_G\sqrt{\|y_k\|_1+1}}{\eta_1}\left(\frac{-M_k}{\mu}\right)^{3/2} \\ &\underset{(e)}{\le} 2\mu\eta_2\sqrt{\|y_k\|_1+1} + \frac{(1-C)\eta_1\mu}{2} + \frac{(1-C)\eta_1\mu\sqrt{\|y_k\|_1+1}}{8} \\ &\le \mu\sqrt{\|y_k\|_1+1}\left(2\eta_2 + \frac{5}{8}(1-C)\eta_1\right) \underset{(f)}{\le} \mu\sqrt{7/8}\sqrt{\|y_k\|_1+1} \underset{(g)}{\le} \mu\sqrt{\|\hat{y}_{k+1}\|_1+1} \end{align}\] where inequality \((a)\) uses \(\|d^{x}_k\|_2 \delta_k \le 2\eta_2 \varepsilon_k = 2\eta_2 \mu \sqrt{\|y_k\|_1 + 1}\) which holds by ?? and \(\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k + d^{x}_k) \le \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) + C\cdot\mathcal{M}_k(d^{x}_k)\) since \(\alpha_k=1\); \((b)\) uses ?? from Condition 1 and 6; inequality \((d)\) uses \(\|y_k\|_2 \le \|y_k\|_1 \le \|y_k\|_1 + 1\); inequality \((e)\) uses \[-M_k\le \min\left\{ \frac{(1-C)^{1/2}\mu^{3/2}\eta_1^{3/2}}{L_H^{1/2}},\; \frac{(1-C)^{2/3}\mu^{5/3}\eta_1^{4/3}}{(8\sqrt{2})^{2/3}L_G^{2/3}} \right\}\] from \(\min\{\underaccent{\bar}{\alpha}_{k}^{(3)}, \underaccent{\bar}{\alpha}_{k}^{(4)}\} \ge 1\); inequality \((f)\) uses that \(2\eta_2 + \tfrac{5}{8}(1-C)\eta_1 \le \sqrt{7/8}\); and inequality \((g)\) uses \(\hat{y}_{k+1} = Y_{k} (\mathbf{1} + Y_{k}^{-1} d^{y}_k) \ge y_k (1 - \| Y_{k}^{-1} d^{y}_k \|_{\infty}) \ge (7/8) y_k\) where the last inequality uses 13 and 14 . ◻
9 shows that if \(\min_{i \in [7]} \underaccent{\bar}{\alpha}_{k}^{(i)} < 1\) then we obtain a reduction in the barrier function of at least \(\Omega(\mu^{5/3})\). 10 shows that if \(\min_{i \in [7]} \underaccent{\bar}{\alpha}_{k}^{(i)} \ge 1\) then the algorithm terminates. Combining these two results together using standard telescoping arguments gives 2.
Proof. Let \(K\) be the iteration that the algorithm terminates, with \(K=\infty\) signifying the algorithm does not terminate. By 10 we deduce that \(\min_{i \in [7]} \underaccent{\bar}{\alpha}_{k}^{(i)} < 1\) for all \(k \in [1,K)\). Using 9 and telescoping, we get: \[\begin{align} \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_1) -\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} ^\star &\ge \sum_{k=1}^{K-1} (\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) - \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_{k+1})) \\ &\geq (K-1) C\gamma\left( \frac{8 L_G^{2/3}}{(1 - C)^{2/3} \eta_1^{4/3}}{} \mu^{-5/3} + \mu^{-1} r(\mu) \right)^{-1}. \end{align}\] Rearranging the above inequality for \(K\) gives the desired result. ◻
3 Convergence analysis of our barrier method with annealing scheme↩︎
1 focused on the case that the barrier parameter \(\mu\) was fixed. Our annealing scheme is described in [alg:Full-IPM] which calls 1 which finds an approximate stationary interior point and decreases \(\mu\), as per a standard interior point method [4].
Condition 3 (Properties the new primal-dual iterate must satisfy when we decrease the barrier parameter). Suppose that the iterate \((\bar{\bar{x}}_{j+1}, \bar{\bar{y}}_{j+1})\) and barrier parameter \(\mu_{j+1}\) satisfy \[\label{eq:condition:new-x-y} \begin{align} \mu_{j+1} &\le \sigma\mu_j \\ a(\bar{\bar{x}}_{j+1}) &\ge 0 \\ \| \grad_x \mathcal{L}(\bar{\bar{x}}_{j+1}, \bar{\bar{y}}_{j+1}) \|&\le \kappa\mu_{j+1} \sqrt{1 + \| \bar{\bar{y}}_{j+1} \|_1} \label{eq:kappa-bound-gradient-of-Lagrangian} \\ \frac{1}{\kappa} \le & ~ \frac{a_i(\bar{\bar{x}}_{j+1}) [\bar{\bar{y}}_{j+1}]_i}{\mu_{j+1}} \le \kappa\quad \quad \forall i \in [q]. \label{eq:complementarity-bound} \end{align}\] {#eq: sublabel=eq:eq:condition:new-x-y,eq:eq:kappa-bound-gradient-of-Lagrangian,eq:eq:complementarity-bound} where \(\kappa\in (2,\infty)\) and \(\sigma\in [2/\kappa, 1)\) are algorithmic constants.
Given a point \((\bar{x}_{j+1}, \bar{y}_{j+1})\) that is a \(\mu_j\) approximate stationary interior point, i.e., satisfies 1, Condition 3 can be achieved trivially by setting \((\bar{\bar{x}}_{j+1}, \bar{\bar{y}}_{j+1}) = (\bar{x}_{j+1}, \bar{y}_{j+1})\) and \(\mu_{j+1} = \sigma\mu_{j}\). However, in practice, we will use a more sophisticated method, see [alg:decrease-barrier-parameter].
Input requirements: \(\bar{\bar{x}}_1 \in \mathbf{interior}(\mathcal{X})\), \(\mu_1 \in (0, \infty)\) Parameters: \(C\in (0, 1/2)\), \(\eta_1 \in (0, 1/2)\), \(\eta_2 \in (\eta_1, 1/2)\), \(\kappa\in (2,\infty)\), \(\sigma\in [2/\kappa, 1)\) Minimize the log barrier with a fixed barrier parameter: \((\bar{x}_{j+1}, \bar{y}_{j+1}) \gets \Call{AdaptiveLineSearchIPM}{\bar{\bar{x}}_j, \mu_j}\) Decrease barrier parameter \(\mu_{j+1}\) and find new starting point \(\bar{\bar{x}}_{j+1}\): Find \((\bar{\bar{x}}_{j+1}, \bar{\bar{y}}_{j+1})\) and barrier parameter \(\mu_{j+1}\) satisfying Condition 3, e.g., [alg:method-to-decrease-barrier-parameter]
Input requirements: \(\bar{x}_{j+1} \in \mathbf{R}^{n}, \bar{y}_{j+1} \in \mathbf{R}^{q}\), \(\mu_j \in (0,\infty)\), and \((\bar{x}_{j+1},\bar{y}_{j+1})\) satisfies 1 Parameter: \(\kappa\in (2,\infty)\), \(\sigma\in [2/\kappa, 1)\) \((x^{\mathrm{prev}},y^{\mathrm{prev}},\mu^{\mathrm{prev}}) \gets \left(\bar{x}_{j+1},\bar{y}_{j+1}, \sigma\mu_j\right)\) \(\hat{\mu}_t \gets \sigma^{t+1}\mu_j\) Calculate search direction \((d^{x},d^{y})\) via a typical primal-dual interior point search direction: \[\label{eq:typical-primal-dual-interior-point-search-direction} \begin{align} \bar{S}_{j+1} = \mathop{\boldsymbol{d}iag}(a(\bar{x}_{j+1})) \quad \bar{Y}_{j+1} &= \mathop{\boldsymbol{d}iag}(\bar{y}_{j+1}) \\ \grad_{xx}^2 \mathcal{L}(\bar{x}_{j+1},\bar{y}_{j+1}) d^{x} - \grad a(\bar{x}_{j+1})^\top d^{y} &= -\grad_x \mathcal{L}(\bar{x}_{j+1},\bar{y}_{j+1}) \\ \grad a(\bar{x}_{j+1}) d^{x} - d^{s} &= \mathbf{0}\\ \bar{S}_{j+1} d^{y} + \bar{Y}_{j+1} d^{s} &= \hat{\mu}_t \mathbf{1}- \bar{S}_{j+1} \bar{y}_{j+1}. \end{align}\tag{15}\] \((x^{\mathrm{trial}},y^{\mathrm{trial}}) \gets (\bar{x}_{j+1}+d^{x},\bar{y}_{j+1}+d^{y})\) \((x^{\mathrm{prev}},y^{\mathrm{prev}},\mu^{\mathrm{prev}})\) \((x^{\mathrm{prev}},y^{\mathrm{prev}},\mu^{\mathrm{prev}}) \gets (x^{\mathrm{trial}},y^{\mathrm{trial}},\hat{\mu}_t)\)
We provide guarantees for [alg:decrease-barrier-parameter] in terms of the total number of regularized Newton steps taken by the method for the unconstrained case (3) and constrained case (4) respectively. One regularized Newton step in [alg:Full-IPM] corresponds to an iteration of \(\Call{AdaptiveLineSearchIPM}{}\). Thus, we can use the total number of regularized Newton steps of [alg:Full-IPM] as a measure of its computational complexity.
To prove 3 and 4 we use a standard argument that after solving a barrier subproblem we can upper bound the suboptimality of a new barrier subproblem which we can use to reduce our estimate of the number of Newton steps required to solve the next subproblem. This is very similar to standard restart arguments [45] which are widespread in the optimization literature. In particular, we use 1 and 2 to establish 2 in the unconstrained and constrained setting respectively, and then employ 11, which is a generic result about the number of Newton steps taken by [alg:Full-IPM] when 2 holds to provide bounds on the number of iterations our method takes to find an \(\epsilon\)-approximately optimal solution in the unconstrained (3) and constrained case (4).
Assumption 2. Suppose that, for any \(x \in \mathbf{interior}(\mathcal{X})\) and \(\mu \in (0,\infty)\), the method
\(\Call{AdaptiveLineSearchIPM}{x, \mu}\) requires at most \(1 + (\ifthenelse{\isempty{}}
{\psi_{\mu}}
{\psi_{\mu_{}}}
(x) - \ifthenelse{\isempty{}}
{\psi_{\mu}}
{\psi_{\mu_{}}}
^\star) \mu^{-1} \theta(\mu)\) iterations to return a point satisfying 1 where \(\theta: (0,\infty) \rightarrow (0,\infty)\) is a nonincreasing function. Additionally, assume that there exists a constant \(W> 0\) such that \(\ifthenelse{\isempty{j+1}}
{\psi_{\mu}}
{\psi_{\mu_{j+1}}}
(\bar{\bar{x}}_{j+1}) - \ifthenelse{\isempty{j+1}}
{\psi_{\mu}}
{\psi_{\mu_{j+1}}}
^\star \le W\mu_{j+1}\) and \(f(\bar{\bar{x}}_{j+1}) - f_\star \le W\mu_{j+1}\) for all \(j \in \mathbf{N}\).
Lemma 11. Suppose 2 holds. Then, for any \(\epsilon \in (0,\infty)\), there exists an iterate \(\bar{\bar{x}}_{J+1}\) of [alg:Full-IPM] with \(J\le 2 + \log_{1/\sigma}( W\mu_1 / \epsilon + 1 / \sigma)\) such that \(f(\bar{\bar{x}}_{J+1}) - f_\star \le \epsilon\) and the total number of regularized Newton steps used by [alg:Full-IPM] to compute \(\bar{\bar{x}}_{J+1}\) is at most \[J+ W\sum_{j=0}^{J-2} \theta\left( \frac{\epsilon}{W\sigma^{j}} \right) + (\ifthenelse{\isempty{1}} {\psi_{\mu}} {\psi_{\mu_{1}}} (\bar{\bar{x}}_1) - \ifthenelse{\isempty{1}} {\psi_{\mu}} {\psi_{\mu_{1}}} ^\star) \mu_1^{-1} \theta(\mu_1).\]
Proof. First, observe that the number of iterations until \(\Call{AdaptiveLineSearchIPM}{\bar{\bar{x}}_1, \mu_1}\) terminates is at most \(1 + (\ifthenelse{\isempty{1}} {\psi_{\mu}} {\psi_{\mu_{1}}} (\bar{\bar{x}}_1) - \ifthenelse{\isempty{1}} {\psi_{\mu}} {\psi_{\mu_{1}}} ^\star) \mu_1^{-1} \theta(\mu_1)\). If \(\epsilon / W\ge \mu_1\) then the result holds with \(J= 1\) because \(\mu_2 \le \sigma\mu_1 < \epsilon / W\) and \(f(\bar{\bar{x}}_{2}) - f_\star \le W\mu_{2}\); so consider the case that \(\epsilon / W< \mu_1\). Since \(\mu_{j+1} \le \sigma\mu_j\) we deduce that there is an index \(J\le 2 + \log_{1/\sigma}( W\mu_1 / \epsilon + 1 / \sigma)\) such that \(\mu_{J+1} < \epsilon / W\le \mu_{J}\). Thus, the total number of regularized Newton steps of [alg:Full-IPM] across iterations \(j=2, \dots, J\) of [alg:Full-IPM] is at most \[\begin{align} \sum_{j=2}^{J} 1 + \frac{(\ifthenelse{\isempty{j}} {\psi_{\mu}} {\psi_{\mu_{j}}} (\bar{\bar{x}}_j) - \ifthenelse{\isempty{j}} {\psi_{\mu}} {\psi_{\mu_{j}}} ^\star) \theta(\mu_j)}{\mu_j} \underset{(i)}{\le} \sum_{j=2}^{J} 1 + W\theta(\mu_j) \underset{(ii)}{\le} \sum_{j=0}^{J-2} 1 + W\theta\left( \frac{\mu_{J}}{\sigma^{j}} \right) \underset{(iii)}{\le} J- 1 + W\sum_{j=0}^{J-2} \theta\left( \frac{\epsilon}{W\sigma^{j}} \right) \end{align}\] where \((i)\) uses \(\ifthenelse{\isempty{j}} {\psi_{\mu}} {\psi_{\mu_{j}}} (\bar{\bar{x}}_j) - \ifthenelse{\isempty{j}} {\psi_{\mu}} {\psi_{\mu_{j}}} ^\star \le W\mu_j\) for all \(j \ge 2\), \((ii)\) uses \(\mu_{j+1} \le \sigma\mu_j\) and the fact that \(\theta\) is nonincreasing, and \((iii)\) uses that \(\epsilon / W\le \mu_{J}\) and the fact that \(\theta\) is nonincreasing. Adding the bound for the first call to \(\Call{AdaptiveLineSearchIPM}{}\) gives the claimed bound on the regularized Newton steps. Furthermore, by \(f(\bar{\bar{x}}_{j+1}) - f_\star \le W\mu_{j+1}\) and \(\mu_{J+1} < \epsilon / W\), we get \(f(\bar{\bar{x}}_{J+1}) - f_\star \le W\mu_{J+1} < \epsilon\). ◻
3 provides a convergence guarantee for our algorithm in the unconstrained setting, showing that it matches the standard convergence \(O(\epsilon^{-1/2})\) bound [5]. This is a better rate than the \(O(\epsilon^{-2/3})\) result that we prove in the constrained setting.
Theorem 3 (Unconstrained case). Suppose that the problem is unconstrained, i.e., \(\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x) = f(x)\) and \(\grad^2 f\) is \(L_H\)-Lipschitz. Let \(D := \mathbf{diam}(\{ x \in \mathbf{R}^{n} : f(x) \le f(\bar{\bar{x}}_1) \})\) and let \(\hat{C} := C\cdot \eta_1 \cdot \min\{\gamma\cdot \sqrt{6(1- C) \eta_1} , \sqrt{2(1-2\eta_2)}\}\) be a problem-independent constant. Then, for any \(\epsilon \in (0,\infty)\), there exists an iterate \(\bar{\bar{x}}_{J+1}\) of [alg:Full-IPM] with \(J\le 2 + \log_{1/\sigma}( \kappa D \mu_1 / \epsilon + 1 / \sigma)\) such that \(f(\bar{\bar{x}}_{J+1}) - f_\star \le \epsilon\) and the total regularized Newton steps [alg:Full-IPM] uses to compute \(\bar{\bar{x}}_{J+1}\) is at most \[\frac{\hat{C}^{-1}\kappa^{3/2}}{1-\sqrt{\sigma}} \cdot \frac{L_H^{1/2} D^{3/2}}{\epsilon^{1/2}} + 2+\log_{1/\sigma}( \kappa D \mu_1 / \epsilon + 1 / \sigma) + \frac{\hat{C} ^ {-1} (f(\bar{\bar{x}}_1) - f_\star)L_H^{1/2}}{\mu_1^{3/2}}.\]
Proof. We will establish the result using 11. First, note that in the unconstrained case, Condition 3 implies \(\|\grad f(\bar{\bar{x}}_{j+1})\|_2 \le \kappa\mu_{j+1}\). Since the iterates remain in the initial sublevel set, convexity gives \(f(\bar{\bar{x}}_{j+1}) - f_\star \le \|\grad f(\bar{\bar{x}}_{j+1})\|_2 \|\bar{\bar{x}}_{j+1}-x^\star\|_2 \le \kappa D \mu_{j+1}\). Thus, 2 holds with \(W=\kappa D\). From 1 we have \(\theta(\mu) = \hat{C} ^ {-1} L_H^ {1/2} \mu ^ {-1/2}\). Thus, by the formula for the sum of an infinite geometric series, \[\begin{align} W\sum_{j=0}^{J-2} \theta\left( \frac{\epsilon}{W\sigma^{j}} \right) &= W\sum_{j=0}^{J-2}\hat{C}^{-1}L_H^{1/2}\left( \frac{\epsilon}{W\sigma^{j}} \right)^{-1/2} = \hat{C}^{-1}L_H^{1/2}W^{3/2}\epsilon^{-1/2}\sum_{j=0}^{J-2}\sigma^{j/2} \\ &\le \frac{\hat{C}^{-1}L_H^{1/2}W^{3/2}}{(1-\sqrt{\sigma})\epsilon^{1/2}} = \frac{\hat{C}^{-1}\kappa^{3/2}L_H^{1/2}D^{3/2}}{(1-\sqrt{\sigma})\epsilon^{1/2}}. \end{align}\] Moreover, by 11, \(J\le 2+\log_{1/\sigma}( \kappa D \mu_1 / \epsilon + 1 / \sigma)\). Finally, \((f(\bar{\bar{x}}_1)-f_\star)\mu_1^{-1}\theta(\mu_1) = \hat{C} ^ {-1} (f(\bar{\bar{x}}_1) - f_\star)L_H^{1/2}\mu_1^{-3/2}\). Combining these three bounds with 11 gives the result. ◻
Before proving our convergence guarantee in the constrained setting (4) we prove 12 which provides a bound on the norm of the dual variables when Condition 3 holds. This is useful to establish bounds on the suboptimality needed to show 2. To prove this result we use standard arguments [46] to leverage the existence of a Slater point, which is well-known to ensure that the dual variables are bounded [47].
Lemma 12 (Bound on the size of the dual multipliers). Suppose 1 holds. Define \(D_{\mathcal{X}} = \mathbf{diam}(\mathcal{X})\) and \(t:= \min_{i\in[q]}a_i(\hat{x})>0\), i.e., \(\hat{x}\) is a Slater point. Define \[\begin{align} \label{eq:bound-y-norm} \lambda := \frac{ \kappa D_{\mathcal{X}}\mu_1 + \sqrt{ \kappa^2D_{\mathcal{X}}^2\mu_1^2 + 4t \left( f(\hat{x})-f_\star + \kappa q\mu_1 + t \right) } }{ 2t }. \end{align}\qquad{(8)}\] If Condition 3 holds then \(\sqrt{1 + \| \bar{\bar{y}}_{j+1} \|_1} \le \lambda\).
Proof. Observe that \[\begin{align} t\|\bar{\bar{y}}_{j+1}\|_1 &\underset{(i)}{\le} \sum_{i=1}^{q}[\bar{\bar{y}}_{j+1}]_ia_i(\hat{x}) \underset{(ii)}{\le} \sum_{i=1}^{q}[\bar{\bar{y}}_{j+1}]_ia_i(\bar{\bar{x}}_{j+1}) + \left(\grad a(\bar{\bar{x}}_{j+1})^\top \bar{\bar{y}}_{j+1}\right)^\top (\hat{x}-\bar{\bar{x}}_{j+1}) \\ &\underset{(iii)}{\le} \sum_{i=1}^{q}[\bar{\bar{y}}_{j+1}]_ia_i(\bar{\bar{x}}_{j+1}) + \grad f(\bar{\bar{x}}_{j+1})^\top(\hat{x}-\bar{\bar{x}}_{j+1}) - \grad_x\mathcal{L}(\bar{\bar{x}}_{j+1},\bar{\bar{y}}_{j+1})^\top (\hat{x}-\bar{\bar{x}}_{j+1}) \\ &\underset{(iv)}{\le} \kappa q\mu_{j+1} + f(\hat{x})-f(\bar{\bar{x}}_{j+1}) + D_{\mathcal{X}}\|\grad_x\mathcal{L}(\bar{\bar{x}}_{j+1},\bar{\bar{y}}_{j+1})\|_2 \\ &\underset{(v)}{\le} \kappa q\mu_1 + f(\hat{x})-f_\star + \kappa D_{\mathcal{X}}\mu_1 \sqrt{1+\|\bar{\bar{y}}_{j+1}\|_1}. \end{align}\] where \((i)\) uses the Slater condition and \([\bar{\bar{y}}_{j+1}]_i>0\) for all \(i\in[q]\), \((ii)\) uses concavity of each \(a_i\), \([\bar{\bar{y}}_{j+1}]_i\ge 0\), \((iii)\) uses the identity \(\grad_x\mathcal{L}(\bar{\bar{x}}_{j+1},\bar{\bar{y}}_{j+1}) = \grad f(\bar{\bar{x}}_{j+1}) - \grad a(\bar{\bar{x}}_{j+1})^\top\bar{\bar{y}}_{j+1}\), \((iv)\) uses the complementarity upper bound in ?? , convexity of \(f\), and \(\|\hat{x}-\bar{\bar{x}}_{j+1}\|_2 \le D_{\mathcal{X}}\), and \((v)\) uses \(\mu_{j+1}\le \mu_1\), \(f(\bar{\bar{x}}_{j+1})\ge f_\star\), and the termination criterion for the gradient of the Lagrangian given in ?? . Rearranging the previous display gives \[t\left(1+\|\bar{\bar{y}}_{j+1}\|_1\right) - \kappa D_{\mathcal{X}}\mu_1 \sqrt{1+\|\bar{\bar{y}}_{j+1}\|_1} - \left( f(\hat{x})-f_\star + \kappa q\mu_1 + t \right) \le 0.\] Solving this quadratic inequality in \(\sqrt{1+\|\bar{\bar{y}}_{j+1}\|_1}\) gives \[\sqrt{1+\|\bar{\bar{y}}_{j+1}\|_1} \le \frac{ \kappa D_{\mathcal{X}}\mu_1 + \sqrt{ \kappa^2D_{\mathcal{X}}^2\mu_1^2 + 4t \left( f(\hat{x})-f_\star + \kappa q\mu_1 + t \right) } }{ 2t } = \lambda,\] which proves the result. ◻
4 is our main result which shows that the total number of regularized Newton steps used in [alg:Full-IPM] to find an \(\epsilon\)-optimal solution is \(O(\epsilon^{-2/3})\). It is a consequence of 2 which gives a bound on the number of Newton steps for each call to \(\Call{AdaptiveLineSearchIPM}{}\) allowing us to establish the premise of 11 using 12 and thus prove the result.
Theorem 4 (Constrained case). Suppose 1 holds. Define \(D_{\mathcal{X}} = \mathbf{diam}(\mathcal{X}) < \infty\). Let \(W:= \kappa\left(q+D_{\mathcal{X}} \lambda \right)\) where \(\lambda\) is defined in ?? , i.e., there exists a Slater point. Then, for any \(\epsilon\in(0,\infty)\), there exists an iterate \(\bar{\bar{x}}_{J+1}\) of [alg:Full-IPM] with \(J\le 2+\log_{1/\sigma} \left(\frac{W\mu_1}{\epsilon} + \frac{1}{\sigma}\right)\) such that \(f(\bar{\bar{x}}_{J+1})-f_\star\le \epsilon\), and the total number of regularized Newton steps used in [alg:Full-IPM] to compute \(\bar{\bar{x}}_{J+1}\) is at most \[\frac{8 L_G^{2/3} W^{5/3}}{(1 - C)^{2/3} \eta_1^{4/3} C\gamma(1-\sigma^{2/3})} \cdot \epsilon^{-2/3} + \ell(\epsilon),\] where \(\ell(\epsilon) = O(\log(1/\epsilon)\epsilon^{-3/5})\), in particular, \[\ell(\epsilon) := \frac{WJ}{C\gamma} r(W^{-1}\epsilon) + J + \frac{\ifthenelse{\isempty{1}} {\psi_{\mu}} {\psi_{\mu_{1}}} (\bar{\bar{x}}_1)-\ifthenelse{\isempty{1}} {\psi_{\mu}} {\psi_{\mu_{1}}} ^\star}{C\gamma\mu_1} \left( \frac{8 L_G^{2/3}}{(1 - C)^{2/3} \eta_1^{4/3}}{}\mu_1^{-2/3} + r(\mu_1) \right),\] and \(r(\mu)\), which is \(O(\mu^{-3/5})\), is defined in ?? .
Proof. We establish the result using 11. Let \(x_{\mu_{j+1}}^\star\in\mathop{\rm argmin}_{x\in \mathcal{X}}\ifthenelse{\isempty{j+1}} {\psi_{\mu}} {\psi_{\mu_{j+1}}} (x)\). Observe that for all \(u, v > 0\) we have \(u (1-v)+\log(v)\le \max\{1/u, u\}\), therefore setting \(u = \frac{[\bar{\bar{y}}_{j+1}]_i a_i(\bar{\bar{x}}_{j+1}) }{\mu_{j+1}}\) and \(v = \frac{a_i(x_{\mu_{j+1}}^\star)}{a_i(\bar{\bar{x}}_{j+1})}\) and employing \(\max\{1/u, u\} \le \kappa\) from ?? we get \[\begin{align} \label{eq:bound-y-mu-plus-log} \sum_{i=1}^{q} \frac{[\bar{\bar{y}}_{j+1}]_i ( a_i(\bar{\bar{x}}_{j+1})-a_i(x_{\mu_{j+1}}^\star) )}{\mu_{j+1}} - \sum_{i=1}^{q} \log( \frac{a_i(\bar{\bar{x}}_{j+1})}{a_i(x_{\mu_{j+1}}^\star)} ) \le \kappa q. \end{align}\tag{16}\] Then, \[\begin{align} \ifthenelse{\isempty{j+1}} {\psi_{\mu}} {\psi_{\mu_{j+1}}} (\bar{\bar{x}}_{j+1})-\ifthenelse{\isempty{j+1}} {\psi_{\mu}} {\psi_{\mu_{j+1}}} ^\star &\underset{(i)}{\le} \grad f(\bar{\bar{x}}_{j+1})^\top (\bar{\bar{x}}_{j+1}-x_{\mu_{j+1}}^\star) - \mu_{j+1} \sum_{i=1}^{q} \log\!\left( \frac{a_i(\bar{\bar{x}}_{j+1})}{a_i(x_{\mu_{j+1}}^\star)} \right) \\ &\underset{(ii)}{\le} \grad_x\mathcal{L}(\bar{\bar{x}}_{j+1},\bar{\bar{y}}_{j+1})^\top (\bar{\bar{x}}_{j+1}-x_{\mu_{j+1}}^\star) + \kappa q\mu_{j+1} \\ &\underset{(iii)}{\le} D_{\mathcal{X}}\|\grad_x\mathcal{L}(\bar{\bar{x}}_{j+1},\bar{\bar{y}}_{j+1})\|_2 + \kappa q\mu_{j+1} \\ &\underset{(iv)}{\le} \kappa D_{\mathcal{X}}\lambda\mu_{j+1} + \kappa q\mu_{j+1} = W\mu_{j+1}. \end{align}\] Here, \((i)\) uses the definition of \(\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}}\) and convexity of \(f\); \((ii)\) uses \(\grad f=\grad_x\mathcal{L}+\grad a^\top\bar{\bar{y}}_{j+1}\), concavity of each \(a_i\) and 16 ; \((iii)\) uses Cauchy-Schwarz and \(D_{\mathcal{X}} = \mathbf{diam}(\mathcal{X})\); and \((iv)\) uses ?? . Similarly, let \(x^\star\in\mathop{\rm argmin}_{x\in\mathcal{X}} f(x)\). Then, \[\begin{align} f(\bar{\bar{x}}_{j+1})-f_\star &\underset{(i)}{\le} \grad f(\bar{\bar{x}}_{j+1})^\top(\bar{\bar{x}}_{j+1}-x^\star) \underset{(ii)}{\le} D_{\mathcal{X}}\|\grad_x\mathcal{L}(\bar{\bar{x}}_{j+1},\bar{\bar{y}}_{j+1})\|_2 + \sum_{i=1}^{q} [\bar{\bar{y}}_{j+1}]_i (a_i(\bar{\bar{x}}_{j+1}) - a_i(x_\star)) \\ &\underset{(iii)}{\le} \kappa D_{\mathcal{X}}\lambda\mu_{j+1} + \kappa q\mu_{j+1} = W\mu_{j+1}. \end{align}\] Here, \((i)\) uses convexity of \(f\), \((ii)\) uses \(\grad f=\grad_x\mathcal{L}+\grad a^\top\bar{\bar{y}}_{j+1}\), concavity of each \(a_i\), \([\bar{\bar{y}}_{j+1}]_i\ge 0\), and \(\|\bar{\bar{x}}_{j+1}-x^\star\|\le D_{\mathcal{X}}\); and \((iii)\) uses \(a_i(x_{\star}) \ge 0\), Condition 3 and \(\sqrt{1+\|\bar{\bar{y}}_{j+1}\|_1}\le\lambda\) from 12. Thus, 2 holds with this value of \(W\).
By 2, \(\theta(\mu)= (C\gamma)^{-1} \left(\frac{8 L_G^{2/3}}{(1 - C)^{2/3} \eta_1^{4/3}}{}\mu^{-2/3}+r(\mu)\right)\). Therefore, 11 gives an iterate \(\bar{\bar{x}}_{J+1}\) with \(J\le 2+\log_{1/\sigma} \left( W\mu_1/\epsilon + 1/\sigma \right)\) such that \(f(\bar{\bar{x}}_{J+1})-f_\star\le\epsilon\), and the total number of regularized Newton steps is at most \[J + W \sum_{j=0}^{J-2} \theta\left( \frac{\epsilon}{W\sigma^j} \right) + (\ifthenelse{\isempty{1}} {\psi_{\mu}} {\psi_{\mu_{1}}} (\bar{\bar{x}}_1)-\ifthenelse{\isempty{1}} {\psi_{\mu}} {\psi_{\mu_{1}}} ^\star)\mu_1^{-1}\theta(\mu_1).\] Moreover, \[\begin{align} W \sum_{j=0}^{J-2} \theta\left( \frac{\epsilon}{W\sigma^j} \right) &= \frac{W}{C\gamma} \sum_{j=0}^{J-2} \left[ \frac{8 L_G^{2/3}}{(1 - C)^{2/3} \eta_1^{4/3}}{} \left( \frac{\epsilon}{W\sigma^j} \right)^{-2/3} + r\left( \frac{\epsilon}{W\sigma^j} \right) \right] \\ &\underset{(i)}{\le} \frac{\frac{8 L_G^{2/3}}{(1 - C)^{2/3} \eta_1^{4/3}}{}W^{5/3}}{C\gamma} \epsilon^{-2/3} \sum_{j=0}^{\infty}\sigma^{2j/3} + \frac{WJ}{C\gamma} r(W^{-1}\epsilon) \\ &= \frac{\frac{8 L_G^{2/3}}{(1 - C)^{2/3} \eta_1^{4/3}}{}W^{5/3}}{C\gamma(1-\sigma^{2/3})} \epsilon^{-2/3} + \frac{WJ}{C\gamma} r(W^{-1}\epsilon), \end{align}\] where \((i)\) uses that \(r\) is nonincreasing and \(\epsilon/(W\sigma^j)\ge \epsilon/W\). Finally, \[(\ifthenelse{\isempty{1}} {\psi_{\mu}} {\psi_{\mu_{1}}} (\bar{\bar{x}}_1)-\ifthenelse{\isempty{1}} {\psi_{\mu}} {\psi_{\mu_{1}}} ^\star)\mu_1^{-1}\theta(\mu_1) = \frac{\ifthenelse{\isempty{1}} {\psi_{\mu}} {\psi_{\mu_{1}}} (\bar{\bar{x}}_1)-\ifthenelse{\isempty{1}} {\psi_{\mu}} {\psi_{\mu_{1}}} ^\star}{C\gamma\mu_1} \left( \frac{8 L_G^{2/3}}{(1 - C)^{2/3} \eta_1^{4/3}}{}\mu_1^{-2/3} + r(\mu_1) \right).\] Combining the last three displays proves the result. ◻
4 Numerical results↩︎
This section compares our method against IPOPT [3] and variants of our interior point method with our regularized Newton method with line search replaced by ARC [48] and AdaN [16]. The latter methods allows us to measure the effectiveness of our regularized Newton method with line search for solving the barrier subproblem. Our method is competitive with IPOPT, while generally outperforming the variants of our interior point method which use ARC or AdaN as the subproblem solver.
4.0.0.1 Computing resources
The experiments are performed in a single-threaded environment on a Linux virtual machine that has an Intel(R) Core(TM) i5-3470 CPU 3.20GHz and 16 GB RAM.
4.0.0.2 Default parameters.
Unless stated otherwise, all runs of our method and ARC use the parameter values listed in Table 1. The initial barrier parameter is \(\mu_1 = 10^{-3}\) and the outer loop terminates when \(\mu_j \leq \bar{\mu}= 10^{-6}\). The maximum number of iterations is \(100,000\) and the wall-clock time limit is 3,600 seconds per instance.
| Parameter | Symbol | Value | Introduced in |
|---|---|---|---|
| Sufficient decrease (I) | \(\eta_1\) | \(2.0\times 10^{-1}\) | [condition:search-dir] |
| Sufficient decrease (II) | \(\eta_2\) | \(2.5\times 10^{-1}\) | [condition:search-dir] |
| Armijo constant | \(\SufficientConstant\) | \(10^{-4}\) | [step-size-condition] |
| Backtracking factor | \(\backtrackingFactor\) | \(5.0\times 10^{-1}\) | [step-size-condition,alg:compute-step-size] |
| Inflation factor | \(\kappa\) | \(8\) | [condition:new-x-y] |
| Initial barrier parameter | \(\mu_1\) | \(10^{-3}\) | [alg:Full-IPM] |
| Barrier reduction factor | \(\sigma\) | \(2.5\times 10^{-1}\) | [condition:new-x-y,alg:decrease-barrier-parameter] |
| Stopping tolerance | \(\StoppingTolerance\) | \(10^{-6}\) | [par:default-parameters] |
| Regularization cold start scale | \(\ColdStartScale\) | \(5.0\times 10^{-1}\) | [rem:actual-search-direction-implementation] |
| Regularization full step shrinkage | \(\RegularizationShrink\) | \(2.0\times 10^{-1}\) | [rem:actual-search-direction-implementation] |
| Line search target reduction | \(\StartingTargetReduction\) | \(1\) | [prop:line-search-iteration-bound] |
4.0.0.3 Datasets
The problem instances draw from standard benchmark datasets, including binary classification tasks from LIBSVM (http://www.csie.ntu.edu.tw/~cjlin/libsvm) and public email corpora.
w8a: 49,749 samples, 300 sparse features. Labels are \(\pm 1\) (web page classification).
a9a: 32,561 samples, 123 features (Adult census-income). Approximately 24% of labels are positive.
Phishing websites: The LIBSVM phishing dataset, represented by 68 website features and binary labels.
SpamAssassin: A public email corpus categorized by collection period and classification difficulty, tokenized into a 500-word vocabulary.
4.0.0.4 Test problems
We evaluate our method on a small set of nonlinear convex optimization problems. These specific formulations were selected because they are not naturally or easily reformulatable as standard conic programs (e.g., semidefinite or second-order cone constraints), making general nonlinear optimization an attractive approach. Furthermore, for each of these formulations, it is straightforward to identify a strictly feasible starting point, which is required for our method.
LSE_Hard. A constrained log-sum-exp regression on the w8a dataset. The problem is formulated as follows: \[\begin{align} \min_{x \in \mathbb{R}^d} \quad & \rho \log \left( \sum_{i=1}^{n} \exp{\left( \frac{a_i^\top x - b_i}{\rho} \right)} \right) \\ \text{s.t.} \quad & a_j^\top x \leq b_j, \quad j = n+1, \ldots, 2n, \end{align}\] where \(a_1,\ldots,a_{2n} \in \mathbb{R}^d\) are vectors and \(\rho, b_1,\ldots,b_{2n}\) are scalars. The objective serves as a smooth approximation of the maximum function \(\max \{a_1^\top x - b_1, \ldots, a_n^\top x - b_n\}\), with the scalar \(\rho\) controlling the tightness of the approximation. We utilize the same foundational log-sum-exp formulation evaluated in [16]; however, while their formulation was strictly for unconstrained optimization, we modified the problem to include constraints by partitioning the dataset such that half of the samples define the objective, and the remaining half form explicit linear constraints. For our experiments, we set \(d=300\), \(n=500\) (resulting in 500 objective terms and 500 constraints), and \(\rho = 0.01\).
NP_Adult. A Neyman-Pearson (NP) classification problem [49] on the a9a dataset with training samples partitioned into positive and negative classes: \[\min_{w} \; \frac{1}{n_+}\sum_{y_i=+1} \log\!\bigl(1+e^{-w^\top x_i}\bigr) \quad \text{s.t.} \quad \frac{1}{n_-}\sum_{y_i=-1} \log\!\bigl(1+e^{+w^\top x_i}\bigr) \leq \alpha, \quad \|w\|_2^2 \leq R^2,\] with \(\alpha = 0.75\) and \(R = 3\). This objective directly addresses asymmetric costs by minimizing the false-negative rate (FNR) surrogate subject to a strict false-positive rate (FPR) budget and an \(\ell_2\)-norm ball regularizer.
Robust Empirical Risk Minimization (ERM) with Feature Partitions. Robust ERM instances [50] model scenarios where training data is drawn from heterogeneous subgroups, formulated as a minimax problem over the logistic loss to identify a single shared classifier that guarantees uniformly low loss across all groups. There are three variants of this problem:
RobustERM_Spam. Uses the SpamAssassin public corpus partitioned into \(K=4\) email-type groups based on their directory source: early spam (collected in 2002), later spam (collected in 2003), easy ham4, and hard ham. By treating the degree of classification difficulty and collection period as unobserved domains at runtime, this problem tests the method’s ability to handle natural distribution shifts in textual data represented by a 500-word vocabulary space.
RobustERM_Phishing. Evaluated on the LIBSVM phishing website dataset, where samples are partitioned into \(K=4\) groups using two website-feature indicators selected to match the expected prevalences of SSL-state and URL-anchor attributes. These grouping features are removed from the optimization feature matrix.
RobustERM_Education. A robust ERM formulation on the a9a census dataset, partitioned into \(K=4\) groups representing distinct education levels (Bachelors, Some-college, High School graduate, and a residual). The education features are omitted from the regression.
4.0.0.5 Results
Table 2 reports our results. Overall, our method is faster than IPOPT on three of five instances, although notably slower on RobustERM_Spam.
Both AdaN and ARC are consistently slower and use many more factorizations our method (with the exception of AdaN on LSE_Hard). The poor performance of these methods is not unexpected. In particular, these methods were designed for
objectives with Lipschitz-continuous Hessians. They maintain a regularization parameter that represents an estimate of the local Lipschitz constant of the Hessian. The log barrier Hessian is not Lipschitz continuous, so this local constant varies widely
throughout the methods trajectories. We believe that repeatedly adapting this regularization parameter to these variations is triggering their large number of factorizations.
| Number of evaluations of | time | ||||||
| Instance | Method | \(f\) | \(\cons\) | \(\grad f\) | \(\grad^2_{xx} \Lag\) | #fact. | (s) |
| LSE_Hard | Our Method | 83 | 78 | 30 | 29 | 114 | 20.3 |
| ARC | 37 | 58 | 27 | 21 | 6017 | 27.1 | |
| AdaN | 63 | 42 | 67 | 36 | 61 | 51.5 | |
| IPOPT | 972 | 969 | 76 | 76 | 104 | 58.7 | |
| Our Method | 43 | 66 | 48 | 42 | 42 | 6.0 | |
| ARC | 89 | 171 | 83 | 75 | 16023 | 13.6 | |
| AdaN | 118 | 56 | 123 | 46 | 115 | 9.6 | |
| IPOPT | 15 | 15 | 15 | 14 | 17 | 5.6 | |
| Our Method | 95 | 124 | 104 | 94 | 94 | 130.9 | |
| ARC | 57 | 111 | 57 | 43 | 6047 | 128.1 | |
| AdaN | 410 | 173 | 418 | 156 | 404 | 311.3 | |
| IPOPT | 17 | 17 | 17 | 16 | 16 | 76.7 | |
| Our Method | 5 | 35 | 27 | 4 | 4 | 0.2 | |
| ARC | 12 | 27 | 16 | 8 | 19 | 1.2 | |
| AdaN | 41 | 17 | 49 | 6 | 39 | 1.1 | |
| IPOPT | 6 | 6 | 6 | 5 | 5 | 0.7 | |
| Our Method | 19 | 56 | 27 | 18 | 18 | 2.5 | |
| ARC | 36 | 74 | 39 | 27 | 3929 | 6.6 | |
| AdaN | 144 | 64 | 151 | 52 | 141 | 12.4 | |
| IPOPT | 47 | 47 | 19 | 18 | 18 | 6.3 | |
5 Discussion and future work↩︎
We emphasize that the primary contribution of this work is theoretical: we establish convergence guarantees for the proposed method under mild assumptions, whereas IPOPT, while practically effective, does not come with the same theoretical guarantees in the general convex constrained setting. The above experiments are therefore preliminary computational experiments intended to demonstrate that the method is a step toward a viable practical method. However, important issues remain:
Modification of the method to be pure primal-dual. Since pure primal-dual interior point methods dominate practical interior point implementations [3], [32], this is likely to improve performance.
Handling infeasible starts. There are many problems where it is not easy to find a feasible starting solution, or the feasible region lacks an interior. To handle such cases one could potentially integrate the method with a penalty or shifted log barrier approach.
Handling nonconvexity. While this paper builds on [10] which handles nonconvex constraints but requires problem parameters as input, this work only covers the convex case (although it does obtain better guarantees). Extending the method and analysis to the nonconvex setting is an important topic for future research.
Ultimately, we believe our work will pave the way for the development of practical log barrier methods for general nonconvex constrained optimization with strong worst-case guarantees. In the long term, we hope this will help improve the robustness and reliability of these nonconvex interior-point methods [2], [3], which are widely used in practice [51].
6 Acknowledgments↩︎
The authors were supported by AFOSR grant #FA9550-23-1-0242. The authors would like to thank Lorenz Biegler for his helpful feedback on a draft of this paper. The authors would also like to thank Akif Khan for identifying errors in an early draft and for the helpful discussions.
7 A method for satisfying Condition 1↩︎
In this section, we detail our approach to satisfying Condition 1. The key idea is to perform a bisection search to find the root function \(\phi_k\) defined in 4 . Before presenting our algorithm and its guarantees we first present 13 which identifies the useful properties of \(\phi_k\).
Lemma 13. For \(\delta > 0\), define \(d(\delta):= -(\grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) + \delta \boldsymbol{I})^{-1} \grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) \text{ and } \phi_k(\delta) := \varepsilon_k^{-1} \delta \|d(\delta)\|_2\) with \(\| \grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) \|_2 \ge \varepsilon_k > 0\). Let \(\eta_1, \eta_2 \in (0, 1)\) and \(C\in (0,1)\). For all \(\delta, \delta' > 0\) such that \(\delta \le \delta'\) we have \(\phi_k(\delta) \le \phi_k(\delta')\) and \(\delta \phi_k(\delta') \le \delta' \phi_k(\delta)\). Moreover, if \(\delta \ge \frac{\eta_1}{1 - \eta_1} \| \grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) \|_2\) then \(\phi_k(\delta) \ge \eta_1\). If \(\delta \le \eta_2^2 C\varepsilon_k^2 (\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) - \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} ^\star)^{-1}\) then either \[\begin{align} \label{eq:general-delta-eta1-condition} \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k + d(\delta)) > \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) + C\cdot \mathcal{M}_k(d(\delta)) \quad \boldsymbol{or} \quad \phi_k(\delta) \le \eta_2. \end{align}\qquad{(9)}\]
Proof. Let \(Q \Lambda Q^\top\) be the eigendecomposition of \(\grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k)\), i.e., \(\grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) = Q \Lambda Q^\top\). Denote the corresponding eigenvalues, i.e., the diagonal entries of \(\Lambda\) as \(\lambda_1,\ldots,\lambda_{n}\) which are nonnegative by convexity of \(\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}}\). Let \(\hat{g} = Q^\top \grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k)\). Then, \[\begin{align} \label{eq:phi-formula} \phi_k(\delta)^2 = \varepsilon_k^{-2} \delta^2 \| d(\delta)\|_2^2 = \varepsilon_k^{-2} \delta^2 \| (\Lambda + \delta \boldsymbol{I})^{-1} \hat{g} \|_2^2 = \sum_{i=1}^{n} \left(\frac{\delta}{\varepsilon_k (\lambda_i+\delta)} \right)^2 [\hat{g}]_i^2 . \end{align}\tag{17}\] Consider \(\delta,\delta'\) such that \(0 < \delta \le \delta'\), then for each \(i\), we have \[\frac{\delta}{\lambda_i+\delta} \le \frac{\delta'}{\lambda_i+\delta'} \le \frac{\delta'}{\lambda_i+\delta} = \frac{\delta'}{\delta} \cdot \frac{\delta}{\lambda_i+\delta}.\] The first inequality follows from monotonicity of \(\delta \mapsto \delta/(\lambda_i+\delta)\) because \(\lambda_i \ge 0\). The first inequality and 17 also show that \(\phi_k\) is nondecreasing. Therefore, by 17 we have \[\phi_k(\delta')^2 = \sum_{i=1}^{n} \left(\frac{\delta'}{\varepsilon_k (\lambda_i+\delta')} \right)^2 [\hat{g}]_i^2 \le \sum_{i=1}^{n} \left(\frac{\delta'}{\delta} \cdot \frac{\delta}{\varepsilon_k (\lambda_i+\delta)} \right)^2 [\hat{g}]_i^2 = \left(\frac{\delta'}{\delta} \phi_k(\delta) \right)^2.\] Thus, \(\delta \phi_k(\delta') \le \delta' \phi_k(\delta)\) as desired.
If \(\delta \ge \frac{\eta_1}{1 - \eta_1} \| \grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) \|_2\) then by \((i)\) \(\| \grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) \|_2 = \| ( \grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) + \delta \boldsymbol{I}) (\grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) + \delta \boldsymbol{I})^{-1} \grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) \|_2 \\ \le (\delta + \| \grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) \|_2) \| (\grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) + \delta \boldsymbol{I})^{-1} \grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) \|_2\), \((ii)\) \(\| \grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) \| \ge \varepsilon_k\), and \((iii)\) \(\delta \ge \frac{\eta_1}{1 - \eta_1} \| \grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) \|_2\) we have \[\phi_k(\delta) = \varepsilon_k^{-1} \delta \| (\grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) + \delta \boldsymbol{I})^{-1} \grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) \|_2 \underset{(i)}{\ge} \varepsilon_k^{-1} \delta \frac{\| \grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) \|_2}{\delta + \| \grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) \|_2} \underset{(ii)}{\ge} \frac{\delta}{\delta + \| \grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) \|_2} \underset{(iii)}{\ge} \eta_1.\] If \(\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k + d(\delta)) \le \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) + C\mathcal{M}_k(d(\delta))\) then \[\begin{align} \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) - \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} ^\star & \ge \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) - \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k + d(\delta)) \ge -C\mathcal{M}_k(d(\delta)) = -C\grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k)^\top d(\delta)- \frac{C}{2}d(\delta)^\top \grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k)d(\delta)\\ &\underset{(i)}{=} \frac{C}{2}d(\delta)^\top \grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k)d(\delta)+ C\delta \| d(\delta)\|^2 \underset{(ii)}{\ge} C\delta \| d(\delta)\|^2 = \frac{C\varepsilon_k^2}{\delta} \phi_k(\delta)^2. \end{align}\] where \((i)\) uses ?? and \((ii)\) uses \(\grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) \succeq 0\). If \(\delta \le \eta_2^2 C\varepsilon_k^2 (\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) - \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} ^\star)^{-1}\) then rearranging the previous inequality gives \(\phi_k(\delta) \le \sqrt{\delta \cdot \frac{\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) - \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} ^\star}{C\varepsilon_k^2}} \le \eta_2\) as desired. ◻
\(\tilde{\delta}\in (0,\infty)\); \(\delta_{\max} \in [\tilde{\delta}, \infty)\), \(\eta_1 \in (0,1/2)\), \(\eta_2 \in (\eta_1,1)\), \(C\in (0,1)\) \((\ell,u) \gets \Call{FindSearchInterval}{\tilde{\delta}, \delta_{\max}, \eta_1, \eta_2}\) \(\Call{GeometricBisectionSearch}{\ell,u, \eta_1, \eta_2}\)
\(a_{1} \gets \tilde{\delta}\), \(v_{a_{1}} \gets \phi_k(\tilde{\delta})\), \(b_{1} \gets \tilde{\delta}\), \(v_{b_{1}} \gets v_{a_{1}}\) \(r \gets \begin{cases} 2, & v_{a_{1}} <\eta_1,\\ 1/2, & \text{otherwise}, \end{cases}\) \((b_{i},b_{i})\) \((\min\{a_{i},b_{i}\},\max\{a_{i},b_{i}\})\) \(a_{i+1} \gets b_{i}\), \(v_{a_{i+1}} \gets v_{b_{i}}\), \(b_{i+1} \gets \min\{\delta_{\max}, \tilde{\delta}r^{2^{(i-1)/2}} \}\), \(v_{b_{i+1}} \gets \phi_k(b_{i+1})\)
\(\ell_1\) \(\delta_{\mathbf{mid}}\gets \sqrt{\ell_j u_j}\), \(v_m \gets \phi_k(\delta_{\mathbf{mid}})\) \(\delta_{\mathbf{mid}}\) \(\ell_{j+1} \gets \delta_{\mathbf{mid}}\), \(u_{j+1} \gets u_j\) \(\ell_{j+1} \gets \ell_j\), \(u_{j+1} \gets \delta_{\mathbf{mid}}\)
Proposition 1. Let \(\| \grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) \|_2 \ge \varepsilon_k > 0\) and \(\delta_{\max} \ge \frac{\eta_1}{1-\eta_1}\| \grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) \|_2\). Then, the total number of evaluations of \(\phi_k\) used by [alg:compute-regularized-parameter] is at most \[6 +3 \log_2\log_2 N_k + \log_2\!\left( 1 + \frac{1}{\log_2(\eta_2^2/\eta_1^2)} \right) ~\text{ where }~ N_k := \max\left\{ 2, \frac{\eta_1 \| \grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) \|_2}{(1-\eta_1)\tilde{\delta}}, \frac{\tilde{\delta}(\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) - \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} ^\star)}{\eta_2^2 C\varepsilon_k^2} \right\}.\]
Proof. We begin by analyzing the runtime of FindSearchInterval. Let \(i_\star\) be the number of iterations used by its loop, let \(A_k:=\frac{\eta_1}{1-\eta_1}\| \grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) \|_2\), and let \(B_k:=\eta_2^2 C\varepsilon_k^2 (\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k)-\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} ^\star)^{-1}\). Consider the case that \(\phi_k(\tilde{\delta}) = v_{a_{1}} \in [\eta_1,\eta_2]\), then by Line [alg-line:sufficient-decrease-fails-or-eta1-good-and-eta-2-good] we have \(i_\star=1\). Consider the case that \(\phi_k(\tilde{\delta}) = v_{a_{1}} < \eta_1\). If \(v_{a_{i}} \le \eta_1\) and \(\eta_1 \le v_{b_{i}}\), then by Line [alg-line:sufficient-decrease-fails-or-eta1-good-and-eta-2-good] or Line [alg-line:good-interval] the for loop ends. Thus since \(\phi_k(\tilde{\delta}) = v_{a_{1}} < \eta_1\) the first index \(i\) with \(\eta_1 \le v_{b_{i}}\) must also have \(v_{a_{i}} < \eta_1\), triggering the end of the loop; by 13 this occurs no later than the first index with \(b_{i}\ge A_k\). Since \(b_{i-1}= \tilde{\delta}2^{2^{(i-3)/2}} < A_k\) for \(i \in [3,i_\star]\) and \(N_k\ge\max\{2,A_k/\tilde{\delta}\}\), we get \(i_\star < 3 + 2 \log_2 \log_2 N_k\). On the other hand, consider the case that \(\phi_k(\tilde{\delta}) = v_{a_{1}} > \eta_2\). If \(v_{b_{i}} \le \eta_2\) and \(\eta_2 \le v_{a_{i}}\), or \(\eta_1 \le v_{b_{i}}\) and \(\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k + d(b_{i})) > \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) + C\mathcal{M}_k( d(b_{i}))\), then by Line [alg-line:sufficient-decrease-fails-or-eta1-good-and-eta-2-good] or Line [alg-line:good-interval] the for loop ends. Since \(v_{a_{1}} > \eta_2\), the first index with \(v_{b_{i}} \le \eta_2\) or \(\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k + d(b_{i})) > \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) + C\mathcal{M}_k( d(b_{i}))\) will trigger the for loop to end; by 13, this occurs no later than the first index with \(b_{i}\le B_k\). Since \(b_{i-1}=\tilde{\delta}2^{-2^{(i-3)/2}} > B_k\) for \(i \in [3,i_\star]\) and \(N_k\ge\max\{2,\tilde{\delta}/B_k\}\), this also gives \(i_\star < 3 + 2 \log_2 \log_2 N_k\).
Next, we analyze GeometricBisectionSearch. Let \(j_\star\) be the number of iterations used by its loop with \(j_\star = 0\) denoting the case that \(\ell_1 = u_1\) and consider the nontrivial case that \(j_\star > 1\). Since \(\ell_1<u_1\), by construction and monotonicity of \(\phi_k\), we have \(\phi_k(\ell_1)\le\eta_1\) and \(\phi_k(u_1)\ge\eta_2\), and these inequalities are maintained until termination. Observe that, if \(u_j / \ell_j \le \eta_2^2 / \eta_1^2\) then by 13 we have \[\eta_1 \le \eta_2 \frac{\ell_j}{\sqrt{\ell_j u_j}} \le \frac{\ell_j}{\sqrt{\ell_j u_j}} \phi_k(u_j) \le \phi_k(\sqrt{\ell_j u_j}) \le \frac{u_j}{\sqrt{\ell_j u_j}} \phi_k(\ell_j) \le \eta_1 \frac{u_j}{\sqrt{\ell_j u_j}} \le \eta_2\] which implies GeometricBisectionSearch terminates at this iteration with \(\delta_{\mathbf{mid}}= \sqrt{\ell_j u_j}\), i.e., \(j = j_\star\). Thus, for \(j \in [2,j_\star]\) we have \(\log_2(\eta_2^2 / \eta_1^2) < \log_2(u_{j-1} / \ell_{j-1}) = 2^{2-j} \log_2(u_1 / \ell_1)\) where the equality holds from induction on \(\log_2(u_j/\ell_j) = 2^{-1} \log_2(u_{j-1}/\ell_{j-1})\). Rearranging this inequality with \(j = j_\star\), it follows that \[j_\star<2+\log_2\!\left(\frac{\log_2(u_1/\ell_1)}{\log_2(\eta_2^2/\eta_1^2)}\right) \underset{(i)}{\le} 2+\log_2\!\left(\frac{\max\{2^{(i_\star - 2) / 2}, 1\}}{\log_2(\eta_2^2/\eta_1^2)}\right) = \max\left\{ 1 + \frac{i_\star}{2}, 2 \right\} + \log_2\!\left(\frac{1}{\log_2(\eta_2^2/\eta_1^2)}\right)\] where \((i)\) uses that \(u_1 / \ell_1 \le \max\{ 2^{2^{(i_\star - 2) / 2}}, 1\}\) from definition of FindSearchInterval. Since FindSearchInterval evaluates \(\phi_k\) exactly \(i_\star\) times and GeometricBisectionSearch evaluates \(\phi_k\) exactly \(j_\star\) times, adding their bounds together gives the desired result. ◻
Remark 2 (Actual implementation of the search direction). [alg:compute-regularized-parameter] does not specify how to choose \(\tilde{\delta}\). We first check if ?? holds with \(\delta_k = 0\), if so we use \(\delta_k = 0\), otherwise we set \[\tilde{\delta}\gets \begin{cases} \delta_{\max} \rho_{c}/ \sqrt{n} & \delta_{k-1} = 0 \text{ or } k = 0 \\ \min\{ \delta_{k-1}, \delta_{\max} \} & \delta_{k-1} \neq 0, ~\alpha_{k-1} < 1 \\ \min\{ \rho_{s}\delta_{k-1}, \delta_{\max} \} & \delta_{k-1} \neq 0, ~\alpha_{k-1} = 1 \end{cases}\] where \(\delta_{\max} = \frac{\eta_1}{1 - \eta_1} \| \grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x) \|_F\), \(\rho_{s}\in (0,1)\), and \(\rho_{c}\in (0,\infty)\). We then call [alg:compute-regularized-parameter] with this value of \(\tilde{\delta}\) and \(\delta_{\max}\).
8 A line search routine for satisfying Condition 2↩︎
2 provides a standard line search routine for computing the step size. The routine starts from an initial guess of the step size \(\hat{\alpha}_{k}\) and either increases the step size (i.e., forward tracks) or decreases the step size (i.e., backtracks) in search of a step size that satisfies Condition 2. 2 provides guarantees on the number of iterations this routine requires. 2 specifies that \(\hat{\alpha}_{k}= \min\{\tau/(-M_k), 1\}\) where \(\tau\in (0,\infty)\). It is natural to select \(\hat{\alpha}_{k}= 1\), in which case the line search is pure backtracking but this can be problematic, for example, if \(\grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) = 0\) and \(\delta_k\) is chosen to be very small, then it is possible that only an exceptionally small step size satisfies the sufficient decrease conditions, which could take a backtracking method a long time to find.
Fact 2 (Well-known). If Condition 1 holds then \(-\grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k)^\top d^{x}_k \le -2 M_k\).
Proof. Substituting \(\grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) d^{x}_k = - \grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) - \delta_k d^{x}_k\) from ?? into \(M_k= \grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k)^\top d^{x}_k + \frac{1}{2} (d^{x}_k)^\top \grad^2 \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k) d^{x}_k\) gives \(M_k= \frac{1}{2} \grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k)^\top d^{x}_k - \frac{\delta_k}{2} \| d^{x}_k \|_2^2\). Using \(\delta_k \ge 0\) gives the desired result. ◻
Proposition 2. Suppose \(d^{x}_k\) satisfies Condition 1. If \(\grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k)^\top d^{x}_k < 0\), and \(\hat{\alpha}_{k}= \min\{\tau/(-M_k), 1\}\) then 2 terminates with a step size \(\alpha_k=\alpha_{k,j}\) satisfying, Condition 2. Moreover, if backtracking branch (Line [line:backtracking-branch]) is entered then \(j \le \log_{1/\gamma} \frac{2\tau}{\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k)-\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_{k+1})}\) and if the forward tracking branch (Line [line:forwardtracking-branch]) is entered then \(j \le \max\left\{0, 1 + \log_{1/\gamma} \frac{2 (\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k)-\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} ^\star)}{C\tau} \right\}\).
Proof. Fix \(k\), and let \(j\) be the value of \(j\) returned by Algorithm 2. Since \(\grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k)^\top d^{x}_k<0\) and \(C< 1\), we conclude by Taylor’s theorem that for sufficiently small \(\alpha\) the sufficient decrease condition holds. Moreover, by construction 2 terminates with a point satisfying Condition 2.
It remains to bound \(j\). First, consider the case that the backtracking branch is entered (Line [line:backtracking-branch]). Then, by \((i)\) convexity of \(\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}}\), \((ii)\) definition of \(\hat{\alpha}_{k}\), and \((iii)\) 2, \[\begin{align} \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k)-\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_{k+1}) &\underset{(i)}{\le} -\alpha_{k,j}\grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k)^\top d^{x}_k = -\gamma^j \hat{\alpha}_{k} \grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k)^\top d^{x}_k \underset{(ii)}{\le} \frac{\gamma^j \tau\grad \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k)^\top d^{x}_k}{M_k} \underset{(iii)}{\le} 2 \gamma^j \tau. \end{align}\] Rearranging yields \(j \le \log_{1/\gamma} \frac{2\tau}{\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k)-\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_{k+1})}\) as desired.
Next, consider the case that the forward tracking branch is entered (Line [line:forwardtracking-branch]). If \(j = 0\) then the result trivially holds. On the other hand, if \(j > 0\) then \(\hat{\alpha}_{k}= \tau/ (-M_k)\) and \[\begin{align} \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k)-\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_{k} + \alpha_{k,j-1}d^{x}_k) &\underset{(i)}{\ge} -C\mathcal{M}_k(\alpha_{k,j-1}d^{x}_k) \underset{(ii)}{\ge} -\frac{C\alpha_{k,j-1} M_k}{2} \underset{(iii)}{=} -\frac{CM_k}{2} \cdot \frac{\gamma^{1-j} \tau}{-M_k} = \frac{C\tau\gamma^{1-j}}{2}. \end{align}\] where \((i)\) holds by Line [line:forwardtracking-branch], Line [line:forwardtracking-update] and the definition of , \((ii)\) 1 and \((iii)\) \(\hat{\alpha}_{k}= \tau/ (-M_k)\) and \(\alpha_{k,j-1} = \hat{\alpha}_{k}\gamma^{1-j}\). Rearranging and using \(\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_{k} + \alpha_{k,j-1}d^{x}_k) \ge \ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} ^\star\) gives the desired result. ◻
Remark 3. The \(\log_{1/\gamma} \frac{2\tau}{\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k)-\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_{k+1})}\) term in the bound on \(j\) from 2 could be large if \(\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k)-\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_{k+1})\) was very tiny. However, we can employ the lower bounds on \(\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k)-\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_{k+1})\) from the body of the paper to rule out this possibility. If \(\min_{i \in [7]} \underaccent{\bar}{\alpha}_{k}^{(i)} < 1\) then 9 shows that \(\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k)-\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_{k+1})\) is bounded below proportional to \(\mu^{5/3}\). On the other hand, if \(\min_{i \in [7]} \underaccent{\bar}{\alpha}_{k}^{(i)} \ge 1\) then \(\alpha_k = 1\) by 8 which implies that the forward tracking branch was entered and thus \(j \le \max\left\{0, 1 + \log_{1/\gamma} \frac{2 (\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} (x_k)-\ifthenelse{\isempty{}} {\psi_{\mu}} {\psi_{\mu_{}}} ^\star)}{C\tau} \right\}\).
References↩︎
[1]
Y. Nesterov and A. Nemirovskii, Interior-point polynomial algorithms in convex programming. SIAM, 1994.
[2]
R. J. Vanderbei, “LOQO user’s manual—version 3.10,” Optimization methods and software, vol. 11, no. 1–4, pp. 485–514, 1999.
[3]
A. Wächter and L. T. Biegler, “On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming,” Mathematical
programming, vol. 106, no. 1, pp. 25–57, 2006.
[4]
J. Nocedal and S. Wright, Numerical optimization. New York: Springer Science & Business Media, 2006.
[5]
Y. Nesterov and B. T. Polyak, “Cubic regularization of Newton method and its global performance,” Mathematical Programming, vol. 108, no. 1, pp.
177–205, 2006.
[6]
C. Cartis, N. I. Gould, and P. L. Toint, “Adaptive cubic regularisation methods for unconstrained optimization. Part II: Worst-case function-and derivative-evaluation
complexity,” Mathematical programming, vol. 130, no. 2, pp. 295–319, 2011.
[7]
F. Hamad and O. Hinder, “A consistently adaptive trust-region method,” Advances in Neural Information Processing Systems, vol. 35, pp. 6640–6653, 2022.
[8]
F. E. Curtis, D. P. Robinson, and M. Samadi, “A trust region algorithm with a worst-case iteration complexity of \(\mathcal{O}(\epsilon ^ {-3/2})\)
for nonconvex optimization,” Mathematical Programming, vol. 162, no. 1–2, pp. 1–32, 2017.
[9]
O. Hinder, Principled algorithms for finding local minima. Stanford University, 2019.
[10]
O. Hinder and Y. Ye, “Worst-case iteration bounds for log barrier methods on problems with nonconvex constraints,” Mathematics of Operations Research, vol. 49, no.
4, pp. 2402–2424, 2024.
[11]
Y. Nesterov, “Accelerating the cubic regularization of Newton’s method on convex problems,” Mathematical Programming, vol. 112, no. 1, pp. 159–181,
2008.
[12]
R. D. Monteiro and B. F. Svaiter, “An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods,” SIAM
Journal on Optimization, vol. 23, no. 2, pp. 1092–1125, 2013.
[13]
N. Agarwal and E. Hazan, “Lower bounds for higher-order convex optimization,” in Conference on learning theory, 2018, pp. 774–792.
[14]
Y. Arjevani, O. Shamir, and R. Shiff, “Oracle complexity of second-order methods for smooth convex optimization,” Mathematical Programming, vol. 178, no. 1, pp.
327–360, 2019.
[15]
Y. Nesterov, “Superfast second-order methods for unconstrained convex optimization,” Journal of Optimization Theory and Applications, vol. 191, no. 1, pp. 1–30,
2021.
[16]
K. Mishchenko, “Regularized Newton method with global convergence,” SIAM Journal on Optimization, vol. 33, no. 3, pp. 1440–1462, 2023.
[17]
R. T. Rockafellar, “Monotone operators and the proximal point algorithm,” SIAM journal on control and optimization, vol. 14, no. 5, pp. 877–898, 1976.
[18]
A. Nemirovski, “Prox-method with rate of convergence \({O}(1/t)\) for variational inequalities with lipschitz continuous monotone operators and
smooth convex-concave saddle point problems,” SIAM Journal on Optimization, vol. 15, no. 1, pp. 229–251, 2004.
[19]
R. D. Monteiro and B. F. Svaiter, “Iteration-complexity of a Newton proximal extragradient method for monotone variational inequalities and inclusion problems,”
SIAM Journal on Optimization, vol. 22, no. 3, pp. 914–935, 2012.
[20]
B. Bullins and K. A. Lai, “Higher-order methods for convex-concave min-max optimization and monotone variational inequalities,” SIAM Journal on Optimization, vol.
32, no. 3, pp. 2208–2229, 2022.
[21]
R. Jiang and A. Mokhtari, “Generalized optimistic methods for convex-concave saddle point problems,” SIAM Journal on Optimization, vol. 35, no. 3, pp. 2066–2097,
2025.
[22]
T. Lin and M. I. Jordan, “Perseus: A simple and optimal high-order method for variational inequalities,” 2024.
[23]
D. Adil, B. Bullins, A. Jambulapati, and S. Sachdeva, “Optimal methods for higher-order smooth monotone variational inequalities,” arXiv preprint arXiv:2205.06167,
2022.
[24]
Y. Zhang, “On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem,” SIAM Journal on Optimization, vol.
4, no. 1, pp. 208–227, 1994.
[25]
E. M. Simantiraki and D. F. Shanno, “An infeasible-interior-point method for linear complementarity problems,” SIAM Journal on Optimization, vol. 7, no. 3, pp.
620–640, 1997.
[26]
E. D. Andersen and Y. Ye, “A computational study of the homogeneous algorithm for large-scale convex optimization,” Computational Optimization and Applications,
vol. 10, no. 3, pp. 243–269, 1998.
[27]
I. J. Lustig, R. E. Marsten, and D. F. Shanno, “On implementing Mehrotra’s predictor–corrector interior-point method for linear programming,” SIAM journal
on Optimization, vol. 2, no. 3, pp. 435–449, 1992.
[28]
J. F. Sturm, “Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones,” Optimization methods and software, vol. 11, no.
1–4, pp. 625–653, 1999.
[29]
K.-C. Toh, M. J. Todd, and R. H. Tütüncü, “SDPT3—a MATLAB software package for semidefinite programming, version 1.3,” Optimization methods and
software, vol. 11, no. 1–4, pp. 545–581, 1999.
[30]
R. H. Byrd, J. C. Gilbert, and J. Nocedal, “A trust region method based on interior point techniques for nonlinear programming,” Mathematical Programming, vol. 89,
no. 1, pp. 149–185, 2000.
[31]
A. R. Conn, N. I. Gould, D. Orban, and P. L. Toint, “A primal-dual trust-region algorithm for non-convex nonlinear programming,” Mathematical programming, vol. 87,
no. 2, pp. 215–249, 2000.
[32]
R. H. Byrd, J. Nocedal, and R. A. Waltz, “KNITRO: An integrated package for nonlinear optimization,” in Large-scale nonlinear optimization, Springer,
2006, pp. 35–59.
[33]
C. Vanaret and S. Leyffer, “Implementing a unified solver for nonlinearly constrained optimization,” 2025.
[34]
S. Bubeck and R. Eldan, “The entropic barrier: A simple and optimal universal self-concordant barrier,” in Proceedings of the 28th conference on learning theory,
2015, vol. 40, pp. 279–279, [Online]. Available: https://proceedings.mlr.press/v40/Bubeck15b.html.
[35]
F. Bach, “Self-concordant analysis for logistic regression,” 2010.
[36]
Y. Carmon et al., “Acceleration with a ball optimization oracle,” Advances in Neural Information Processing Systems, vol. 33, pp. 19052–19063, 2020.
[37]
N. Doikov, “Minimizing quasi-self-concordant functions by gradient regularization of Newton method,” Mathematical Programming, pp. 1–39, 2025.
[38]
F. E. Curtis, D. P. Robinson, C. W. Royer, and S. J. Wright, “Trust-region Newton-CG with strong second-order complexity guarantees for nonconvex
optimization,” SIAM Journal on Optimization, vol. 31, no. 1, pp. 518–544, 2021.
[39]
F. Hamad and O. Hinder, “A simple and practical adaptive trust-region method,” arXiv preprint arXiv:2412.02079, 2024.
[40]
E. G. Birgin, J. Gardenghi, J. Martı́nez, S. Santos, and P. L. Toint, “Evaluation complexity for nonlinear constrained optimization using unscaled KKT conditions and
high-order models,” SIAM Journal on Optimization, vol. 26, no. 2, pp. 951–967, 2016.
[41]
C. Cartis, N. I. Gould, and P. L. Toint, “On the evaluation complexity of composite function minimization with applications to nonconvex nonlinear programming,” SIAM
Journal on Optimization, vol. 21, no. 4, pp. 1721–1739, 2011.
[42]
C. Cartis, N. I. Gould, and P. L. Toint, “An adaptive cubic regularization algorithm for nonconvex optimization with convex constraints and its function-evaluation
complexity,” IMA Journal of Numerical Analysis, vol. 32, no. 4, pp. 1662–1695, 2012.
[43]
G. N. Grapiglia and Y. Nesterov, “Regularized Newton methods for minimizing functions with Hölder continuous Hessians,” SIAM
Journal on Optimization, vol. 27, no. 1, pp. 478–506, 2017.
[44]
C. Cartis, N. I. Gould, and P. L. Toint, “Universal regularization methods: Varying the power, the smoothness and the accuracy,” SIAM Journal on Optimization, vol.
29, no. 1, pp. 595–615, 2019.
[45]
B. O’Donoghue and E. Candes, “Adaptive restart for accelerated gradient schemes,” Foundations of computational mathematics, vol. 15, no. 3, pp. 715–732, 2015.
[46]
G. Haeser, O. Hinder, and Y. Ye, “On the behavior of Lagrange multipliers in convex and non-convex infeasible interior point methods,” Mathematical
Programming, vol. 186, no. 1–2, p. 257, 2021.
[47]
D. P. Bertsekas, “A note on error bounds for convex and nonconvex programs,” Computational Optimization and Applications, vol. 12, no. 1, pp. 41–51, 1999.
[48]
C. Cartis, N. I. Gould, and P. L. Toint, “Adaptive cubic regularisation methods for unconstrained optimization. Part i: Motivation, convergence and numerical results,”
Mathematical Programming, vol. 127, no. 2, pp. 245–295, 2011.
[49]
P. Rigollet and X. Tong, “Neyman-Pearson classification, convexity and stochastic constraints,” Journal of machine learning research, 2011.
[50]
Q. Qian, S. Zhu, J. Tang, R. Jin, B. Sun, and H. Li, “Robust optimization over multiple domains,” in Proceedings of the AAAI conference on artificial intelligence,
2019, vol. 33, pp. 4739–4746.
[51]
L. T. Biegler and V. M. Zavala, “Large-scale nonlinear programming using IPOPT: An integrating framework for enterprise-wide dynamic optimization,”
Computers & Chemical Engineering, vol. 33, no. 3, pp. 575–582, 2009.
Department of Industrial Engineering, University of Pittsburgh. Email: {fah33, ohinder}pitt.edu?.↩︎
These bounds are not directly comparable because (i) of the aforementioned subproblem solver, (ii) our final bound (4) includes a dependence on the number of constraints, \(q\), and (iii) we assume the problem has a strict relative interior.↩︎
Although the assumptions are slightly different, in particular, 1 assumes only that the initial suboptimality is bounded.↩︎
In the spam-filtering community, ham denotes legitimate, non-spam email.↩︎