Optimization with multiple constraints I would like to solve the following optimization problem. I have the following quadratic object function:
$$f=\sum\limits_{i=1}^n (x_i-y_i)^2 = min$$
subject to the following linear constraints:
$$\sum\limits_{i=1}^n y_i = 0$$
and
$$\sum\limits_{i=1}^n \beta_i y_i = 0$$
If I only take the first constraint, the solution is 
$$ y_k = x_k - \frac{1}{n} \sum\limits_{i=1}^n x_i $$
However, I can't find a similar simple solution when I apply both constraints.
 A: We can apply the Lagrange multiplier method.
Denoting
$$
A=\begin{bmatrix}
1 & 1 & \ldots & 1\\
\beta_1 & \beta_2 & \ldots & \beta_n
\end{bmatrix}
$$
the problem is
$$
\min\, (y-x)^T(y-x)\quad\text{subject to } Ay=0.
$$
The Lagrange function is
$$
L(y,\lambda)=(y-x)^T(y-x)+\lambda^TAy.
$$
The optimality conditions are
$$
\nabla_y L=2(y-x)+A^T\lambda=0,\quad Ay=0.
$$
Solving the first one for $y$ 
$$
y=x-\frac{1}{2}A^T\lambda
$$
and substituting into $Ay=0$ gives
$$
Ay=Ax-\frac{1}{2}AA^T\lambda=0\quad\Rightarrow\quad\frac{1}{2}\lambda=(AA^T)^{-1}Ax. 
$$
(Here we assume that the matrix $A$ has full rank, i.e. the rows are not parallel.) It gives
$$
y=x-A^T(AA^T)^{-1}Ax=[I-A^T(AA^T)^{-1}A]x.
$$
A: The method needed to solve this problem is the Lagrange multiplier method with multiple constraints. In general, if you wish to minimise or maximise $f(\mathbf{x})$, subject to any number of constraints $g_1(\mathbf{x}) = 0$, $g_2(\mathbf{x}) = 0$, $g_3(\mathbf{x}) = 0$ etc., then define the "Lagrangian" as the function
$$\mathcal{L}(\mathbf{x},\lambda_1,\lambda_2,\lambda_3, \dots) = f(\mathbf{x}) + \lambda_1 g_1(\mathbf{x}) + \lambda_2 g_2(\mathbf{x}) + \dots $$
The problem is solved by doing an unconstrained optimisation of $\mathcal{L}$. That is $\partial \mathcal{L}/\partial x_i = 0$ for all $i$ and $\partial \mathcal{L}/\partial \lambda_i = 0$. Note that the second equation just recovers the constraint $g_i(\mathbf{x}) = 0$.
In your case, the Lagrangian would be
$$\mathcal{L}(\mathbf{y}, \lambda_1,\lambda_2) = \sum_{i = 1}^n (x_i - y_i)^2 + \lambda_1 \sum_{i = 1}^n y_i + \lambda_2 \sum_{i = 1}^n \beta_i y_i$$
The solution is then found by
$$\partial \mathcal{L}/\partial y_j = 0 = -2(x_j - y_j) + \lambda_1 + \lambda_2 \beta_j$$
Your constraints can then be used to eliminate the lambdas.
