12.1 The logarithmic barrier method and the central path
Replace inequality constraints by a logarithmic barrier, follow the central path, and certify a duality gap of at most m/t.
§12.1Estimated reading time: 20 min
Why a barrier method
The penalty and augmented Lagrangian methods treat a constraint by punishing its violation, so their iterates are generally infeasible. An interior-point method does the opposite: every iterate is strictly feasible, and a barrier term that tends to +∞ at the boundary keeps the iterates away from it. The barrier is slowly switched off by a parameter t, and the resulting curve of minimizers, the central path, converges to a solution. A short argument based on the Lagrangian and weak duality, from the Lagrange and KKT unit, turns each point of the path into a certified bound on how far the objective is from optimal. We also use Newton's method with line search, from the unit on line search and Newton's method, to compute the points.
Definitions
Consider the problem
x∈Rdminf0(x)subject togi(x)≤0,i=1,…,m,
where f0,g1,…,gm:Rd→R are convex and continuously differentiable. Let p∗ denote the optimal value.
Definition 12.1.1
(Strict feasibility and the logarithmic barrier)
The problem is strictly feasible if the set
S={x:gi(x)<0 for all i}
is nonempty. On S the logarithmic barrier is
ϕ(x)=−i=1∑mlog(−gi(x)).
The barrier is convex on S: the function −log is convex and decreasing, and −gi is concave and positive, so each term is convex. It is differentiable with ∇ϕ(x)=i∑−gi(x)1∇gi(x), and ϕ(x)→+∞ as x approaches a point where some gi=0 from within S. Note that ϕ depends on the functions gi, not only on the feasible set they describe; this matters below.
Definition 12.1.2
(Centering problem, central path and central multipliers)
For t>0, the centering problem is
x∈Smintf0(x)+ϕ(x).
When it has a minimizer x(t) for each t>0, the set {x(t):t>0} is the central path, and the central multipliers are λi(t)=tgi(x(t))−1 for i=1,…,m.
We assume that a minimizer exists for each t>0. This holds, for example, when the feasible set is bounded, because the objective is continuous on S and tends to +∞ at the boundary of S. Since S is open and the objective is differentiable, x(t) is characterized by the stationarity condition
t∇f0(x(t))+i=1∑m−gi(x(t))1∇gi(x(t))=0.
Because the centering objective is convex, this condition is also sufficient for a minimizer. The central multipliers are strictly positive because gi(x(t))<0.
Concept lensAlgebraic
The central path as a perturbed KKT system
The pair (x(t),λ(t)) is exactly a solution of the KKT system with complementary slackness relaxed to the same positive level:
Dividing the stationarity condition by t shows that (x(t),λ(t)) satisfies these equations. Conversely, if (x,λ) satisfies them, then λi=−1/(tgi(x)), and multiplying the first equation by t gives the centering stationarity condition, so x minimizes the centering problem. As t→∞ the products −λigi are driven to zero, which is the KKT complementarity condition. This description is the one Newton-type primal–dual methods linearize.
The duality gap on the central path
The perturbed complementarity λi(t)gi(x(t))=−1/t is what produces a computable gap.
Theorem 12.1.3
(Duality gap on the central path)
Under the standing assumptions, for every t>0,
f0(x(t))−tm≤p∗≤f0(x(t)).
Proof
(Evaluate the dual function at the central multipliers)
The point x(t) is feasible, so p∗≤f0(x(t)). Dividing the stationarity condition by t gives
∇f0(x(t))+i∑λi(t)∇gi(x(t))=0.
This says that x(t) is a stationary point of the Lagrangian L(x,λ)=f0(x)+i∑λigi(x) with λ=λ(t)≥0. For fixed λ≥0 the Lagrangian is convex in x, so a stationary point is a global minimizer over Rd. Hence the dual function satisfies
because λi(t)gi(x(t))=−1/t for each of the m constraints. Weak duality gives q(λ)≤p∗ for every λ≥0.
Proof X-ray
Three hypotheses, three separate jobs
Feasibility of x(t) gives the upper bound and nothing else. Strict feasibility is what makes the central multipliers well defined and positive, so that λ(t) is an admissible dual point. Convexity has one job: it promotes a stationary point of L(⋅,λ(t)) to a global minimizer, which is what identifies L(x(t),λ(t)) with the dual value q(λ(t)). The number m/t then comes from a bookkeeping identity, each constraint contributing exactly λigi=−1/t, and the argument closes with weak duality. No uniqueness of x(t) or of a solution of the original problem is used, and no value of p∗ is needed.
Thus x(t) is m/t-suboptimal, and a stopping rule is available without knowing p∗. The convexity requirement concerns the functions gi, and it cannot be weakened to convexity of the feasible set.
Counterexample mode
A nonconvex description of a convex set
Claim: if the feasible set is convex, the gap bound holds for any smooth description of it. Describe {x≥0}⊂R by g(x)=−x3, which is not convex on x>0, and minimize f0(x)=x, so p∗=0 and m=1. Then ϕ(x)=−3logx, the centering objective tx−3logx has stationarity t=3/x, and x(t)=3/t. The bound would give f0(x(t))−1/t=2/t≤0, which is false. The proof breaks at the convexity step: λ(t)=−1/(tg(x(t)))=t2/27, and L(x,λ)=x−λx3 is unbounded below, so its stationary point is not a minimizer. With the convex description g(x)=−x, the same problem gives x(t)=1/t and a gap of exactly 1/t. The repaired statement keeps the hypothesis that every gi is convex.
The quantity f0(x(t)) is also nonincreasing in t, by an argument that uses minimality alone.
Proposition 12.1.4
(The objective decreases along the central path)
If 0<t<s, then f0(x(s))≤f0(x(t)).
Proof
(Add the two minimality inequalities)
Write x=x(t) and y=x(s). Minimality gives tf0(x)+ϕ(x)≤tf0(y)+ϕ(y) and sf0(y)+ϕ(y)≤sf0(x)+ϕ(x). Adding the two inequalities cancels ϕ(x)+ϕ(y) and leaves (s−t)(f0(y)−f0(x))≤0. Since s−t>0, f0(y)≤f0(x).
The algorithm
Given a strictly feasible x(0)∈S, an initial t0>0, a factor μ>1 and a tolerance ε>0:
Set k=0.
Centering. Starting from the current point, minimize tkf0+ϕ over S by Newton's method with backtracking line search. The line search is kept inside S: a trial step is reduced until it is strictly feasible and gives sufficient decrease. Let x(k) be the (approximately) centered point x(tk).
Stop if m/tk≤ε; by the duality-gap theorem, f0(x(k))−p∗≤ε.
Set tk+1=μtk and k←k+1; return to step 2.
Invariant. Every iterate lies in S, so ϕ is finite and the stationarity condition makes sense at each centering stage. Termination of the outer loop. Since tk=μkt0, the test m/tk≤ε first holds at
k=⌈logμlog(m/(εt0))⌉
(taken to be 0 if the quantity inside is nonpositive), so exactly k+1 centering problems are solved. The inner Newton iterations are not counted by this formula. For general convex data their number cannot be bounded by a formula of this kind without further structure on the barrier (self-concordance), which we do not develop here; the choice of μ trades fewer outer steps against harder centering problems.
Worked examples
Worked example 12.1.5
(One constraint: the gap bound is attained)
Minimize f0(x)=x subject to x≥1, i.e. g1(x)=1−x≤0, m=1, p∗=1. Then S=(1,∞) and ϕ(x)=−log(x−1). The centering problem is to minimize tx−log(x−1). Stationarity gives t−x−11=0, so x(t)=1+t1. Here f0(x(t))−p∗=t1=tm: the bound of the duality-gap theorem holds with equality. The central multiplier is λ1(t)=t(1−x(t))−1=t⋅t11=1, which is the true multiplier of the constraint. For example, to certify a gap of 10−3 it suffices to take t=1000, giving x=1.001.
Worked example 12.1.6
(Two constraints, one of them inactive)
Minimize f0(x)=x subject to 1≤x≤3, with g1=1−x, g2=x−3, m=2, p∗=1. Here ϕ(x)=−log(x−1)−log(3−x) on S=(1,3). Writing u=x−1∈(0,2), stationarity is
t−u1+2−u1=0.
Multiplying by u(2−u) gives tu(2−u)−(2−u)+u=0, that is tu2−(2t+2)u+2=0, with roots u=t(t+1)±t2+1. The root with plus sign exceeds 2 (it is at least tt+1+t>2), so it is outside S and
x(t)=1+t(t+1)−t2+1.
For t=1: u=2−2≈0.5858, x(1)≈1.5858. Check of stationarity: u1=1.7071 and 2−u1=21=0.7071, so 1−1.7071+0.7071=0. The multipliers are λ1=tu1≈1.7071 and λ2=t(2−u)1≈0.7071, and 1−λ1+λ2=0 is the Lagrangian stationarity condition. The certified bounds are
f0(x(1))−12=−0.4142≤p∗≤1.5858,
consistent with p∗=1. For t=10: u=1011−101≈0.09501, so x(10)≈1.09501 and the bounds are 0.89501≤p∗≤1.09501; the true gap 0.09501 is smaller than m/t=0.2. The inactive constraint still costs 1/t in the bound. Both the gap theorem and the monotonicity proposition are visible: f0(x(1))=1.5858>f0(x(10))=1.0950>p∗.
Worked example 12.1.7
(A warm-started Newton step that leaves the domain)
In the one-constraint problem, suppose centering at t0=1 has produced x(1)=2 and the parameter is raised to t1=10. The new objective h(x)=10x−log(x−1) has h′(x)=10−x−11 and h′′(x)=(x−1)21, so at x=2 the Newton direction is p=−h′(2)/h′′(2)=−9. The full step reaches −7∈/S. Halving the step gives trial points −2.5, −0.25 and 0.875, all outside S=(1,∞), and then 2−9/16=1.4375∈S. There h(1.4375)=14.375−log0.4375≈15.20, below h(2)=20, and the Armijo test with c=0.01 requires only h≤20+0.01⋅161⋅(9)(−9)≈19.95. The step is accepted on the way to x(10)=1.1. The edge case shows why the line search must test membership in S before evaluating h: the Newton formula itself proposed a point where the barrier is undefined.
Common mistakes and subtle points
Common mistake
(Starting from a point that is not strictly feasible)
The method needs a strictly feasible starting point. A problem with an empty interior, such as one containing an equality written as two inequalities, has S=∅; equalities must be handled as affine constraints in the centering problem, not as barrier terms. Finding a first point of S is a separate phase-one problem.
Common mistake
(Quoting m/t at a point that is not centered)
The bound m/t is for an exactly centered point. In the one-constraint problem with t=1000, the strictly feasible point x=3 would give the false bound 3−10−3≤p∗=1. A point only approximately on the path has a gap bound that includes an extra term depending on how far the stationarity condition fails.
Common mistake
(Letting the line search leave the interior)
The line search must reject steps that leave S: the barrier is +∞ (undefined) there, and the formula for the Newton step knows nothing about the domain, as the warm-start example shows.
Three further points are easy to overlook.
The central path is a curve of minimizers of a changing problem, not a path of the iterates; the iterates follow it only approximately.
Increasing t makes the centering problem more ill conditioned: its Hessian contains terms of size 1/gi2 that blow up near the boundary. This is why a moderate μ and warm starts are used instead of solving once with a huge t.
The duality-gap theorem does not require the minimizer x(t) or the solution of the original problem to be unique; it uses only that x(t) is a minimizer of the centering problem.
Exercises
Quick check
(Minimize f0(x)=x subject to x≥2. Find x(t) and the smallest t for which the duality-gap theorem certifies f0(x(t))−p∗≤10−3.)
Use g1=2−x and solve the centering stationarity condition.
Solution
With g1=2−x, the centering objective is tx−log(x−2), with stationarity t=x−21, so x(t)=2+t1 and f0(x(t))−p∗=t1 with p∗=2. The theorem certifies a gap of m/t=1/t for m=1, so we need 1/t≤10−3, i.e. t≥1000; the smallest such t is 1000.
Quick check
(With m=10, t0=1, μ=10 and ε=10−4, how many centering problems does the barrier method solve, and at which values of t?)
Find the first k with m/tk≤ε.
Solution
The test m/tk≤ε requires tk≥10/10−4=105. Since tk=10k, the first such k is 5. The formula gives k=⌈log10(105)⌉=5. So k+1=6 centering problems are solved, at t=1,10,102,103,104,105.
Quick check
(Minimize f0(x)=x subject to 0≤x≤1. Compute x(1), the central multipliers at t=1, and the resulting certified lower bound on p∗.)
Clear denominators in the stationarity condition and keep the root in (0,1).
Solution
Here g1=−x, g2=x−1, m=2 and ϕ=−logx−log(1−x). Stationarity at t=1 is 1−x1+1−x1=0. Multiplying by x(1−x) gives x(1−x)−(1−x)+x=0, i.e. x2−3x+1=0, whose root in (0,1) is x=23−5≈0.381966. The multipliers are λ1=x1≈2.618034 and λ2=1−x1≈1.618034; they satisfy 1−λ1+λ2=0. The lower bound is f0(x(1))−tm=0.381966−2=−1.618034, which equals the dual value −λ2 and is at most p∗=0. (The true gap is 0.381966.)
Quick check
(Minimize x1+2x2 subject to x1≥0 and x2≥0. Find x(t), the central multipliers, and the exact gap f0(x(t))−p∗.)
The centering objective separates into one-variable problems.
Solution
The centering objective is (tx1−logx1)+(2tx2−logx2), so x1(t)=1/t and x2(t)=1/(2t). With g1=−x1 and g2=−x2, the central multipliers are λ1=1/(tx1)=1 and λ2=1/(tx2)=2, which satisfy ∇f0=(1,2)=λ. Since p∗=0, the gap is f0(x(t))=1/t+1/t=2/t=m/t exactly: when every constraint is active at the solution of a linear problem, the bound can be attained.
Quick check
(In the two-constraint worked example, give the certified interval for p∗ obtained from t=10 and verify it contains p∗=1.)
Use x(10)=1+u with u=(11−101)/10.
Solution · Answer
At t=10, m/t=0.2 and f0(x(10))=1+u=1.095012 with u=1011−101=0.0950124 (using 101=10.0498756). The interval is 1.095012−0.2=0.895012≤p∗≤1.095012, which contains p∗=1.