Has anyone adapted the simplex method to use the distance from a point as the minimization criteria?

E.g. Given target vector $\mathbb{t}$, matrix $\mathbb{A}$ and limits $\mathbb{b}$
Minimize $\sqrt{\sum _{i=0}^m \left(\mathbf{x}_i-\mathbf{t}_i\right){}^2}$ where
$\mathbb{A}.\mathbf{x}\leq \mathbf{b}$
$\forall _{i,1\leq i\leq m}x_i\geq 0$

It seems to me there should be an efficient variant of the simplex method for a problem like this.

In a linear minimization problem, the solution is either (1) one of the vertices of the feasible region (2) an entire "edge" of the feasible region. (Where an "edge" may have any of 1 ... m-1 dimensions)

With a distance function, the solution is either (1) one of the vertices of the polytope (2) a point somewhere on an edge, since for each edge there is one unique point that is closest to the target point $\mathbb{t}$.

Is it possible to pivot towards these closest points as efficiently as you can pivot towards a vertex? Has anyone worked out the details on this?

  • $\begingroup$ $\sum _{i=1}^m \sqrt{\mathbb{x}_i^2-\mathbb{t}_i^2}$ should be $\sqrt{\sum _{i=1}^m (\mathbb{x}_i-\mathbb{t}_i)^2}$ but you can drop the global "square root" symbol because minimizing a certain quantity is the same as minimizing its square. $\endgroup$ – Jean Marie Aug 5 '16 at 4:13
  • $\begingroup$ There is stil a missing square. $\endgroup$ – Jean Marie Aug 5 '16 at 4:14
  • $\begingroup$ Sorry -- I'm trying to fix my bad TeX formatting. I think it's right at this point. $\endgroup$ – Charles Gillingham Aug 5 '16 at 4:15
  • $\begingroup$ Yes, you're right about the square root -- but it helps my geometric intuition to see it as the regular old distance function. $\endgroup$ – Charles Gillingham Aug 5 '16 at 4:16
  • $\begingroup$ Your problem (once you have suppressed the square root sign...) is in the domain of quadratic programming $\endgroup$ – Jean Marie Aug 5 '16 at 4:17

See for instance:

Philip Wolfe, The Simplex Method for Quadratic Programming, Econometrica, Vol. 27, No. 3, (Jul., 1959), pp. 382-398

This is an extension to the Simplex method for a standard Quadratic Programming (QP) problem, so a slightly more general problem than you are stating.


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.