Non-Lipschitz Optimization Problems Involving Eigenvalues

纽约大学michael overton涉及特征值的非lipschitz优化问题涉及特征值的优化问题在许多应用中出现。半定规划是具有半定正约束的实对称矩阵空间中的线性优化问题，近年来得到了广泛的关注。这个项目关注的是在更大的方阵空间中的优化问题，不一定是对称的。在所研究的问题中，特征值可能出现在优化目标中，也可能出现在约束中，或者两者兼而有之。特征值作为矩阵函数的依赖关系在特征值的倍数大于1的点上是非利普希茨的。因此，这种优化问题是非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.