OPTIMIZATION OF SPARSE POLYNOMIALS AND SIGNOMIALS
Abstract
Due to their numerous and varying applications, optimization problems involving multivariate polynomials within the objective function and constraints have become a significant topic of research. Combinatorial problems on graphs commonly yield quadratic polynomials (functions involving pairwise products of variables) while engineering design problems in which relations between physical quantities are given by power laws yield higher-degree polynomials. Many classes of aircraft design problems that involve the optimal sizing of the wing, tail, and fuselage can be formulated as high-degree polynomial optimization problems. Other examples arise in hitting-time estimation and time-to-target estimation in dynamic systems. The most popular approach for obtaining bounds on such problems is based on sums-of-squares methods which yield semidefinite relaxations. A significant drawback with these methods is that they scale exponentially in the degree of the underlying polynomials. However, polynomial programs in practice are often structured, and alternative approaches to semidefinite relaxations that exploit problem structure will be better suited to large-scale problems. The research is to provide a convex relaxation framework for signomial optimization based on relative entropy optimization. The idea is to take advantage of sparsity so that the size of the relaxation grows in the number of terms as opposed to the exponential increase required for semi-definite type relaxations. The expected outcome is improved understanding of the theory and algorithms for solving signomial optimization problems, with detailed computational experiments to demonstrate the scalablity and feasibility for providing bounds and extracting high-quality feasible solutions.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Mar 07, 2023
- Source ID
- FA95502210225
Entities
People
- Venkat Chandrasekaran
Organizations
- Air Force Office of Scientific Research
- California Institute of Technology
- United States Air Force