3
$\begingroup$

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...

$\endgroup$
  • $\begingroup$ There are cases when no such $x^*$ exists. I think the assumption $M\cap N^\perp\neq\emptyset$ does not guarantee existence of $x^*$. $\endgroup$ – supinf Nov 22 '18 at 14:46
  • $\begingroup$ why you say so? the projection theorem guarantees that if $x$ is in some (non-empty) subspace then a unique solution exists... $\endgroup$ – D... Nov 22 '18 at 14:48
  • $\begingroup$ $M\cap N^\perp$ is not the feasible set from your question. You mentioned something about "translation by $c$" in the sentence before that, but that doesnt make much sense either because $c$ would be a vector in $\mathbb R^m$ and $N^\perp$ is a subset of a Hilbert space. $\endgroup$ – supinf Nov 22 '18 at 14:52
  • $\begingroup$ yes, it is a linear variety but of course not a 'translation by $c$'. just edited my answer. the problem remains valid, though. $\endgroup$ – D... Nov 22 '18 at 14:59
  • 1
    $\begingroup$ the Lagrangian approach results in a linear system $\endgroup$ – LinAlg Nov 26 '18 at 18:33
1
+100
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ wonderful explanation, thank you! $\endgroup$ – D... Dec 10 '18 at 10:05
  • $\begingroup$ Just a quick question: when you say that $X \beta \perp x^* - x_0$ is equivalent to $\beta \perp X'(x^* - x_0)$ aren't you assuming that the inner product in $H$ is the usual dot product? In case it is not, it should suffice to define an $m$ dimensional vector $v$ where the $j$-th element $v_j = \langle x_j, x^* - x_0 \rangle$. Then we have $v'\beta = 0$ and the result follows, right? $\endgroup$ – D... Dec 10 '18 at 11:54
  • 1
    $\begingroup$ @D... You are right with the vector $\nu$. What I wrote with $\nu=X'(x^*-x_0)$ was for notational simplicity (without any assumptions on the inner product). For any vector $y$ we have $\langle X\beta, y\rangle=\langle \sum \beta_i x_i, y\rangle=\sum\beta _i\langle x_i, y\rangle=\langle \beta, \nu\rangle$. $\endgroup$ – A.Γ. Dec 10 '18 at 12:10
  • $\begingroup$ I'm a bit confused now... You have written $\sum_i \beta_i \langle x_i, y \rangle = \langle \beta, \nu \rangle$, but how is it true if the inner product is, for instance, $\langle a, b \rangle = 2 a' b$ $\endgroup$ – D... Dec 10 '18 at 13:56
  • 1
    $\begingroup$ @D... Sorry for the confusion. My notation $x'y$ apparently differs from yours. I mean exactly $x'y=\langle x,y\rangle$ in the sense that $x$ is a linear functional. It is simply a notational thing. In this sense, $X'y$ in my answer above means exactly the vector of $\langle x_i,y\rangle$ and nothing else. $\endgroup$ – A.Γ. Dec 10 '18 at 14:32

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.