3
$\begingroup$

The following least-square problem can be solved efficiently (e.g. using matlab's lsqlin):

$$\vec{x}^*=\arg\min_\vec{x} ||C\vec{x}-\vec{t}||^2\,\ s.t.\ Ax \le \vec{b}$$

where the parameters of the problem are vectors $\vec{t},\vec{b}$, and matrices $A,C$.

Is there an efficient way to solve this in parallel for multiple $\vec{t}_i$, but using the same $A, C, \vec{b}$? A solution which further assumes $C=I$ (the identity matrix) would work for me.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Depends on dimensions, but for small problems you can compute an explicit piecewise affine representation of the solution, i.e., a function $x = f(t)$. This field is called multiparametric programming. There is a toolbox in MATLAB called MPT addressing this problem.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks! From the samples I saw it working only for very small number of dimensions, 2-3, where I'm interested in vectors of size ~10-100. Can it work for such problems? $\endgroup$
    – Uri Cohen
    Commented Jun 14, 2017 at 14:43
  • $\begingroup$ I do not think so. $\endgroup$
    – Johan Löfberg
    Commented Jun 14, 2017 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.