Is the problem: $\underset{x}{\min}\|x-c\|_{2}^{2}$ subject to $Ax=b$ convex?

Question

We define the problem:

$\underset{x}{\min} \|x-c\|_{2}^{2}$

subject to $Ax=b$.

First, I found the optimal solution

$$x^{\text{opt}}=c-A^{T}(AA^{T})^{-1}(Ac-b)$$

Next I want to find if this problem is convex or not. How I can do this?

---

Edit: I know how to check the convexity of the objective function. I want to know how to verify if the convexity condition holds on the feasible area.

Answer 1

Yes

First let's find the definition of an optimization problem being convex:

An optimization problem $$ \begin{array}{rl} \underset{x}{\arg \min} & f(x) \\ \text{subject to} & A x = b \end{array} $$ is convex if the function $f$ is convex and the feasible region (defined by the constraint) is also convex.

Now. The quadratic objective is definitely convex \begin{align} f(\lambda x + (1-\lambda)y) &= \lVert \lambda x + (1-\lambda)y - c \rVert_2^2 \\ &= \lVert \lambda (x - c) + (1-\lambda)(y - c) \rVert_2^2 \\ &\leq \lambda\lVert x-c\rVert_2^2 + (1-\lambda)\lVert y -c \rVert_2^2 \tag{triangle inequality} \\ &= \lambda f(x) + (1-\lambda)f(y). \end{align} The feasible set is defined by a linear constraint and therefore also convex. Suppose $$A x = b, A y = b$$ Then, \begin{align} A(\lambda x + (1-\lambda)y) &= \lambda A x + (1-\lambda) Ay \\ &= \lambda b + (1-\lambda)b \\ &= b \end{align} In other words, if $x$ and $y$ are inside the feasible region, so is the line between the two points. We have proved the two conditions of the definition and conclude that the problem is convex.