Discretization Methods

See Also: Constrained Optimization Semi-infinite Programming

Let \(P\) be an arbitrary semi-infinite programming (SIP) problem. We associate with any nonempty set \(S \subset T\) the problem
\[P(S) : \min_{x} f(x)\,\,\text{s.t.}\,\, g(x,t) \geq 0\, \text{for all}\, t \in S.\]

Obviously, \(P(T)\) coincides with \(P\), and \(P(S)\) is a finite program when \(S\) is finite. Discretization methods generate sequences of points in \(\mathbb{R}^n\) converging to an optimal solution of \(P\) by solving a sequence of problems of the form \(P(T_{k})\), where \(T_{k}\) is a nonempty finite subset of \(T\) for \(k=1,2,\dots\). Let \(\varepsilon < 0\) be a fixed small scalar called accuracy.

Step \(k\) : Let \(T_{k}\) be given.

  1. Compute a solution \(x_{k}\) of \(P(T_{k})\).
  2. Stop if \(x_{k}\) is feasible within the fixed accuracy \(\varepsilon\), i.e., \(g(x,t) \geq -\varepsilon\) for all \( t \in T\). Otherwise, replace \(T_{k}\) with a new grid \(T_{k+1}\).

Obviously, \(x_{k}\) is infeasible before optimality. Grid discretization methods select a priori sequences of grids, \(T_{1},T_{2},…,\) usually satisfying \(T_{k+1} \subset T_{k}\) for all \(k\). The alternative discretization approaches generate the sequence \(T_{1},T_{2},…,\) inductively. For instance, the classical Kelley cutting plane approach used in convex SIP consists of taking \(T_{k+1} = T_{k}\cup \{t_{k}\}\), for some \(t_k\in T\), or \(T_{k+1}=(T_{k}\cup \{t_{k}\}) \backslash\{t_{k}’\}\) for some \(t_{k}’\in T_{k}\) (if an elimination rule is included).

Convergence of discretization methods requires \(P\) to be continuous. The main difficulties with these methods are undesirable jamming in the proximity of an optimal solution and the increasing size of the auxiliary problems \(P(T_{k})\) (unless elimination rules are implemented). These methods are only efficient for low-dimensional indices.

For more details, see Gustafson (1979), Hettich and Zencke (1982), Hettich (1986), Hettich and Kortanek (1993), Reemtsen and Görner (1998), and López and Still (2007) in the Semi-infinite Programming References.