| EPSRC Reference: |
EP/K007645/1 |
| Title: |
Large-Scale Optimization on Euclidean Distance Matrices |
| Principal Investigator: |
Qi, Professor H |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
School of Mathematics |
| Organisation: |
University of Southampton |
| Scheme: |
Standard Research |
| Starts: |
25 April 2013 |
Ends: |
24 April 2015 |
Value (£): |
157,641
|
| EPSRC Research Topic Classifications: |
| Mathematical Aspects of OR |
Numerical Analysis |
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
The Euclidean distance is a familiar metric in everyday life. For example, we use it when we measure the distance between two places. The distances used in the Pythagoras theorem learned in our school days are Euclidean. To generalize, suppose we have a number of objects with their mutual Euclidean distances, which form a Euclidean Distance Matrix (EDM) when orderly put into a matrix? What has amazed researchers is that this distance matrix contains rich information about locations of those objects. The solution of this has been famously solved as early as 1935 by I.J. Schoenberg and 1938 independently by G. Young and A.S. Householder.
However, as expected from real applications, full content of a EDM is rarely available. The situation becomes more difficult when the embedding dimension is enforced. For example, the embedding dimension is 3 in molecular conformation. In the application of wireless sensor network localization and positioning vehicles, the dimension is 2 or 3. The small embedding dimension forces the problem to be non-convex and the EDM cone cut by the embedding dimension becomes peculiar. Famous models that deal with this non-convex problem include the coordinate parameterization and SDP relaxation. The former is a polynomial optimization and the solution of latter has to be corrected in order to satisfy the embedding dimension. Both are of large scale and often end up at a local minimizer. The focus of current research is on efficient methods that find a global solution at fast speed in order to meet requirement of applications.
The purpose of this project is to consider a new model that decomposes the peculiar geometry body of EDMs and treats each part differently. First, we keep the convex cone of EDMs in the model. Second, we represent the set related to the embedding dimension as a level set of a concave function and we penalize the concave function to the objective. Third, when we have a large number of range constraints (i.e., the well-known data box case) we either deal with them via H-weighting scheme or keep them explicitly. Therefore, the model can be adapted to real situation. Our model has a close link to the rank minimization problem that is undergoing significant change at the moment.
The key method that behind this new model is the Newton method based on the dual problem of the model. Our model is built with the aim that the Newton method can be structurally analysed. It will rely on new second-order characterizations of the orthogonal projection onto the convex cone of EDMs. Computable global optimality condition will be established for some special cases. This ensures that our algorithmic scheme is not just fast (being Newton's method) but also able to provide approximate solution of high quality. We will draw techniques from Google's PageRank algorithm, concave quadratic penalization from classical optimization, and majorization scheme from multi-dimensional scaling to facilitate our analysis and computation. We expect that good mathematics behind the model and the algorithm will be nicely harmonized with its numerical performance.
Our tasks will be then enhanced by engaging relevant practitioners. We plan to stress-test our theory as well as the algorithm by applying them to real problems from molecular conformation and wireless sensor networks. Our expectation will be that the solution produced will be good enough for the purpose of further analysis and the time taken will be fast enough to meet the realistic demanding of the end-users. By showing strong numerical performance, we will also keep in constant touch with Numerical Algorithms Group (NAG) aiming for the algorithm to be implemented by NAG in future. The results will also make a nice contribution to the Polynomial Optimization workshop planned in 2013 at The Newton Institute, Cambridge.
|
|
Key Findings |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Potential use in non-academic contexts |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Impacts |
|
| Description |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk |
| Summary |
|
| Date Materialised |
|
|
|
|
Sectors submitted by the Researcher |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
| Project URL: |
|
| Further Information: |
|
| Organisation Website: |
http://www.soton.ac.uk |