We study another class of optimization algorithms: interior point methods. These require a more specific structure than general convex optimization, but can still be used beyond linear programming. These algorithms also work by following an interior path, determined by successive minima of a modified objective function. We will study in complete detail, one of the simplest variants, the primal-dual interior-point method.
Consider the primal program (P)
with corresponding dual (D)
Note that (P) (D). Then, . If the complimentary slackness conditions hold, this is achieved with equality, indicating that either each primal variable is 0, or it’s corresponding dual constraint is tight (zero slack).
Modify the primal objective to , with the same constraints. This modification effectively punishes low very severely, with having value of , and is relatively easy to optimize. As approaches 0, this modification becomes the original, so we can solve the original by successively reducing .
We have the constraints , where . We can start with a solution for some such that is feasible in (P), are feasible in (D), and . Our goal is to iteratively find new solutions with lower until eventually we get to 0. In doing this, we can’t quite maintain , but we can keep the values close, with an -approximate solution .
Now, suppose we have a valid , and we want to make smaller. We fix some and let . Then, solve the following system of linear equations:
We then update , , and .
Let $\varepsilon < 1/2$. If is a solution of with , then is a -approximate solution with .
Let latex (x, y, s)$ is a -solution, then is an -approximation with .
This interior point method reaches a solution with duality gap at most in iterations, where each iteration is the solution of an linear system.
Proof. (Theorem 1)
Start at . After each iteration, . To reach , we need suffices.
Proof. (Lemma 1)
and let satisfy
Note the following:
Proof. (Lemma 2)
Let . Then, we have .
Plugging in , we get . So solving for , we get suffices.