Harnessing the Complex Numbers for Efficiently Solving Real Problems
Abstract
Statement of Work:The PI will develop efficient algorithms for convex~optimization problems.Objective:The goal of the proposed research is develop new, innovative methods for convex optimization based on numerical algebraic geometry. The primary focus of the proposed research will be on primal~dual interior~point methods (IPMs), which are used extensively for solving linear, semi~definite, and convex~optimization problems. IPMs start out at a point in the relative interior of the feasible region, and then trace out a path to an optimal solution on the boundary. Interior~point methods are fairly robust, but can fail on certain types of problems. In particular, if the optimization problem is ill conditioned, or if the feasible region of the optimization problem implicitly lies in a lower dimensional space, then IPMs can encounter problems.Approach:The approach will be to address the computational issues of ill~conditioning and degeneracy that IPMs can encounter. To address ill conditioning, the PI proposes to apply Newton homotopies over the complex domain to trace out a path to an optimal solution. By extending the domain of the path from the reals to complex numbers, the PI has shown that ill conditioning can potentially be avoided. To address the degeneracy, the PI proposes using witness sets, a techniquewhich he has developed in the context of algebraic geometry.Overall Merit and ONR Mission/Relevance:Convex~optimization problems arise in many Navy~relevant areas, such as compressed sensing for images and signals, classification problems, and decision problems with missing data. The goal of the proposed research is develop new, innovative methods for convex optimization based on numerical algebraic geometry. The proposed approach is extremely innovative and certainly qualifies as high~risk/high payoff research.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Aug 12, 2016
- Source ID
- N000141612722
Entities
People
- Jonathan D Hauenstein
Organizations
- Office of Naval Research
- United States Navy
- University of Notre Dame