Try
Minimize x over x≥0. The optimum lies at the boundary zero. Add a logarithmic barrier and instead minimize tx−log x for x>0 and t>0. The derivative t−1/x vanishes at x=1/t, and the positive second derivative confirms the unique minimizer. As t increases, these strictly feasible points approach the boundary optimum. The barrier never evaluates log zero; it approaches the boundary through a family of different smooth problems.
Predict
Predict the error in the original objective at the barrier solution. It is exactly 1/t in this one-constraint example. Predict whether solving the barrier problem only approximately preserves that exact certificate. It need not: the clean gap relation uses exact stationarity or a separately controlled residual. Also predict whether a full Newton step stays inside the domain. Even for this simple barrier, a starting point far from its center can produce a trial step crossing zero.
Experiment
Track the exact central path of the opening problem. The multiplier obtained from λ=1/(tx) is one at every central point.
| t | Central point x | Original objective | Dual bound |
|---|
| 1 | 1 | 1 | 0 |
| 4 | 1/4 | 1/4 | 0 |
| 16 | 1/16 | 1/16 | 0 |
The gap equals 1/t, while complementarity is relaxed to λx=1/t rather than zero. Verify the dual bound by minimizing L=x−λx over all real x at λ=1. The vanishing coefficient makes the infimum zero. This is a concrete central-path certificate, not merely a graph of points approaching the boundary.
Understand
For convex differentiable minimization with m inequalities gᵢ(x)≤0 and affine equalities, the logarithmic barrier problem minimizes tf(x)−Σlog(−gᵢ(x)) over strict feasibility. At an exact central minimizer, define λᵢ=−1/(t gᵢ(x))>0 and scale the equality multipliers by 1/t. Dividing barrier stationarity by t yields Lagrangian stationarity. Convexity makes this point a global minimizer of that Lagrangian, so the dual function is attained there. The primal–dual gap equals −Σλᵢgᵢ=m/t. These deductions require an existing central point and the stated convex stationarity conditions.
For affine positive slacks sᵢ=bᵢ−aᵢᵀx, the barrier gradient is Σaᵢ/sᵢ and Hessian Σaᵢaᵢᵀ/sᵢ². The Hessian is positive semidefinite, becoming positive definite on relevant directions only when the normals span them. Equality constraints require a tangent-space solve or a KKT linear system. A fraction-to-boundary rule limits a trial step to a fixed fraction of the first point where any slack would vanish, then a line search checks sufficient decrease. Domain feasibility and objective decrease are separate acceptance requirements.
Apply
For t=1, starting at x=3 gives Newton displacement d=−(1−1/3)/(1/9)=−6, which would land at−3. A step shorter than 1/2 is necessary to keep x positive; a strict fraction of that boundary limit leaves a margin. Compute a trial at step 1/4 and compare the barrier objective before deciding whether the line search accepts it. This demonstrates why the word “interior” is an invariant maintained by the algorithm, not a property guaranteed by every raw Newton solve.
Polynomial iteration bounds need more than the m/t gap. Self-concordant barrier theory controls Newton decrement, central neighborhoods and how quickly t can grow while tracking them. Encoding, conditioning and precision also matter. This lesson derives the gap and update mechanism; the full self-concordance complexity theorem is an explicitly stated further dependency, not inferred from a few successful steps.
Derive a short-step arithmetic bound
Use equality-free coordinates on the feasible affine space and a linear objective cᵀx. Suppose the open domain has positive slacks sᵢ=bᵢ−aᵢᵀx, its normals span these coordinates, and each centering problem F_t(x)=tcᵀx−Σlog sᵢ has a minimizer. Write H=∇²F_t=∇²φ, ||v||_x²=vᵀHv and ||w||_x²=wᵀH⁻¹w. The Newton decrement is λ_t(x)=||∇F_t(x)||_x. It measures centrality in local curvature units, not Euclidean distance to feasibility.
For a direction h put uᵢ=aᵢᵀh/sᵢ. Then D²φ[h,h]=Σuᵢ² and D³φ[h,h,h]=2Σuᵢ³. Since |Σuᵢ³|≤Σ|uᵢ|³≤(Σuᵢ²)^(3/2), the barrier is self-concordant. Also |Dφ[h]|=|Σuᵢ|≤√m(Σuᵢ²)^(1/2), hence ||∇φ||*_x≤√m. Adding a linear term does not change the second and third derivatives.
Prove the Newton estimate for this affine log barrier
Let d=−H⁻¹∇F_t(x) and λ=||d||_x<1. Each |aᵢᵀd|/sᵢ≤λ because its square is one summand of λ². Along x+τd, every slack is sᵢ−τaᵢᵀd and stays positive for 0≤τ≤1. Comparing the individual rank-one terms of the Hessian gives
(1+τλ)⁻²H ≤ H(x+τd) ≤ (1−τλ)⁻²H.
These are matrix-order inequalities: test them on any vector and sum the nonnegative squared terms. The line segment stays in the domain. Put y=x+d. Since ∇F_t(x)+Hd=0, the fundamental theorem of calculus gives ∇F_t(y)=∫₀¹[H(x+τd)−H]d dτ. In the fixed H metric the operator norm of the bracket is at most (1−τλ)⁻²−1; the lower-side deviation is smaller. Thus ||∇F_t(y)||_x≤λ∫₀¹[(1−τλ)⁻²−1]dτ=λ²/(1−λ). At τ=1, H(y)≥(1+λ)⁻²H, so ||w||_y≤(1+λ)||w||*_x. Therefore
λ_t(y)≤(1+λ)λ²/(1−λ)≤λ²/(1−λ)².
The last inequality uses 1−λ²≤1. This proves the feasibility and decrement estimate needed here, directly for the affine logarithmic barrier with a linear objective. General self-concordant functions require a corresponding Hessian-comparison proof; the present derivation must not be applied to arbitrary smooth convex functions. Compare the authors’ self-concordance material, section 9.6 for that broader setting.
Maintain λ_t(x)≤1/10. Increase t to t′=(1+1/(20√m))t. At the same x,
||∇F_t′||_x ≤ λ_t + (1/(20√m))||tc||_x ≤ 1/10 + (1/(20√m))(1/10+√m) ≤ 0.155.
Here tc=∇F_t−∇φ and m≥1. One full Newton step then gives a decrement at most 0.155²/(1−0.155)²<0.034, restoring the invariant with room to spare. Thus each parameter increase needs only one Newton correction after a suitable initial central point is found. To reach t≥m/ε takes O(√m log(m/(t₀ε))) such updates, because log(1+1/(20√m)) is bounded below by a positive constant divided by √m. Initialization, a tangent-space linear solve, and arithmetic precision are separate costs. This is an arithmetic iteration bound, not a strongly polynomial bit-complexity claim.
Approximate centrality is not an exact dual certificate
The m/t certificate derived earlier holds at exact stationarity. At an approximate iterate set λᵢ=1/(tsᵢ); these are positive, but the stationarity residual r=c+Σλᵢaᵢ need not vanish. For an LP with a known Euclidean diameter bound D between x and an optimizer x, direct expansion gives cᵀ(x−x)≤m/t+||r||₂D: λᵀA(x−x)=Σλᵢ(sᵢ−sᵢ)≥−m/t and the residual contributes at most||r||D. Without a bound or corrected dual feasibility, use a residual-qualified estimate rather than calling m/t a certified primal-dual gap.
Worked repair. Minimize x on 0<x<2 with t=4. At x=1/4, slacks are 1/4 and 7/4, barrier gradient−4+4/7, so F′=4/7 and F″=16+16/49=800/49. The Newton step is−(4/7)/(800/49)=−7/200 and the new point 43/200 remains interior. Merely using the one-sided solution 1/t ignores the upper-bound barrier. With these two inequalities the exact-center gap would be 2/t, not 1/t.
Changed task. If m is multiplied by 4 with the same accuracy ratio m/(t₀ε), how does the short-step update count scale? Feedback: its leading √m factor doubles. The dimension and cost of each Hessian solve may also change, so this is not a statement that runtime merely doubles. Record initialization and precision assumptions in every complexity comparison.
Continue
Report primal feasibility, centrality residual and a justified dual bound separately. Continue to Semidefinite programming for a matrix cone that generalizes nonnegative scalar variables. Log-determinant barriers extend the interior-point idea to positive-definite matrices, but their numerical and complexity analysis requires the corresponding matrix-domain conditions.
