Nearest point problems: Theory and algorithms.

摘要

The nearest point problem (NPP) may be stated as follows: Given a set $\Omega$ $\subset$ R$\sp{n}$ and a point $q$ $\in$ R$\sp{n}$, find a point $\bar x$ $\in$ ${\bf \Omega}$ such that $\bar x$ has the minimum distance "defined by a certain $p$-norm" to $q$ among all $x$ $\in$ ${\bf \Omega}$. NPP has many applications in robotics, remote sensing, chemical analysis, and so forth. It also appears as a subproblem in many optimization problems. Moreover, mathematical programming problems such as linear programs, linearly constrained least squares problems, and some special classes of linear complementarily problems and quadratic programs can be transformed to NPP's. In this dissertation, the NPP is studied. Variants of the problem are identified and the relationships among them are discussed. Four efficient algorithms are developed for solving the Euclidean NPP. Convergence of the algorithms are established and computational experience is reported. Algorithm 1 solves the NPP when ${\bf \Omega}$ is a convex polyhedron characterized by sets of points and directions. It uses an active set strategy, where in each step, it operates with an affine space of only a subset of points and directions. Algorithms 2, 3, and 4 solve the NPP when ${\bf \Omega}$ is a convex polyhedral cone. One of them (Algorithm 2) uses a series of two ray projections combined with an active set strategy which utilizes the geometry of the problem. Algorithms 1 and 2 are combinatorial in nature. Algorithm 3 uses an exterior point penalty approach in a novel way. The algorithm solves a series of uncontrained minimization problems approximately by performing only a single Newton step to solve each problem. It generates points that converge to the optimal solution. The performance of the algorithm is startling since it requires almost 6 iterations (where each iteration requries $O(n\sp{2.5})$ flops) to solve large problems. Its strategy is promising for approaching other mathematical programs. Algorithm 4 utilizes the geometry of the problem and solves it by generating interior points on the surfaces of spheres of reduced radii until the sphere that just touches the cone is constructed. Again, the algorithm requires a number of iterations (around 25 for n = 400) which increases very slowly with the dimension of the problem. Clearly, Algorithms 3 and 4 are noncombinatorial in nature. The dissertation compares the performance of combinatorial algorithms (Algorithms 1 and 2) and noncombinatorial algorithms (Algorithms 3 and 4) and display the relative merits and shortcomings of the two fundamentally different approaches to mathematical programs.