1

I'm having a bit of trouble with the following exercise:

Let $f\colon \mathbb{R}^n\to \mathbb{R}$ be given by $f(x)=\|x\|$. Consider the problem of minimizing $f$ subject to $Ax=b$, where $A\in\mathbb{R}^{m\times n}$, $b\in\mathbb{R}^m$, $m<n$, and rank($A)=m$. Prove that the solution of this problem can be written as $\bar{x}=\bar{A}b$, where $\bar{A}\in\mathbb{R}^{n\times m}$ and $A\bar{A}=I$.

My attempt was to use the fact that if $\bar{x}$ is optimal, then $\bar{x}$ satisfies the necessary optimality conditions. That is, $\nabla f(\bar{x})\in \text{Null}(A)^\bot=\text{Im}(A^\top).$ Or, in other words, there exists $\bar{\lambda}$ such that $\nabla f(\bar{x})=A^\top\bar{\lambda}$. Then I should somehow obtain something such as that $\bar{\lambda}=b$ and $AA^\top=I$.

Does anyone know how do I continue from this point or have another idea?

Thanks!

Rodrigo de Azevedo
  • 1
Ariel Serranoni
  • 494

1 Answers1

1

First, note that you can replace $f(x)$ by $\tilde{f}(x):=\frac{1}{2}||x||^2$, so that now the problem becomes differentiable and the KKT conditions may be formulated, but this does not change the solution set, as Rodrigo suggested. That is, there is a Lagrange multiplier $\lambda\in \mathbb{R}^m$ such that $\overline{x}=A^{T}\lambda$. Then $A\overline{x}=AA^{T}\lambda$ and, since $rank(A)=m$, the matrix $AA^{T}$ is invertible and $\lambda=(AA^{T})^{-1}b$. Now, replacing $\lambda$ in the KKT conditions give you $$\overline{x}=A^{T}(AA^{T})^{-1}b,$$ and the matrix $\overline{A}:=A^{T}(AA^{T})^{-1}$ satisfies all the properties you need.

Koto
  • 909