New variable in a convex optimization problem

137 Views Asked by At

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$.

1

There are 1 best solutions below

1
On BEST ANSWER

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.