Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


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.

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.