Discretization Methods

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.

Compute a solution $x_{k}$ of $P(T_{k})$ .
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.