ORIE Colloquium: Daniel Bienstock (Columbia) - Complexity and Exactness in Polynomial Optimization

Description

Polynomial optimization problems, that is to say, optimization problems whose constraint and objectives are multivariate polynomials, have acquired increased visibility in recent years due to their application in science and engineering. They are typically (highly) nonconvex and can be quite large, and, as a result, can prove very challenging. The methodology for solving such problems includes the development of relaxations that prove bounds, such relaxations are frequently described in a different space, of higher dimension, and often (almost always) only prove a bound on the objective value -- the vector they output, often, cannot be easily converted into a feasible solution in the original space. At the other end, we have logarithmic barrier methods that seek to compute feasible solutions but without any guarantee of optimality. Software packages include an additional feature, branching, in order to guarantee (at least in principle) the computation of a near-optimal solution. The lower bounding and upper bounding techniques, both, can exhibit serious numerical issues. One point that is not widely understood is that in the presence of nonlinearities and nonconvexities, it is easy to obtain examples where 'a little infeasibility buys you a lot of optimality', or, in other words, solvers output slightly infeasible solutions that are very superoptimal.

In this talk, we examine classical issues regarding the solutions to polynomially constrained problems, or semi-algebraic sets as are known in the mathematics community. One example of the results we have is that, given a feasible system of quadratic inequalities with integer coefficients, it is strongly NP-hard to decide if the system has a rational feasible solution. And, given a system of quadratic inequalities which is known to have rational feasible solutions, it is strongly NP-hard to decide if the system has a rational feasible solution of polynomial-size (= number of bits).

This is joint work with Alberto del Pia (U. of Wisconsin) and Robert Hildebrand (Virginia Tech).

Bio:
Daniel Bienstock received a B.A. in mathematics from Brandeis University in 1982 and a Ph.D. in operations research from Massachusetts Institute of Technology in 1982. He is a fellow of INFORMS and was a plenary speaker at the 2005 SIAM Optimization Conference and a semi-plenary speaker at ISMP 2006. He has received a Presidential Young Investigator Award and an IBM Faculty Partnership Award. He joined the faculty of Columbia Engineering in 1989 after working in combinatorics and optimization research at Bellcore. Bienstock’s current research focuses on two complementary topics. He is studying problems related to analysis and operations of power transmission networks, including analysis of the vulnerabilities of electrical power grids, a topic of increasing relevance to society, and one of fascinating mathematical complexity, which he explores in a book recently published by SIAM. The mathematics of power grids is nonlinear and nonconvex, as well as stochastic. A second recent thrust focuses on mixed-integer nonlinear programming problems and more generally polynomial optimization problems. The physics of power networks is nonlinear and subject to noise due to ambient conditions, ill-defined control actions (including human actions), and imprecise device operation. This subjects mathematical algorithms to complex forms of data uncertainty. Yet engineering practice demands precise answers and actions. An interesting topic is the verification of near-feasibility or infeasibility of candidate solutions to algebraic systems.