Chapter 11: Interior-Point Methods

Interior-point methods solve convex optimization problems by reducing them to a sequence of unconstrained (or equality-constrained) problems via barrier functions. They are powerful alternatives to the simplex method for linear programming and extend naturally to general convex optimization.

---

11.1 Single-Inequality Optimization Problem

Consider the simplest constrained convex problem:

$$\underset{x}{min}f(x)\text{s.t.}g(x)\le 0$$

where $f$ and $g$ are convex and twice continuously differentiable.

11.1.1 Standard KKT Conditions

Let $x^{\ast }$ be the optimal solution. Under Slater's condition, there exists a Lagrange multiplier ${\lambda }^{\ast }$ satisfying the KKT conditions:

KKT Conditions (Single Inequality)

1. Primal feasibility: $g(x^{\ast })\le 0$
2. Dual feasibility: ${\lambda }^{\ast }\ge 0$
3. Complementary slackness: ${\lambda }^{\ast }g(x^{\ast })=0$
4. Stationarity: $\mathrm{\nabla }f(x^{\ast })+{\lambda }^{\ast }\mathrm{\nabla }g(x^{\ast })=0$

11.1.2 The KKT(t) Conditions — A Modified System

To derive the barrier method, we introduce a parameter $t>0$ and consider the modified KKT system, denoted KKT($t$):

KKT($t$) Conditions

1. $g(x_t)\le 0$
2. ${\lambda }_t\ge 0$
3. ${\lambda }_{t}g(x_t)=-t$    (perturbed complementary slackness)
4. $\mathrm{\nabla }f(x_t)+{\lambda }_t\mathrm{\nabla }g(x_t)=0$

From condition 3, we see that ${\lambda }_t=-{\displaystyle \frac{t}{g(x_t)}}$ (note $g(x_t)<0$ when $t>0$ and $x_t$ is strictly feasible). Substituting into the stationarity condition yields:

$$\mathrm{\nabla }f(x_t)-\frac{t}{g(x_t)}\mathrm{\nabla }g(x_t)=0$$

We solve for $x_t$ using Newton's method. The key bound is:

Duality Gap Bound (Single Inequality)

$$f(x_t)-p^{\ast }\le t$$

As $t\to 0$, the solution $x_t$ converges to the true optimum $x^{\ast }$, and the KKT($t$) conditions converge to the standard KKT conditions.

---

11.2 Logarithmic Barrier Function: An Alternative Interpretation

11.2.1 Indicator Function Approximation

The original constrained problem

$$\underset{x}{min}f(x)\text{s.t.}g(x)\le 0$$

is equivalent to the unconstrained problem

$$\underset{x}{min}(f(x)+I_{g\le 0}(x))$$

where the indicator function is

$$I_{g\le 0}(x)=\{\begin{array}{ll}0,& g(x)\le 0,\\ +\mathrm{\infty },& g(x)>0.\end{array}$$

The interior-point approach approximates the non-smooth indicator with a smooth function. For $t>0$, we define:

Logarithmic Barrier Approximation

$$I_{g\le 0}(x)\approx -t\ln (-g(x))$$

This yields the approximate problem:

$$\underset{x}{min}f(x)-t\ln (-g(x))$$

11.2.2 Properties of the Barrier

• The term $-t\ln (-g(x))$ acts as a barrier: it approaches $+\mathrm{\infty }$ as $g(x)\to 0$ from below, keeping iterates strictly inside the feasible region ($g(x)<0$).
• As $t\to 0$, the barrier effect diminishes, and the solution approaches the true optimum.
• The optimality condition for the barrier problem is precisely the KKT($t$) stationarity condition:

$$\mathrm{\nabla }f(x_t)-\frac{t}{g(x_t)}\mathrm{\nabla }g(x_t)=0$$

• The duality gap bound is $f(x_t)-p^{\ast }\le t$.

Key Insight

The barrier method can be viewed as solving a sequence of modified KKT systems. Each subproblem (the "centering step") is solved by Newton's method. When $t$ is small enough, the solution is near-optimal for the original problem.

---

11.3 General Barrier Problem

11.3.1 Problem Statement

Consider the general convex optimization problem:

$$\begin{array}{rl}\underset{x}{min}& f(x)\\ \text{s.t.}& g_i(x)\le 0,i=1,\dots ,m\\ & Ax=b\end{array}$$

We assume $f,g_1,\dots ,g_m$ are convex and twice continuously differentiable, and Slater's condition holds.

Definition (Logarithmic Barrier Function)

$$\varphi (x)=-\sum _{i=1}^m\ln (-g_i(x))$$

The domain of $\varphi$ is $\{x\mid g_i(x)<0,i=1,\dots ,m\}$.

Definition (Barrier Problem / Centering Problem)

For a given parameter $t>0$, solve:

$$\begin{array}{rl}\underset{x}{min}& f(x)+t\varphi (x)\\ \text{s.t.}& Ax=b\end{array}$$

Equivalently:

$$\underset{x}{min}f(x)-t\sum _{i=1}^m\ln (-g_i(x))\text{s.t.}Ax=b$$

11.3.2 Duality Gap Bound

Let $x_t$ be the solution of the barrier problem (the minimizer for a given $t$).

Theorem (Duality Gap for $m$ Inequalities)

$$f(x_t)-p^{\ast }\le mt$$

Proof sketch: The KKT($t$) conditions give ${\lambda }_{t,i}=-t/g_i(x_t)$ so ${\lambda }_{t,i}\ge 0$ (dual feasible). The Lagrangian is

$$L(x_t,{\lambda }_t)=f(x_t)+\sum _i{\lambda }_{t,i}{g}_i(x_t)=f(x_t)-mt$$

By weak duality, $p^{\ast }\ge \underset{x}{min}L(x,{\lambda }_t)\ge L(x_t,{\lambda }_t)$ (since the barrier problem returns the exact minimizer under equality constraints), yielding

$$p^{\ast }\ge f(x_t)-mt⟹f(x_t)-p^{\ast }\le mt.$$

Interpretation

When $mt<ϵ$, the solution $x_t$ is guaranteed to be $ϵ$-suboptimal for the original problem. This is the stopping criterion for the barrier method.

---

11.4 The Barrier Method Algorithm

11.4.1 Algorithm

Algorithm: Barrier Method

Input: strictly feasible $x^{(0)}$, $t^{(0)}>0$, $\mu \in (0,1)$, tolerance $ϵ>0$.

Repeat:

1. Centering Step: Compute $x_t$ by solving the barrier problem

   $$\underset{x}{min}f(x)-t\sum _{i=1}^m\ln (-g_i(x))\text{s.t.}Ax=b$$

   using Newton's method, initialized at $x^{(0)}$.

2. Update: $x^{(0)}:=x_t$

3. Stopping Criterion: Quit if $mt<ϵ$.

4. Parameter Update: $t:=\mu t$

11.4.2 Key Parameters

• Initial $t^{(0)}$: Chosen to balance the influence of the objective and the barrier. Typically $t^{(0)}\approx f(x^{(0)})-p^{\ast }$ if an estimate of $p^{\ast }$ is available, or a moderate value like $t^{(0)}=1$ is used.
• $\mu$: The decreasing factor for $t$. Typical values: $\mu \in [10,20]$ for linear programming (aggressive), $\mu \in [2,5]$ for general nonlinear problems (conservative).
• Centering tolerance: Each centering step is solved to sufficient accuracy (not full convergence). A typical Newton method stops when the Newton decrement $\lambda (x{)}^2/2\le {10}^{-5}$.

11.4.3 Convergence Properties

• Outer iterations: Each iteration reduces $t$ by factor $\mu$, so $O(\log (1/ϵ))$ outer iterations are needed.
• Inner iterations (Newton): Since each centering step is warm-started from the previous solution, only a few Newton steps per outer iteration are required in practice.
• The method is polynomial-time for linear programming and converges superlinearly or quadratically in practice.

11.4.4 Relation to KKT Conditions

As $t\to 0$, the barrier problem solution $x_t$ approaches a KKT point of the original problem:

• The modified complementary slackness ${\lambda }_{t,i}{g}_i(x_t)=-t$ becomes ${\lambda }_i^{\ast }{g}_i(x^{\ast })=0$.
• The central path $\{x_t\mid t>0\}$ converges to the optimal solution $x^{\ast }$.
• Each centering step computes a point on the central path, which is a smooth trajectory of solutions parameterized by $t$.

---

11.5 Exercises

Exercise 1 — Barrier Formulation

Consider the problem

$$\underset{x}{min}{x}_1^2+x_2^2\text{s.t.}{x}_1>0,x_2>0,x_1+x_2<1.$$

1. Logarithmic barrier function $\varphi (x)$:

Rewrite each strict inequality into the standard form $g_i(x)\le 0$:

$$\begin{array}{rl}{g}_1(x)& =-x_1\le 0\\ g_2(x)& =-x_2\le 0\\ g_3(x)& =x_1+x_2-1\le 0\end{array}$$

Barrier Function

$$\varphi (x)=-\ln (x_1)-\ln (x_2)-\ln (1-x_1-x_2)$$

2. Barrier problem for parameter $t>0$:

$$\underset{x}{min}{x}_1^2+x_2^2-t(\ln (x_1)+\ln (x_2)+\ln (1-x_1-x_2))$$

3. Behavior of the minimizer as $t$ decreases:

As $t\to 0$, the barrier term weakens, and the minimizer approaches the unconstrained minimum of $x_1^2+x_2^2$ within the simplex. The unconstrained minimizer of $f(x)=\parallel x{\parallel }^2$ within the feasible polytope is the origin projected onto the simplex, i.e., the point closest to the origin inside the triangle. By symmetry, this is $(1/3,1/3)$. As $t$ decreases, the minimizer $x_t$ moves along the central path toward $x^{\ast }=(1/3,1/3)$.

Exercise 2 — Centering Step with Equality Constraint

Consider

$$\underset{x}{min}{x}_1^2+x_2^2\text{s.t.}{x}_1+x_2=1,x_1>0,x_2>0.$$

1. Barrier problem for parameter $t$:

Rewrite inequalities: $g_1(x)=-x_1$, $g_2(x)=-x_2$. The barrier problem is:

$$\underset{x}{min}{x}_1^2+x_2^2-t(\ln (x_1)+\ln (x_2))\text{s.t.}{x}_1+x_2=1.$$

2. KKT conditions of the centering step:

The Lagrangian for the barrier problem is

$$L(x,\nu )=x_1^2+x_2^2-t\ln (x_1)-t\ln (x_2)+\nu (x_1+x_2-1).$$

KKT Conditions

$$\begin{array}{rl}\frac{\partial L}{\partial x_1}& =2x_1-\frac{t}{x_1}+\nu =0\\ \frac{\partial L}{\partial x_2}& =2x_2-\frac{t}{x_2}+\nu =0\\ x_1+x_2& =1\end{array}$$

3. Analytical solution for $x_t$:

From symmetry ($x_1=x_2$), and the equality constraint $x_1+x_2=1$, we obtain:

$$x_{t,1}=x_{t,2}=\frac{1}{2}$$

This solution is independent of $t$, because the problem is symmetric and the barrier respects that symmetry. (For non-symmetric problems, $x_t$ depends on $t$ and converges to the constrained optimum as $t\to 0$.)

Exercise 3 — Barrier Method for Linear Programs

Consider the linear program in inequality form:

$$\underset{x}{min}{c}^{\mathrm{\top }}x\text{s.t.}{a}_i^{\mathrm{\top }}x\le b_i,i=1,\dots ,m.$$

(Write $Ax⪯b$ for the vector of inequalities.)

1. Logarithmic barrier objective:

Barrier Objective

$$B_t(x)=c^{\mathrm{\top }}x-t\sum _{i=1}^m\ln (b_i-a_i^{\mathrm{\top }}x)$$

The barrier problem is an unconstrained minimization: $\underset{x}{min}{B}_t(x)$.

2. Gradient and Hessian:

Define the slack variables $s_i=b_i-a_i^{\mathrm{\top }}x$ (strictly positive in the barrier domain). Then:

Gradient

$$\mathrm{\nabla }{B}_t(x)=c+t\sum _{i=1}^m\frac{a_i}{s_i}=c+t{A}^{\mathrm{\top }}{S}^{-1}\mathbf{1}$$

where $S=\mathrm{diag}(s_1,\dots ,s_m)$ and $\mathbf{1}=(1,\dots ,1{)}^{\mathrm{\top }}$.

Hessian

$${\mathrm{\nabla }}^2{B}_t(x)=t\sum _{i=1}^m\frac{a_i{a}_i^{\mathrm{\top }}}{s_i^2}=t{A}^{\mathrm{\top }}{S}^{-2}A$$

Note that the Hessian is positive definite when $A$ has full column rank (or more generally when the $a_i$ span ${\mathbb{R}}^n$), guaranteeing that the barrier objective is strictly convex.

3. Newton step:

The Newton direction $\mathrm{\Delta }{x}_{\text{nt}}$ is obtained by solving the linear system:

$${\mathrm{\nabla }}^2{B}_t(x)\mathrm{\Delta }{x}_{\text{nt}}=-\mathrm{\nabla }{B}_t(x)$$

Substituting the gradient and Hessian:

$$t{A}^{\mathrm{\top }}{S}^{-2}A\mathrm{\Delta }{x}_{\text{nt}}=-c-t{A}^{\mathrm{\top }}{S}^{-1}\mathbf{1}$$

This is a symmetric positive definite system that can be solved efficiently.

Exercise 4 — Duality Gap and Stopping Rule

Let $x_t$ be the solution of the barrier problem with $m$ inequality constraints.

1. Show that the duality gap is bounded by $mt$:

From the KKT($t$) conditions, set ${\lambda }_{t,i}=-{\displaystyle \frac{t}{g_i(x_t)}}$. Since $g_i(x_t)<0$, we have ${\lambda }_{t,i}>0$ (dual feasible). Define the dual function:

$$q({\lambda }_t)=\underset{x}{min}L(x,{\lambda }_t)=\underset{x}{min}(f(x)+\sum _{i=1}^m{\lambda }_{t,i}{g}_i(x_t))$$

By weak duality, $p^{\ast }\ge q({\lambda }_t)$. The barrier solution satisfies the stationarity condition $\mathrm{\nabla }f(x_t)+\sum _i{\lambda }_{t,i}\mathrm{\nabla }{g}_i(x_t)=0$, so $x_t$ minimizes the Lagrangian. Hence $q({\lambda }_t)=f(x_t)+\sum _i{\lambda }_{t,i}{g}_i(x_t)=f(x_t)-mt$.

Therefore $p^{\ast }\ge f(x_t)-mt$, which implies:

$$f(x_t)-p^{\ast }\le mt$$

2. Explain the stopping criterion $mt<ϵ$:

When $mt<ϵ$, the duality gap bound guarantees that $f(x_t)-p^{\ast }\le ϵ$. The current iterate $x_t$ is $ϵ$-suboptimal, and the algorithm can terminate.

3. Theoretical interpretation:

This bound provides a certificate of near-optimality: the algorithm always maintains a provably feasible dual solution, and the duality gap shrinks geometrically (by factor $\mu$ per outer iteration). The number of outer iterations to achieve $ϵ$-suboptimality is:

$$K=\lceil \frac{\log (m{t}^{(0)}/ϵ)}{\log (1/\mu )}\rceil$$

---

11.6 Summary: The Central Path

The sequence of minimizers $\{x_t\mid t>0\}$ of the barrier problems forms a smooth curve called the central path. Key properties:

• Every point on the central path is strictly feasible ($g_i(x_t)<0$).
• As $t\to \mathrm{\infty }$, $x_t$ converges to the analytic center of the feasible set (the minimizer of $-\sum \ln (-g_i(x))$).
• As $t\to 0$, $x_t$ converges to the optimal solution $x^{\ast }$.

Central Path Equations

$$\begin{array}{rl}\mathrm{\nabla }f(x_t)+\sum _{i=1}^m{\lambda }_{t,i}\mathrm{\nabla }{g}_i(x_t)+A^{\mathrm{\top }}{\nu }_t& =0\\ {\lambda }_{t,i}{g}_i(x_t)& =-t,i=1,\dots ,m\\ A{x}_t& =b\end{array}$$

The barrier method follows this central path approximately, using Newton's method within each centering step and decreasing $t$ to march toward optimality. The relationship between the barrier method, KKT conditions, and duality theory provides a unified framework for understanding interior-point methods in convex optimization.