1

I'd like to prove the following:

Given an optimization problem, $\min_{x} f(x)+\rho*P(x)$, as $\rho$ increases, the penalty function evaluated at the optimal value $x^*$, $P(x^*)$ decreases. $x\in \mathcal{R}^n$.

I tried breaking this into different cases for each possible minimum value $x_1^*$ and $x_2^*$ for different problems involving different $\rho$'s where $\rho_1 < \rho_2$:

  • i) $f(x_1^*)+\rho_1P(x_1^*)< f(x_2^*)+\rho_2 P(x_2^*)$
  • ii) $f(x_1^*)+\rho_1P(x_1^*) > f(x_2^*)+\rho_2 P(x_2^*)$
  • iii) $f(x_1^*)+\rho_1P(x_1^*) = f(x_2^*)+\rho_2 P(x_2^*)$

The only obvious case is case iii). I'm having trouble showing $P(x_2^*)<P(x_1^*)$ for the other cases.

Someone give me a hint?

somewhere
  • 69
  • Could you be a little more precise so that we can help you: what do you know about $x$ (for example, is it a single variable $x \in [0,1]$ or $x \in \mathbb{R}$), what do you know about $f$ and $P$? Also, please write down the different cases you identified so we can take it from here. – cs89 May 04 '23 at 16:54
  • Sure. Let me know if this is better. – somewhere May 04 '23 at 17:34
  • You can probably use the fact that, if $x_1^$ was a possible value of $x$ for a penalty $\rho_1$, then $x_2^$ must perform "at least as good" as $x_1^*$. – cs89 May 04 '23 at 17:46

1 Answers1

0

Let, $\rho_1 > \rho_2$, then, by definition,

\begin{align} f(x_{\rho_1})+\rho_1 P(x_{\rho_1}) \leq {} & f(x_{\rho_2})+\rho_1 P(x_{\rho_2}) \\ f(x_{\rho_2})+\rho_2 P(x_{\rho_2}) \leq {} & f(x_{\rho_1})+\rho_2 P(x_{\rho_1}). \end{align} Hence, multiplying by $(-1)$ the second equation, \begin{align} f(x_{\rho_1})+\rho_1 P(x_{\rho_1}) \leq {} & f(x_{\rho_2})+\rho_1 P(x_{\rho_2}) \\ -f(x_{\rho_1})-\rho_2 P(x_{\rho_1}) \leq {} & -f(x_{\rho_2})-\rho_2 P(x_{\rho_2}). \end{align} Summing up both equations, $$( \rho_1 - \rho_2 )P(x_{\rho_1}) \leq ( \rho_1 - \rho_2 ) P(x_{\rho_2}).$$ Thus, since $( \rho_1 - \rho_2 )>0$, we have $$ P(x_{\rho_1}) \leq P(x_{\rho_2}),$$ as desired.

R. W. Prado
  • 787