Tight Relaxation Methods for Optimization

University Of California-San Diego, La Jolla CA

Investigators

Abstract

This project is on the development of a class of methods known as "tight relaxation methods" for solving optimization problems, such as polynomial optimization, generalized Nash equilibria, matrix constrained optimization, and other related research questions. These problems are usually nonlinear, nonconvex, and are often given by polynomial or rational functions. Locating their global optima is a crucial task in various applications. Tight relaxation methods are especially useful for solving these optimization problems globally, which, in the case of a nonconvex objective function, is a non-trivial task. Results produced by this project have broad applications in science and engineering and have the potential to provide tools for locating Nash equilibria, solving mixed integer nonlinear programming problems, and optimizing power flow. This project works on research tasks for solving some hard optimization problems. In many applications, computing a critical point or local optimizer may not be satisfactory for the needs. Tight relaxation methods are preferable for computing the global optima. One problem, considered in this project, is the generalized Nash equilibrium problem (GNEP), which deals with solving several optimization problems simultaneously. Each optimization problem represents the strategy selection by a player. All players look for a common selection of strategies such that all players achieve their optimal decisions. The GNEP is particularly hard, since the objective function and feasible set for each player depend on strategy selections by other players. Another problem in this project is the matrix-constrained polynomial optimization problem (MCPOP). Its constraints are given by polynomial matrix inequalities, which are typically nonlinear and nonconvex. A major challenge in solving MCPOP is the lack of efficient computational methods for computing global optimizers. There are other types of hard optimization problems with behavior similar to the GNEP and MCPOP. Tight relaxation methods provide a computational framework for solving them. The tools used in constructing tight relaxation methods are Lagrange multiplier expressions, sum of squares, moment relaxations, and semidefinite programs. This project aims to develop efficient computational methods for solving these hard optimization problems. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.