SQP Reduction Methods

Back to Semi-infinite Programming.

Sequential quadratic programming (SQP) methods can be applied to problems that satisfy the same assumptions as those required for the KKT reduction methods. SQP methods can be obtained from a local reduction of \(P\) to a finite program, which is inspired in the implicit function theorem. Let \(\overline{x}\) be a local minimizer of \(P\). Under suitable assumptions, \(T_{a}(\overline{x}) = \{ \overline{t_{j}}, j=1, \dots, q(\overline{x} \}\), with \(q(\overline{x}) \in \mathbb{N}\), and there exists a neighborhood of \(\overline{x}\), say \(U_{\overline{x}}\), and smooth functions say \(t_{j} : U_{\overline{x}} \rightarrow T, j= 1, \dots, q(\overline{x})\), such that \(t_{j}(\overline{x})=\overline{t_{j}}, j= 1, \dots, q(\overline{x})\), and for all \(x \in U_{\overline{x}}\), \(x\) is a local minimum for \(P\) if and only if it is a local minimum of the (finite) reduced problem at \(\overline{x}\)
\[\begin{array}{lll}
P(\overline{x}) & \min_{x} & f(x) \\
& \text{s. t.} & g(x,t_{j}(x)) \geq 0, \, \, j=1, \dots, q(\overline{x}).
\end{array}\]

Step \(k\) : Start with a given \(x_{k}\) (not necessarily feasible).

  1. Determine the set of local minima \(\{ \overline{t}_{j}, j=1, \dots, q(x_{k}) \}\) of \(Q(x_{k}).\)
  2. Apply \(N_{k}\) steps of a SQP solver (for finite programs) to
    \[\begin{array}{lll}
    P(x_{k}) & \min_{x} & f(x) \\
    & \text{s.t.} & g(x,t_{j}(x)) \geq 0, \, \, j=1, \dots, q(x_{k}),
    \end{array}\]
    leading to iterates \(x_{k,i}, i=1, \dots, N_{k}\).
  3. Set \(x_{k+1} = x_{k,N_{k}}\) and \(k=k+1\).

This sketch of the method can be easily adapted to generalized SIP. As it happens with KKT reduction methods, SQP methods are usually combined with discretization or central cutting plane methods in two-phase methods.

For more details, see Hettich and Kortanek (1993), López and Still (2007), and Stein (2003) in the Semi-infinite Programming References.