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.


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.

  • $\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 Jun 14 '17 at 14:43
  • $\begingroup$ I do not think so. $\endgroup$ – Johan Löfberg Jun 14 '17 at 15:27

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.