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$
0

2 Answers 2

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.

$\endgroup$
1
  • 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$ Jul 11, 2014 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.

$\endgroup$
4

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.