0
$\begingroup$

I want to prove (or disprove) the convexity of a function $f:\mathbb{R}^n \times \mathbb{R}^n \rightarrow\mathbb{R}$ defined as $$f(x,y) = \frac{1}{2}\|x-y\|_2^2.$$ My attempt: We know that $$f \text{ is convex} \iff \text{Hessian matrix is positive semi-definite}.$$ Hence, we want to show $$ H = \begin{bmatrix} \frac{\partial^2f}{\partial x_1^2} & \frac{\partial^2f}{\partial x_1\partial x_2} & \dots & \frac{\partial^2f}{\partial x_1\partial x_n} & \frac{\partial^2f}{\partial x_1\partial y_1} & \dots & \frac{\partial^2f}{\partial x_1\partial y_n}\\ \frac{\partial^2f}{\partial x_2 \partial x_1} & \frac{\partial^2f}{\partial x_2^2} & \dots & \frac{\partial^2f}{\partial x_2\partial x_n} & \frac{\partial^2f}{\partial x_2\partial y_1} & \dots & \frac{\partial^2f}{\partial x_2\partial y_n}\\ \vdots & \vdots & \ddots\\ \frac{\partial^2f}{\partial x_n\partial x_1} & \frac{\partial^2f}{\partial x_n\partial x_2} && \frac{\partial^2f}{\partial x_n^2}\\ \frac{\partial^2f}{\partial y_1\partial x_1} & \frac{\partial^2f}{\partial y_1\partial x_2} &&& \frac{\partial^2f}{\partial y_1^2}\\ \vdots & \vdots &&&& \ddots\\ \frac{\partial^2f}{\partial y_n\partial x_1} & \frac{\partial^2f}{\partial y_n\partial x_2} &&&&& \frac{\partial^2f}{\partial y_n^2} \end{bmatrix} $$ is positive semi-definite. Here, I am constructing $H$ by treating the function as a multivariate function in $\mathbb{R}$ like so: $$f(x_1, \dots, x_n, y_1, \dots, y_n) = \frac{1}{2}\sum_{i=1}^{n}(x_i-y_i)^2.$$ Then, I look at each possible element of the Hessian matrix: $$\frac{\partial^2 f}{\partial x_i \partial x_j} = \delta_{ij}$$ $$\frac{\partial^2 f}{\partial x_i \partial y_j} = \frac{\partial^2 f}{\partial y_i \partial x_j} = -\delta_{ij}$$ $$\frac{\partial^2 f}{\partial y_i \partial y_j} = \delta_{ij}$$ where $\delta_{ij} := \begin{cases}1,\ \ i=j\\0,\ \ i\ne j\end{cases}$.
This means our Hessian will be $$ H = \begin{bmatrix} I^{n\times n} & -I^{n \times n}\\ -I^{n \times n} & I^{n\times n} \end{bmatrix} $$ where $I^{n\times n}$ is the $n\times n$ identity matrix. Now, all I need to do is determine if $H$ is positive semi-definite. That is, if $$x^THx \ge 0, \ \ \forall x\in \mathbb{R}^n.$$

By playing around with small examples of $H$ I believe the general formula for $x^THx$ is $$x^THx = \sum_{i=1}^{n} x_i^2 - 2\sum_{j=1}^{n/2} x_ix_{i+n/2}.$$ (although I don't know how to show this). An example here.

From here, I use the fact that $x_i^2 + x_j^2 > 2x_ix_j$ to claim $$x^THx \ge 0$$ and hence $H$ is positive semidefinite. Thus, $f$ is convex.

Is this reasoning correct? How might I prove the determinant is what I claim?

$\endgroup$
0
1
$\begingroup$

Looks good.

In the verification, you could have used the stacked vector $\pmatrix{x\\y}$, then $$ \pmatrix{x\\y}^TH\pmatrix{x\\y} = x^Tx - 2x^Ty + y^Ty = \|x-y\|_2^2 \ge0. $$

This task gets easier, if one realizes that $f$ is the composition of a linear map $\pmatrix{I\\-I}$ with the convex function $\frac12\|\cdot\|_2^2$. Such a composition is always convex.

$\endgroup$

Your Answer

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