Structured Non-Smooth Optimization: Theory and Methods

结构化非光滑优化：理论与方法

• 批准号: 1908890
• 负责人: James Burke
• 金额: $ 28.04万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-09-01 至 2024-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1908890&HistoricalAwards=false
• 关键词: Structured; Non; Smooth; Optimization; Theory

The investigator develops theory and algorithms to solve optimization problems arising in present-day business, science, and engineering applications, often specifically related to data analysis problems where the aim is to better inform decisions about alternative choices. The project's topics arise in model selection techniques (used in applications such as the identification of social networks and the selection of covariates that best inform health outcomes), in imaging applications, and in the dynamics, tracking, and control of waste streams and of vehicles. Commonly in applications the objective function (the function to be optimized) may be nonsmooth, nonconvex, or high-dimensional; each of these features presents major challenges for classical optimization methods. A key aspect of the project is the use of nonsmooth techniques that allow for the introduction or discovery of special properties in the desired solution, such as sparsity, stability, and robustness. The work falls into four main areas. The first concerns study of the BFGS method and matrix secant methods for nonsmooth convex optimization (why BFGS works as well as it does is unclear), and the design of algorithms that automatically discover a so-called UV-decomposition of the objective function. Here the U is the smooth part and the V is the nonsmooth part. Such decompositions are essential for rapid solution identification as they allow one to follow a smooth valley (U) with steep sides (V) toward the optimal solution. The second examines the rate at which a solution is obtained as well as its accuracy, depending on functional and parameter inputs. The third examines the determination of optimal stability and control of linear dynamical systems occurring, for example, in orbital dynamics or drug metabolism. The goal here is to help recognize optimal solutions. Indeed, in many cases methods for identifying optimality remain unknown. The final task concerns the development of novel smoothing methodologies for optimization problems over matrix spaces, such as those occurring in social network discovery. These problems are typically very high-dimensional, and nonsmoothness of the objective function is the key to discovering hidden structures within the data. Here the goal is to develop smooth approximations whose solution can be rapidly computed and whose proximity to the true solution is precisely controlled. Graduate students participate in the research.More technically, the areas of study are (i) BFGS and matrix secant methods for nonsmooth convex optimization, (ii) local and global convergence theory for convex-composite optimization, (iii) variational analysis of spectral functions for non-symmetric matrices, and (iv) the generalized matrix fractional function and smoothing on matrix spaces. The study of BFGS methods focuses on the relationship between the iterates and smooth, convex, uniform approximations. The study of convex composite problems analyses the behavior of algorithms using Robinson's method of generalized equation. The study of nonsymmetric matrices focuses on extending variational techniques to the difficult nonderogatory case. The final area considers the embedding of a wide range of matrix optimization problems in a smooth setting by the use of infimal projection with the generalized matrix fractional function introduced by the investigator and collaborators. Graduate students participate in the research.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.

研究者开发了理论和算法，以解决当今业务，科学和工程应用中引起的优化问题，这些问题通常与数据分析问题特别相关，目的是更好地告知有关替代选择的决策。 该项目的主题是在模型选择技术中出现的（用于识别社交网络的识别以及最能为健康结果提供依据的协变量），成像应用以及对废物流和车辆的动态，跟踪和控制。 通常，在应用中，目标函数（要优化的函数）可以是非平滑，非凸或高维的。这些功能中的每一个都面临经典优化方法的主要挑战。 该项目的一个关键方面是使用非平​​滑技术，该技术允许在所需解决方案中引入或发现特殊属性，例如稀疏性，稳定性和鲁棒性。 工作分为四个主要领域。 对BFGS方法和矩阵SEV的第一个关注研究（用于非平滑凸优化）（为什么BFGS的运作以及它的作用既不清楚），并且设计算法的设计自动发现了目标功能的所谓UV分解。 在这里，U是光滑的部分，V是非平滑部分。 这样的分解对于快速溶液识别至关重要，因为它们允许人们沿着陡峭的侧面（v）沿朝最佳溶液的光滑山谷（u）沿着。 第二个检查了获得溶液的速率以及其精度，具体取决于功能和参数输入。 第三个检查了在轨道动力学或药物代谢中的最佳稳定性和控制线性动力学系统的确定。 这里的目标是帮助识别最佳解决方案。 实际上，在许多情况下，识别最佳性的方法仍然未知。 最终任务涉及开发新颖的平滑方法，以优化矩阵空间，例如在社交网络发现中发生的问题。 这些问题通常是非常高的维度，目标函数的非平滑度是发现数据中隐藏结构的关键。 在这里，目标是开发可以快速计算的解决方案，并且与真实解决方案的接近度得到精确控制。 Graduate students participate in the research.More technically, the areas of study are (i) BFGS and matrix secant methods for nonsmooth convex optimization, (ii) local and global convergence theory for convex-composite optimization, (iii) variational analysis of spectral functions for non-symmetric matrices, and (iv) the generalized matrix fractional function and smoothing on matrix spaces. BFGS方法的研究集中于迭代和光滑，凸，均匀近似值之间的关系。 凸复合问题的研究使用鲁滨逊的广义方程方法分析了算法的行为。 对非对称矩阵的研究重点是将变异技术扩展到困难的非构造情况。 最终区域考虑了通过使用虚拟投影与研究者和协作者引入的广义矩阵分数函数的使用，将各种矩阵优化问题嵌入在平滑环境中。 研究生参加了研究。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛影响的评论标准来评估值得支持的。

项目成果

Inexact Sequential Quadratic Optimization with Penalty Parameter Updates within the QP Solver

QP 求解器内带有惩罚参数更新的不精确序列二次优化

• DOI: 10.1137/18m1176488
• 发表时间: 2020
• 期刊: SIAM Journal on Optimization
• 影响因子: 3.1
• 作者: Burke, James V.;Curtis, Frank E.;Wang, Hao;Wang, Jiashan
• 通讯作者: Wang, Jiashan

Convergence of the Gradient Sampling Algorithm on Directionally Lipschitz Functions

定向Lipschitz函数梯度采样算法的收敛性

• DOI: 10.1007/s11228-021-00610-3
• 发表时间: 2022
• 期刊: Setvalued and variational analysis
• 作者: J. V. Burke;Q. Lin
• 通讯作者: Q. Lin

On the Global Minimizers of Real Robust Phase Retrieval With Sparse Noise

稀疏噪声实鲁棒相位检索的全局极小化

• DOI: 10.1109/tit.2020.3040959
• 发表时间: 2021
• 期刊: IEEE Transactions on Information Theory
• 影响因子: 2.5
• 作者: Aravkin, Aleksandr;Burke, James V.;He, Daiwei
• 通讯作者: He, Daiwei

Algorithms for Block Tridiagonal Systems: Stability Results for Generalized Kalman Smoothing

分块三对角系统的算法：广义卡尔曼平滑的稳定性结果

• DOI: 10.1016/j.ifacol.2021.08.463
• 发表时间: 2021
• 期刊: IFAC-PapersOnLine
• 作者: Aravkin, Aleksandr Y.;Burke, James V.;Bell, Bradley M.;Pillonetto, Gianluigi
• 通讯作者: Pillonetto, Gianluigi

A Relaxation Approach to Feature Selection for Linear Mixed Effects Models

• DOI: 10.1080/10618600.2023.2231496
• 发表时间: 2022-05
• 期刊: Journal of Computational and Graphical Statistics
• 影响因子: 2.4
• 作者: A. Sholokhov;J. Burke;D. Santomauro;P. Zheng;A. Aravkin