Minimum norm problem in Hilbert space with two constraints

Question

Let $x_0$ be a fixed vector in a Hilbert space $H$ and suppose $\{x_1,...,x_n\}$ and $\{y_1,...,y_m\}$ are sets of linearly independent vectors in $H$. We seek the vector

$x^* = \operatorname{arg} \min\limits_x \|x-x_0\|$,

subject to

$x \in M=\text{span}(x_1,...,x_n)$ and $\langle x, y_i \rangle=c_i$ for $i=1,...,m$ where the $c_i$'s are constants.

ADDITIONAL INFO:

1. This question corresponds to exercise 22 in chapter 3 of Luenberger's book Optimization by Vector Space Methods.
2. The exercise only asks for a set of linear equations which uniquely determine the solution (and not for the solution itself).
3. The exercise should be solved by using the Hilbert projection theorem (and not other techniques, like Lagrange multipliers).

---

My attempt:

Let $N=\text{span}(y_1,...,y_m)$. Then, the linear variety defined by the equality constraints $\langle x, y_i \rangle=c_i$ is a translation of $N^\perp$.

Since $M$ and $N^\perp$ are closed, $M \cap N^\perp$ is also closed and, by the projection theorem, $x^*$ exists and is unique, assuming that $M \cap N^\perp$ is not empty. Furthermore, $x^*-x_0 \in (M \cap N^\perp)^\perp$.

$x^* \in M \iff x^*=\sum_{j=1}^n\alpha_j x_j$, for some scalars $\alpha_j$. Defining $X$ as the matrix with columns $x_j$ and $\alpha$ as the vector of the $\alpha_j$'s, we can write $x^*=X \alpha$.

Using this in the equality constraints yields $\sum_{j=1}^n \alpha_j \langle x_j, y_i \rangle=c_i$ for $i=1,...,m$. Defining the $n \times m$ matrix $G$ with elements $G_{j,i} =\langle x_j, y_i \rangle$ and $c$ as the vector of the $c_i$'s, we can write $G'\alpha = c$.

If $m \geq n$, the solution of $G'\alpha = c$ either does not exist or is unique, so assume $m < n$.

Now, I probably have to use the fact that $\langle x^*-x_0, z \rangle = 0$ for any $z \in M \cap N^\perp$. Using this, we have:

$z \in M \cap N^\perp \implies z \in M \iff z = X\beta$ for some $n$-dimensional vector $\beta$.

Also, $z \in M \cap N^\perp \implies z \in N^\perp \iff \langle z, y_i \rangle=0$ for $i=1,...,m$.

Replacing $z = X\beta$ in the equalities $\langle z, y_i \rangle = 0$ yields $G'\beta = 0$, where $G$ is naturally the same as above.

Finally, using $x^* = X\alpha$ and $z = X\beta$ in $\langle x^*-x_0, z \rangle = 0$, we obtain

$\langle X\alpha, X\beta \rangle = \langle x_0, X\beta \rangle$.

And this is where I am stuck right now. We have $2n$ unknowns (the vectors $\alpha$ and $\beta$) and $2m+1$ equations:

$G'\alpha = c$ ($m$ equations),

$G'\beta = 0$ ($m$ equations),

$\langle X\alpha, X\beta \rangle = \langle x_0, X\beta \rangle$ (one equation),

where the last equation is clearly non-linear. Therefore, this cannot be the solution...

Answer 1

The mistake is at the very last point where you interpret $\beta$ as a solution (together with $\alpha$). Your condition basically says that $$ \exists\beta\colon G'\beta=0, z=X\beta\ \bot\ x^*-x_0 $$ However, it should be $$ \forall\beta\colon G'\beta=0\Rightarrow z=X\beta\ \bot\ x^*-x_0, $$ or equivalently $$ \beta\in\ker G'\Rightarrow \beta\ \bot\ X'(x^*-x_0). $$ In other words, $X'(x^*-x_0)$ annihilates the kernel of $G'$. Hence, it must belong to the image of $G$ $$ \exists\lambda\colon X'(x^*-x_0)=G\lambda\quad \Leftrightarrow\quad X'(X\alpha-x_0)=G\lambda. $$ This equation together with $G'\alpha=c$ results in $n+m$ equations and $n+m$ unknowns $(\alpha,\lambda)$.