# Solving multiple least-square problems with the same constraints

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.

## 1 Answer

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.

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