0
$\begingroup$

I'm looking for a numerical solution to the constrained least squares problem below: $$ \min_\mathbf{x}\|\mathbf{a+Bx}\|^2 ~~\text{s.t}~~\|\mathbf{x}\|^2 \leq \alpha^2$$ where $\mathbf{a} \in \mathbb{C^{M\times 1}}$ and $\mathbf{B} \in \mathbb{C^{M\times N}}$. I'd appreciate it if anyone can point me to a solver, preferably Matlab. I have already looked, but it doesn't look like Matlab has a solver for this.

$\endgroup$
  • 1
    $\begingroup$ You can try CVX. $\endgroup$ – AnonSubmitter85 Aug 2 '14 at 0:28
  • $\begingroup$ @AnonSubmitter85 Thank you. I will try it. $\endgroup$ – user4259 Aug 2 '14 at 0:49
  • $\begingroup$ @AnonSubmitter85 Thank you again, CVX works perfect. $\endgroup$ – user4259 Aug 2 '14 at 2:13
0
$\begingroup$

Your problem is known as the "trust region subproblem", because it occurs as a subproblem in trust region methods for nonlinear optimization. There are many papers that discuss the numerical challenges of this problem and give specialized algorithms for its solution.

CVX is certainly capable of solving the problem, but one of the specialized algorithms is likely to be much faster.

$\endgroup$
0
$\begingroup$

The problem is given by:

$$ \begin{alignat*}{3} \text{minimize} & \quad & \frac{1}{2} \left\| A x - b \right\|_{2}^{2} \\ \text{subject to} & \quad & {x}^{T} x \leq \alpha \end{alignat*} $$

The Lagrangian is given by:

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

The KKT Conditions are given by:

$$ \begin{align*} \nabla L \left( x, \lambda \right) = {A}^{T} \left( A x - b \right) + 2 \lambda x & = 0 && \text{(1) Stationary Point} \\ \lambda \left( {x}^{T} x - \alpha \right) & = 0 && \text{(2) Slackness} \\ {x}^{T} x & \leq \alpha && \text{(3) Primal Feasibility} \\ \lambda & \geq 0 && \text{(4) Dual Feasibility} \end{align*} $$

From (1) one could see that the optimal solution is given by:

$$ \hat{x} = {\left( {A}^{T} A + 2 \lambda I \right)}^{-1} {A}^{T} b $$

Which is basically the solution for Tikhonov Regularization of the Least Squares problem.

Now, from (2) if $ \lambda = 0 $ it means $ {x}^{T} x = 1 $ namely $ \left\| {\left( {A}^{T} A \right)}^{-1} {A}^{T} b \right\|_{2} = 1 $.

So one need to check the Least Squares solution first.
If $ \left\| {\left( {A}^{T} A \right)}^{-1} {A}^{T} b \right\|_{2} \leq \alpha $ then $ \hat{x} = {\left( {A}^{T} A \right)}^{-1} {A}^{T} b $.

Otherwise, one need to find the optimal $ \hat{\lambda} $ such that $ \left\| {\left( {A}^{T} A + 2 \lambda I \right)}^{-1} {A}^{T} b \right\| = \alpha $.

You can see how to solve it in my solution for $ \min_{x^Tx=1} x^TAx-c^Tx$.

$\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.