2
$\begingroup$

Consider the convex optimization program $$ \min_{x \in X } x^\top P x + p^\top x \quad \text{ sub. to: } Ax = b $$ where $X \subset \mathbb{R}^n$ is compact, $P \succ 0$, $A \in \mathbb{R}^{m \times n}$. Let $x^*$ be the optimizer.

Now consider the convex optimization program $$ \min_{x \in X, y \in \mathbb{R}^m } x^\top P x + p^\top x + \alpha\left\| y-b\right\|^2 \quad \text{ sub. to: } Ax = y $$ where $\alpha > 0$ is a parameter to be chosen. Let $(x_{\alpha}^*, y_{\alpha}^*)$ be the optimizer.

I am wondering about $\left\| x^* - x_{\alpha}^*\right\|$ for large $\alpha$. I am not sure it is true that $\lim_{\alpha \rightarrow \infty}\left\| x^* - x_{\alpha}^*\right\| = 0$.

$\endgroup$
2
  • 1
    $\begingroup$ I'm curious why this was voted down. Would the voter care to share why? (It's one thing not to vote on it at all; but to vote it down with no comment seems unfortunate. It seems like a perfectly reasonable question to me.) $\endgroup$ – Michael Grant Jul 11 '14 at 17:58
  • $\begingroup$ Thanks a lot for your comment. Seems someone has personal matters to downvote my questions. My last one got -17. $\endgroup$ – user693 Jul 11 '14 at 22:04
3
$\begingroup$

This is exactly equivalent (in all the respects that matter to us here) to $$\begin{array}{ll}\text{minimize} & x^T P x + p^T x + \alpha \| A x - b \|^2\end{array}$$ Now, this is actually a well-studied approach to solving constrained problems. The term $\|Ax-b\|_2^2$ is a penalty function. I encourage you to do a literature search to learn about the theoretical details.

Yes, it is indeed true that $x^*_\alpha\rightarrow x^*$ as $\alpha\rightarrow \infty$. But in fact, there is a more interesting question: is $x^*_\alpha=x^*$ for some finite value of $\alpha$ (and larger)? It turns out that no, the squared-norm penalty is what is called an inexact penalty function, and there is no finite value of $\alpha$ for which $A x^*_\alpha=b$ (in general; there might be for certain specific values of $P$, $p$, $A$, $b$).

On the other hand, consider the following alternative: $$\begin{array}{ll}\text{minimize} & x^T P x + p^T x + \alpha \| A x - b \|_1\end{array}$$ notice that we have eliminated the square, and are using the sum-of-absolute-values norm $\|\cdot\|_1$. This is an exact penalty function, which means that for some finite value of $\alpha$ (and larger), you will get $x_\alpha^*=x^*$. Of course, it's also not differentiable anymore :-) There's no free lunch.

Again, please read the literature on penalty functions to see a formal development. You will have to trust me that introducing the new variable $y$ and the accompanying equality constraint does not change anything I have said here.

$\endgroup$
1
  • 1
    $\begingroup$ Yes, you're right. I've made the edit. $\endgroup$ – Michael Grant Jul 11 '14 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.