Convex Optimization 2026, 44 - Primal-Dual Interior-Point Methods

Primal dual interior-point methods are similar to the barrier method, though they only use one iteration, the search directions are obtained from Newton's method applied to modified KKT equations and the primal and dual iterates are not necessarily feasible. These are often more efficient than the barrier method, and can potentially work for not strictly feasible problems.

The search starts off with the modified KKT conditions, written in matrix form. The first block component of the condition vector defines the primal residual with a centrality residual r_cent = -diag(λ)f(x) - 1/t 1 defines the residual for the modified complementarity condition. The primal-dual search direction is defined as the solution of the resulting matrix equation (Eq. 11.54). The method iterates x, λ, and ν, which don't need to be feasible, except in the convergence limit, so the duality gap of a single step can't be easily evaluated. The surrogate duality gap is defined as -f(x)^Tλ, which would be the duality gap, if x were primal feasible and the other variables were dual feasible (11.7.2). The primal-dual interior-point method algorithm (Algorithm 11.2) requires no initial step. It's iteration consists of

• determining t
• computing primal-dual search direction Δy
• Line search and update with step length s and position y

The line search step is a standard backtracking line search, based on the norm of the residual, so that λ ≻ 0, f(x) ≺ 0. The current iterate is defined by x, λ, ν (11.7).

The main effort in the barrier method is computing the Newton step for the centering problem

(Eq. 11.60). The Newton equations for the primal-dual method have the same structure. If the original problem is sparse, the then the gradients and Hessians of the objective and constraint functions, and the coefficient matrix A are sparse. If the objective function is separable and there are only a relatively small number of linear constraints, the objective function's second derivative is diagonal and the second derivative of the constraint functions vanish, so the H-matrix is diagonal plus low rank (p. 616). The barrier method for standard form LPs is usually solved by block elimination of Δx_nt. The coefficient matrix is positive definite. If A is also sparse, then a sparse Cholesky factorization can be used (11.8.1).

The l₁-norm approximation problem minimizes ||Ax - b||₁. It can be rewritten as minimizing 1^Ty with

It's usually solved through the Newton equation applied to its centering problem. After block elimination of Δy_nt, A^TDAΔx_nt = -A^Tg and Δy_nt = (D₁ + D₂)^-1(-g₂ + (D₁ - D₂)AΔx_nt). This substitution can be applied directly to give a weighted least-squares problem (11.8.2). Given a semi-definite program, the associated centering problem defines the Hessian and gradient, which can be used in a Cholesky factorization. The unstructured case assumes all matrices are dense. The dominating order of the step count is of max{np³, n²p², n³} (11.8.3).