1

Prove that the following set is convex $$\{ x : \|Ax + b\|_2 \leq c^Tx + d\}$$

My initial thought is to choose two points $x_1,x_2$ in the set and then plug this back into the inequality to prove convexity, so:

$||Ax+b||_2 \Rightarrow ||A(\lambda x_1+(1-\lambda)x_2)+b||_2$ $\Rightarrow ||\lambda (Ax_1+b) +(1-\lambda)(Ax_2+b)||_2 \leq \lambda ||Ax_1+b||_2 +(1-\lambda)||Ax_2+b||_2$

This proves convexity of the LHS. I would then do the same for the RHS and because the LHS must be less than or equal to the RHS it must be a set contained within the RHS. Thus all x that satisfy the condition would be contained within the intersection of two convex sets and therefore the set is convex.

Is this the right way to think about it or am I totally off? Thanks in advance for the help!

Rodrigo de Azevedo
  • 1
jagr7
  • 79

2 Answers2

2

You have to show that if $x_1,x_2$ satisfy the inequality, then so does $\lambda x_1+(1-\lambda)x_2$, for any $\lambda \in (0,1)$. So the goal is to show that $$\|A(\lambda x_1+(1-\lambda)x_2)+b\|\leq c^T(\lambda x_1+(1-\lambda)x_2)+d,$$assuming that $\|Ax_i+b\|\leq c^Tx_i+d$, for $i=1,2$, which is not quite what you have there. We do not think of "convexity on each side". One proceeds as follows: $$\begin{align} \|A(\lambda x_1+(1-\lambda)x_2)+b\| & = \|\lambda (Ax_1+b) + (1-\lambda )(Ax_2+b)\| \\ &\leq \lambda \|Ax_1+b\| + (1-\lambda)\|Ax_2+b\| \\ &\leq \lambda(c^Tx_1+d) + (1-\lambda)(c^Tx_2+d) \\ &= c^T(\lambda x_1+(1-\lambda)x_2) + d.\end{align}$$

Ivo Terek
  • 77,665
  • Thanks for the response! One question, why can we say the last two equations are equal? By definition of convexity shouldn't it be $c^T(\lambda x_1 + (1-\lambda)x_2)+d \leq \lambda(c^Tx_1 + d) + (1-\lambda)(c^Tx_2+d)$? I believe either way it proves convexity but I was just curious if I had missed something. – jagr7 Oct 23 '19 at 17:42
  • 1
    Factor $c^T$ and use $\lambda+(1-\lambda)=1$ to get the single $d$. – Ivo Terek Oct 23 '19 at 17:47
  • Ahh got it thanks! – jagr7 Oct 23 '19 at 17:51
1

Call the left side $f(x)$ and the right side $g(x)$.

The set of points where a convex function $\le$ a constant is convex.

Here $f$ is convex and $g$ is affine, so $f-g$ is convex.

Robert Israel
  • 448,999