Alphabeta Math
Pipeline-generated
How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

  • Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
  • AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
  • AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Barrier and primal dual interior point methods

1 · Prerequisites

2 · Summary

Objective

Develop log barriers and central paths for smooth convex inequalities and conic programs; prove the exact central-point primal-dual barrier gaps m/t and ν/t together with the resulting objective-error bounds; define finite-budget LP/QP and symmetric-cone primal-dual Newton residual systems with fraction-to-boundary updates; and prove the short-step path-following bound from local self-concordant calculus. The page includes the orthant, Lorentz, and positive-semidefinite barriers with their domains and parameters. Residual tolerances alone remain candidate diagnostics; a stopping certificate requires verified primal and dual feasibility and a gap bound. Phase I gives a strict-feasibility margin; a zero margin without an attainment check remains inconclusive, including for weakly infeasible SDPs.

3 · Logical flowchart

4 · Definitions, theorems and proofs

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Self-concordant log-homogeneous barriers and their local geometry

Definition

Let E be a finite-dimensional real inner-product space, let D⊂E be open and convex, and let F:D→R be C3. Write HF(x)=D2F(x) for its Hessian as a self-adjoint operator. A self-concordant barrier on D is a strictly convex F with positive-definite Hessian, with F(xk)→+∞ whenever xk approaches a finite boundary point of D, and satisfying both conditions below.

For x∈D, define the local norm and its dual by ∥h∥x=D2F(x)[h,h],∥ℓ∥x,∗=sup⁡∥h∥x≤1∣ℓ[h]∣. The Dikin inclusion is {x+h:∥h∥x<1}⊂D. The self-concordance inequality is ∣D3F(x)[u,v,v]∣≤2∥u∥x∥v∥x2(u,v∈E). The Newton decrement is λF(x)=∥DF(x)∥x,∗.

If K⊂E is a closed convex cone with nonempty interior and D=int⁡K, the barrier is ν-log-homogeneous when ν>0, F(αx)=F(x)−νlog⁡α for every x∈D and α>0, and λF(x)≤ν for every x∈D. The number ν is its barrier parameter. When equality constraints Ax=b are imposed, local norms and decrements are computed after restricting D2F and DF to the tangent space ker⁡A.

DefinitionDefinition: AI-adaptedProof: Not applicableOpen item page →

Conic, LP, and convex QP primal-dual models

Definition

For a finite-dimensional real inner-product space E, a cone is a set closed under addition and multiplication by nonnegative scalars. A cone K⊂E is proper when it is closed, convex, pointed (K∩(−K)={0}), and has nonempty interior. Its dual cone is K∗={z∈E:⟨z,s⟩≥0 for every s∈K}.

Let A:Rn→Rp and G:Rn→E be linear, let b∈Rp, c∈Rn, and h∈E. A matrix A has full row rank when its rows are linearly independent. The conic primal problem and its displayed dual pair are inf⁡{cTx:Ax=b, h−Gx∈K},sup⁡{bTy−⟨h,z⟩:ATy−G∗z=c, z∈K∗}, where G∗ is the adjoint, defined by ⟨Gx,z⟩=xTG∗z. For any feasible pair, its gap is cTx−bTy+⟨h,z⟩=⟨z,h−Gx⟩≥0. The special case inf⁡{cTx:Ax=b, x∈K} has dual sup⁡{bTy:ATy+z=c, z∈K∗} and gap ⟨z,x⟩.

For K=R+n, the latter is the standard-form LP min⁡cTx subject to Ax=b, x≥0, with dual variables y free and s=c−ATy≥0. A convex QP in this convention has objective f0(x)=12xTQx+cTx, with symmetric Q⪰0, the same equality, and x≥0. Its Lagrangian is L(x,y,s)=f0(x)+yT(b−Ax)−sTx; a feasible KKT tuple obeys Qx+c−ATy−s=0, and its dual function is q(y,s)=inf⁡w∈RnL(w,y,s). The dual value is d∗=sup⁡y∈Rp, s≥0q(y,s).

For a Lorentz cone Ld+1={(t,u)∈R×Rd:t≥∥u∥2}, let Fj∈Rdj×n, fj∈Rdj, gj∈Rn, and hj∈R. Then ∥Fjx+fj∥2≤gjTx+hj is membership of (gjTx+hj,Fjx+fj) in Ldj+1. With no equality constraints, the SOCP min⁡cTx under these constraints has dual max⁡−∑j(fjTuj+hjτj)subject to ∑j(FjTuj+gjτj)=c,(τj,uj)∈Ldj+1. For symmetric matrices, S⪰0 means vTSv≥0 for every v and the pairing is ⟨X,S⟩=X∙S:=tr⁡(XS). Thus min⁡C∙X subject to A(X)=b, X⪰0 has dual max⁡bTy subject to A∗y+S=C, S⪰0, with gap X∙S. The affine-matrix SDP min⁡cTx subject to F0+∑ixiFi⪰0 has dual max⁡−F0∙Z subject to Fi∙Z=ci for every i and Z⪰0.

The smooth convex inequality convention is that of Inequality constrained programs, tangent cones, constraint qualifications, and KKT: inequalities are written gi(x)≤0 and their multipliers are nonnegative. The Lagrangian dual-value convention is that of Finite-dimensional convex program, Lagrangian dual, and Slater condition.

LemmaStatement: AI-adaptedProof: AI-adaptedOpen item page →

Local Hessian comparison, damped Newton decrement, and center distance

Statement

Let F be a self-concordant barrier as in Self-concordant log-homogeneous barriers and their local geometry. Put Hx=D2F(x), λ=λF(x), and let d=−Hx−1∇F(x) be the Newton direction when the ambient Hessian is used. The analogous statements hold on an affine feasible subspace with its restricted Hessian and gradient.

For h∈E, put r=∥h∥x. Whenever the whole segment x+[0,t]h lies in D, the local metric satisfies the lower bound below. If tr<1 (with no restriction when r=0), Dikin inclusion guarantees that the segment lies in D and the upper bound also holds: r1+tr≤∥h∥x+th≤r1−tr. If tr<1, then (1−tr)2Hx⪯Hx+th⪯(1−tr)−2Hx. For every λ≥0, the damped step y=x+d/(1+λ) lies in D and obeys λF(y)≤2λ2. If λF(x)<1, then F has a unique attained global minimizer x∗ in D, and ∥x−x∗∥x≤λF(x)1−λF(x).

Facts & Assumptions

Given: The self-concordance, Dikin inclusion, and local norm definitions in Self-concordant log-homogeneous barriers and their local geometry.

[F1]

The defining mixed derivative bound is ∣D3F(x)[u,v,v]∣≤2∥u∥x∥v∥x2 (Self-concordant log-homogeneous barriers and their local geometry).

[F2]

The local norm is induced by the positive-definite Hessian Hx and its dual norm is induced by Hx−1 (Self-concordant log-homogeneous barriers and their local geometry).

Proof

1.1givenF1algebra

Fix h≠0 and put q(t)=∥h∥x+th. Differentiation gives q′(t)=D3F(x+th)[h,h,h]/(2q(t)), so [F1] implies ∣q′(t)∣≤q(t)2. Therefore ∣(1/q)′∣≤1. Integrating from 0 to t yields 1/r−t≤1/q(t)≤1/r+t whenever tr<1, and the lower inequality 1/q(t)≤1/r+t holds along every segment in D. Taking reciprocals gives the asserted two-sided metric bound for tr<1 and the lower bound for all t≥0.

2.1F1step 1.1algebra

For a fixed v≠0, put p(t)=D2F(x+th)[v,v]. By [F1], ∣(log⁡p)′∣=∣D3F[h,v,v]∣/(2p2)≤q(t). When tr<1, step 1.1 gives q(t)≤r/(1−tr); integration gives ∣log⁡(p(t)/p(0))∣≤−log⁡(1−tr). Squaring this inequality for every v proves the stated Hessian comparison.

2.2F1F2step 1.1algebra

For any y∈D, put h=y−x and r=∥h∥x. Taylor's formula with integral remainder and step 1.1 give F(y)≥F(x)+DF(x)[h]+r2∫011−t(1+tr)2 dt=F(x)+DF(x)[h]+r−log⁡(1+r). The dual-norm inequality DF(x)[h]≥−λF(x)r makes the right side at least F(x)+(1−λF(x))r−log⁡(1+r), which tends to +∞ as r→∞ when λF(x)<1. Under this condition the sublevel set {y∈D:F(y)≤F(x)} is bounded.

3.1F2step 2.1algebraconstruct

Since ∥d∥x=λ, the damped displacement h=d/(1+λ) has local length r=λ/(1+λ)<1, so Dikin inclusion places y in D. The gradient expansion is ∇F(y)=∇F(x)+Hxh+R, where R=∫01(Hx+th−Hx)h dt. The first two terms have x-dual norm λ2/(1+λ). By step 2.1, ∥R∥x,∗≤r∫01((1−tr)−2−1) dt=r2/(1−r)=λ2/(1+λ). Thus ∥∇F(y)∥x,∗≤2λ2/(1+λ). Since Hy⪰(1−r)2Hx, the dual norm at y is at most (1−r)−1=1+λ times the x-dual norm, giving λF(y)≤2λ2.

3.2givenstep 2.2construct

Assume now λF(x)<1. The sublevel set in step 2.2 cannot accumulate at a finite boundary point of D, because F blows up there while its values on the sublevel are at most F(x). It is closed in E and bounded, hence compact. Continuity gives a minimizer on it, which is a global minimizer on D; positive-definite Hessian makes it unique.

4.1step 1.1step 3.2F2algebra∎

Let h=x∗−x and r=∥h∥x. If r=0 the claim holds. Otherwise, stationarity at the minimizer from step 3.2 and the fundamental theorem of calculus give −∇F(x)Th=∫01∥h∥x+th2 dt. By the global lower bound from step 1.1, this is at least r2∫01(1+tr)−2 dt=r2/(1+r). Cauchy–Schwarz in the local metric bounds it above by λF(x)r. Dividing by r and rearranging gives r≤λF(x)/(1−λF(x)).

LemmaStatement: Literature-sourcedProof: AI-adaptedOpen item page →

The orthant logarithmic barrier has parameter equal to its dimension

Statement

For m≥1, let K=R+m, D=R++m, and F(x)=−∑i=1mlog⁡xi. Under the standard Euclidean pairing, K∗=K. The function F is an m-log-homogeneous self-concordant barrier on D and λF(x)=m for every x∈D.

Facts & Assumptions

Given: The local norm and self-concordant barrier convention of Self-concordant log-homogeneous barriers and their local geometry.

[F1]

For the Euclidean norm, Cauchy–Schwarz gives ∣aTb∣≤∥a∥2∥b∥2 (Cauchy-Schwarz ∣⟨x,y⟩∣≤∥x∥2∥y∥2 with its equality case, the triangle inequality for ∥⋅∥2, the parallelogram law and polarisation).

[F2]

The dual cone is K∗={z:⟨z,y⟩≥0 for every y∈K} (Conic, LP, and convex QP primal-dual models).

Proof

1.1givenF2algebra

Coordinatewise inequalities show that K is closed, convex, and closed under addition and nonnegative scaling. If both z and −z lie in K, every coordinate is zero, so K is pointed; because m≥1, D=R++m is nonempty and is the interior of K. If z∈K, then ⟨z,y⟩=∑iziyi≥0 for every y∈K, so z∈K∗ by [F2]. Conversely, if z∈K∗, testing against each standard basis vector ei∈K gives zi=⟨z,ei⟩≥0. Hence z∈K and K∗=K.

1.2givenF1algebra

Direct differentiation gives DF(x)[h]=−∑ihi/xi, D2F(x)[h,k]=∑ihiki/xi2, and D3F(x)[u,v,v]=−2∑iuivi2/xi3. The Hessian is positive definite because D2F(x)[h,h]=∑i(hi/xi)2>0 for h≠0. If ∥h∥x<1, then each ∣hi∣/xi<1, hence xi+hi>0 and the Dikin inclusion holds. If a sequence in D approaches a finite boundary point, at least one coordinate tends to zero while all coordinates remain bounded above; each term −log⁡xi is bounded below and one tends to +∞, so F→+∞.

2.1F1step 1.2algebra∎

Put ai=ui/xi and bi=vi/xi. By [F1] and ∑ibi4≤(∑ibi2)2, ∣D3F(x)[u,v,v]∣≤2∥a∥2(∑ibi4)1/2≤2∥u∥x∥v∥x2. Also F(αx)=F(x)−mlog⁡α, and ∥DF(x)∥x,∗2=∑i(1/xi)2xi2=m. These are exactly the required self-concordance and parameter conditions.

LemmaStatement: Literature-sourcedProof: AI-adaptedOpen item page →

The Lorentz logarithmic barrier has parameter two

Statement

For d≥1, let K=Ld+1={(t,u):t≥∥u∥2} and F(t,u)=−log⁡(t2−∥u∥22) on D=int⁡K. The cone is self-dual under the Euclidean pairing. The function F is a 2-log-homogeneous self-concordant barrier and λF(x)=2 throughout D.

Facts & Assumptions

Given: The Euclidean pairing and the self-concordant barrier convention of Self-concordant log-homogeneous barriers and their local geometry.

[F1]

The local norm is the square root of the Hessian quadratic form, and its dual is induced by the inverse Hessian (Self-concordant log-homogeneous barriers and their local geometry).

[F2]

The dual cone is the set of vectors pairing nonnegatively with every cone element (Conic, LP, and convex QP primal-dual models).

Proof

1.1F2givenalgebra

Continuity of the Euclidean norm makes K closed, and its triangle inequality makes K convex and closed under addition and nonnegative scaling. If (t,u) and its negative are both in K, then t≥∥u∥ and −t≥∥u∥, forcing t=0,u=0; hence K is pointed. The point (1,0) is interior, so K is proper. If (a,v)∈K and (t,u)∈K, then at+vTu≥at−∥v∥2∥u∥2≥0, so K⊆K∗ by [F2]. Conversely, suppose (a,v)∈K∗. If v=0 and a<∥v∥2=0, then pairing with (1,0)∈K gives a<0, a contradiction. If v≠0 and a<∥v∥2, pairing with (1,−v/∥v∥2)∈K gives a−∥v∥2<0, also a contradiction. Thus a≥∥v∥2 and K∗=K.

1.2givenF1algebraconstruct

Write ρ=t2−∥u∥22>0. An orthogonal change of spatial coordinates followed by the Lorentz boost ρ−1/2(t−∥u∥−∥u∥t) on the time and first spatial coordinate preserves ρ and maps (t,u) to (ρ,0). Since F is invariant under this invertible linear cone map, the chain rule transports its Hessian, third derivative, and local norms; the Newton decrement is invariant as well. At the canonical point ∇F=(−2/ρ,0) and D2F=(2/ρ)I. For directions h=(a,p) and k=(b,v), direct differentiation gives D3F[h,k,k]=−4{a(b2+∥v∥22)+2b pTv}ρ3/2. These formulas also show the Hessian is positive definite.

2.1step 1.2F1algebra∎

By Cauchy–Schwarz and 2∣b∣∥v∥2≤b2+∥v∥22, the numerator in step 1.2 has absolute value at most 42a2+∥p∥22(b2+∥v∥22)/ρ3/2=2∥h∥x∥k∥x2. If ∥h∥x<1, set A=∣a∣/ρ and B=∥p∥2/ρ. Then A2+B2<1/2, so 1+a/ρ≥1−A>0 and (1+a/ρ)2−B2≥(1−A)2−B2>2(A−1/2)2≥0. Thus ρ+a>∥p∥2 and the Dikin ball stays inside D. The Lorentz transformation carries this inclusion to every x. Approaching a finite boundary point makes ρ↓0, hence F→+∞. Finally, F(αx)=F(x)−2log⁡α, and step 1.2 gives ∥DF(x)∥x,∗2=2.

LemmaStatement: Literature-sourcedProof: AI-adaptedOpen item page →

The positive semidefinite cone is self-dual and its log determinant barrier has parameter n

Statement

Let n≥1, let Sn have trace pairing ⟨X,Y⟩=tr⁡(XY), and let S+n be the cone of real symmetric positive semidefinite matrices. Then (S+n)∗=S+n. On S++n, F(X)=−log⁡det⁡X is an n-log-homogeneous self-concordant barrier, with DF(X)[H]=−tr⁡(X−1H),D2F(X)[H,J]=tr⁡(X−1HX−1J), and λF(X)=n.

Facts & Assumptions

Given: The trace pairing, positive-definite matrices, and the self-concordant barrier convention.

[F1]

Every real symmetric matrix has an orthonormal eigenbasis (Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis).

[F2]

The trace pairing on symmetric matrices is ⟨X,Y⟩=tr⁡(XY) and X⪰0 means vTXv≥0 for every v (Conic, LP, and convex QP primal-dual models).

[F3]

The determinant differential on invertible matrices is Ddet⁡(X)[H]=det⁡(X)tr⁡(X−1H) (The determinant differential is Ddet⁡(A)[H]=tr⁡(adj⁡(A)H) at every matrix, and Jacobi's formula holds on the invertible locus).

[F4]

The derivative of inversion is D(X−1)[H]=−X−1HX−1 (On the invertible locus, Dinv⁡(A)[H]=−A−1HA−1).

[F5]

The trace is linear in matrix entries (Trace and Frobenius-linear matrix functionals differentiate by inspection, The trace tr⁡(A) as the sum of the diagonal entries).

[F6]

The log determinant is concave on the positive-definite cone (The log determinant is concave on positive-definite matrices); this published result is reused, not reproved as a separate concavity theorem here.

[F7]

The Frobenius norm is ∥M∥F=(∑i,jMij2)1/2 for real matrices.

[F8]

Euclidean vectors satisfy Cauchy–Schwarz (Cauchy-Schwarz ∣⟨x,y⟩∣≤∥x∥2∥y∥2 with its equality case, the triangle inequality for ∥⋅∥2, the parallelogram law and polarisation).

Proof

1.1F1F2F5F7algebra

The set S+n is a closed convex cone because quadratic-form inequalities are preserved by nonnegative sums and limits. If both X and −X are positive semidefinite, their quadratic forms vanish on every vector; testing ei gives Xii=0, then testing ei+ej gives Xij=0, so the cone is pointed. The identity is interior: diagonalize E=ET=Udiag⁡(λi)UT. From the entry definition, ∥E∥F2=∑i,jEij2=tr⁡(E2); the finite sums give tr⁡(AB)=∑i,jAijBji=∑j,iBjiAij=tr⁡(BA), so tr⁡(E2)=tr⁡(diag⁡(λi2))=∑iλi2. Thus ∥E∥F<1 implies ∣λi∣<1 for every i, hence I+E≻0, proving that I is interior and the cone is proper. If X,Y⪰0, their positive square roots exist by [F1]. The same trace identity gives tr⁡(XY)=tr⁡(X1/2YX1/2)≥0, since X1/2YX1/2⪰0 and its diagonal entries are nonnegative. Thus S+n⊆(S+n)∗. Conversely, if Y is in the dual cone under [F2], testing against vvT⪰0 gives vTYv=tr⁡(YvvT)≥0 for every v, so Y⪰0.

1.2F1F2F3F4F5algebraconstruct

For X≻0 and symmetric H, set Z=X−1/2HX−1/2. Then det⁡(X+sH)=det⁡(X)det⁡(I+sZ). Diagonalizing the symmetric Z and differentiating the scalar sum −log⁡det⁡(X+sH)=−log⁡det⁡X−∑ilog⁡(1+sλi(Z)) gives DF(X)[H]=−tr⁡(X−1H) and D2F(X)[H,H]=tr⁡(Z2). Polarization gives the displayed bilinear Hessian formula. Equivalently the first derivative follows from [F3], and differentiating it uses [F4]–[F5].

2.1F1F7F8step 1.2algebra

Differentiating the inverse formula once more gives D3F(X)[U,V,V]=−2tr⁡(ZUZV2), where ZU=X−1/2UX−1/2 and ZV=X−1/2VX−1/2. By [F8] after vectorizing matrices, ∣tr⁡(ZUZV2)∣≤∥ZU∥F∥ZV2∥F. Diagonalizing the symmetric ZV gives ∥ZV2∥F2=∑iλi4≤(∑iλi2)2=∥ZV∥F4. The latter Frobenius norms are exactly the local norms, proving the mixed self-concordance inequality. Also ∥Z∥2=max⁡i∣λi(Z)∣≤(∑iλi(Z)2)1/2=∥Z∥F, so if ∥H∥X=∥Z∥F<1, then I+Z≻0 and X+H≻0.

3.1F1F5F6step 1.2algebra∎

Scaling gives F(αX)=F(X)−nlog⁡α. The local dual norm satisfies ∥DF(X)∥X,∗2=tr⁡(In)=n. If a sequence tends to a finite boundary matrix, its determinant tends to zero through positive values, so F→+∞. These facts, [F6], and the positive-definite Hessian in step 1.2 establish the stated barrier properties.

LemmaStatement: AI-adaptedProof: AI-adaptedOpen item page →

The negative gradient of a log-homogeneous cone barrier is dual feasible

Statement

Let K be a proper cone in a finite-dimensional real inner-product space and let F be a differentiable ν-log-homogeneous barrier on int⁡K. Then for every x∈int⁡K, −∇F(x)∈K∗,DF(x)[x]=−ν.

Facts & Assumptions

Given: The dual-cone and log-homogeneity definitions in Conic, LP, and convex QP primal-dual models and Self-concordant log-homogeneous barriers and their local geometry.

[F1]

K∗={z:⟨z,k⟩≥0 for all k∈K} (Conic, LP, and convex QP primal-dual models), and F(αx)=F(x)−νlog⁡α for α>0 (Self-concordant log-homogeneous barriers and their local geometry).

Proof

1.1givenF1algebra

Fix y∈int⁡K and let ϕ(t)=F(x+ty) for t≥0. The sum of an interior cone point and a cone point is interior, so ϕ is defined and convex. Log-homogeneity gives ϕ(t)=F(y+x/t)−νlog⁡t for t>0, which tends to −∞ as t→∞. If DF(x)[y]=ϕ′(0)>0, convexity would imply ϕ(t)≥ϕ(0)+tϕ′(0)→+∞, a contradiction. Thus DF(x)[y]≤0 for all interior y.

2.1F1step 1.1algebra∎

For any y∈K and ε>0, y+εx∈int⁡K: an open ball around εx lies in K, and adding y∈K keeps that ball in K. Step 1.1 applied to y+εx and continuity of the linear functional DF(x) as ε↓0 give DF(x)[y]≤0. Hence −∇F(x) pairs nonnegatively with every y∈K, so it lies in K∗ by [F1]. Differentiating F(αx)=F(x)−νlog⁡α at α=1 gives DF(x)[x]=−ν.

DefinitionDefinition: AI-adaptedProof: Not applicableOpen item page →

Log-barrier central paths and primal-dual Newton residuals

Definition

For a C2 inequality problem with the convention of Inequality constrained programs, tangent cones, constraint qualifications, and KKT, let D⊆Rn be open and convex, let f0,g1,…,gm be convex C2 functions on D, and let A∈Rp×n and b∈Rp. Assume there exists x∈D with Ax=b and gi(x)<0 for every i. For t>0, its log-barrier objective is Ψt(x)=tf0(x)−∑i=1mlog⁡(−gi(x)),Ax=b,gi(x)<0. Any attained minimizer is a central point. Its central multipliers are λi=−1/(tgi(x))>0. A central point and multiplier tuple satisfy Ax=b, g(x)<0, and ∇f0(x)+Dg(x)Tλ+ATν=0 for an equality multiplier ν.

For the conic model of Conic, LP, and convex QP primal-dual models, let s=h−Gx∈int⁡K and let F be a self-concordant barrier on K. The conic barrier objective is Φt(x)=tcTx+F(h−Gx) restricted to Ax=b. An attained minimizer xt satisfies tc−G∗∇F(st)+ATw=0,Axt=b,st=h−Gxt∈int⁡K for some w∈Rp. Its barrier multiplier is zt=−∇F(st)/t.

For a standard-form LP or convex QP with n≥1, Ax=b, x≥0, and objective f0(x)=12xTQx+cTx (Q=0 for an LP), define the primal-dual residuals rd=Qx+c−ATy−s,rp=Ax−b,rc=Xs−σμ1, where X=diag⁡(x), S=diag⁡(s), μ=xTs/n, and 0<σ<1. For x,s>0, the modified KKT Newton direction solves [Q−AT−IA00S0X][ΔxΔyΔs]=−[rdrprc].

For orthant, Lorentz, or positive-semidefinite cone factors, define the diagnostic conic residuals as rp=Ax−b, rd=ATy−G∗z−c, and rc=s∘z−σμe. These factors are self-dual under their standard Euclidean or trace pairings by The orthant logarithmic barrier has parameter equal to its dimension, The Lorentz logarithmic barrier has parameter two, and The positive semidefinite cone is self-dual and its log determinant barrier has parameter n, so s and z occupy the same factor spaces. For the orthant, ∘ is coordinatewise multiplication and e=1. The Lorentz Jordan product is (t,u)∘(q,v)=(tq+uTv,tv+qu) with e=(1,0); for symmetric matrices X∘S=(XS+SX)/2 with e=I. In each factor, pairing s∘z with e gives ⟨s,z⟩: this is the coordinate sum for the orthant, the first coordinate for the Lorentz product, and tr⁡((XS+SX)/2)=tr⁡(XS) for symmetric matrices by the finite-index trace identity. In each product cone, μ=⟨s,z⟩/ν, where ν is the sum of the factor barrier parameters. This Jordan target is a diagnostic convention, not in general the centered residual for the selected barrier F: for a Lorentz factor F(t,u)=−log⁡(t2−∥u∥22), s∘(−∇F(s))=2e, whereas the orthant and log-determinant barriers give e. Thus their barrier multipliers have factor targets 2e/t and e/t, respectively, although the product gap gives μ=1/t. No equivalence between rc=0 and that barrier central path is asserted. When forming a Newton direction for this diagnostic target, hold σμ fixed. The linearized slack is Δs=−GΔx.

Residual tolerances describe a candidate unless an independent argument also verifies feasibility and a primal-dual gap. A finite iteration or factorization budget that returns a candidate, failure, or inconclusive status is not itself an optimality certificate.

TheoremStatement: AI-adaptedProof: AI-adaptedOpen item page →

The conic phase-I margin separates strict feasibility but may leave weak infeasibility undecided

Statement

Let K be a proper cone, let e∈int⁡K, and consider the conic feasibility system Ax=b, h−Gx∈K. Define its Phase-I margin value ρ∗=inf⁡{τ∈R:Ax=b, h−Gx+τe∈K}, with ρ∗=+∞ if the set is empty. If ρ∗<0, the original system has a strictly feasible point. If ρ∗>0 or ρ∗=+∞, the original system is infeasible. If ρ∗=0 and the infimum is attained, the original system is feasible but not strictly feasible; if ρ∗=0 and the infimum is not attained, the original system is infeasible. Thus a zero value without an attainment check decides neither. A finite-budget Phase-I computation certifies a negative sign from a verified feasible margin point with τ<0, or a positive sign from a verified positive lower bound; failure to find strict feasibility is not an infeasibility certificate.

Facts & Assumptions

Given: The conic feasibility model and proper-cone convention of Conic, LP, and convex QP primal-dual models.

[F1]

A proper cone is closed, convex, closed under addition and positive scaling, and has nonempty interior (Conic, LP, and convex QP primal-dual models).

Proof

1.1givenF1algebra

If ρ∗<0, then by the definition of an infimum some feasible pair (x,τ) has τ<0. Write h−Gx+τe=k∈K. Then h−Gx=k+(−τ)e. An open ball around (−τ)e∈int⁡K lies in K; translating that ball by k∈K keeps it in K+K⊆K. Hence k+(−τ)e∈int⁡K, so Ax=b and h−Gx∈int⁡K.

2.1F1step 1.1algebra∎

If the original system has a feasible x, then τ=0 is feasible for the Phase-I set, hence ρ∗≤0. This proves infeasibility when ρ∗>0 or the Phase-I set is empty. If ρ∗=0 is attained, the attaining pair cannot have τ<0, since that would force ρ∗<0; hence it has τ=0 and its x is originally feasible. Strict feasibility at some x would give s=h−Gx∈int⁡K. Because int⁡K is open and e∈int⁡K, there is δ>0 small enough that s−δe∈K, making τ=−δ feasible and contradicting ρ∗=0. If ρ∗=0 is not attained, original feasibility would itself provide an attaining pair at τ=0, a contradiction. Thus zero is inconclusive until attainment is checked.

TheoremStatement: AI-adaptedProof: AI-adaptedOpen item page →

Exact central points have barrier gap m/t or nu/t

Statement

For the smooth convex inequality problem of Log-barrier central paths and primal-dual Newton residuals, suppose a strict feasible exact minimizer xt of the barrier objective exists, the primal value p∗ is finite, and the equality multiplier is included. Use the sign convention L(x,λ,ν)=f0(x)+λTg(x)+νT(Ax−b), and define qD(λ,ν)=inf⁡x∈DL(x,λ,ν) on the common open domain D. Then the Lagrangian dual pair generated by λi=−1/(tgi(xt)) has value qD(λ,ν)=f0(xt)−m/t, so 0≤f0(xt)−p∗≤m/t. For the conic model of Conic, LP, and convex QP primal-dual models, suppose xt is an exact barrier minimizer and F is a ν-log-homogeneous barrier. Its barrier multiplier zt=−∇F(st)/t and equality multiplier give a dual feasible pair with gap ν/t, and hence 0≤cTxt−p∗≤ν/t. No primal attainment or strong-duality assumption is used; existence of the exact barrier minimizer and finiteness of p∗ are required.

Facts & Assumptions

Given: The smooth and conic barrier objectives, their strict feasibility and exact minimizers, and a finite primal value.

[F1]

The smooth inequality convention is gi≤0, with multiplier λi≥0 (Inequality constrained programs, tangent cones, constraint qualifications, and KKT).

[F2]

For differentiable convex L on an open convex domain, L(y)≥L(x)+∇L(x)T(y−x) (Differentiable convex functions are characterized by the gradient inequality).

[F3]

The barrier identity is DF(s)[s]=−ν and −∇F(s)∈K∗ (The negative gradient of a log-homogeneous cone barrier is dual feasible).

Proof

1.1F1F2algebra

In the smooth case, differentiating Ψt at its affine-constrained minimizer gives t∇f0(xt)+Dg(xt)T(−1/g(xt))+ATw=0. Since gi(xt)<0, λi=−1/(tgi(xt))>0, and ν=w/t make this ∇f0+DgTλ+ATν=0. Also λigi(xt)=−1/t for every i. Thus ∇xL(xt,λ,ν)=0 and L(⋅,λ,ν) is convex; [F2] proves that xt globally minimizes this Lagrangian on D. Therefore qD(λ,ν)=L(xt,λ,ν)=f0(xt)−m/t.

2.1F1step 1.1algebra

For every primal feasible x∈D, [F1] gives λi≥0 and gi(x)≤0, hence L(x,λ,ν)=f0(x)+λTg(x)≤f0(x). Thus qD(λ,ν)≤f0(x) for every feasible x, so qD(λ,ν)≤p∗. Since xt is feasible, p∗≤f0(xt). Combining this with step 1.1 yields 0≤f0(xt)−p∗≤m/t.

3.1F3step 2.1algebra∎

In the conic case set zt=−∇F(st)/t∈K∗ by [F3] and yt=−w/t. The stationarity equation in Log-barrier central paths and primal-dual Newton residuals gives ATyt−G∗zt=c, so the pair is dual feasible. The conic gap identity in Conic, LP, and convex QP primal-dual models gives cTxt−(bTyt−⟨h,zt⟩)=⟨zt,st⟩=−DF(st)[st]/t=ν/t. For every primal feasible x, the same identity and zt∈K∗ make its objective at least the dual value, so bTyt−⟨h,zt⟩≤p∗. Since xt is primal feasible, p∗≤cTxt; combining these inequalities with the exact gap gives 0≤cTxt−p∗≤ν/t.

AlgorithmAlgorithm: AI-adaptedProof: Not applicableOpen item page →

Short-step self-concordant path following with finite failure statuses

Definition

Let K be a proper cone, F a ν-log-homogeneous self-concordant barrier on int⁡K, and consider min⁡cTx subject to Ax=b, s=h−Gx∈K. Require the barrier Hessian restricted to ker⁡A to be positive definite, so the affine restriction has a local norm. The local calculus lemma proves that each barrier subproblem has an attained unique center whenever its Newton decrement is below one.

For a strict feasible x with Ax=b, define the restricted local norm by ∥d∥t,x=D2Φt(x)[d,d] for d∈ker⁡A. The decrement used below is the restricted dual norm λt(x)=sup⁡{∣DΦt(x)[d]∣:d∈ker⁡A, ∥d∥t,x≤1}. Thus λt(x) is induced by the barrier Hessian restricted to the feasible tangent space.

Inputs: t0>0, target ε>0, a strictly feasible x0 with restricted decrement λt0(x0)≤1/4, integer caps Nout≥0 and Nin≥2, and an exact linear-system solver for the equality-constrained Newton equations. Output: a record with a status and optional iterate fields. gap-tolerance returns the feasible iterate x, current t, and certified gap bound (ν+ν/2)/t. outer-cap, centering-cap, and newton-solve-failure return the last feasible iterate and current t with no gap certificate. invalid-start returns no iterate and no gap certificate.

  1. Verify Ax0=b, h−Gx0∈int⁡K, the stated initial decrement, and all cap/parameter conditions; otherwise return invalid-start. Set x=x0, t=t0, and both counters to zero.
  2. While (ν+ν/2)/t>ε, first return outer-cap if the outer counter equals Nout. Set α=1+1/(8ν) and t+=αt.
  3. At the current x, compute λ=λt+(x). While λ>1/4 and the inner counter is below Nin, solve the restricted Newton equation D2Φt+(x)[d,⋅]=−DΦt+(x)[⋅] on ker⁡A. If the solve fails, return newton-solve-failure. Otherwise set x←x+d/(1+λ), increment the inner counter, and recompute λ.
  4. If λ>1/4 after the inner loop, return centering-cap. Otherwise accept t←t+, increment the outer counter, reset the inner counter, and repeat step 2.
  5. When the loop condition is false, return gap-tolerance with x, t, and bound (ν+ν/2)/t.

The cap counts Newton corrections, not factorization operations. This definition does not construct a strict feasible start; a Phase-I certificate is a separate input obligation.

TheoremStatement: AI-adaptedProof: AI-adaptedOpen item page →

A verified inexact gradient residual bounds central-path distance and objective error

Statement

Consider the conic model with proper cone K, equality Ax=b, and barrier objective Φt(x)=tcTx+F(h−Gx) as in Log-barrier central paths and primal-dual Newton residuals, where F is a ν-log-homogeneous self-concordant barrier on int⁡K with parameter ν>0. Parameterize the affine feasible space by x=x0+Pz, where Ax0=b and the columns of P are an orthonormal basis of ker⁡A. Let φt(z)=Φt(x0+Pz) on an open convex region containing an exact central minimizer z∗ and a strict feasible candidate z~. Assume D2φt(z)⪰μI on that region for a known μ>0, and the minimum is attained in its interior. If η,δ≥0 and a computed gradient g^ has independently verified bounds ∥g^∥2≤η and ∥g^−∇φt(z~)∥2≤δ, then ∥x~−x∗(t)∥2≤η+δμ,cTx~−p∗≤νt+∥c∥2η+δμ, provided x~ is primal feasible. A tolerance or software stopping flag alone supplies neither verified bound.

Facts & Assumptions

Given: The affine parameterization, uniform restricted Hessian lower bound, attained central minimizer, primal feasibility, and two verified gradient bounds.

[F1]

Under a Hessian lower bound D2φ⪰μI, a verified computed-gradient residual η and discrepancy δ imply distance at most (η+δ)/μ from the exact minimizer (An inexact gradient residual certifies distance under strong convexity).

[F2]

For a ν-log-homogeneous barrier, −∇F(s)∈K∗ and DF(s)[s]=−ν (The negative gradient of a log-homogeneous cone barrier is dual feasible).

[F3]

When the primal value is finite, an exact central point has objective gap at most ν/t (Exact central points have barrier gap m/t or nu/t).

[F4]

Euclidean Cauchy--Schwarz gives ∣aTb∣≤∥a∥2∥b∥2 (Cauchy-Schwarz ∣⟨x,y⟩∣≤∥x∥2∥y∥2 with its equality case, the triangle inequality for ∥⋅∥2, the parallelogram law and polarisation).

[F5]

At an exact conic barrier minimizer, tc−G∗∇F(s)+ATw=0 for some equality multiplier w (Log-barrier central paths and primal-dual Newton residuals).

Proof

1.1F1givenalgebra

The linear map z↦x0+Pz preserves Euclidean distances because PTP=I. The restriction φt is C2 on the stated open convex coordinate region, its exact minimizer is attained in the interior, and the assumed Hessian lower bound is precisely the strong-convexity hypothesis in [F1]. Applying [F1] gives ∥z~−z∗∥2≤(η+δ)/μ, hence the same bound for x~−x∗(t).

1.2F2F5givenalgebra

Let x∗=x0+Pz∗ and s∗=h−Gx∗. By [F5], tc−G∗∇F(s∗)+ATw=0 for some w. Set z^∗=−∇F(s∗)/t∈K∗ by [F2] and y∗=−w/t. The stationarity equation gives ATy∗−G∗z^∗=c, so (y∗,z^∗) is dual feasible. The conic gap identity in Conic, LP, and convex QP primal-dual models then gives a finite dual lower bound on every primal feasible objective. Since x∗ is primal feasible with finite objective, this proves that p∗ is finite, establishing the finiteness hypothesis needed for [F3].

2.1F3F4step 1.1step 1.2givenalgebra∎

Since PTP=I, ∣cT(x~−x∗(t))∣=∣(PTc)T(z~−z∗)∣≤∥c∥2(η+δ)/μ by [F4] and ∥PTc∥2≤∥c∥2. Add the exact-center gap [F3]. Primal feasibility of x~ makes p∗≤cTx~, giving the stated candidate bound.

TheoremStatement: AI-adaptedProof: AI-adaptedOpen item page →

Short-step path following takes O(νlog⁡(ν/(εt0))) Newton steps

Statement

Assume the inputs of Short-step self-concordant path following with finite failure statuses, with a positive-definite restricted barrier Hessian, and assume the primal value p∗ is finite. The initial decrement and the update rule imply existence of the exact center at each path parameter. If the finite caps permit each path update, then after k path updates the returned iterate satisfies cTx−p∗≤ν+ν/2tk≤3ν2tk,tk=t0(1+18ν)k. Consequently, for R=3ν/(2εt0)>1, at most k=⌈log⁡Rlog⁡(1+1/(8ν))⌉≤1+9νlog⁡R path updates suffice, with at most two damped Newton corrections per update. Uniformly for R>1, this is O(1+νlog⁡R) Newton corrections. As ν/(εt0)→∞, it is O(νlog⁡(ν/(εt0))) Newton corrections. If an input cap is smaller than the required number, the algorithm returns its named failure status and makes no successful-complexity claim.

Facts & Assumptions

Given: A strict feasible start with decrement at most 1/4, attained barrier centers, and the short-step algorithm and local self-concordant calculus.

[F1]

λF(x)≤ν and F(αx)=F(x)−νlog⁡α for α>0 (Self-concordant log-homogeneous barriers and their local geometry).

[F2]

A damped Newton correction has decrement at most 2λ2 and ∥x−x∗∥x≤λ/(1−λ) when λ<1 (Local Hessian comparison, damped Newton decrement, and center distance).

[F3]

An exact central point has gap at most ν/t (Exact central points have barrier gap m/t or nu/t).

[F4]

Any self-concordant barrier point with decrement below one has a unique attained global minimizer, and its local distance to that minimizer is bounded (Local Hessian comparison, damped Newton decrement, and center distance).

Proof

1.1F1algebra

Log homogeneity gives DF(x)[x]=−ν, D2F(x)[x,x]=ν, and D3F(x)[x,x,x]=−2ν. The self-concordance inequality in [F1] therefore implies 2ν≤2ν3/2, hence ν≥1.

1.2F1givenalgebra

At an iterate with λt(x)≤1/4, set α=1+1/(8ν) and B(x)=F(h−Gx). On ker⁡A, D2B(x)[d,d]=D2F(s)[Gd,Gd], so the restricted dual norm of DB(x) is at most the ambient dual norm of DF(s), hence at most ν by [F1]. Since DΦαt=αDΦt+(1−α)DB, the triangle inequality gives λαt(x)≤αλt(x)+(α−1)ν≤3/8+1/(32ν)≤13/32.

2.1F2F4step 1.2algebra

Adding the linear term t+cTx does not change the barrier Hessian, local norms, or third derivatives, so [F2] applies to Φt+. The starting decrement is at most 13/32<1, so [F4] gives a unique attained center for that subproblem. After the first damped correction the decrement is at most 2(13/32)2=338/1024. Applying [F2] once more gives at most 2(338/1024)2<1/4. Dikin inclusion keeps both corrections in the cone interior. Thus each path update is recentered in at most two corrections.

3.1F1F2F3step 2.1algebra

Let x∗(t) be the exact center at the new t and let x be the accepted iterate with λt(x)≤1/4. By [F2], r=∥x−x∗(t)∥x≤1/3. Applying its local Hessian comparison to this segment gives ∥x−x∗(t)∥x∗(t)≤r/(1−r)≤1/2. For h=x−x∗(t), the restricted barrier norm is ∥Gh∥s∗(t)=∥h∥x∗(t). Stationarity of x∗(t) along the feasible affine space gives tcTh=−DF(s∗(t))[s(x)−s∗(t)]. The restricted barrier dual norm of this functional is at most the ambient ν from [F1], because restricting the unit-vector supremum can only decrease it. Hence ∣cTh∣≤ν/(2t). Combining this with [F3] yields cTx−p∗≤(ν+ν/2)/t≤3ν/(2t), since ν≥1.

4.1step 2.1step 3.1algebra∎

Each path update multiplies t by α, so tk=t0αk. The bound in step 3.1 is at most ε once tk≥3ν/(2ε), which gives the displayed ceiling. For u=1/(8ν)≤1/8, log⁡(1+u)≥u/(1+u)≥1/(9ν); hence k≤1+9νlog⁡R. Step 2.1 bounds corrections by 2k≤2+18νlog⁡R, giving the uniform bound. As ν/(εt0)→∞, log⁡R=log⁡(ν/(εt0))+log⁡(3/2) gives the asserted asymptotic bound.

LemmaStatement: AI-adaptedProof: AI-adaptedOpen item page →

The LP/QP primal-dual Newton matrix is nonsingular from a strict positive start

Statement

Let Q⪰0 be symmetric, let A∈Rp×n have full row rank, and let x,s∈Rn have strictly positive coordinates. Then the LP/QP Newton matrix M=[Q−AT−IA00S0X],X=diag⁡(x),S=diag⁡(s), is nonsingular.

Facts & Assumptions

Given: The matrix and residual convention of Log-barrier central paths and primal-dual Newton residuals, with Q⪰0, full-row-rank A, and x,s>0.

[F1]

The Newton equations have first block QΔx−ATΔy−Δs, second block AΔx, and complementarity block SΔx+XΔs (Log-barrier central paths and primal-dual Newton residuals).

[F2]

A full-row-rank matrix has injective transpose, and a symmetric positive-semidefinite Q satisfies uTQu≥0 (Conic, LP, and convex QP primal-dual models).

Proof

1.1F1givenalgebra

Let (u,v,w) lie in the kernel of M. The last block equation is Su+Xw=0. Since X is invertible, w=−X−1Su=−Du, where D=diag⁡(si/xi)≻0. Substituting into the first block gives (Q+D)u−ATv=0, and the second block gives Au=0.

2.1F2step 1.1algebra∎

Take the inner product of (Q+D)u−ATv=0 with u. Since Au=0, this yields uTQu+uTDu=0. Both terms are nonnegative by [F2], and D≻0, so u=0. The first block then gives ATv=0, hence v=0 by [F2], and the last block gives w=0. The square matrix M has trivial kernel and is therefore nonsingular.

AlgorithmAlgorithm: AI-adaptedProof: Not applicableOpen item page →

Finite-budget primal-dual Newton methods for LP, convex QP, and symmetric cones

Definition

This procedure has two admissible modes. All input values are finite stored floating-point numbers. Audits interpret them as exact dyadic rationals, and rounded operations obey Operationwise real and complex floating point arithmetic with rounded square roots and fused multiply-add.

LP/QP mode. Let n≥1, p≥0, Q∈Rn×n be symmetric positive semidefinite, and A∈Rp×n have full row rank. The supplied data are A,b,c,Q for min⁡12xTQx+cTx subject to Ax=b, x≥0; LP is Q=0. The iterate inputs are x>0, s>0, and free y. Also supply 0<σ<1, 0<η<1, finite tolerances ϵp,ϵd,ϵg≥0, and an integer update cap N≥0.

Symmetric-cone mode. Let K be a nonempty finite product of nonnegative orthant, Lorentz, or positive-semidefinite cones, let A have full row rank, and use the primal-dual pair of Conic, LP, and convex QP primal-dual models. Supply A,b,c,G,h, a point x with s=h−Gx∈int⁡K, a dual point z∈int⁡K∗, and free y. Equality feasibility Ax=b is checked as a residual, not required of the initial point. Also supply 0<σ<1, 0<η<1, finite tolerances ϵp,ϵd,ϵg≥0, and integer cap N≥0. The positive barrier parameter ν is the sum of the cone-factor parameters.

The input audit checks all dimensions, exact symmetry of Q, and full row rank of A by rational elimination. It checks Q⪰0 by finite exact symmetric Schur elimination: reject a negative diagonal; if a positive diagonal exists, permute it to the first position and recurse on its Schur complement; if every diagonal is zero, accept only when every off-diagonal entry is zero. This test is equivalent by completing the square at each positive pivot; with zero diagonal, a nonzero off-diagonal makes one of the vectors ei+ej or ei−ej have negative quadratic form. In symmetric-cone mode it also checks that each listed factor has a positive finite dimension, that the data match the declared product spaces, and that A has full row rank. All these checks use exact rational arithmetic on the stored dyadic inputs.

In LP/QP mode form rd=Qx+c−ATy−s,rp=Ax−b,μ=xTs/n,rc=Xs−σμ1. In symmetric-cone mode form rd=ATy−G∗z−c,rp=Ax−b,μ=⟨s,z⟩/ν,rc=s∘z−σμe. The cone rc is the stated diagnostic Jordan residual; for Lorentz factors its target normalization differs from that of the selected log-homogeneous barrier. In either mode, ϵp bounds ∥rp∥2, ϵd bounds both ∥rd∥2 and ∥rc∥, and ϵg bounds the surrogate complementarity gap nμ=xTs in LP/QP mode or νμ=⟨s,z⟩ in symmetric-cone mode. On product cones use Euclidean norms on orthant and Lorentz factors and Frobenius norms on matrix factors. Norm tests compare exact squared values with squared tolerances. The output is a record containing status, the last accepted iterate when one exists, update count, audited residuals, and audited gap; it carries the exact audited gap as an objective-suboptimality bound only for status certified-gap. The possible statuses are invalid-input, strict-start-unavailable, nonpositive-gap, certified-gap, residual-candidate, singular-system, lost-range, uncertified-newton-solve, boundary-status-unavailable, and budget-exhausted. invalid-input has no iterate. A residual candidate is diagnostic, never a certificate.

Interior audits. For an orthant factor, require every coordinate to be positive. For a Lorentz factor (t,u), require t>0 and t2−∥u∥22>0. For a symmetric matrix factor Y, test positive definiteness by exact rational Schur elimination: require Y11>0, form S=Y2:n,2:n−Y2:n,1Y1,2:n/Y11, and repeat on S until the matrix is empty. Completing the square gives vTYv=Y11(v1+Y1,2:nv2:n/Y11)2+v2:nTSv2:n, so this finite test succeeds exactly for Y≻0.

Instructions. First reject invalid dimensions, nonfinite data, parameters outside their stated domains, or a negative cap with invalid-input. Reject an LP/QP start unless x,s>0, or a cone start unless s,z pass the interior audits, with strict-start-unavailable; this is not an infeasibility claim. Set the accepted-update count to zero and repeat the following audit and update loop.

Compute the residuals and complementarity gap exactly as rational expressions in the stored inputs; compare exact squared norms with squared tolerances. A nonpositive or nonfinite gap returns nonpositive-gap. Return certified-gap in LP/QP mode only when Ax=b, x,s≥0, Qx+c−ATy−s=0, and xTs≤ϵg; in cone mode require Ax=b, s=h−Gx∈K, z∈K∗, ATy−G∗z=c, and ⟨s,z⟩≤ϵg. Otherwise, if ∥rp∥2≤ϵp, ∥rd∥2≤ϵd, ∥rc∥≤ϵd, and the surrogate gap is at most ϵg, return residual-candidate. If the update count equals N, return budget-exhausted.

Assemble the Newton derivative specified in Log-barrier central paths and primal-dual Newton residuals. In LP/QP mode solve its displayed block system. In symmetric-cone mode solve AΔx=−rp,ATΔy−G∗Δz=−rd,Δs=−GΔx,Δs∘z+s∘Δz=−rc. The exact equations form a square system after eliminating Δs. Form each system coefficient as an exact dyadic expression in the stored inputs, then round that coefficient once to the nearest normal representable value, preserving exact zeros; any failed conversion returns lost-range. Use the row order of the displayed system: (−rd,−rp,−rc) in LP/QP mode and, after eliminating Δs, (−rp,−rd,−rc) in symmetric-cone mode. Convert that exact rational right-hand side componentwise by the same nearest-normal rule, preserving exact zeros; a failed conversion also returns lost-range. In LP/QP mode, The LP/QP primal-dual Newton matrix is nonsingular from a strict positive start proves nonsingularity of the exact Newton matrix under the stated rank and strict-start hypotheses; in either mode an exact rank audit detects a singular stored system.

Stored floating-point numbers are treated as exact dyadic rationals (rationals with denominator a power of two) for audits; the unit roundoff u and failure behavior of elementary operations are those of Operationwise real and complex floating point arithmetic with rounded square roots and fused multiply-add. For a matrix M, ∥M∥F2 is the sum of the squares of its entries. Check exact rank by rational row elimination: scan columns from left to right, find the first nonzero entry at or below the next pivot row, swap it into that row, subtract exact multiples to clear entries below, and count pivots. If fewer pivots than rows are found, return singular-system. For a full-rank matrix, use a reduced QR solve: for each active column apply Scaled Householder reflector formation and application to the column and trailing block, store the reflector, apply the stored reflectors in order to the right-hand side using the same sequential dot, scale, multiply, and subtraction order as that procedure, and solve the resulting upper-triangular system by descending substitution ti=fl⁡(qi−fl⁡(∑j>iR^ijd^j)), d^i=fl⁡(ti/R^ii). A range exception returns lost-range; a zero pivot returns singular-system. Let d be the system dimension. If (d+3)u≥1, return uncertified-newton-solve. Otherwise define γd+3=(d+3)u/(1−(d+3)u). Require γd+3<1/8, and, for the computed triangular factor R^, verify with exact dyadic arithmetic that γd+32∥R^∥F2∥R^−1∥F2<1. If the test fails, return uncertified-newton-solve. Otherwise Computed reduced QR least squares is backward stable for full column rank applies: the returned direction solves a nearby system with a nonsingular perturbed factor. Compute exactly and report the direction residual both against the rounded stored Newton system and against the original exact rational Newton equations.

For LP/QP mode set αˉ=min⁡(1,min⁡Δxi<0−xiΔxi,min⁡Δsi<0−siΔsi), where an empty minimum is +∞, and use α=ηαˉ. In symmetric-cone mode compute a positive safe fraction β for each primal-slack and dual factor, and use α=η times the minimum of those bounds. For an orthant factor use the same coordinate ratios. For a Lorentz factor at (t,u)∈int⁡L with direction (t˙,v), set q=t2−∥u∥22 and c=∣t˙∣+∑i∣vi∣; take β=1 if c=0, and otherwise β=min⁡(1,q/(2tc)). For a positive-semidefinite factor at Y≻0 with symmetric direction D, let L(M)=∑i,j∣Mij∣, compute Y−1 by exact rational elimination, and set C=L(Y−1)L(D); take β=1 if C=0 and otherwise β=min⁡(1,1/C). These calculations are finite and use exact rational comparisons; their safety is proved by the fraction-to-boundary theorem on the A page.

Round α downward to a positive normal representable value; if none exists, return lost-range. Update each stored coordinate as fl⁡(v+fl⁡(αΔv)) under the operationwise model. Any failed operation returns lost-range. Before accepting the candidate update, verify exactly that LP/QP variables x,s remain positive, or that cone variables remain interior and s=h−Gx still holds. If an audit fails, reject the candidate and return boundary-status-unavailable with the previous accepted iterate. Otherwise accept it, increment the update count, and return to the audit loop. Every factorization, inverse, rank, and safe-fraction calculation is bounded by finite matrix dimensions, and the outer loop is bounded by N. No failure status is an infeasibility conclusion; Phase I is a separate model.

TheoremStatement: AI-adaptedProof: AI-adaptedOpen item page →

Fraction-to-boundary steps preserve positivity and exact primal-dual feasibility certifies a gap

Statement

In symmetric-cone mode of Finite-budget primal-dual Newton methods for LP, convex QP, and symmetric cones, let s,z be strictly interior primal and dual cone variables and let αˉs,αˉz∈(0,1] be their largest boundary-preserving step fractions. If 0<βs≤αˉs, 0<βz≤αˉz, and 0<η<1, then α=ηmin⁡(βs,βz) keeps both updated cone variables interior. The conservative fractions in the algorithm's Lorentz and PSD branches satisfy these inequalities. For any exactly primal- and dual-feasible conic pair, the gap ⟨z,s⟩ is a rigorous upper bound on primal suboptimality.

In LP/QP mode, the coordinate fraction-to-boundary formula keeps x,s>0. For the convex QP of that algorithm, if x is primal feasible, s≥0, y is free, and the exact stationarity residual Qx+c−ATy−s vanishes, then 0≤f0(x)−p∗≤xTs. For LP/QP iterates with full-row-rank A, Q⪰0, and x,s>0, the exact Newton matrix is nonsingular. Thus a requested gap is certified only under exact feasibility and stationarity conditions. Nonzero residual tolerances alone are not a certificate. Every finite iteration cap returns a status after finitely many bounded updates; a failure status proves no infeasibility claim.

Facts & Assumptions

Given: The proper-cone modes, fraction formulas, exact residual audits, and Lagrangians in the algorithm and conic model.

[F1]

For conic primal and dual feasible variables, cTx−(bTy−⟨h,z⟩)=⟨z,h−Gx⟩ (Conic, LP, and convex QP primal-dual models).

[F2]

A proper cone is closed and convex, and K∗={z:⟨z,k⟩≥0 for every k∈K} (Conic, LP, and convex QP primal-dual models).

[F3]

The QP Lagrangian is L(w,y,s)=12wTQw+cTw+yT(b−Aw)−sTw (Conic, LP, and convex QP primal-dual models).

[F4]

Every primal feasible point and dual feasible pair satisfy q(y,s)≤p∗ (Every Lagrangian dual feasible pair is a lower-bound certificate).

[F5]

A differentiable convex function lies above its tangent plane (Differentiable convex functions are characterized by the gradient inequality).

[F6]

The LP/QP primal-dual Newton matrix has trivial kernel under Q⪰0, full-row-rank A, and x,s>0 (The LP/QP primal-dual Newton matrix is nonsingular from a strict positive start).

[F7]

A real symmetric matrix has an orthonormal eigenbasis (Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis), so its spectral norm is at most its Frobenius norm.

Proof

1.1F2givenalgebra

Because s is interior, a small positive segment from s in direction Δs remains in K. The set of feasible fractions in [0,1] is closed by [F2], so its maximum αˉs>0 is attained and s+αˉsΔs∈K. Any 0<α≤ηαˉs has θ=α/αˉs<1, and the update is (1−θ)s+θ(s+αˉsΔs). An open ball about s lies in K; scaling that ball by 1−θ>0 and adding θ(s+αˉsΔs)∈K shows the updated point is interior. The same argument applies to z in K∗. In the orthant, the coordinate-ratio formula is the maximal nonnegative boundary fraction. For a negative coordinate direction, α≤η(−xi/Δxi) gives xi+αΔxi≥(1−η)xi>0; nonnegative directions preserve positivity, and the same two cases apply to s.

1.2F7givenalgebra

For a Lorentz factor, write s=(t,u) and Δs=(t˙,v), with t>∥u∥2. Set q=t2−∥u∥22>0 and c=∣t˙∣+∑i∣vi∣. If c=0 the step is unchanged. Otherwise t−∥u∥2=q/(t+∥u∥2)≥q/(2t), while ∣t˙∣+∥v∥2≤c. The algorithm's safe fraction β=min⁡(1,q/(2tc)) therefore gives α=ηβ with α(∣t˙∣+∥v∥2)<t−∥u∥2. The triangle inequality then yields t+αt˙>∥u+αv∥2, so the updated Lorentz vector is interior. For a PSD factor Y≻0 and symmetric direction D, let C=L(Y−1)L(D) as in the algorithm, where L(M)=∑i,j∣Mij∣. If C=0, then D=0. Otherwise set B=Y−1/2DY−1/2. Submultiplicativity of the operator norm and [F7] give ∥B∥2≤∥Y−1∥2∥D∥2≤∥Y−1∥F∥D∥F≤C. Since α=ηmin⁡(1,1/C), αC<1, and for every nonzero w, wT(I+αB)w≥(1−α∥B∥2)∥w∥22>0. Thus Y+αD=Y1/2(I+αB)Y1/2≻0. The same bounds apply separately to primal and dual factors, so each computed safe fraction is no larger than its maximal boundary-preserving fraction.

1.3F1F2algebra

For any feasible conic pair, [F1] and [F2] give bTy−⟨h,z⟩≤cTx. Taking the infimum over primal feasible x and the supremum over dual feasible pairs shows that a feasible dual value is a lower bound on p∗. Hence a computed primal-dual feasible pair with exact gap ⟨z,s⟩≤ε is an ε-suboptimality certificate.

1.4F3F4F5givenalgebra

In LP/QP mode, exact Ax=b, x≥0, s≥0, and Qx+c−ATy−s=0 make ∇wL(x,y,s)=0. To apply [F4], use the smooth inequality convention gi(w)=−wi≤0, multiplier λ=s, and equality multiplier ν=−y. Since Q⪰0, L is convex, so [F5] implies L(w,y,s)≥L(x,y,s) for every w; therefore q(y,s)=L(x,y,s)=f0(x)−xTs. By [F4], q(y,s)≤p∗, and primal feasibility gives p∗≤f0(x). Thus 0≤f0(x)−p∗≤xTs.

1.5F6given

In LP/QP mode, [F6] supplies a unique exact Newton direction under the stated rank and strict-interiority hypotheses. Symmetric-cone mode may have a singular derivative, which the algorithm tests and reports.

2.1givenstep 1.5algebra∎

Every dimension-bounded loop terminates after finitely many operations, and the outer loop increments its update counter until it reaches the finite cap N or returns an earlier status. Therefore every invocation terminates with one of its declared statuses. A tolerance status based on nonzero residuals is explicitly residual-candidate, so no step above treats it as a certificate.

5 · Examples, counterexamples and false statements

None yet.

Sources