Non-Lipschitz Optimization Problems Involving Eigenvalues

点击翻译按钮获取中文摘要

Proposal #0098145New York UniversityMichael OvertonNon-Lipschitz Optimization Problems involving EigenvaluesOptimization problems involving eigenvalues arise in many applications. In recent years, attention has focused on semidefinite programs, which are linear optimization problems in the space of real symmetric matrices, with positive semidefinite constraints. This project focuses on optimization problems in the larger space of square matrices, not necessarily symmetric. In the problems being studied, eigenvalues may appear in the optimization objective, in the constraints, or both. The dependence of eigenvalues as functions of a matrix is non-Lipschitz at points where the eigenvaluemultiplicity is greater than one. Hence, such optimization problems are non-Lipschitz. They arise in areas ranging from control theory (e.g., stability constraints) to Markov chains (e.g., optimizing convergence rates).The goal is fourfold: analyze theoretical questions including necessary and sufficient conditions for optimality; build on these theoretical foundations to develop numerical algorithms that are able to find minimizers and verify that they satisfy optimality conditions; implement the algorithms in software that can be used by the general scientific community; and apply the results to the solution of important interesting problems that arise in practice.