The design centering problem as a d.c. programming problem (Q1106730)

The mathematical problem associated with the design centering problem may be stated in very general terms as follows: Find a point x in a given set \(S\subset {\mathbb{R}}^ n\) maximizing the distance to the complement of S (under proper additional restrictions). The Euclidean distance is replaced by a Minkowski functional \(p(x)\) and the set S is assumed to be the intersection of a closed convex set C and several sets which have open convex complements. The problem is then reformulated as a two stage process: first, for each \(x\in S\) find \(r(x)=\max \{r:\) \(p(y-x)\leq r\Rightarrow y\in S\}\) and, secondly, find the optimal value \(\bar r=\max \{r(x):\) \(x\in S\}\) and the optimal points \(\bar x\in S\) such that \(r(\bar x)=\bar r\). Assuming that int \(S\neq \emptyset\), (i.e. \(\bar r>0)\), the main result is that r(x) is the difference of two convex functions (d.c. function). Using that result, several suggestions for improved solution algorithms are offered and, in particular, for the case \(p(x)=(x\) \(TAx)^{1/2}\) with \(A=A\) T positive definite, an algorithm is described with proofs of convergence and finiteness. An example with \(n=2\), \(p(x)=\| x\|\), (i.e.: \(A=I)\) and a polygonal set C closes the paper.