Central Cutting Plane Methods

See Also: Constrained Optimization Semi-infinite Programming

Let \(P\) be a linear semi-infinite programming (SIP) problem. Given \(\lambda \in \mathbb{R}\), the set \(\{x \in F \, : \,f(x) \leq \lambda \}\) is called the sublevel set of \(P\) of \(\lambda\). We associate with any polytope \(Q\) (i.e., a bounded polyhedral set) a certain center (e.g., the center of the greatest ball contained in \(Q\) or the analytic center of \(Q\)) and the LP problem
\[
P(Q) \, : \, \min_{x} f(x) \,\,\, \text{s.t.}\,\, \, x \in Q.
\] Central cutting plane methods generate sequences of points in \(\mathbb{R}^n\) converging to an optimal solution of \(P\) by solving a sequence of LP problems of the form \(P(Q_{k})\), where \(Q_{k}\) is a polytope for \(k = 1,2,\dots \). Let \(\varepsilon ≥ 0 \) be a fixed accuracy.

Step \(k\) : Let \(Q_{k}\) be a polytope containing some sublevel set of \(P\).

  1. Compute a center \(x_{k}\) of \(Q_{k}\).
  2. If \(x_{k} \notin F\), set
    \[Q_{k+1}=\{x \in Q_{k} : g(x,t) \geq 0 \},\] where \(t \in T\) satisfies \(g(x_{k},t) ≤ 0\), and \(k=k+1\). Otherwise, continue.

    3. If \(f(x_{k}) \leq \min \{f(x) : x \in Q_{k} \} + \varepsilon\), stop. Otherwise, set
    \[Q_{k+1} = \{ x \in Q_{k} : f(x) \leq f(x_{k}) \}\] and \(k=k+1\).

Obviously, item 2 aggregates to the current polytope \(Q_{k}\) a feasibility cut (some constraint of \(P\) violated by \(x_{k}\)) when \(x_{k}\) is infeasible, whereas item 3 checks the \(\varepsilon\)-optimality of \(x_{k}\), aggregating to \(Q_{k}\) an objective cut when the result is negative.

The comments on the convergence and the drawbacks of discretization methods also apply to cutting plane methods. Nevertheless, efficient implementations of the latter methods turn out to be computationally faster than the discretization counterparts and, moreover, they stop before optimality at a feasible solution.

See Betro (2004) and Goberna and Lopez (1998) in the Semi-infinite Programming References.