Practical algorithms for polynomial optimization
Abstract
Short Work Statement: This project will develop new theory and computational approach to solve polynomial optimization problems (POPs) numerically.Merit/Relevance: Polynomial optimization problems (POPs) arise in several areas of science that are important to theNavy and DoD, network security, photonics, and computational chemistry. Polynomial optimization is widely present in new and emerging technologies,including technologies that are important to national security and the military. Examples of applications directly related to this proposal include network security, photonics, and computational chemistry. These models are difficult to solve, and require fundamental research. A direct consequence of this project will be the development of theory and computational methods that will improve our ability to solve these hard and important problems both heuristically, as well as exactly.Objective:This project will develop new theory and computational approach to solve polynomial optimization problems (POPs) numerically. These problems are notoriously difficult, and require fundamental research. A direct consequence of this project will be the development of theory and computational methods that will improve our ability to solve these hard and important problems both heuristically, as well as exactly. The PIs will use tools from integer optimization and algebraic geometry. The end result will be new and improved subroutinesthat will expand the frontier of knowledge and the ability to solve POP in practice.Approach:The approach will be based on three ideas: First, sparsity in the optimization problem will be exploited.This will be done by finding a tree decomposition of the problem having of small width. Next, the PI will introducebinary variables, which will be used to approximate the polynomial-optimization problem with a pure binary problem that inherits the tree-decomposition of smallwidth. Finally, the binary problem lifted into an exact linear-programming problem, which is then solved directly (if it is small enough), solved using cutting-plane techniques.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Sep 30, 2016
- Source ID
- N000141612889
Entities
People
- Daniel Bienstock
Organizations
- Office of Naval Research
- Trustees of Columbia University in the City of New York
- United States Navy