2
$\begingroup$

What is the exact solution $x_{n \times 1}$ of the following constrained optimization problem \begin{align*} &\min \|A x - b\|^2 \\ s.t.& C x = 0 \end{align*} where $A$ is full column rank $m \times n$ matrix ($m>n$); $b$ is $m \times 1$ matrix; $C$ is full row rank $1 \times n$ matrix?

$\endgroup$
1
$\begingroup$

The Lagragian is the following:

$$ L = \sum \limits_{i = 1}^{m}(\sum \limits_{j = 1}^{2}a_{ij}x_{j} - b_{i})^{2} + \lambda \sum \limits_{j = 1}^{n}c_{i}x_{i} $$

$$ \frac{\partial L}{\partial x_{k}} = 2 \sum \limits_{j = 1}^{n}(\sum \limits_{i = 1}^{n}a_{ij}a_{ik})x_{j} - 2 n \sum \limits_{i = 1}^{m}b_{i} a_{ik} + \lambda c_{k} = 0 $$

There are $n + 1$ equations and $n + 1$ unknowns.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Just to make it clear: $n$ equations come from $\frac{\partial L}{\partial x_k}$, the last is the constraint $Cx=0$. $\endgroup$ – AndreaCassioli Jul 11 '14 at 11:23
1
$\begingroup$

The problem is given by:

$$ \begin{alignat*}{3} \arg \min_{x} & \quad & \frac{1}{2} \left\| A x - b \right\|_{2}^{2} \\ \text{subject to} & \quad & C x = \boldsymbol{0} \end{alignat*} $$

The Lagrangian is given by:

$$ L \left( x, \nu \right) = \frac{1}{2} \left\| A x - b \right\|_{2}^{2} + {\nu}^{T} C x $$

From KKT Conditions the optimal values of $ \hat{x}, \hat{\nu} $ obeys:

$$ \begin{bmatrix} {A}^{T} A & {C}^{T} \\ C & 0 \end{bmatrix} \begin{bmatrix} \hat{x} \\ \hat{\nu} \end{bmatrix} = \begin{bmatrix} {A}^{T} b \\ \boldsymbol{0} \end{bmatrix} $$

Now all needed is to solve the above with any Linear System Solver.

| cite | improve this answer | |
$\endgroup$

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.