Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§7.2, p. 31 — ⟨s̃(λ), x̂⟩ = ⟨−F′(x̂), p(c)⟩ + λ((‖F′(x̂)‖∗_x̂)² − ‖p(d)‖²_x̂) is increasing in λ

Proved
SelfScaledLongStep.AffinePot.gap_monotone

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

interior-pointlower-bound-updatep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1potential-reductionself-scaled-barrier

Let KKK be a self-scaled cone in EEE with ν\nuν-self-scaled barrier FFF, and consider the conic problem (P)(P)(P): min⁡⟨c,x⟩\min \langle c, x\ranglemin⟨c,x⟩ subject to Ax=bAx = bAx=b, x∈Kx \in Kx∈K, with AAA surjective and the dual (D)(D)(D) strictly feasible. Let x^∈S0(P)\hat x \in S^0(P)x^∈S0(P), i.e. x^∈int⁡K\hat x \in \operatorname{int} Kx^∈intK and Ax^=bA\hat x = bAx^=b. Let p(c)p(c)p(c) and p(d)p(d)p(d) be the projections of ccc and of d=F′(x^)d = F'(\hat x)d=F′(x^) into ker⁡A\ker AkerA with respect to F′′(x^)F''(\hat x)F′′(x^), i.e.

Ap(u)=0,A∗y(u)+F′′(x^)p(u)=u(u=c, d),Ap(u) = 0,\qquad A^*y(u) + F''(\hat x)p(u) = u\qquad (u = c,\ d),Ap(u)=0,A∗y(u)+F′′(x^)p(u)=u(u=c, d),

and for λ∈R\lambda \in \mathbb Rλ∈R let s~(λ)=F′′(x^)(p(c)+λp(d))−λF′(x^)\tilde s(\lambda) = F''(\hat x)(p(c) + \lambda p(d)) - \lambda F'(\hat x)s~(λ)=F′′(x^)(p(c)+λp(d))−λF′(x^). Then for every λ\lambdaλ,

⟨s~(λ),x^⟩=⟨−F′(x^),p(c)⟩+λ((∥F′(x^)∥x^∗)2−⟨F′(x^),p(d)⟩)=⟨−F′(x^),p(c)⟩+λ((∥F′(x^)∥x^∗)2−∥p(d)∥x^2),\langle \tilde s(\lambda), \hat x\rangle = \langle -F'(\hat x), p(c)\rangle + \lambda\Big(\big(\|F'(\hat x)\|^*_{\hat x}\big)^2 - \langle F'(\hat x), p(d)\rangle\Big) = \langle -F'(\hat x), p(c)\rangle + \lambda\Big(\big(\|F'(\hat x)\|^*_{\hat x}\big)^2 - \|p(d)\|^2_{\hat x}\Big),⟨s~(λ),x^⟩=⟨−F′(x^),p(c)⟩+λ((∥F′(x^)∥x^∗​)2−⟨F′(x^),p(d)⟩)=⟨−F′(x^),p(c)⟩+λ((∥F′(x^)∥x^∗​)2−∥p(d)∥x^2​),

and this gap is a nondecreasing function of λ\lambdaλ. Here ∥u∥x^∗=⟨u,[F′′(x^)]−1u⟩1/2\|u\|^*_{\hat x} = \langle u, [F''(\hat x)]^{-1}u\rangle^{1/2}∥u∥x^∗​=⟨u,[F′′(x^)]−1u⟩1/2 and ∥p∥x^=⟨F′′(x^)p,p⟩1/2\|p\|_{\hat x} = \langle F''(\hat x)p, p\rangle^{1/2}∥p∥x^​=⟨F′′(x^)p,p⟩1/2.

The monotonicity is what makes the lower-bound update (7.17) well defined: the best dual bound obtainable from s~(λ)∈K∗\tilde s(\lambda) \in K^*s~(λ)∈K∗ is attained at the smallest admissible λ\lambdaλ.

Formalization Note E=E∗=RnE = E^* = \mathbb R^nE=E∗=Rn through the inner product. ∥u∥x^∗\|u\|^*_{\hat x}∥u∥x^∗​ is dnorm F x̂ u and ∥p∥x^\|p\|_{\hat x}∥p∥x^​ is lnorm F x̂ p (the published 1998 setting drops the star). Nondegeneracy of F′′F''F′′ is part of the inherited barrier definition, and the conjugate barrier of the setting is an sSup over int⁡K\operatorname{int}KintK; neither is used in this statement. The paper says "increasing"; the slope (∥F′(x^)∥x^∗)2−∥p(d)∥x^2=ν−∥p(d)∥x^2(\|F'(\hat x)\|^*_{\hat x})^2 - \|p(d)\|^2_{\hat x} = \nu - \|p(d)\|^2_{\hat x}(∥F′(x^)∥x^∗​)2−∥p(d)∥x^2​=ν−∥p(d)∥x^2​ can be zero, so the statement is Monotone (nondecreasing), which is the true reading. The standing hypothesis ν≥1\nu \ge 1ν≥1 is carried as a binder (the paper derives it from pointedness). The §7 assumption that the objective is not constant on the feasible region is not needed here and is omitted.

Preamble
import Mathlib
import Definitions.Def_dualCone
import Definitions.Def_SelfScaledIPM_ShortStep_Setting
import Definitions.Def_SelfScaledIPM_ShortStep_Measures
import Definitions.Def_SelfScaledLongStep_AffinePot_Defs

open scoped InnerProductSpace
open SelfScaledIPM.ShortStep
Formal statement
namespace SelfScaledLongStep.AffinePot

/-- **§7.2, p. 31, display before (7.17).** With `pc = p(c)`, `pd = p(d)` the projections (7.12)
of `c` and `d = F'(x̂)`, the gap
`⟨s̃(λ), x̂⟩ = ⟨−F'(x̂), p(c)⟩ + λ((‖F'(x̂)‖*_x̂)² − ⟨F'(x̂), p(d)⟩)
           = ⟨−F'(x̂), p(c)⟩ + λ((‖F'(x̂)‖*_x̂)² − ‖p(d)‖²_x̂)`
is a (weakly) increasing function of `λ`. -/
theorem gap_monotone {n m : ℕ} (K : Set (EuclideanSpace ℝ (Fin n))) (hK : IsProperCone K)
    (F : EuclideanSpace ℝ (Fin n) → ℝ) (ν : ℝ) (hν : 1 ≤ ν) (hF : IsSelfScaledBarrier K F ν)
    (A : EuclideanSpace ℝ (Fin n) →L[ℝ] EuclideanSpace ℝ (Fin m)) (hA : Function.Surjective A)
    (b : EuclideanSpace ℝ (Fin m)) (c : EuclideanSpace ℝ (Fin n))
    (hD : ∃ y s, IsDualStrict K A c y s)
    (xh : EuclideanSpace ℝ (Fin n)) (hxh : IsPrimalStrict K A b xh)
    (yc : EuclideanSpace ℝ (Fin m)) (pc : EuclideanSpace ℝ (Fin n))
    (hpc : SelfScaledLongStep.PrimalDual.IsProjection F A xh c yc pc)
    (yd : EuclideanSpace ℝ (Fin m)) (pd : EuclideanSpace ℝ (Fin n))
    (hpd : SelfScaledLongStep.PrimalDual.IsProjection F A xh (gradient F xh) yd pd) :
    (∀ t : ℝ, ⟪sTilde F xh pc pd t, xh⟫_ℝ =
        ⟪-gradient F xh, pc⟫_ℝ + t * ((dnorm F xh (gradient F xh)) ^ 2 - ⟪gradient F xh, pd⟫_ℝ)) ∧
    (∀ t : ℝ, ⟪sTilde F xh pc pd t, xh⟫_ℝ =
        ⟪-gradient F xh, pc⟫_ℝ + t * ((dnorm F xh (gradient F xh)) ^ 2 - (lnorm F xh pd) ^ 2)) ∧
    Monotone (fun t : ℝ => ⟪sTilde F xh pc pd t, xh⟫_ℝ) := by sorry

end SelfScaledLongStep.AffinePot
Source
Nesterov & Todd, Self-scaled barriers and interior-point methods for convex programming, Math. Oper. Res. 22(1) (1997) 1–42, p. 31, §7.2, display before (7.17)
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me