2
$\begingroup$

On page 47 of Nocedal & Wright's Numerical Optimization, the authors provide a proof for Theorem 3.7 and there is one idea that I didn't understand. The authors prove the following inequality:

$$\|x_k+p_k-x^*\| \le \|x_k+p_k^N-x^*\| + \|p_k-p_k^N\| = O(\|x_k - x^*\|^2) + o(\|p_k\|)$$

and say that a simple manipulation of the above inequality reveals that

$$\|p_k\|=O(\|x_k-x^*\|).$$

Question: What ideas and manipulation are needed to prove that $\|p_k\|=O(\|x_k-x^*\|)$ from the above inequality?

Thank you for taking the time to read my question. Any advice is helpful.

$\endgroup$
1
  • $\begingroup$ Since the link to the PDF file is broken, I removed it. $\endgroup$ Commented Jun 15, 2021 at 14:53

1 Answer 1

2
$\begingroup$

We have: $\|p_k\| \le \|x_k -x^*\| + \|x_k + p_k -x^* \| $, and so, $\|p_k\| \le \|x_k -x^*\| + O(\|x_k-x^*\|^2) + o(\|p_k\|)$.

Choose $K$ large enough so that $o(\|p_k\|) \le {1 \over 2} \|p_k\|$, then for $k \ge K$ you have ${1 \over 2} \|p_k\| \le \|x_k -x^*\| + O(\|x_k-x^*\|^2)$, from which the result follows.

$\endgroup$
5
  • $\begingroup$ I am not a fan of o/O calculations for proofs of this sort as it often 'loses' constants which can provide intuition. $\endgroup$
    – copper.hat
    Commented Oct 7, 2016 at 14:31
  • $\begingroup$ Your answer was very helpful to me! Thank you a lot! $\endgroup$ Commented Oct 7, 2016 at 15:54
  • $\begingroup$ Glad to help! ${}{}$ $\endgroup$
    – copper.hat
    Commented Oct 7, 2016 at 16:06
  • $\begingroup$ @jjjjjj: I don't follow your question? $\endgroup$
    – copper.hat
    Commented Feb 5, 2018 at 5:04
  • $\begingroup$ Oops, nvm, I think I was wrong, thanks! $\endgroup$
    – jjjjjj
    Commented Feb 5, 2018 at 23:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .