Interior-point Method

Interior-point Method#

Inequality Constrained Minimization Problems#

The interior-point methods are usually for solving convex optimization problem that include inequality constraints:

(1)#

\begin{aligned} min & f_{0} (x) \\ s.t. & f_{i} (x) \leq 0, i = 1, . . ., m \\ A x = b \end{aligned}

where $f_{0}, f_{i}$ are convex and twice continuously differentiable.

If the problem is strictly feasible, based on Slater’s constraint qualification, there exist dual optimal $λ^{*}, μ^{*}$ , which together with $x^{*}$ statisfy the KKT conditions:

\begin{matrix} A x^{*} = b \\ f_{i} (x^{*}) \leq 0 \\ λ^{*} \geq 0 \\ \nabla f_{0} (x^{*}) + \sum_{i = 1}^{m} λ_{i} \nabla f_{i} (x^{*}) + A^{T} v^{*} = 0 \\ λ^{*} f_{i} (x^{*}) = 0, i = 1, . . ., m \end{matrix}

Solving the orginal optimizaiton problem is equvelant to solving its KKT conditions. Interior-point method applies Newton's method to solve the modified version of the KKT conditions or a sequence of equality constrained problems transformed from the origin inequality constrained problem.

Two types of methods can be used: Primal-dual interior-point or Barrier method.

Barrier Fucntion#

A straight-forward way to solve the orignal problem is to approxmimately formulate the inequality constrained problem as an equality constrained problem to which Newton's method can be applied directly. The original problem can be rewritten as:

\begin{matrix} min & f_{0} (x) + \sum_{i = 1}^{m} I_{-} (f_{i} (x)) \\ s.t. & A x = b \end{matrix}

where $I_{-}$ is the indicator method for the nonpositive reals,

I_{-} (u) = {\begin{cases} 0, & u \leq 0 \\ \infty, & u > 0 \end{cases}

Logarithmic Barrier Function#

The basic idea of the barrier method is to approximate the indicator function by the logorithmic function:

(2)#

{\hat{I}}_{-} (u) = - (1 / t) l o g (- u)

where $t > 0$ is a parameter that sets the accuracy of the approximation. The ${\hat{I}}_{-}$ is convex and nondecreasing, and differentiable unlike $I_{-}$ . Therefore the following approximation holds:

\begin{matrix} min & f_{0} (x) + \sum_{i = 1}^{m} - (1 / t) \log (- f_{i} (x)) \\ s.t. & A x = b \end{matrix}

The function

(3)#

ϕ (x) = - \sum_{i = 1}^{m} \log (- f_{i} (x))

is called the logarithmic barrier, whose gradient and Hessian are given by:

\begin{matrix} \nabla ϕ (x) = \sum_{i = 1}^{m} \frac{1}{- f_{i} (x)} \nabla f_{i} (x) \\ \nabla^{2} ϕ (x) = \sum_{i = 1}^{m} \frac{1}{f_{i}^{2} (x)} \nabla f_{i} (x)^{2} + \sum_{i = 1}^{m} \frac{1}{- f_{i} (x)} \nabla^{2} f_{i} (x) \end{matrix}

Central Path#

By arranging t we have the following equavelant problem, which has the same minimizers.

\begin{matrix} min & t f_{0} (x) + ϕ (x) \\ s.t. & A x = b \end{matrix}

If the problem has a unique solution for each $t > 0$ , then the solution is associated with the choice of t, which can be denoted by $x^{*} (t)$ . $x^{*} (t)$ is called the central points, which characterize a central path.

Modified KKT Conditions#

The moodified KKT conditions for the original problem with the barrier function approximation are as follows, which is also called centrality conditions in this background:

\begin{matrix} A x^{*} = b \\ f_{i} (x^{*}) \leq 0 \\ λ^{*} \geq 0 \\ \nabla f_{0} (x^{*}) + \sum_{i = 1}^{m} λ_{i} \nabla f_{i} (x^{*}) + A^{T} v^{*} = 0 \\ - λ^{*} f_{i} (x^{*}) = 1 / t, i = 1, . . ., m \end{matrix}

The difference between the KKT condition and the modifided KKT is that the complementary condition $- λ^{*} f_{i} (x^{*}) = 0$ is replaced by the condition $- λ^{*} f_{i} (x^{*}) = 1 / t$ . In particular, for large $t, x^{*} (t)$ and the associated dual point $λ^{*} (t), μ^{*} (t)$ almost satisfy the KKT optimality conditions.

Primal-dual Interior-point Method#

Primal-dual interior-point method solves the modified KKT conditions using Newton's method by finding a pair of solutions $(x^{*}, λ^{*}, ν^{*})$ .

Newton's method updates at each iteration the solution by a Newton step.

We define a residual function from the modified KKT conditions as:

(4)#

\begin{matrix} r_{t} (x, λ, ν) = [\begin{matrix} \nabla f_{0} (x) + D f (x)^{T} λ + A^{T} ν \\ - d i a g (λ) f (x) - (1 / t) I \\ A x - b \end{matrix}] \end{matrix}

where

(5)#

\begin{matrix} f (x) = [\begin{matrix} f_{1} (x) \\ . . . \\ f_{m} (x) \end{matrix}], D f (x) = [\begin{matrix} \nabla f_{1} (x) \\ . . . \\ \nabla f_{m} (x) \end{matrix}] \end{matrix}

The first element in the the residual function is the dual residual, the middle element is centrality residual, and the last element is primal residual.

The Newton's method can be used to find $(x^{*}, λ^{*}, ν^{*})$ so that the residual function is 0.

The Newton step for the residual function can be:

(6)#

- \frac{r_{t}}{\nabla r_{t}}