Operations Research

Motivation

Karmarkar's projective method (1984) was the first interior-point algorithm for linear programming with a polynomial bound that was also fast in practice. Its analysis rests on a potential function that combines the logarithm of the objective gap with a logarithmic barrier: if every iteration lowers the potential by a fixed constant, then the gap shrinks geometrically. Nesterov and Nemirovskii (1994, §4.3) carried the method over to general convex cones with self-concordant barriers, but only with short steps, which move a fraction of the way to the boundary of a ball in the local norm.

Nesterov and Todd (1997) introduced self-scaled barriers, the class behind the cones of linear, second-order cone and semidefinite programming. They used it to allow long steps, which go a large fraction of the way to the boundary of the cone itself. Section 7.1 of that paper analyses the Karmarkar method with long steps on a self-scaled cone. It shows that the potential decrease per iteration is at least the absolute constant $1-\ln 2$, independent of the barrier parameter, as in the linear-programming case. This mission formalizes that analysis.

Timeline:

• 1984, Karmarkar: projective method for linear programming, with potential decrease per step bounded below by a constant.
• 1986, Anstreicher: a strengthened acceptance criterion for approximate projections in Karmarkar's algorithm for standard linear programming, containing the result that Lemma 7.1 of the 1997 paper generalizes (p. 28).
• 1994, Nesterov–Nemirovskii, Interior-Point Polynomial Algorithms in Convex Programming, §4.3: the extension to self-concordant barriers on general cones, short steps.
• 1997, Nesterov–Todd: self-scaled barriers and long steps (this paper, Theorem 7.2).

Setting

Let $E=\mathbb R^n$ with inner product $\langle\cdot,\cdot\rangle$, which identifies the dual space $E^*$ with $E$. Let $K\subseteq E$ be a closed convex cone with nonempty interior that contains no line, and let $K^*=\{s:\langle s,x\rangle\ge0\ \forall x\in K\}$ be its dual cone. A $\nu$-self-scaled barrier $F:\operatorname{int}K\to\mathbb R$ is a self-concordant barrier that is logarithmically homogeneous, $F(\tau x)=F(x)-\nu\ln\tau$, and satisfies the two scaling conditions of Definition 2.1 of the paper. $F'$ and $F''$ are its gradient and Hessian.

Two measures of a direction $p\in E$ at $x\in\operatorname{int}K$ are used:

• the local norm $\|p\|_x=\langle F''(x)p,p\rangle^{1/2}$;
• the σ-measure $\sigma_x(p)=\min\{\beta\ge0:\beta x-p\in K\}$, and the uniform norm $|p|_x=\max\{\sigma_x(p),\sigma_x(-p)\}$.

The point $x-\alpha p$ stays in $\operatorname{int}K$ exactly when $\alpha\,\sigma_x(p)<1$.

The problem is in Karmarkar form:

$$(P)\qquad\min\ \langle c,x\rangle\quad\text{s.t.}\quad Bx=0,\ \ \langle d,x\rangle=1,\ \ x\in K,$$

with $B:E\to\mathbb R^m$ linear and surjective and $d\in K^*$. Its dual is $\max\{\zeta: B^*y+d\zeta+s=c,\ s\in K^*\}$. The standing assumptions are that (P) and the dual have strictly feasible points, and that $\langle c,\cdot\rangle$ is not constant on the feasible set of (P). The optimal value is $\zeta^*$. The method decreases the potential

$$\Phi(x;\zeta)=\nu\ln\langle c-\zeta d,x\rangle+F(x),$$

which is homogeneous of degree $0$ in $x$.

One iteration starts from a strictly feasible $\hat x$ and a lower bound $\hat\zeta\le\zeta^*$:

1. Put $\hat c=c+\frac{\langle c,\hat x\rangle}{\nu}F'(\hat x)$ and $\hat d=d+\frac{\langle d,\hat x\rangle}{\nu}F'(\hat x)$. Let $p(c)$, $p(d)$ be their projections into $\ker B$ with respect to $F''(\hat x)$: $Bp(u)=0$ and $B^*y(u)+F''(\hat x)p(u)=\hat u$ (7.3).
2. Put $\tilde x(\zeta)=\frac{\langle c-\zeta d,\hat x\rangle}{\nu}\hat x+p(c)-\zeta p(d)$ (7.4). If $\tilde x(\hat\zeta)\notin\operatorname{int}K$, keep $\zeta^+=\hat\zeta$. Otherwise raise the bound to $\zeta^+=\hat\zeta+1/\sigma_{\tilde x(\hat\zeta)}(p(d)+\hat x/\nu)$ (7.6).
3. Take the direction $p=p(c)-\zeta^+p(d)$ (7.5) and the new point $x^+=\hat x-\alpha p$.

Formalization targets

Goal: Theorem 7.2 (p. 28)

For a suitable $\alpha>0$, the point $x^+=\hat x-\alpha p$ lies in $\{x\in\operatorname{int}K:Bx=0\}$ and

$$\Phi(x^+;\zeta^+)\le\Phi(\hat x;\hat\zeta)-\frac{\|p\|_{\hat x}^2}{|p|_{\hat x}^2}(1-\ln2)\le\Phi(\hat x;\hat\zeta)-(1-\ln2).\qquad(7.9)$$

The goal asserts the existence of the step, not a particular step size, so it does not commit to the step chosen in the proof.

Milestones

• Lemma 7.1 (p. 27): $\zeta^+\le\zeta^*$, and $\langle c,\hat x\rangle-\zeta^+\le\nu\,\sigma_{\hat x}(-p)$ (7.7).
• (7.8) (p. 28): $\|p\|_{\hat x}^2=\langle c-\zeta^+d,p\rangle$.

Companion: Theorem 7.1 (p. 26)

With $\bar K=\{x\in K:Bx=0,\ \langle c,x\rangle\le\max(\langle c,x_0\rangle,0)+1,\ \langle d,x\rangle\le1\}$ and $\underline F$ the minimum of $F$ over it: if $\Phi(x;\zeta)\le\Phi(x_0;\zeta_0)-\Delta$ with $\zeta\in[\zeta_0,\zeta^*]$ and $\Delta$ large enough, then

$$\langle c,x\rangle-\zeta\le(\langle c,x_0\rangle-\zeta_0)\,e^{(F(x_0)-\underline F)/\nu}\,e^{-\Delta/\nu}.\qquad(7.2)$$

Significance

Theorem 7.2 together with Theorem 7.1 gives the $O(\nu\ln(1/\epsilon))$ iteration bound of the long-step conic Karmarkar method. The decrease constant $1-\ln2$ does not depend on $\nu$ or on the cone. The finer bound $\frac{\|p\|^2}{|p|^2}(1-\ln 2)$ can be much larger than $1-\ln 2$, since $\|p\|_x\ge|p|_x$ always holds. This explains why long steps outperform short ones in practice. Lemma 7.1 shows that the lower bound obtained from dual information is valid and tight enough to drive the analysis. The paper presents it as a generalization of a result of Anstreicher (1986) for standard linear programming.

The results are proved in the paper; none of them is formalized anywhere. A formal development checks the interplay of the lower-bound update with the σ-measure and the homogeneity of $\Phi$, which the paper treats briefly. It also records a correction: on p. 27 the paper prints $\hat c=c-\frac{\langle c,\hat x\rangle}{\nu}F'(\hat x)$ (and likewise $\hat d$). The paper's own surrounding identities, in particular $\langle\hat u,\hat x\rangle=0$ on p. 28, require the sign "$+$", and the formalization uses "$+$".

Difficulty

The obvious argument bounds the change of $F$ along $x-\alpha p$ with self-concordance in the local norm. That argument only controls steps with $\alpha\|p\|_{\hat x}<1$, and it gives a decrease that degrades with the step length. The long step goes up to $1/\sigma_{\hat x}(p)$, which can be much larger. Reaching it requires the long-step barrier bound for self-scaled barriers (Theorem 4.2 of the paper, stated in another mission of this series). That bound controls $F(x-\alpha p)$ through $\sigma_x(p)$ instead of $\|p\|_x$.

The second obstacle is the linear term. The decrease in $\nu\ln\langle c-\zeta^+d,\cdot\rangle$ must be compared with $\|p\|^2$, which needs both the identity (7.8) and the gap bound (7.7). The gap bound is the step at which the lower-bound update is essential: without the update, $\langle c,\hat x\rangle-\hat\zeta$ is not bounded by $\nu\sigma_{\hat x}(-p)$.

Formalization scope

The Lean development reuses the published self-scaled setting of the series SelfScaledIPM (IsProperCone, IsSelfScaledBarrier, hess, lnorm, sigma, absn) and ConvexOptimization.dualCone. Conventions:

• $E=$ EuclideanSpace ℝ (Fin n), with $E^*$ identified with $E$.
• $F''$ is assumed nondegenerate on $\operatorname{int}K$. This follows from the other axioms for a pointed cone.
• The conjugate barrier is a supremum over $\operatorname{int}K$.
• $\nu\ge1$ is a binder. The paper derives it from pointedness on p. 3.
• $\zeta^*$ is a real infimum, made finite by the strict dual feasibility assumption, which every statement carries. Nonconstancy of the objective is stated as the existence of two feasible points with different objective values.
• The projections $p(c)$, $p(d)$ are data satisfying (7.3), not chosen by a selection function. The lower-bound update and the direction are definitions computed from them.
• The goal adds the conjunct $\langle c-\zeta^+d,x^+\rangle>0$, so that the logarithm in $\Phi(x^+;\zeta^+)$ is genuine. It does not assert $\langle d,x^+\rangle=1$, which the paper notes may fail.
• Identity (7.8) is stated for every real $\zeta$, which contains the page's $\zeta=\zeta^+$.
• $\underline F$ is an infimum over $\bar K\cap\operatorname{int}K$, where the barrier is finite.
• $\hat c$ and $\hat d$ carry the corrected sign "$+$".

A statement with $\zeta^+$ an arbitrary real, or with $p$ an arbitrary vector, would be false or vacuous. The statements here fix both by the page's construction (7.3)–(7.6), and the logarithm in $\Phi$ is guarded by the positivity conjunct.

A proof needs the long-step barrier inequality (Theorem 4.2), the monotonicity facts of Proposition 4.1, $K^*=F''(v)K$ (Theorem 3.1 (iii)), and $\|p(u)\|^2_w=\langle u,p(u)\rangle$ (Proposition 6.2). These are milestones of the other missions of this series, and contributions proving them are reusable here. Elementary facts about $\sigma$ (positive homogeneity, the boundary characterization $x-\alpha p\in\partial K$ at $\alpha=1/\sigma_x(p)$) are useful beyond this mission.

Selected references

• Yu. E. Nesterov and M. J. Todd, Self-scaled barriers and interior-point methods for convex programming, Mathematics of Operations Research 22(1), 1997, 1–42. https://doi.org/10.1287/moor.22.1.1
• N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica 4, 1984, 373–395. https://doi.org/10.1007/BF02579150
• K. M. Anstreicher, A strengthened acceptance criterion for approximate projections in Karmarkar's algorithm, Operations Research Letters 5, 1986, 211–214. https://www.sciencedirect.com/journal/operations-research-letters/vol/5
• Yu. Nesterov and A. Nemirovskii, Interior-Point Polynomial Algorithms in Convex Programming, SIAM, 1994. https://doi.org/10.1137/1.9781611970791
• Yu. E. Nesterov and M. J. Todd, Primal-dual interior-point methods for self-scaled cones, SIAM Journal on Optimization 8(2), 1998, 324–364. https://doi.org/10.1137/S1052623495290209

Motivation

Potential-reduction methods solve a linear or conic program by driving down a single merit function that combines the objective gap with a barrier for the constraint cone. For linear programming the primal version goes back to Karmarkar (1984) and, without Karmarkar's special problem form, to Gonzaga (1990, Math. Programming 49, 7–21), whose method reduces the potential by a constant at every step while updating a lower bound on the optimal value. Nesterov and Nemirovskii (1994) extended such methods to general convex cones with self-concordant barriers, but their analysis only allows short steps: steps confined to a ball of the local norm, which in practice is a small fraction of the way to the boundary.

Nesterov and Todd (1997) singled out the self-scaled cones (the nonnegative orthant, the second-order cone, the cone of positive semidefinite matrices, and their products) and showed that for them long steps are admissible. This mission formalizes their extension of Gonzaga's method (§7.2 of the paper): a primal potential-reduction step, with a lower-bound update, that decreases the potential by a constant and, when the potential parameter is large enough, by an amount that scales with how far the step can go.

Setting

Let $E = \mathbb R^n$ with its inner product, identified with its dual $E^*$. Let $K \subseteq E$ be a closed convex pointed cone with nonempty interior, and $F$ a $\nu$-self-scaled barrier for $K$: a $\nu$-self-concordant logarithmically homogeneous barrier ($F(\tau x) = F(x) - \nu\ln\tau$) such that for all $w, x \in \operatorname{int} K$ the Hessian satisfies $F''(w)x \in \operatorname{int} K^*$ and $F_*(F''(w)x) = F(x) - 2F(w) - \nu$, where $K^*$ is the dual cone and $F_*$ the conjugate barrier. Here $\nu \ge 1$.

The problem is

$$(P)\qquad \min\ \langle c, x\rangle \quad\text{s.t.}\quad Ax = b,\ x \in K,$$

with $A : E \to \mathbb R^m$ linear and surjective, and dual $(D)$: $\max \langle b, y\rangle$ s.t. $A^*y + s = c$, $s \in K^*$. Both have strictly feasible points: $S^0(P) = \{x \in \operatorname{int}K : Ax = b\}$ and $S^0(D)$ are nonempty, and the objective is not constant on the feasible region of $(P)$. Let $\zeta^*$ be the optimal value.

At $x \in \operatorname{int}K$ the local norm is $\|p\|_x = \langle F''(x)p, p\rangle^{1/2}$, its dual is $\|u\|^*_x = \langle u, [F''(x)]^{-1}u\rangle^{1/2}$, and $\sigma_x(p) = \min\{\beta \ge 0 : \beta x - p \in K\}$ measures how far one can move from $x$ along $-p$: the point $x - \alpha p$ stays in $\operatorname{int}K$ for $\alpha\sigma_x(p) < 1$. The uniform norm is $|p|_x = \max\{\sigma_x(p), \sigma_x(-p)\} \le \|p\|_x$.

For $\mu > \nu$ and a lower bound $\zeta \le \zeta^*$, the primal potential is

$$\Phi(x;\zeta) = \mu\ln(\langle c, x\rangle - \zeta) + F(x).$$

At an iterate $\hat x \in S^0(P)$ with lower bound $\hat\zeta$, let $p(c)$ and $p(d)$ be the projections of $c$ and of $d = F'(\hat x)$ into $\ker A$ with respect to $F''(\hat x)$: $Ap(u) = 0$, $A^*y(u) + F''(\hat x)p(u) = u$. For $\lambda \in \mathbb R$ put $\tilde s(\lambda) = F''(\hat x)(p(c) + \lambda p(d)) - \lambda F'(\hat x)$. Whenever $\tilde s(\lambda) \in K^*$, the number $\langle c, \hat x\rangle - \langle \tilde s(\lambda), \hat x\rangle$ is the value of a feasible dual solution, hence a lower bound on $\zeta^*$. The updated lower bound $\zeta^+$ is the larger of $\hat\zeta$ and the best such bound. Finally $\lambda^+ = (\langle c, \hat x\rangle - \zeta^+)/\mu$ and the search direction is $p = p(c) + \lambda^+ p(d)$, which is $\lambda^+$ times the projected gradient of $\Phi(\cdot;\zeta^+)$. Write $p_+ = \sigma_{\hat x}(p)$.

Formalization targets

Goal: Theorem 7.4 (b), the long step

If $\mu \ge 2\nu$, there is $\alpha > 0$ with $x^+ = \hat x - \alpha p \in S^0(P)$ and

$$\Phi(x^+;\zeta^+) \le \Phi(\hat x;\hat\zeta) - \frac{\|p\|^2_{\hat x}}{(\max\{p_+, |p|_{\hat x}\})^2}(1-\ln 2) = \Phi(\hat x;\hat\zeta) - \frac{\|p\|^2_{\hat x}}{|p|^2_{\hat x}}(1-\ln 2) \le \Phi(\hat x;\hat\zeta) - (1-\ln 2).$$

Companion: Theorem 7.4 (a), the short step

If $\mu \ge \nu + \sqrt\nu$, there is $\alpha > 0$ with $x^+ = \hat x - \alpha p \in S^0(P)$ and

$$\Phi(x^+;\zeta^+) \le \Phi(\hat x;\hat\zeta) - \frac{\|p\|^2_{\hat x}}{(\max\{p_+, \|p\|_{\hat x}\})^2}(1-\ln 2) = \Phi(\hat x;\hat\zeta) - (1-\ln 2).$$

Milestones

1. (§7.2, p. 31) The gap $\langle\tilde s(\lambda), \hat x\rangle = \langle -F'(\hat x), p(c)\rangle + \lambda\big((\|F'(\hat x)\|^*_{\hat x})^2 - \|p(d)\|^2_{\hat x}\big)$ is nondecreasing in $\lambda$.
2. (Lemma 7.2) If $\mu \ge \nu + \sqrt\nu$ then $\lambda^+ \le \|p\|_{\hat x}$; if $\mu \ge 2\nu$ then $\lambda^+ \le |p|_{\hat x}$.

Companion: Theorem 7.3

A total potential decrease $\Delta > \mu\ln(\langle c, x_0\rangle - \zeta_0) + F(x_0) - \underline F$ from the starting pair $(x_0, \zeta_0)$ forces $\langle c, x\rangle - \zeta \le (\langle c, x_0\rangle - \zeta_0)\,e^{(F(x_0) - \underline F)/\mu}\,e^{-\Delta/\mu}$, where $\underline F$ is the minimum of $F$ on a bounded truncation $\bar K$ of the homogenized feasible region.

Significance

Theorem 7.4 together with Theorem 7.3 gives an $O(\mu\ln(1/\epsilon))$-iteration method for conic programming over self-scaled cones that needs only a primal strictly feasible point and a lower bound, and that, for $\mu = O(\nu)$, matches the complexity of the short-step theory. Part (b) is the substantive claim: the step $\alpha$ may go a large fraction of the way to the boundary of $K$ (half way when $\sigma_{\hat x}(p) = \sigma_{\hat x}(-p)$) and the guaranteed decrease $(\|p\|^2_{\hat x}/|p|^2_{\hat x})(1 - \ln 2)$ is typically much larger than $1 - \ln 2$. This is the property that distinguishes self-scaled barriers from general self-concordant ones, for which only steps inside the local unit ball are controlled.

The results are proved in the paper. None of them, nor the long-step theory of self-scaled barriers on which they rest, is formalized in any proof assistant as far as is known.

Difficulty

The obvious approach bounds $F(\hat x - \alpha p) - F(\hat x)$ by the self-concordance inequality, which controls $F$ only for $\alpha\|p\|_{\hat x} < 1$; that is the short-step regime and yields at best part (a). Part (b) requires a bound on $F$ along $-p$ valid all the way to $\alpha < 1/\sigma_{\hat x}(p)$, which holds for self-scaled barriers but not for self-concordant ones. The second difficulty is the interplay with the lower-bound update: the decrease of the barrier term must be paid for by the decrease of $\mu\ln(\langle c, x\rangle - \zeta^+)$, and this needs the scaling factor $\lambda^+$ of the direction to be at most $|p|_{\hat x}$, which in turn depends on how $\zeta^+$ was chosen. With an arbitrary admissible lower bound the claim fails.

Formalization scope

$E$, $E^*$ are EuclideanSpace ℝ (Fin n) identified through the inner product, and the problem data are $A : \mathbb R^n \to_L \mathbb R^m$ surjective, $b$, $c$. The cone, the barrier, the local norms $\|\cdot\|_x$ (lnorm), $\|\cdot\|^*_x$ (dnorm), $\sigma_x$ (sigma) and $|\cdot|_x$ (absn) are the published definitions of the SelfScaledIPM.ShortStep setting; the paper's starred dual norms map to dnorm at a primal point. Nondegeneracy of $F''$ is part of that barrier definition, and the conjugate barrier is an sSup over $\operatorname{int}K$.

Standing assumptions are hypotheses of every statement: surjectivity of $A$ (6.1), strict dual feasibility (6.3) (strict primal feasibility follows from the given iterate), the objective not constant on the feasible region, and $\nu \ge 1$. The optimal value $\zeta^*$ is the infimum of the objective over the feasible set, finite under these assumptions. The projections (7.12) are given as data satisfying their defining equations. The updated lower bound $\zeta^+$ is defined as $\max(\hat\zeta, \sup G)$, with $G$ the set of dual bounds $\langle c, \hat x\rangle - \langle\tilde s(\lambda), \hat x\rangle$ over $\lambda$ with $\tilde s(\lambda) \in K^*$, and $\zeta^+ = \hat\zeta$ when $G$ is empty. Because the gap is nondecreasing in $\lambda$, this equals the paper's value at the minimal admissible $\lambda$. "A suitable value of $\alpha$" is an existential over $\alpha > 0$, and the conclusion also asserts $\langle c, x^+\rangle > \zeta^+$ so that the logarithm in $\Phi(x^+;\zeta^+)$ is genuine. $\bar K$ and $\underline F$ of Theorem 7.3 are defined explicitly, with $\underline F$ the infimum of $F$ over $\bar K \cap \operatorname{int}K$.

A statement in which $\zeta^+$ is an arbitrary lower bound above $\hat\zeta$, or $p$ an arbitrary vector in $\ker A$, or $\alpha$ arbitrary instead of existentially chosen, would be false; the formalization fixes $\zeta^+$ by (7.17) and $p$ by (7.14).

A complete development needs the theory of self-scaled barriers along a line (Theorem 4.2 and Proposition 4.1 of the paper, posed in the sibling mission I of this series), the projection identities (Propositions 6.2–6.3, posed in mission IV), weak conic duality, and the inequalities $\langle -F'(x), p\rangle \le \sqrt\nu\|p\|_x$ and $\langle -F'(x), p\rangle \le \nu\sigma_x(p)$. These are reusable across self-scaled interior-point methods; proofs of any of them are welcome.

Selected references

• Yu. E. Nesterov and M. J. Todd, Self-scaled barriers and interior-point methods for convex programming, Mathematics of Operations Research 22(1), 1997, 1–42. https://doi.org/10.1287/moor.22.1.1
• Yu. E. Nesterov and M. J. Todd, Primal-dual interior-point methods for self-scaled cones, SIAM Journal on Optimization 8(2), 1998, 324–364. https://doi.org/10.1137/S1052623495290209
• Yu. Nesterov and A. Nemirovskii, Interior-Point Polynomial Algorithms in Convex Programming, SIAM, 1994. https://doi.org/10.1137/1.9781611970791
• C. C. Gonzaga, Polynomial affine algorithms for linear programming, Mathematical Programming 49, 1990, 7–21 (cited as in the paper's reference list).
• N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica 4, 1984, 373–395. https://doi.org/10.1007/BF02579150

Motivation

Interior-point methods solve linear, second-order cone and semidefinite programs by following a smooth curve through the interior of the feasible region. Nesterov and Nemirovskii (1994) showed that the right object to build such methods on is a self-concordant barrier for the cone, and that the number of Newton steps needed by a path-following method is governed by the barrier parameter $\nu$. For general cones, however, their analysis of Newton's method only controls a small neighbourhood of the path, so the step in the path parameter must be short.

Nesterov and Todd (1997) singled out the cones that admit a self-scaled barrier: the nonnegative orthant, the second-order cone, the cone of positive semidefinite matrices and their products. For these cones the barrier satisfies global, long-range inequalities that general self-concordant barriers do not. Section 9 of the paper uses them to sharpen the classical primal path-following method: Newton's method converges quadratically on the whole region where the proximity measure is below $1$ (extending Roos and Vial, 1992), and a predictor-corrector scheme takes a tangent step whose length adapts to the geometry of the cone at the current point.

Setting

Let $E=\mathbb R^n$ with its Euclidean inner product $\langle\cdot,\cdot\rangle$; the dual space $E^*$ is identified with $E$. Let $K\subset E$ be a proper cone: closed, convex, containing no line, with nonempty interior $\operatorname{int}K$. A function $F:\operatorname{int}K\to\mathbb R$ is a $\nu$-self-scaled barrier for $K$ if it is a $\nu$-self-concordant logarithmically homogeneous barrier ($F(tx)=F(x)-\nu\ln t$) and, for all $w,x\in\operatorname{int}K$, $F''(w)x\in\operatorname{int}K^*$ and $F_*(F''(w)x)=F(x)-2F(w)-\nu$, where $F_*$ is the conjugate barrier (Definition 2.1). Then $\nu\ge1$.

At a point $x\in\operatorname{int}K$ the paper uses three measures of a vector $p\in E$:

• the local norm $\|p\|_x=\langle F''(x)p,p\rangle^{1/2}$, and for $q\in E^*$ the dual norm $\|q\|^*_x=\langle q,[F''(x)]^{-1}q\rangle^{1/2}$;
• $\sigma_x(p)=\min\{\beta\ge0:\beta x-p\in K\}$, the reciprocal of the largest step from $x$ along $-p$ that stays in $K$;
• the uniform norm $|p|_x=\max\{\sigma_x(p),\sigma_x(-p)\}$, which satisfies $|p|_x\le\|p\|_x$.

The problem is $\min\{\langle c,x\rangle: Ax=b,\ x\in K\}$ with $A:E\to Y=\mathbb R^m$ surjective; $S^0(P)=\{x\in\operatorname{int}K:Ax=b\}$ is the set of strictly feasible points, and the dual problem is assumed strictly feasible. For $w\in\operatorname{int}K$ and $u\in E^*$ the system

$$Ap=0,\qquad A^*y+F''(w)p=u \tag{6.4}$$

defines the projection $p=p(u)$ of $u$ into $\ker A$ with respect to $F''(w)$.

For $\tau>0$ the penalty function is $\psi(\tau,x)=\tau\langle c,x\rangle+F(x)$; its minimizers $x(\tau)$ over $S^0(P)$ form the central path. The Newton direction $p(\tau,x)$ is the projection of $\tau c+F'(x)$ with respect to $F''(x)$, and the proximity measure is $\pi(\tau,x)=\|p(\tau,x)\|_x$. The tangent direction $v(x)$ is the projection of $c$ with respect to $F''(x)$.

One iteration of the path-following scheme (p. 39) from $(\tau,x)$ with $\pi(\tau,x)\le1/4$ is:

$$\Delta\tau=\frac{3}{8\sqrt{|v|_x\|v\|_x}},\quad z=x-\Delta\tau\,v,\quad \tau_+=\tau+\Delta\tau,\quad x_+=z-p(\tau_+,z),\qquad v=v(x).$$

Formalization targets

Goal: Theorem 9.3

For one iteration of the scheme, with $v\ne0$:

$$z\in\operatorname{int}K,\qquad x_+\in S^0(P),\qquad \pi(\tau_+,x_+)\le\tfrac14,$$ $$\tau_+\ \ge\ \Bigl(1+\frac{3}{8\sqrt\nu+2}\sqrt{\frac{\|v\|_x}{|v|_x}}\Bigr)\tau\ \ge\ \Bigl(1+\frac{3}{8\sqrt\nu+2}\Bigr)\tau .$$

By induction from $\pi(\tau_0,x_0)\le1/4$, the condition (9.3) holds at every iterate and $\tau_k$ grows geometrically.

Milestones

• Corollary 3.1: for $v,z\in\operatorname{int}K$ there is $w\in\operatorname{int}K$ with $F'(v)=-F''(w)z$, $F'(z)=-F''(w)v$, hence $F'(v)-F'(z)=F''(w)(v-z)$.
• Corollary 4.1 (iii): for such $w$ (with $F'(v)=-F''(w)x$), $\sigma_x(v)^{-1}F''(x)\le F''(w)\le\sigma_v(x)F''(x)$.
• Theorem 4.3: $\|F'(v)-F'(x)-F''(x)(v-x)\|^*_v\le|v-x|_x\,\|v-x\|_x$.
• Proposition 6.2: $\|p(u)\|_w^2=\langle u,p(u)\rangle$.
• Proposition 6.3: $\|p(u)\|_w\le\|u-A^*y\|^*_w$ for all $y\in Y$, with equality only at a minimizer.
• Theorem 9.2: if $\pi(\tau,x)<1$, the full Newton step $x_+=x-p(\tau,x)$ satisfies $\pi(\tau,x_+)\le|p|_x\,\pi(\tau,x)\le\pi^2(\tau,x)$.

A companion item, Theorem 9.1, states the decrease of $\psi(\tau,\cdot)$ along the damped Newton step $\alpha=1/(1+\sigma_x(p))$.

Significance

Theorem 9.3 shows that the primal path-following method for self-scaled cones increases the penalty parameter by a factor at least $1+3/(8\sqrt\nu+2)$ per iteration, which yields the $O(\sqrt\nu\ln(1/\epsilon))$ iteration bound, and that the step can be much longer when the ratio $\|v\|_x/|v|_x$ is large. The paper notes that this ratio is the maximal step $\alpha^*$ along the normalized tangent direction that keeps $x\pm\alpha^*\bar v$ in $K$, so the rule is a "large-step" rule in disguise. Theorem 9.2 removes the restriction of the general self-concordant theory, where quadratic convergence of Newton's method is only shown on a smaller neighbourhood, by allowing any point with $\pi(\tau,x)<1$.

The milestones are general tools for self-scaled barriers. Theorem 4.3 is a global second-order estimate for the gradient, with no restriction on the distance between the two points; Corollary 3.1 is an exact mean-value identity with a single interior intermediate point; Propositions 6.2 and 6.3 are the basic facts about the projections that every algorithm of the paper computes.

None of these results has a machine-checked proof that we know of. The platform has general self-concordant Newton estimates (the contraction $\lambda_+\le(\lambda/(1-\lambda))^2$ and the damped Newton decrease $\lambda-\ln(1+\lambda)$), which use different measures and do not involve $\sigma_x$, $|\cdot|_x$ or the constraint $Ax=b$.

Difficulty

The obvious route to Theorem 9.2 is the standard self-concordance argument, which compares $F''$ at the new point with $F''(x)$ through the local norm $\|p\|_x$ alone. It gives $\pi_+\le\pi^2/(1-\pi)^2$, which is weaker than the claimed bound and gives nothing near $\pi=1$. The sharper bound needs estimates that hold only for self-scaled barriers: a second-order remainder for the gradient measured at the new point and controlled by the uniform norm $|\cdot|_x$ (Theorem 4.3), which in turn requires the intermediate point of Corollary 3.1 and the two-sided Hessian comparison of Corollary 4.1 (iii). These fail for general self-concordant barriers, and they depend on the structure theory of §3 (Theorem 3.2 of the paper).

In Theorem 9.3 the predictor step is long in the local norm, so no estimate based on $\|v\|_x$ alone keeps the predictor point close enough to the central path for one corrector step to restore $\pi\le1/4$; the constant $3/8$ in $\Delta\tau$ is fixed by the page and leaves little slack.

Formalization scope

The development reuses the published setting of the 1998 Nesterov–Todd series: IsProperCone, IsSelfScaledBarrier, hess, IsPrimalStrict, IsDualStrict, lnorm ($\|\cdot\|_x$), dnorm ($\|\cdot\|^*_x$), sigma and absn. Its conventions are:

1. $E^*$ is identified with $E=\mathbb R^n$ through the Euclidean inner product.
2. Positive definiteness of $F''$ on $\operatorname{int}K$ is part of the barrier definition.
3. The conjugate is a real supremum over $\operatorname{int}K$.
4. $\nu\ge1$ is a hypothesis.

The paper stars dual norms; the 1998 modules do not, so dnorm F x is the paper's $\|\cdot\|^*_x$.

New definitions are the projection system (6.4) (IsProjection), the penalty $\psi$, the Newton and tangent systems as predicates on their solutions, and the step size $\Delta\tau$. Solutions of linear systems are always data satisfying these predicates, never chosen by a function. Operator inequalities are written through quadratic forms.

Every theorem of §9 assumes (6.1)–(6.3) ($A$ surjective, a strictly feasible dual point), which the paper states on p. 38. Theorems 9.2 and 9.3 are stated for one iteration and state explicitly that the new points are interior, which the scheme presupposes. Theorem 9.3 assumes $v(x)\ne0$: when $c$ lies in the range of $A^*$ the objective is constant on the feasible set and $\Delta\tau$ is undefined. In Theorem 9.1 the middle bound of (9.1), which divides by $\sigma_x(p)$, is stated under $\sigma_x(p)>0$, and the outer bound in all cases.

A formalization that leaves $\Delta\tau$ as a free positive parameter, drops the corrector step, or treats $\pi$ as any number at most $1/4$ that is not tied to the Newton system at the new point would state a different, weaker or vacuous theorem. The goal fixes $\Delta\tau$ by the formula of p. 39 and bounds $\|p\|_{x_+}$ for every solution of the Newton system at $(\tau_+,x_+)$.

Contributions welcome: proofs of the milestones, the structure results they rest on (existence of the scaling point, Theorem 3.2; the Hessian bounds of Theorem 4.1), and reusable lemmas on $\sigma_x$ and the uniform norm, which also serve the other missions of this series.

Selected references

• Yu. E. Nesterov and M. J. Todd, Self-scaled barriers and interior-point methods for convex programming, Mathematics of Operations Research 22(1) (1997) 1–42. https://doi.org/10.1287/moor.22.1.1
• Yu. E. Nesterov and M. J. Todd, Primal-dual interior-point methods for self-scaled cones, SIAM Journal on Optimization 8(2) (1998) 324–364. https://doi.org/10.1137/S1052623495290209
• Yu. Nesterov and A. Nemirovskii, Interior-Point Polynomial Algorithms in Convex Programming, SIAM, 1994. https://doi.org/10.1137/1.9781611970791
• C. Roos and J.-Ph. Vial, A polynomial method of approximate centers for linear programming, Mathematical Programming 54 (1992) 295–305.

Motivation

A retailer who orders a seasonal product before demand is known faces the newsvendor trade-off. Ordering too much leaves unsold stock, and ordering too little forgoes sales. A risk-neutral newsvendor orders a critical fractile of demand. A risk-averse one orders less, since inventory is a risky investment, and this reduction has been shown under constant and decreasing absolute risk aversion (Eeckhoudt, Gollier and Schlesinger, Management Science 41(5), 1995, doi:10.1287/mnsc.41.5.786). Agrawal and Seshadri (2000) and Chen and Federgruen (2000) reached related conclusions.

Demand for many products moves with traded financial quantities: a stock index, a commodity price, an exchange rate. V. Gaur and S. Seshadri (Manufacturing & Service Operations Management 7(2), 2005, pp. 103–120, doi:10.1287/msom.1040.0061) ask what happens when the newsvendor can trade a financial instrument correlated with demand. Their Proposition 7 answers one half of the question: hedging moves the risk-averse newsvendor's order up, towards the risk-neutral quantity. This mission formalizes Proposition 7 and the steps of its appendix proof. The source is the published article, a library scan.

Setting

Let $S_T$ be the price at time $T$ of a traded asset, with law $\nu$ on $\mathbb R$. Demand is $D=a+b(S_T+\varepsilon)$ with $b>0$. Here $\varepsilon$ is the scaled forecast error, independent of $S_T$, with law $G$, $E[\varepsilon]=0$ and $E[\varepsilon^2]<\infty$. The unit selling price, cost and salvage value are $p>ce^{rT}>s$. In the paper's scaled units ((11), p. 110) these collapse into one cost parameter $c_1$ with $0<c_1$ and $c_1b<1$, and an initial-wealth term $W$.

A hedge is a portfolio with time-$T$ payoff $X_T=\varphi(S_T)$ for a nondecreasing function $\varphi$, and time-0 price $X_0$. It is a fair gamble, $E[X_T]=X_0e^{rT}$ (display (12)). A firm that stocks $I>\max\{a,0\}$ units and shorts $\alpha$ units of the hedge ends with the scaled wealth (14)

$$\Pi_H(I,\alpha)=W+\min\Big\{S_T+\varepsilon,\ \frac{I-a}{b}\Big\}-c_1I-\alpha X_T+\alpha X_0e^{rT}.$$

A decision maker with utility $u:\mathbb R\to\mathbb R$ ranks $(I,\alpha)$ by $E[u(\Pi_H(I,\alpha))]$, and $I^*(\alpha)$ maximizes it over $I$.

The absolute risk aversion is $R_A(w)=-u''(w)/u'(w)$ and the absolute prudence is $-u'''(w)/u''(w)$. The utility displays DARA or CARA when $R_A$ is decreasing or constant, and DAP when prudence is decreasing or constant.

The hedge ratio is bounded by $\bar\alpha$, chosen so that $E_\varepsilon[\Pi_H(I,\alpha)\mid S_T]$ is nondecreasing in $S_T$ for $0\le\alpha\le\bar\alpha$. Beyond $\bar\alpha$ the firm over-hedges: its expected profit falls as the asset price rises.

Formalization targets

Goal: Proposition 7 (p. 112)

For an increasing, concave, differentiable utility with constant or decreasing absolute risk aversion and constant or decreasing absolute prudence,

$$\frac{dI^*}{d\alpha}\ \ge\ 0\qquad\text{for }0\le\alpha\le\bar\alpha,$$

stated as: $\alpha\mapsto I^*(\alpha)$ is nondecreasing on $[0,\bar\alpha]$.

Milestones

1. Lemma 2 (p. 118), in its weak form. If $f$ is decreasing with $E[f(X)]=0$, then $E[w(X)f(X)]\ge0$ for decreasing nonnegative $w$, and $E[w(X)f(X)]\le0$ for increasing nonnegative $w$.
2. Utility facts of §3.2 (p. 111). DARA or CARA implies $u'''\ge0$, and DAP implies that $u'''$ is decreasing.
3. Steps of the proof (pp. 118–119).
   • $E_\varepsilon[u''(\Pi)\mid S_T]$ is increasing in $S_T$.
   • The first term of the cross-partial representation (25) is nonnegative.
   • The quantity $(1/b)R_A(\Pi_0)u'(\Pi_0)\Pr\{\varepsilon>(I-a)/b-S_T\}\,\partial\Pi/\partial\alpha$ has nonpositive mean.
   • $\partial^2E[u(\Pi)]/\partial I\partial\alpha\ge0$, as increasing differences of $E[u(\Pi_H(I,\alpha))]$ on $(\max\{a,0\},\infty)\times[0,\bar\alpha]$.

Significance

Proposition 7 reverses the conclusion of Eeckhoudt et al. Those authors find that an additional uncorrelated background risk lowers the risk-averse newsvendor's order. Here a correlated financial position that offsets the inventory risk raises it. Hedging therefore increases expected profit as well as reducing variance, and brings a risk-averse firm's operational decision closer to the risk-neutral one. The result is one of the basic statements linking operational and financial risk management in supply-chain finance.

The formalization adds three things.

• Corrected lemmas. The proof rests on a one-variable Chebyshev inequality (Lemma 2) whose printed strict form is false, and on a cross-partial computation that differentiates under the expectation without comment. A machine-checked proof fixes the correct hypotheses: the weak inequalities, and the integrability under which (24)–(25) hold.
• Reusable monotone comparative statics. The steps from increasing differences in (inventory, hedge ratio) to a monotone argmax apply to other stochastic inventory models with expected-utility objectives.
• Formal status. The result is proved in the paper. To our knowledge no part of it has been formalized.

Difficulty

The obvious argument signs the cross-partial derivative directly: $E[u''(\Pi)\,\partial\Pi/\partial I\,\partial\Pi/\partial\alpha]$, with $\partial\Pi/\partial\alpha=X_0e^{rT}-X_T$ of mean zero. That needs the sign of a covariance between $\partial\Pi/\partial\alpha$ and $u''(\Pi)\,\partial\Pi/\partial I$, a weight that depends on both $S_T$ and $\varepsilon$ and is not monotone in either.

The paper first conditions on $S_T$ and splits the weight into two terms. The first is a conditional mean of $u''(\Pi)$. The second is concentrated on the sell-out event. Each term then needs its own monotonicity in $S_T$.

• For the second term, monotonicity comes from DARA alone.
• For the first term, $E_\varepsilon[u''(\Pi)\mid S_T]$, a second application of the Chebyshev inequality, in $\varepsilon$, is needed. It uses prudence (DAP) and the bound $\alpha\le\bar\alpha$.

Neither ingredient can be dropped. Without $\alpha\le\bar\alpha$ the conditional mean payoff decreases in $S_T$ and the first term changes sign.

Two further obstacles are technical:

• the expectation is not differentiable in $I$ where $\varepsilon=(I-a)/b-S_T$ has an atom;
• the hedge $\varphi$ is only monotone, hence differentiable only almost everywhere.

Formalization scope

Representation.

• $S_T\sim\nu$ and $\varepsilon\sim G$ are probability measures on $\mathbb R$, and every expectation is taken over $\nu\otimes G$. Independence is built in, and $E_\varepsilon[\,\cdot\mid S_T=s]$ is the integral over $G$ at fixed $s$.
• The parameters are the scaled $W,a,b,c_1$ of (11). The constraint $p>ce^{rT}>s$ becomes $0<c_1$ and $c_1b<1$, an exact reparametrization.
• The hedge is a nondecreasing, measurable, $\nu$-integrable $\varphi$ with $\int\varphi\,d\nu=X_0e^{rT}$. The paper's "piecewise continuous, differentiable a.e." is dropped, so the formal statement is more general.
• $R_A$ is the platform's Arrow–Pratt coefficient MDPFinance.FinancialMarkets.arrowPrattCoefficient, referenced rather than redefined.

Conventions.

• "Increasing, concave, differentiable" is taken as $C^3$ with $u'>0$ and $u''<0$ on all of $\mathbb R$. Absolute prudence $-u'''/u''$ requires $u''\ne0$, and the proof uses $u''<0$.
• DARA/CARA and DAP are stated as $R_A$ and the prudence being nonincreasing.
• $\bar\alpha$ is any value for which the conditional mean payoff is nondecreasing in $S_T$ for every $\alpha\in[0,\bar\alpha]$ and every admissible $I>\max\{a,0\}$.
• $I^*$ is any selection of maximizers over $I>\max\{a,0\}$; the maximizer is unique by strict concavity.
• $dI^*/d\alpha\ge0$ is stated as monotonicity of $I^*$. The cross-partial claim is stated as increasing differences.
• Lemma 2 and "the second term is negative" are weakened to the non-strict inequalities, because the printed strict forms fail for constant weights.

Integrability. The goal and the increasing-differences milestone assume integrability of $u(\Pi)$, $u'(\Pi)$, $u''(\Pi)$ and of their products with $\partial\Pi/\partial\alpha$ on the whole region, which is the regularity the proof uses. Without it a Bochner integral would silently be $0$: the objective would be constant in $I$ and every $I$ a maximizer. A hypothesis set that forces $\bar\alpha=0$ would also trivialize the goal. A sorry-free check file exhibits the utility class, the standing assumptions and the $\bar\alpha$-condition with $\bar\alpha=1/2$ for $u(w)=-e^{-w}$, $\varepsilon=\pm1$ with equal probability and $\varphi(s)=\min\{s,-1/2\}$.

Infrastructure and contributions. A one-variable Chebyshev association inequality for monotone functions is needed. So are differentiation under the integral, or an integrated mean-value argument, for piecewise-linear payoffs, and the step from increasing differences plus a unique maximizer to a monotone argmax. All three are reusable. Proofs of the milestones in any order are welcome, as are alternative arguments that avoid the cross-partial derivative altogether.

Selected references

• V. Gaur, S. Seshadri, Hedging Inventory Risk Through Market Instruments, Manufacturing & Service Operations Management 7(2), 103–120, 2005. https://doi.org/10.1287/msom.1040.0061
• L. Eeckhoudt, C. Gollier, H. Schlesinger, The Risk-Averse (and Prudent) Newsboy, Management Science 41(5), 786–794, 1995. https://doi.org/10.1287/mnsc.41.5.786
• M. S. Kimball, Precautionary Saving in the Small and in the Large, Econometrica 58(1), 53–73, 1990. https://doi.org/10.2307/2938334
• K. J. Arrow, Essays in the Theory of Risk-Bearing, North-Holland, 1971.
• P. Milgrom, C. Shannon, Monotone Comparative Statics, Econometrica 62(1), 157–180, 1994. https://doi.org/10.2307/2951479

Motivation

Interior-point methods solve linear, second-order cone and semidefinite programs in polynomial time, and they are the engine of most conic optimization software. The general theory of Nesterov and Nemirovskii (1994) covers any convex cone with a self-concordant barrier, but its methods are essentially primal and short-step: their analysis controls the barrier only inside a unit Dikin ellipsoid around the current point. Practical codes for linear programming, in contrast, use symmetric primal-dual methods that take long steps, a large fraction of the way to the boundary.

Nesterov and Todd (1997) isolated the class of cones and barriers for which the primal-dual long-step theory of linear programming carries over: self-scaled cones with self-scaled barriers. The class contains the nonnegative orthant, the second-order cone and the cone of positive semidefinite matrices, and their products. This mission formalizes the paper's §8 result: a primal-dual potential-reduction method with joint scaling decreases a symmetric potential function by an absolute constant at every iteration, which yields an $O(\sqrt\nu\ln(1/\epsilon))$ iteration bound.

Timeline. Todd and Ye (1990) introduced the symmetric primal-dual potential function for linear programming with a short-step method. Kojima, Mizuno and Yoshise (1991) gave a symmetric long-step primal-dual potential-reduction method for linear complementarity problems; their Lemma 2.5 is the linear-programming case of the key inequality posed here. Nesterov and Nemirovskii (1994, §4.5) extended Ye's non-symmetric method to general cones. Nesterov and Todd (1997) extended the method of Kojima et al. to self-scaled cones; the companion paper (1998) treats short-step and functional-proximity variants.

Setting

Let $E$ be a finite-dimensional real vector space with dual $E^*$ and pairing $\langle s,x\rangle$. Let $K\subset E$ be a proper cone: closed, convex, with nonempty interior, and pointed (it contains no line). Its dual cone is $K^*=\{s:\langle s,x\rangle\ge0\ \forall x\in K\}$.

A $\nu$-self-concordant logarithmically homogeneous barrier for $K$ is a convex $C^3$ function $F$ on $\operatorname{int}K$ that tends to $+\infty$ at the boundary, satisfies the self-concordance inequality $|F'''(x)[h,h,h]|\le2\langle F''(x)h,h\rangle^{3/2}$, the bound $\langle F'(x),h\rangle^2\le\nu\langle F''(x)h,h\rangle$, and $F(\tau x)=F(x)-\nu\ln\tau$ for $\tau>0$. Its conjugate barrier is

$$F_*(s)=\max\{-\langle s,x\rangle-F(x):x\in\operatorname{int}K\},\qquad s\in\operatorname{int}K^*.$$

$F$ is $\nu$-self-scaled (Definition 2.1) if for all $v,x\in\operatorname{int}K$, $F''(v)x\in\operatorname{int}K^*$ and $F_*(F''(v)x)=F(x)-2F(v)-\nu$. For $x\in\operatorname{int}K$, $s\in\operatorname{int}K^*$ the scaling point is the $w\in\operatorname{int}K$ with $F''(w)x=s$.

The distance to the boundary is measured by

$$\sigma_x(p)=\min\{\beta\ge0:\beta x-p\in K\},\qquad\sigma^*_s(q)=\min\{\beta\ge0:\beta s-q\in K^*\},$$

so $x-\alpha p\in\operatorname{int}K$ for $\alpha\in[0,1/\sigma_x(p))$; local norms are $\|p\|_x=\langle F''(x)p,p\rangle^{1/2}$.

The problem is the primal-dual pair $\min\{\langle c,x\rangle:Ax=b,\ x\in K\}$, $\max\{\langle b,y\rangle:A^*y+s=c,\ s\in K^*\}$ with $A$ surjective. For $\rho\ge\sqrt\nu$ the primal-dual potential is

$$\phi(x,s)=(\nu+\rho)\ln\langle s,x\rangle+F(x)+F_*(s).$$

One iteration from a strictly feasible $(x,y,s)$: take the scaling point $w$ and $\sigma=\sigma_x(w)$; solve

$$F''(w)\Delta x+\Delta s=\tfrac{\nu+\rho}{\langle s,x\rangle}s+F'(x),\qquad A\Delta x=0,\qquad A^*\Delta y+\Delta s=0;\qquad(8.1)$$

put $\bar\sigma=\max\{\sigma_x(\Delta x),\sigma^*_s(\Delta s)\}$, $\bar\alpha=1/(\sigma^2+\bar\sigma)$, and accept any $\alpha$ with $\phi(x-\alpha\Delta x,s-\alpha\Delta s)\le\phi(x-\bar\alpha\Delta x,s-\bar\alpha\Delta s)$.

Formalization targets

Goal: Theorem 8.2

$$\phi(x-\bar\alpha\Delta x,\,s-\bar\alpha\Delta s)\le\phi(x,s)-\frac{\sqrt3}{2}+\ln\Big(1+\frac{\sqrt3}{2}\Big),$$

with $x-\bar\alpha\Delta x\in\operatorname{int}K$ and $s-\bar\alpha\Delta s\in\operatorname{int}K^*$, and the same bound for every accepted step $\alpha$, whose iterate is again strictly feasible. The constant $\sqrt3/2-\ln(1+\sqrt3/2)\approx0.243$ is the paper's.

Milestones

In attack order: the structure of Hessians (Theorem 3.1), existence and uniqueness of scaling points (Theorem 3.2), convexity of $-\langle F'(\cdot),v\rangle$ (Lemma 3.1) and the third-derivative bounds (Corollary 3.2 (i)–(ii)); the long-step Hessian comparison (Theorem 4.1), its corollaries (Corollary 4.1 (i)–(ii)), the barrier estimate (4.8) (Theorem 4.2) and the scalar monotonicity facts (Proposition 4.1); separability along orthogonal boundary directions (Lemma 5.1, Theorem 5.1) and the key inequality

$$\langle F'(x),F_*'(s)\rangle\ge\frac{\nu(\nu-1)}{\langle s,x\rangle}+\frac34\sigma_x^2(w)\qquad(\text{Theorem 5.2});$$

and unique solvability of the projection system (Proposition 6.1).

Significance

A constant decrease of $\phi$ per iteration gives, through the bound of Nesterov–Nemirovskii (Theorem 8.1 of the paper), primal and dual solutions within $\epsilon$ of optimal in $O(\sqrt\nu\ln(1/\epsilon))$ iterations when $\rho=\gamma\sqrt\nu$, with step sizes that are long (a fixed fraction of the distance to the boundary) rather than confined to a Dikin ellipsoid. Theorems 4.1–4.2 and 5.2 are reused by the potential-reduction and path-following analyses of the same paper and by later work on symmetric cones.

The results are proved in the paper. They are not formalized anywhere known to us: Mathlib has no self-concordant barriers, and the platform has the definitions of self-scaled barriers (from the companion 1998 paper) but none of these theorems. The mission produces machine-checked versions of the paper's structure theory of self-scaled barriers (§§3–5) and of the per-iteration decrease of its primal-dual method.

Difficulty

The obvious attempt bounds the change of $F$ and $F_*$ along the step by self-concordance alone. Self-concordance controls $F''(x-\alpha p)$ only for $\|\alpha p\|_x<1$, so it cannot certify a step of length $\bar\alpha$, which may be far outside the Dikin ellipsoid. The long-step analysis needs Theorem 4.1, which compares Hessians all the way to the boundary and holds for self-scaled barriers but fails for general self-concordant ones. The constant decrease then needs a lower bound on $\mu/\sigma$, where $\mu$ is the scaled norm of the right-hand side of (8.1); that bound is Theorem 5.2, whose proof rests on the separability of $F$ along orthogonal boundary directions (Theorem 5.1), a structural property with no analogue for general barriers.

Formalization scope

• Spaces. $E=E^*=\mathbb R^n$ and $Y=Y^*=\mathbb R^m$ (EuclideanSpace), identified through the inner product; $A^*$ is ContinuousLinearMap.adjoint A. $F''$ is hess F (derivative of gradient F), $F'''(x)[u]$ is fderiv ℝ (hess F) x u, $[F''(v)]^{-1}$ is ContinuousLinearMap.inverse.
• Published setting reused. IsProperCone, IsSelfScaledBarrier, conj, IsScalingPoint, IsPrimalStrict, IsDualStrict, sigma, lnorm (SelfScaledIPM.ShortStep), and ConvexOptimization.dualCone. The barrier definition includes nondegeneracy of $F''$ on $\operatorname{int}K$, which follows from the other axioms for a pointed cone. conj K F is a supremum over $\operatorname{int}K$ and is only evaluated at points of $\operatorname{int}K^*$. $\sigma$ is an infimum, equal to the page's minimum at interior centres.
• Standing binders. Every theorem except Proposition 4.1 assumes IsProperCone K, IsSelfScaledBarrier K F ν and $\nu\ge1$; the paper derives $\nu\ge1$ from pointedness.
• Conventions. Operator inequalities are quadratic-form inequalities. Step ranges $\alpha\in[0,1/\sigma_x(p))$ are encoded as $0\le\alpha$, $\alpha\sigma_x(p)<1$. Scaling points and search directions are data satisfying their equations; their existence is Theorem 3.2 and Proposition 6.1. "Monotonically" in Proposition 4.1 is read strictly.
• Goal form. Theorem 8.2 is stated for one iteration from any strictly feasible pair. It asserts that the $\bar\alpha$-step is strictly interior and achieves the bound. Without that clause, a goal asserting the bound only for steps accepted by rule (c) would be vacuous whenever no step is accepted, since $F_*$ and $\ln$ take junk values off their domains.
• New definitions (SelfScaledLongStep.PrimalDual.Defs): the projection system (6.4), the potential $\phi$, the system (8.1), $\bar\sigma$ and $\bar\alpha$. The projection system is shared, under the same name, with the other missions of this series.
• Contributions welcome: calculus of self-concordant barriers on cones (C³ smoothness, logarithmic homogeneity identities, Legendre duality between $F$ and $F_*$), which is reusable for any interior-point formalization; proofs of the milestones in any order.

Selected references

• Yu. E. Nesterov and M. J. Todd, Self-scaled barriers and interior-point methods for convex programming, Mathematics of Operations Research 22(1), 1997, 1–42. https://doi.org/10.1287/moor.22.1.1
• Yu. E. Nesterov and M. J. Todd, Primal-dual interior-point methods for self-scaled cones, SIAM Journal on Optimization 8(2), 1998, 324–364. https://doi.org/10.1137/S1052623495290209
• Yu. Nesterov and A. Nemirovskii, Interior-Point Polynomial Algorithms in Convex Programming, SIAM, 1994. https://doi.org/10.1137/1.9781611970791
• M. Kojima, S. Mizuno and A. Yoshise, An $O(\sqrt n L)$ iteration potential reduction algorithm for linear complementarity problems, Mathematical Programming 50, 1991, 331–342. https://doi.org/10.1007/BF01594942
• M. J. Todd and Y. Ye, A centered projective algorithm for linear programming, Mathematics of Operations Research 15(3), 1990, 508–529. https://doi.org/10.1287/moor.15.3.508