New variable in a convex optimization problem 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$.
 A: 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.
