Localization and Cutting-Plane MethodsS. Boyd and L. VandenbergheApril 14, 2011Contents1 Cutting-planes 22 Finding cutting-planes 32.1 Unconstrained minimization . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.2 Feasibil ity problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.3 Inequality constrained problem . . . . . . . . . . . . . . . . . . . . . . . . . 63 Localization algorithms 73.1 Basic cutting-plane and localiza t io n algorith m . . . . . . . . . . . . . . . . . 73.2 Measuring uncertainty and pr o gr ess . . . . . . . . . . . . . . . . . . . . . . . 93.3 Choosing the qu e ry point . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 Some specific cutting-plane methods 124.1 Bisection method on R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134.2 Center of gravity method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144.3 MVE cutti n g- p l a n e method . . . . . . . . . . . . . . . . . . . . . . . . . . . 154.4 Chebyshev center cutting-plane method . . . . . . . . . . . . . . . . . . . . . 164.5 Analytic center cutting-plane method . . . . . . . . . . . . . . . . . . . . . . 165 Extensions 165.1 Multiple cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165.2 Dropping or pruning constraints . . . . . . . . . . . . . . . . . . . . . . . . . 175.3 Nonlinear cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 Epigraph cutting-plane method 187 Lower bo unds and stopping criteria 191In these notes we describe a class of method s for solving general convex and quasi convexoptimization problems, based on the use of cutting -planes, which are hyperplanes that sepa-rate the current point from the optimal points. These methods, called cutting-plane methodsor localization methods, are quit e different from interior-point methods, such as the barriermethod or primal-dual interior-poi nt met h od described in [BV04, §11]. Cutting-plane meth-ods are usually less efficient for problems to which interior-point methods apply, but theyhave a number of advantages that can ma ke them an att r act i ve choice in certain situations.• Cutting-plane methods do not r equ i r e differentiability of the objective and constraintfunctions, and can directly handle quasi convex a s well as convex problems. Each itera-tion requires th e computatio n of a subgradient of t he objective or constr ai nt functions.• Cutting-plane methods can exploit certain types of st r ucture in large and complexproblems. A cutting-plane method that exploits structure can be faster than a general-purpose interior-point method for the same problem.• Cutting-plane methods do not require evalu a t io n of the objective and all the constraintfunctions at each iteration. (In contrast, interior-point methods require evaluating allthe objective and constraint functions, as well as their fi rs t and second derivatives.)This can m ake cutting-p l ane methods usefu l for probl em s with a very large number ofconstraints.• Cutting-plane methods can be used to decompose problems into smaller pr ob l em s thatcan be solved sequentially or in parallel.To apply these methods to nond i ffer entiable problems, you need to know about subgra-dients, which are described in a separate set of notes. More details of the analytic centercutting-plane method are given in another separate set of notes.1 Cutting-planesThe goal of cutting-plane and loca li za ti o n methods is to find a point in a convex set X ⊆Rn, which we call the target set, or, in some cases, to determine that X is empty. In anoptimization problem, the target set X can be taken as the set of optimal (or ǫ-suboptim al )points for the problem, and our goa l is fi n d an opt i m al ( or ǫ- su boptimal) point for theoptimization problem.We do not have direct access to any description of the target set X (such as the objectiveand constraint functions in an underlying opt i m i zat i on problem) except through an oracle.When we query the oracle at a point x ∈ Rn, the oracle returns th e foll owing informationto us: it either tells us that x ∈ X ( i n which case we are done), or it returns a separatinghyperplane between x and X, i.e., a 6= 0 and b such t h ataTz ≤ b for z ∈ X , aTx ≥ b.2xXaFigure 1: The inequality aTz ≤ b defines a cut ti ng- pl ane at the query point x, forthe target set X, shown shaded. To find a point in the target set X we need onlysearch in the lightly shade d halfspace; the unshaded halfspace {z | aTz > b} cannotcontain any point in the target set.This hyperplane is called a cutting-plane, or cut, since it ‘cuts’ or elim i n a te s the halfspace{z | aTz > b} from our search; no such point could be in t h e t ar g et s et X. This is illustratedin figur e 1. We call the oracle th at generates a cutting-plane at x (or the message thatx ∈ X) a cutting-plane oracle. We can assume kak2= 1, since dividing a and b by kak2defines the same cutting-plane.When the cutting-plane aTz = b contains the query point x, we refer to it as a neutralcut or neutral cutting-plane. When aTx > b, which means that x lies in the interior of thehalfspace that is being cut from consideration, the cutting-plane is called a deep cut. Figure 2illustrates a neutral and deep cut. Intuition suggests that a deep cut is better, i.e., moreinformative, than a neutral cut (with the sam e normal vector a), since it excludes a largerset of points from consideration.2 Finding cutting-planesIn this section we show …