Global minimization by reducing the duality gap (Q1322556)

The authors discuss nonlinear optimization problems of the form \[ (P_ Q)\qquad \min_{x,q} \bigl\{f_ 0(q,x): q\in Q,\;f_ j(q,x)\leq 0,\;j= 1,\dots,m\bigr\}, \] where \(Q\) is a nonempty set. The aim is to find lower bounds for the global minimum of \((P_ Q)\). One of the most important ways is based on the introduction of the Lagrange dual problem \((D_ Q)\) but in general no strict duality relations hold. To reduce the duality gap the authors provide an interesting approach by partitioning the set \(Q\). If \(Q= \bigcup_{i\in I} Q_ i\) then it is easy to show that \[ \min(P_ Q)= \min_{i\in I}\{\min (P_{Q_ i})\}\geq \min_{i\in I} \{\max(D_{Q_ i})\}\geq \max(D_ Q). \] So the value \(\min_{i\in I} \{\max(D_{Q_ i})\}\) is a better estimation for the optimal value of \((P_ Q)\). Moreover, one can guess that the gap will be smaller if the partition is taken finer i.e. if the radius of the partition (the radius of the smallest ball containing the sets \(Q_ i\)) tends to zero. Naturally, suitable convexity and regularity conditions for the partial problems \((P_{Q_ i})\) must be assumed. For ``partially linear'' problems (here all functions are linear in the variable \(x\) and \(Q\) is a polytop) the authors provide sufficient conditions that for any \(\varepsilon> 0\) there exists a partition of \(Q\) with the duality gap smaller than \(\varepsilon\). It is worthy to state that for such problems all dual problems reduce to linear semi-infinite problems which can simplified by additional convexity assumptions for the variable \(q\). At the end of the paper a branch-and-bound type algorithm and first results by solving a special two-stage process are presented.