Convex Optimization 2026, 41 - Infeasible Start Newton Method

The feasibility so far presupposed for the Newton method can be generalized away by inspecting the behavior at infeasible points. Assuming an infeasible point, we require a step that satisfies the optimality conditions. This happens by substituting x + ∇x for x* and w for v* in the optimality conditions and apply the first order approximation. The resulting system of linear equations allow to solve for ∇x. It is analogous to the primal-dual method for the equality constrained problem (p. 532). At infeasible points, the Newton direction is not necessarily a descent direction for the function in question. Using the primal-dual interpretation, the norm of the residual decreases in the Newton direction, so one can take the derivative of the square residual (Eq. 10.23). If a step length of one is taken using the Newton step, the next iteration is feasible, and the Newton step becomes a feasible direction (p. 534). An extension could be approched through the dual part of the Newton step by using the backtracking line search on the primal and dual Newton steps (p. 535). The main advantage of this infeasible start Newton method is in the initialization required. If dom f = ℝⁿ, then there is no advantage over convenience. Otherwise, finding Ax = b is a nontrivial problem. If dom f is complex and not known to intersect {z : Az = b} is to use a phase I method to compute those points first (10.3.2). The convergence analysis for the infeasible start Newton method is similar to the one for standard Newton method with equality constraints. It assumes that the sublevel set S = {(x, ν) | x ∈ dom f, ||r(x, ν)||₂ ≤ ||r(x⁽⁰⁾, ν⁽⁰⁾)||₂ } is closed. On it, ∃ K : ||Dr(x, ν)^-1||₂ ≤ K. For points in S, Dr satisfies the Lipschitz condition (10.3.3).