Convex Optimization 2026, 42 - Interior Point Methods

Interior-point methods are applied to problems that include inequality constraints. If assuming that the problem is solvable and strictly feasible, adopt the usual notation. The assumptions imply that Slater's constraint qualification holds. Interior point methods solve the problem or their KKT conditions by applying the Newton method to a sequence of equality constrained problems, to a sequence of modified versions of the KKT conditions. For a problem f₀(x) + ∑^m_i=1I_-(f₀(x)) where I_- is the indicator function for nonpositive reals, the problem has no inequality constraints but the objective function is not generally differentiable, so the Newton method can't be applied. To get the barrier method, the indicator function can be approximated through -(1/t)log(-u) where t is a parameter for the accuracy of the approximation. Applied to the target function, turns the objective convex, so now Newton's method can be applied (11.2.1). The notation can be further simplified through rewriting the problem into the form tf₀(x) + φ(x), subject to Ax = b which has the same minimizers. Assuming that it's solvable via Newton's method and has a unique solution for all positive definite t. Then, the solution is associated with a central path (p. 564). Every central point yields a dual feasible point, which also defines a lower bound on the optimal value so that -tf_i(x^*(t))λ_i^*(t) = 1 (Eq. 11.10). λ^* and ν^* are dual feasible. The central path conditions can be interpreted as a continuous deformation of the KKT optimality conditions (11.2).

The unconstrained minimization method can be extended by computing the optimal point for a sequence of increasing values of t, until it suprasses the weighted threshold. This is the sequential unconstrained minimization tenchnique (SUMT), also known as the barrier method or the path-following method. The first step computes x^*(t) as the centering step, which can in itself be a multi-step process. The accuracy of this centering step requires an accurate minimizer of tf₀ + φ (p. 570). Important to the process are the choices of the parameters μ, and the initial value of t. An infeasible start Newton method can be used for the centering steps (p. 571).