optimization by convex space methods problem

Question

Given a function $x \in L_2[0, 1]$, we seek a polynomial $p$ of degree $n$ or less which minimizes $\int_{0}^{1}|x(t) - p(t)|^2dt$ while satisfying the requirement $\int_{0}^{1}p(t)dt = 0$.

(a) Show that this problem has a unique solution.

(b) Show that this problem can be solved by first finding the polynomial $q$ of degree $n$ or less which minimizes $\int_{0}^{1}|x(t) - p(t)|^2dt$ and then finding $p$ of degree $n$ or less which minimizes $\int_{0}^{1}|q(t) - p(t)|^2dt$ while satisfying $\int_{0}^{1}p(t)dt = 0$.

Solution:

I tried to used the projection theorem over a Hilbert Space L_2[0, 1] to try to show part a) but I am not sure if it is sufficient to proof part B.

Source: Optimization by Vector Space Methods (Ch.3, prob 6)

Answer 1

This answer is a bit of overkill, the result at the bottom generalises jing007's answer a bit.

Let $P_n$ be the polynomials of degree $n$ or less. Note that $P_n$ is a finite dimensional subspace hence closed. Let $\Pi$ be the orthogonal projection onto $P_n$, that is $\Pi x \in P_n$ is the unique solution of $\min_{p \in P_n} \|x-p\|$. The projection is linear and self adjoint.

Let $Z = \{x | \int_0^1 x(t) dt = 0 \} = \{1\}^\bot$, where $1$ denotes the function $1(t) = 1$ for all $t$. Hence $Z$ is a closed subspace. Let $N x$ be the orthogonal projection onto $Z$, note that $Z$ is linear, self adjoint and we have the formula $Nx = x-\int_0^1 x(t)dt$.

Since $P_n \cap Z$ is a closed subspace there is a uniquely defined orthogonal projection onto $P_n \cap Z$, this answers (a).

Note that $x - \Pi x \in P_n^\bot \subset \{1\}^\bot$ and so $x - \Pi x \in Z$, that is $\int_0^1 x(t) dt = \int_0^1 (\Pi x)(t)dt$.

We have $\Pi N x = \Pi x - \Pi \int_0^1 x(t) dt = \Pi x - \int_0^1 (\Pi x)(t) dt = N \Pi x$ and so $\Pi, N$ commute.

Hence $\Pi N = N \Pi$ is an orthogonal projection onto $P_n \cap Z$ (see Orthogonal projection and two subspaces for example). In particular, the desired projection can be computed by applying $\Pi, N$ in either order. This answers (b).

Addendum:

If $C$ is a closed convex set then for each $x$ there is a unique point $N_C(x)$ that solves $\min_{c \in C} \|x-c\|$. $N_C(x)$ is called the projection of $x$ onto $C$.

If $C$ is a closed subspace then we can show that $x \mapsto N_C(x)$ is linear and is an orthogonal projection (onto $C$) in the usual sense of linear operators.

In the above, we have $\Pi x = N_{P_n}(x)$ and $N x = N_Z(x)$.

A very useful characterisation for a closed subspace $C$ is that $p$ is the nearest point in $C$ to $x$ iff $p \in C$ and $p-x \in C^\bot$.

Useful result:

Here is a useful, geometrically satisfying result that addresses the question.

Suppose $C$ is a closed convex set and $A$ is a closed affine set that contains $C$ (in particular, any closed subspace is affine). Then $N_C(x) = N_C(N_A(x))$.

That is, the nearest point can be computed by projecting onto an affine set that contains $C$ first and then projecting the resulting point onto $C$. (Projecting onto affine spaces or subspaces is often a more straightforward computation.)

To prove this, note that for any closed convex set $K$ we have $p = N_B(x)$ iff $\langle x-p,p-b \rangle \le 0$ for all $b \in B$.

Let $a = N_A(x)$ and $c = N_C(N_A(x))$, then for $c' \in C$ we have

\begin{eqnarray} \langle x-c,c-c' \rangle &=& \langle x-a + a-c,c-c' \rangle \\ &=& \langle x-a,c-c' \rangle + \langle a-c,c-c' \rangle \\ &=& \langle a-c,c-c' \rangle \\ &\le& 0 \end{eqnarray} It follows from this that $c=N_C(x)$.

To apply to the question, take $C = P_n \cap Z$, $A = P_n$.

Note that this is not quite as strong a conclusion as the above answer.

Answer 2

Let $U = \{p \in L^2[0,1] : \text{polynomials with degree less or equal to $n$}\}$. $U$ is finite dimensional and is thus closed. Let $V = \{p \in U : \int_{0}^1 p(t) dt =0\}$. Easy to check $V$ is a subspace of $U$ and hence is finite dimensional and $V$ is also closed. Now by projection theorem, for any $x \in L^2[0,1]$, there exists a unique minimizing vector $q \in V$, i.e. $\|x-q\| \le \|x - p\|$ for any $p \in V$.

In part b, we are given $q \in U$, $p \in V$, and \begin{align} x-q \perp U \qquad q-p \perp V. \label{eq:cond1} \end{align} It suffices to show $x - q \perp V$ since by projection theorem $q$ minimizes $\|x-p\|$. Now we write down above condition explicitly \begin{align*} \forall q' \in U, \; \langle x-q, q'\rangle = 0 \\ \forall p' \in V, \; \langle q-p, p'\rangle = 0 \end{align*} We choose any $p_0 \in V$. Since $V$ is a subspace and $p \in V$, $p - p_0 \in V \subseteq U$. Then we have \begin{align} \langle x-q, p-p_0\rangle = 0 \label{eq:cond2}\\ \langle p-q, p-p_0\rangle = 0 \label{eq:cond3} \end{align} Taking the difference, we have \begin{align*} \langle x-p, p-p_0\rangle = 0 \end{align*} Since $p_0$ is an arbitrary element in $V$, above condition is equivalent to \begin{align*} x-p \perp V \end{align*}