I have a linear least squares problem with linear constraints:
$$\min_x \| A x - b \|^2 \quad\text{subject to}\quad k_1 \leq x_i \leq k_2$$
Should quadratic programming be used here? If so, what would the formulation be?
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
What should be used may depend on what software you are using. Maple has a command LSSolve in its Optimization package to handle least-squares problems, including linearly-constrained ones. It uses an active-set method.
answered Jan 12, 2014 at 18:49
$\begingroup$
$\endgroup$
I think that this is a fit case for the Matlab function lsqlin. One of the dangers of quadratic programming in this case is that if your matrix $A$ is ill-conditioned, then quadratic programming leads to the formation of $A^T A$ in the cost function, whose condition number is even worse (squared).
$\begingroup$
$\endgroup$
4
You can either solve it by a special solver (As noted by other answers) or use Gradient Descent where each iteration you project the solution onto the box of the constraints.
It will be something like that:
$$ \begin{align*} {x}^{k + 1} & = {x}^{k} - \alpha ( {A}^{T} \left( A {x}^{k} - b \right) \\ {x}^{k + 2} & = \max \left\{ \min \left\{ {x}^{k + 1}, {k}_{2} \right\}, {k}_{1} \right\} \end{align*} $$
Where $ \alpha $ is the step size in the Gradient Descent.
-
$\begingroup$ Do you have an explanation or reference for why the max(min()) operator is a good idea? $\endgroup$ May 27, 2021 at 20:39
-
$\begingroup$ Because it is the projection on the set of constraints. So it is not a good idea, it is the optimal idea. $\endgroup$– RoyiMay 27, 2021 at 22:04
-
$\begingroup$ I'm not too familiar with optimization, but I think I can think of a counter example. Imagine an objective function shaped like W, such that the left and right ends are higher than the middle part, but also outside the bounded region. So finding the left end or the right end and then projecting onto the bounded region gives a suboptimal solution, which is in the middle of the region. Is this incorrect? $\endgroup$ May 27, 2021 at 22:25
-
$\begingroup$ The set $ \mathcal{S} = \left\{ \boldsymbol{x} \mid {k}_{1} \leq {x}_{i} \leq {k}_{2} \forall i \right\} $ is a convex function and the projection onto that set is given by the above. You won't find a counter example for that as it is a simple projection problem solved in any book on convex optimization. $\endgroup$– RoyiMay 27, 2021 at 22:29