C-programming and the minimization of pseudolinear and additive concave functions (Q579142)

The paper considers problems of the form \[ (P): \min \Phi (u(x))\quad subject\quad to\quad x\in X, \] where \(u: X\to R^ k\), \(\Phi\) : u(X)\(\to R\). It is shown that under certain assumptions a solution of (P) can be obtained through the solution of the parametric problem \[ P(\lambda): \min \quad \lambda^ Tu(x)\quad subject\quad to\quad x\in X\quad (\lambda \in R^ k) \] (the point of this approach is that in many cases P(\(\lambda)\) is easily amenable to standard optimization methods). Let \(X^*\) denote the solution set of P, and \(X^*(\lambda)\) the solution set of P(\(\lambda)\). For the case where \(\Phi\) is pseudo-linear a simple algorithm is given for finding a \(\lambda\) such that \(X^*(\lambda)\subset X^*\). For the case where \(\Phi\) is concave separable, an exclusionary rule is formulated that by virtue of discarding subsets of \(R^ k\) enables the identification of elements of \(X^*\). However, the difficulty with this method (Algorithm 2) is that it requires in a basic step the search for an element of a set of the form \(V\setminus V^ m\), where \(V^ m\) is in general a union of convex sets (such a problem may be as difficult as the original problem itself).