Convex Optimization 2026, 43 - Newton Steps for Modified KKT Equations
A minor variation on the basic phase I method can solve a set of convex inequalities with continuous second derivatives by minimizing the results of each function. The feasible set of those inequalities are contained in a Euclidean ball of radius R as a prior bound on the norm of any point in the feasible set. The sublevel sets of the phase I problem are then bounded. The initial guess can be set at x = 0. The sign of the optimal value of the phase I optimization problem determines the feasibility of the set of inequalities. Via analytical methods, the zero-step can be identified through the derivative. When both the sign of the optimal value is known, the original inequalities can be solved, for example through the barrier method, which has a bounded number of Newton steps (11.5.4). The end-to-end complexity analysis given an extra constraint can be solved with a variation on the barrier method, by adding the assumptions of self-concordance and the additional bounded sublevel set assumptions of the phase I problem. An additional constraint f0(x) ≤ M is added so that the phase I central path intersects with the one for phase II. M is some prior bound on the optimal value. By applying the barrier problem, the total number of Newton steps is limited through two summands on the upper bound (11.5.5). For generalized inequalities, the KKT conditions are extended from the problem constraints by
(11.39). On a proper cone, the generalized logarithm (a concave, closed, twice differentiable function with domain in the interior of K and second derivative strictly negative) defines a constant so that ψ(sy) = ψ(y) + θlog s. It behaves like a logarithm along any ray in the cone K. A familt of generalized logarithms can be packaged into a logarithmic barrier function φ(x) = -∑mi=1ψi(-fi(x)) (p. 598). The central path emerges from the minimizer of and the optimality condition. Points on the central path give dual feasible points for the original problem again.