Ellipsoid Method - Inequality-Constrained Minimization

Inequality-Constrained Minimization

At the -th iteration of the algorithm for constrained minimization, we have a point at the center of an ellipsoid as before. We also must maintain a list of values recording the smallest objective value of feasible iterates so far. Depending on whether or not the point is feasible, we perform one of two tasks:

• If is feasible, perform essentially the same update as in the unconstrained case, by choosing a subgradient that satisfies

• If is infeasible and violates the -th constraint, update the ellipsoid with a feasibility cut. Our feasibility cut may be a subgradient of which must satisfy

for all feasible .