A Finitely Solvable Class of Approximating Problems

• Published in: SIAM journal on control and optimization 1977-05, Vol.15 (3), p.400-406
• Main Author: Meyer, Gerard G. L.
• Format: Article
• Language: English
• Subjects: Algorithms; Hypotheses; Neighborhoods
• ISSN: 0363-0129; 1095-7138
• DOI: 10.1137/0315027

Let $P$ be the following nonlinear programming problem: given $m + 1$ continuously differentiable convex maps $f^0 ( \cdot ),f^1 ( \cdot )$,$ \ldots $ , $f^ m ( \cdot )$ from $E^n $ into $E$, minimize $f^0 (z)$ subject to $f^j (z) \leqq 0$, $j = 1,2, \ldots ,m$. A well known approach for solving $P$ consists of embedding $P$ into a family of approximate problems $P(\alpha )$. Given $\alpha > 0$, the problem $P(\alpha )$ is to find a point $z$ such that $f^i (z) \leqq 0$, $j = 1,2, \ldots ,m$, and such that for every $h$ in $E^n $, there exists $j$ in $J(z,\alpha )$, $j$ depending on $h$, satisfying $\langle {\nabla f^i (z),h} \rangle \geqslant 0$ with $J(z,\alpha ) = \{ j \in \{ 1,2, \ldots ,m\} \mid {{f^i (z) + 1} / {\alpha \geqq 0}}\} \cup \{ 0\} $. In general, $P(\alpha )$ cannot be solved in a finite number of iterations and therefore one is obliged to use antizigzagging schemes of varying complexity. The purpose of this paper is to describe a class $C$ of problems $P$ such that the approximating problems $P(\alpha )$ may be solved in a finite number of steps. It is shown that if $P$ is in $C$, then its solution is unique and is stable with respect to variation in the cost function. There are indications that this phenomenon is not restricted to the particular case under study and that there is a definite connection between the stability of the solution of a problem and the existence of a finite procedure for solving it.