Adapting the Simplex method to use the distance function as the target.

Question

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?

Answer 1

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.