A method for solving reverse convex programming problems (Q1091943)

We shall be concerned with the following problem: (P) Minimize \(f(x)=<c,x>\) subject to \(x\in D=\{x:\) \(h_ i(x)\leq 0\), \(i=1,2,...,m\}\), g(x)\(\leq 0\), where \(h_ i(x)\) \((i=1,2,...,m)\) and -g(x) are real-valued convex functions defined throughout \(R^ n\), c and x are n-dimensional vectors. We shall assume that D is compact and has a nonempty interior. In general, finding an exact optimal solution to problem (P), often called the reverse convex programming problem, is computationally very expensive. Therefore, we present a finite algorithm for finding a vector x(\(\epsilon\),\(\theta)\) satisfying \[ x(\epsilon,\theta)\in D,\quad g(x,(\epsilon,\theta))\leq \theta,\quad f(x(\epsilon,\theta))-f^*\leq \epsilon, \] where \(f^*\) denotes the optimal value of the problem. Such a vector will be called (\(\epsilon\),\(\theta)\)-solution. While in practice it is usually sufficient to have an (\(\epsilon\),\(\theta)\)-solution with reasonably small \(\epsilon,\theta >0\), the cost for finding it may often be much less than finding an exact optimal solution.