simard@cs.rochester.edu (11/27/89)
Help, I'm looking for an algorithm which given a point P and and a convex polygone M in a n-dimentional space S, find the closest point of M to P. The convex M is given by the set of m linear constraints: A X + B > 0 where A is an m by n matrix, X is an n-dimensional vector, and B and 0 are of dimension m. The (inelegant) solution I have now is to find a point of M using the simplex method and then do some kind of gradient descent (O((mn)^2)) to find the closest point to P. Any help would be appreciated. -- Patrice (simard@cs.rochester.edu) ps: Any information about where to get C code to do this will be welcome (also if you have a good C program for simplex...).
rjfrey@kepler1.UUCP (Robert J Frey) (11/28/89)
In article <1989Nov27.060304.27985@cs.rochester.edu> simard@cs.rochester.edu writes: > >I'm looking for an algorithm which given a point P and and a convex polygone M >in a n-dimentional space S, find the closest point of M to P. The convex >M is given by the set of m linear constraints: > > A X + B > 0 > The square distance between the variable X and the fixed point P is a quadratic function of X; your problem is the quadratic program (QP): minimize (X1-P1)^2 + (X2-P2)^2 + ... + (Xn-Pn)^2 subject to X in M This is easy to solve. Consult any intro text in Operations Research. -- Dr. Robert J Frey, Kepler Financial Management, Ltd. {acsm, lilink, polyof, sbcs}!kepler1!rjfrey *or* frey@sbcs.sunysb.edu voice: (516) 689-6300 * fax: (516) 751-8678