Week 2¶

Exercise 1¶

Exercise

Let $S\subset \mathbb{R}^n$ be a closed convex set and let $f$ be function $f(x)=Ax+b$, with $A\in\mathbb{R}^{n\times n}$, and $b\in\mathbb{R}^n$.

(Actually we don’t need $S$ closed for any of this)

Exercise 1a)¶

Exercise

Prove that $f(S)=\left\{f(x)\,|\, x\in S\right\}$ is convex.

Let $z=f(x)\in f(S)$ and $w=f(y)\in f(S)$. Then for $\lambda \in [0,1]$ we have

\[\lambda f(x)+(1-\lambda) f(y)=f(\lambda x+(1-\lambda) y)\]

By convexity of $S$ we have that $\lambda x+(1-\lambda y)\in S$, and hence $f(S)$ is convex.

Exercise 1b)¶

Exercise

Prove that $f^{-1}(S)=\left\{x\in\mathbb{R}^n\,|\,f(x)\in S\right\}$ is convex.

Suppose $f(x),f(y)\in S$. Then

\[f(\lambda x+(1-\lambda)y) = \lambda f(x) +(1-\lambda)f(y),\]

which is again in $S$ by convexity. Hence $f^{-1}(S)$ is convex.

Exercise 1c)¶

Exercise

Suppose $T\subset \mathbb{R}^n$ is convex. Prove that the Minkowski sum $S+T=\left\{x+y\,|\,x\in S\,,y\in T\right\}$ is also convex.

Fix the points $s_1+t_1,s_2+t_2\in S+T$, with $s_i\in S, t_i\in T$, $i=1,2$. Choose $\lambda\in(0,1)$ and consider the point

\[z=\lambda(s_1+t_1)+(1-\lambda)(s_2+t_2)=\lambda s_1+(1-\lambda)s_2+ \lambda t_1+(1-\lambda)t_2 \,.\]

Since $\lambda s_1+(1-\lambda)s_2\in S$ and $\lambda t_1+ (1-\lambda)t_2\in T$ by convexity of $S$ and $T$ respectively, $z\in S+T$.

Exercise 2¶

Exercise

Let $\Omega$ be a convex set. Show that $f\colon \Omega\to \mathbb R$ is convex if and only if $\operatorname{epi}(f)$ is convex.

Recall $\operatorname{epi}(f) = \{(x,t)\in \Omega\times \mathbb R\mid f(x)\leq t\}$

“$\Leftarrow$” Let $x,y\in \Omega$, then in particular $(x,f(x)),\,(y,f(y))\in \operatorname{epi}(f)$. Let $t\in (0,1)$, then by convexity of the epigraph we have that

\[(tx+(1-t)y,\,tf(x)+(1-t)f(y))\in \operatorname{epi}(f)\]

This means that

\[f(tx+(1-t)y)\leq tf(x)+(1-t)f(y)\]

which is the definition of convexity.

“$\Rightarrow$” Suppose that $f$ is convex and let $(x,a)$, $(y,b)\in \operatorname{epi}(f)$, and $t\in (0,1)$. Then we have that $f(x)\leq a$ and $f(y)\leq b$. We then consider the convex combination

\[z_t=(tx+(1-t)y, ta+(1-t)b)\]

By convexity,

\[f(tx+(1-t)y)\leq tf(x)+(1-t)f(y)\leq ta+(1-t)b\]

Inspecting the first and last inequalities tells us that, $z_t\in \operatorname{epi}(f)$, and hence $\operatorname{epi}(f)$ is convex.

Exercise 3¶

Exercise

For a compact set $S \subset \mathbb{R}^{n}$ with $n\in\mathbb{N}$, show that $\operatorname{conv}(S)$, the convex hull of $S$, is a compact set.

Hint: recall that if $S\subset\mathbb{R}^n$ then every $x\in \operatorname{conv}(S)$ can be written as a convex combination of $n+1$ points of $S$ (Carathéodory’s Theorem).

Short proof: Let

\[\Lambda:=\{\mathbf\lambda\in [0,1]^{n+1}\mid \sum_{i=0}^n\lambda_i = 1\}\]

This space is compact, since it’s a closed subspace of $[0,1]^{n+1}$. By Carathéodory’s theorem the following map is surjective:

\[f\colon S^{n+1}\times \Lambda \to \operatorname{conv}(S),\qquad (y^0,\alpha^0,\dots,y^n,\alpha^n)\mapsto \sum_{i=0}^n\alpha^iy^i\]

Since $\operatorname{conv}(S)$ is the image of a continuous map from a compact space, it is also compact.

Using sequential compactness definition: Let $\{x_k\}_{k\in \mathbb N}\subset \operatorname{conv}(S)$ be a sequence, then we will show it has a convergent subsequence with limit in $\operatorname{conv}(S)$, i.e. we will show that $\operatorname{conv}(S)$ is sequentially compact which is equivalent to compactness for metric spaces.

By Carathéodory’s theorem for each $x_k$ there are $y_k^i\in S$ and $\alpha_k^i\in[0,1]$ such that $\sum_{i=0}^n\alpha_k^iy_k^i=x_k$. This defines a sequence

\[z_k = (y_k^0,\alpha_k^0,\dots,y_k^n,\alpha_k^n) \in S^{n+1}\times \Lambda\]

Since $S^{n+1}\times \Lambda$ is compact, $z_k$ has a convergent subsequence $\{z_{k_m}\}$. Since the map

\[f\colon S^{n+1}\times \Lambda\to \operatorname{conv}(S),\qquad (y^0,\alpha^0,\dots,y^n,\alpha^n)\mapsto \sum_{i=0}^n\alpha^iy^i\]

is continuous, we have that $f(z_{k_m})=x_{k_m}$ defines a convergent subsequence of $\{x_k\}$. We conclude that $\operatorname{conv}(S)$ is indeed compact.

Exercise 4¶

Exercise

For $n\in\mathbb{N}$, $A\in\mathbb{R}^{n \times n}$, $b\in\mathbb{R}^n$ and $c\in\mathbb{R}$, let us consider the function $f:\mathbb{R}^n \rightarrow \mathbb{R}$ given by

\[f(x) = \frac12 \, x^{\top} \!\! A \, x - b^{\top} \! x + c \quad\text{for all}\quad x\in\mathbb{R}^n\]

and the unconstrained-optimization problem

\[\tag{$*$} \min_{x\in\mathbb{R}^n} f(x) \, .\]

Exercise 4a)¶

Exercise

Assume that $A$ is indefinite. Show that the problem has no solution.

Since $\nabla^2f = A$, and $A$ is indefinite, none of the critical points are local minima, and function doesn’t have a minimum.

More directly, since $A$ is indefinite, there exists $x\in\mathbb{R}^n$ such that $\mu=-x^{\top}A x > 0$ and, thus,

\[f(tx) = -\frac{\mu}{2} \, t^2 - t \, (b^{\top} \! x) + c\]

is not bounded from below with respect to $t\in\mathbb{R}$. As a result, the infimum of $f$ on $\mathbb{R}^n$ is not attained and problem ($*$) has no solution.

Exercise 4b)¶

Exercise

Let $A$ be positive definite. Show that the problem is uniquely solvable. Obtain the solution for given $A$, $b$ and $c$.

Differentiation yields

\[\nabla f (x) = A x - b \quad\text{and}\quad \nabla^2 f(x) = A\]

for all $x\in\mathbb{R}^n$.

Since $A$ is positive definite, $f$ is strongly convex with a positive parameter, and the first-order necessary condition $Ax=b$ is sufficient for $x$ to be the solution of problem ($*$). Every positive-definite matrix is invertible, so the solution is unique and equals $x=A^{-1}b$.

Exercise 4c)¶

Exercise

When $A$ is positive semi-definite but not positive definite, find an example where the problem $(*)$ admits

no solution;
several solutions.

First case: The matrix $A=0$ is positive semi-definite, but then problem $(*)$ with $b\neq 0$ has no solution since $f$ is not bounded from below.

Second case: The matrix

\[\begin{split}A = \begin{pmatrix} 1 & 1 \\ 1 & 1 \\ \end{pmatrix}\end{split}\]

is positive semi-definite, but then the solution set of problem $(*)$ with $b=0$ is

\[\big\{x\in\mathbb{R}^2: \; x_1+x_2=0\big\} \, .\]

Exercise 5¶

Exercise

For $m\in\mathbb{N}$ such that $m \geq n$, a matrix $M\in\mathbb{R}^{m \times n}$ and a vector $u\in\mathbb{R}^m$, consider the least-squares problem

\[\tag{$**$} \min_{x\in\mathbb{R}^n} \|Mx-u\|_2 \, .\]

Exercise 5a)¶

Exercise

Demonstrate that problem $(**)$ is a problem of type $(*)$ defined in Exercise 4.

What is the matrix $A$ and the vectors $b,c$ in this case?

The problem $(**)$ is equivalent to minimizing

\[\|Mx-u\|^2_2 = (Mx-u)^\top (Mx-u) = x^\top M^\top Mx-2 u^\top M x+u^\top u\]

That is, problem $(*)$ with $A=2M^\top M$, $b=2M^\top u$ and $c=u^\top u$.

Exercise 5b)¶

Exercise

Show that the matrix $A$ of part a) is always positive semidefinite. Show that problem $(**)$ always admits a solution.

(Remark: this is not a contradiction to 4c) )

$A=2M^\top M$ which is always positive semidefinite ($x^\top M^\top M x = \|Mx\|^2\geq 0$). The problem can be reprased as $\min_{y\in \operatorname{im}M}\|y-u\|$. In exercise 3 of week 1 we showed this problem has a unique solution granted $\operatorname{im}M$ is convex and closed, but any linear subspace is convex and closed.

This doesn’t contradict problem 4c), because here the vector $b$ is given, whereas in problem 4c) we were free to choose it.

Exercise 5c)¶

Exercise

Now suppose that $M$ has full rank. Show that the solution is then unique, and give an explicit formula for the solution.

If $M$ has full rank then $M^\top M$ is in fact positive definite. The solution is therefore unique by exercise 4 b). The solution is then $x=A^{-1}b$, i.e. $x=(M^\top M)^{-1}M^\top u$.

Note that $M^\dagger:=(M^\top M)^{-1}M^\top$ is the Moore-Penrose pseudoinverse of $M$, and even if $M$ is not of full rank we can still define this pseudoinverse such that in particular $x=M^\dagger u$ solves $(**)$.