# proof of convergence of penalty function algorithm in nesterov's 2004 text

Hi: If anyone has yuri nesterov's 2004 "introductory lectures on convex optimization" book, I will write the question down in latex but otherwise, if no one does, then it's too confusing to explain my question here. thanks.

Actually, I'll write the whole algorithm down because maybe someone that doesn't have the book can still prove that it converges. ( I know there are some serious experts on this list and any proof that I understand is fine with me ).

Suppose I have the following problem: minimize $f_{0}(x)$ subject to $f_{i}(x) <= 0 ~~~ i = 1,\ldots m.$ Let $\phi(x)$ denote some penalty function so that it is positive when any of the m constraints aren't met and zero otherwise. Now, the penalty function method is the following: Denote $\psi_{k}(x) = f_{0}(x) + t_{k} \phi(x)$ and $\psi_{k}^{*} =$ min of $\psi_{k}(x)$ over $R^{n}$.

step 0): Choose $x_{0} \in R^{n}$. Choose a sequence of penalty coefficients $0 < t_{k} < t_{k+1}$ and $t_{k} \longrightarrow \infty$.

step 1): kth iteration ( $k \ge 0$ ). Find a point $x_{k+1} =$ arg min $(f_{0}(x) + t_{k}\phi_{x})$ over $R^{n}$ using $x_{k}$ as a starting point.

END OF ALGORITHM.

The author gives a proof that the algorithm above converges to $f_{0}(x^{*})$ ( and meets the constraints ) assuming there exists a value $\bar{t}$ such that the set $S = \{x \in R^{n} | f_{0}(x) + \bar{t}\phi(x) \le f_{0}(x^{*})\}$ is bounded.

But I still don't see how gets the initial statement of the proof, namely $\psi_{k}^{*} <= \psi_{k}(x^{*}) = f_{0}(x^{*})$. Thanks. Oh, if anyone wants the full proof, let me know and I can write that down also.

-
I found a similar proof in nocedal and wright that I was able to understand so this question can be considered solved. thank you for your efforts. –  mark leeds Jan 16 '13 at 1:43