Given $S=\{x\in\mathbb{R}^n | Ax = b\}$ and
$U=\{x\in\mathbb{R}^n|Cx=d\}$ where $A\in\mathbb{R}^{m\times n}$,
$b\in\mathbb{R}^m$, $C\in\mathbb{R}^{p\times n}$ and
$d\in\mathbb{R}^p$, consider the problem of finding the point of $S$
which is closer to $U$. Make this an optimization problem and write
the conditions for optimality
I'm learning to solve $\min f(x)$ subject to $Ax = b$. In theory we'd simply transform this to an unconstrained problem by analyzing $\phi(\overline{x}+Z\gamma)$ where $\overline{x}$ is a solution for $Ax=b$, $Z$ is the matrix of the basis of $\ker(A)$ and $\gamma$ is our variable of unscontrained optimization. We must now find $\min \phi(\gamma)$ subject to the entire $\mathbb{R}^{\mbox{something}}$.
However for this problem I cannot identity which is going to be our function from $\mathbb{R}^n$ to $\mathbb{R}$, Maybe $\frac{1}{2}||x-y||^2$ for $x\in S$ and $y\in U$. And we're subject to $Ax=b$ and $Cx=d$. How should I proceed?
UPDATE:
Following the answer given below, our condition in one matrix would be
$$\begin{bmatrix}A & 0\\0 & C\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix}=\begin{bmatrix}b\\d\end{bmatrix}$$
Basically, if $\overline{z}\in \mathbb{R}^{2n}$ is a point such that $\begin{bmatrix}A & 0\\0 & C\end{bmatrix}\overline{z}=\begin{bmatrix}b\\d\end{bmatrix}$, any vector $d$ in $\ker \begin{bmatrix}A & 0\\0 & C\end{bmatrix}$ is such that $\begin{bmatrix}A & 0\\0 & C\end{bmatrix}(\overline{z}+d) = \begin{bmatrix}b\\d\end{bmatrix}$, so $\overline{z}+Z\gamma$ being $Z$ a basis of kernel of $\begin{bmatrix}A & 0\\0 & C\end{bmatrix}$ and $\gamma\in\mathbb{R}^{m+p}$ is also a solution for any $\gamma$, because $Z\gamma\in\ker$ of that matrix.
Therefore we can construct the uncontstrained problem like this:
$$\phi(\gamma) = f(\overline{x}+Z\gamma) $$
which is equivalent to the constrained problem. So finding the minimum of the problem above is to find the minimum of the constrained problem. If $\gamma^*$ is a minimum of the unconstrained problem we have
$$\phi'(\gamma^*) = Z^t\nabla f(\overline{x}+Z\gamma) = 0$$
If the point is a minimum then the second order condition is
$$z^t\nabla^2 \phi(\gamma^*) z\ge 0$$
so
$$Z^t\nabla f(\overline{x}+Z\gamma)Z\ge 0$$
Are these conditions ok?
ps: my book says that the above condition ($Z^t\nabla f(\overline{x}+Z\gamma)Z\ge 0$) is the same as saying $y^t\nabla f(\overline{x}+Z\gamma)y\ge 0$ for all $y\in \ker Z$. Why?
Best Answer
You are almost right, since $y$ is different from $x$, you need $Cy=d$ instead of $Cx=d$: $$\min_{x,y} \left\{ \frac{1}{2}||x-y||^2 : Ax=b, Cy=d \right\}$$ The Lagrangian is $L(x,y,\lambda,\mu) = 0.5(x-y)^T(x-y) + \lambda^T(Ax-b) + \mu^T(Cy-d)$. The stationarity conditions together with feasibility conditions form a linear system: $$x-y + A^T \lambda = 0$$ $$x-y + C^T \mu = 0$$ $$Ax=b, Cy=d$$