Non-Lipschitz Optimization Problems Involving Eigenvalues

提案#0098145新约克大学Michael Overton涉及特征值的非Lipschitz优化问题涉及特征值的优化问题在许多应用中出现。 半定规划是真实的对称矩阵空间中具有半正定约束的线性优化问题，近年来引起了人们的广泛关注。 这个项目的重点是在更大的方阵空间中的优化问题，不一定是对称的。 在所研究的问题中，特征值可能出现在优化目标中，约束中，或两者兼而有之。 在特征值多重性大于1的点处，作为矩阵函数的特征值的依赖性是非Lipschitz的。 因此，这样的优化问题是非Lipschitz的。它们出现在从控制理论（例如，稳定性约束）到马尔可夫链（例如，目标有四个：分析理论问题，包括最优性的必要和充分条件;在这些理论基础上开发能够找到最小值并验证它们满足最优性条件的数值算法;在一般科学界可以使用的软件中实现算法;并将结果应用于解决实践中出现的重要有趣问题。

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.