# 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.

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.