Krdytkyu

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} minlimits_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}^nalpha_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 = Xbeta$ 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 = Xbeta$ in the equalities $langle z, y_i rangle = 0$ yields $G'beta = 0$, where $G$ is naturally the same as above.

Finally, using $x^* = Xalpha$ and $z = Xbeta$ in $langle x^*-x_0, z rangle = 0$, we obtain

$langle Xalpha, Xbeta rangle = langle x_0, Xbeta 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 Xalpha, Xbeta rangle = langle x_0, Xbeta rangle$ (one equation),

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

The mistake is at the very last point where you interpret $beta$ as a solution (together with $alpha$). Your condition basically says that
$$
existsbetacolon G'beta=0, z=Xbeta bot x^*-x_0
$$
However, it should be
$$
forallbetacolon G'beta=0Rightarrow z=Xbeta bot x^*-x_0,
$$
or equivalently
$$
betainker 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$
$$
existslambdacolon X'(x^*-x_0)=Glambdaquad Leftrightarrowquad X'(Xalpha-x_0)=Glambda.
$$
This equation together with $G'alpha=c$ results in $n+m$ equations and $n+m$ unknowns $(alpha,lambda)$.