Chapter 5 Interior Point Methods

Inequality constrained minimization problems can be written as

$$\begin{align} \tag{5.1} \text{minimize}& & f_0(x) & & \\ \text{subject to}& & f_i(x) \leq 0, & & i = 1,\dots,m \\ & & Ax=b & \end{align}$$

where $f_0,\dots,f_m:\mathbf{R}^n\rightarrow \mathbf R^n$ are convex and $\mathcal{C}^2$ differentiable, and $A\in \mathbf R^{p\times n}$ with $\mathbf{rank} A = p < n$ (Boyd and Vandenberghe 2004). Assuming that the solution $x^*$ exists with the optimum value $p^* = f_0(x^*)$.

5.1 KKT conditions

$$\begin{align} \tag{5.2} Ax^* = b, f_i(x^*) & \leq & 0 &, & i=1,\dots, m \\ \lambda^* & \leq & 0 & & \\ \nabla f_0(x^*) + \sum_{i=1}^{m} \lambda^*_i \nabla f_i(x^*) + A^Tv^* & = & 0 & & \\ \lambda^*_i f_i(x^*) & = & 0 &, & i=1,\dots,m \end{align}$$

The KKT conditions (5.2) means, respectively:

1. All constraints are satisified at $x^*$;
2. Corresponding Lagrange multiplier is sufficiently larger than zero;
3. The gradient of the Lagrangian at $x^*$ is 0;
4. Inequality constraints are either inactive or on the edge.

5.2 Logarithmic barrier function and central path

The aim is to approximate (5.1) as an equality-constrained problem and apply Newton’s method. This proposes the following formulation: $$\begin{align} \tag{5.3} \text{minimize}& & f_0(x) + \sum_{i=1}^m I_{-}(f_i(x)) \\ \text{subject to}& & Ax = b, \end{align}$$ where $I_{-} : \mathrm R \rightarrow \mathrm R$ is the indicator function $$\begin{equation} \tag{5.4} I_{-}(u) = \begin{cases} 0 & u\leq 0 \\ \infty & u > 0. \end{cases} \end{equation}$$

However, it is obvious that (5.3) is non-differentiable, so we cannot optimize it with Newton’s method.

5.2.1 Logarithmic barrier

We can replace $I_{-}$ (5.4) with another function: $$\begin{equation} \tag{5.5} \hat I_{-}(u) = -(1/t) \log (-u) \end{equation}$$

Figure 5.1: Logarithmic barrier

This will convert (5.3)