CCF AF:EAGER:ASSESSING PRACTICALITY OF A NEW FRAMEWORK FOR SOLVING CONIC OPTIMIZATION PROBLEMS BY FIRST-ORDER METHODS

CCF AF：Eager：评估通过一阶方法解决圆锥优化问题的新框架的实用性

• 批准号: 1552518
• 负责人: James Renegar
• 金额: $ 10万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2018-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1552518&HistoricalAwards=false
• 关键词: CCF; AF; EAGER; ASSESSING; PRACTICALITY

A key component of Analytics, the scientific process of transforming data into insight for better decisions, is Optimization, which produces the best solution satisfying given constraints -- the solution that maximizes a chosen "objective" function. The objective and constraints together form "an optimization model." The difficulty of solving a model depends on the types of objective and constraint functions, and on the number of variables in the functions. Since huge, complicated, real-world models can have many variables, the amount of computer memory needed becomes the bottleneck for solutions by classical algorithms. Modern algorithms avoid this bottleneck by calculating fewer structures that have to be stored in memory. For example, some modern algorithms evaluate only first derivatives of functions, whereas older algorithms also stored second derivatives in memory. These modern algorithms are known as "first-order methods" (meaning, roughly, "algorithms using only first derivatives"). First-order methods can handle complicated objective functions, but it has been unknown how to handle complicated constraint functions. The focus of the project is a new framework that allows many optimization models with complicated constraints to be easily transformed into equivalent models with only simple constraints, so that existing first-order methods can be applied. The goal of the project is to thoroughly test whether, using the new framework, important huge models that were previously unsolvable can now be solved routinely. If so, entities relying on Analytics could benefit, in that their huge models involving complicated constraints might actually become solvable by existing first-order methods. The new framework transforms any convex, conic optimization problem into an equivalent optimization problem whose only constraints are linear equations, one more equation than for the original problem. Virtually any subgradient method can be applied to the equivalent problem. Moreover, for a wide class of conic optimization problems (hyperbolic programs), the objective function for the equivalent problem can be "smoothed," thus allowing for application of accelerated gradient methods. The goal of the project is to thoroughly test practicality of the new approach in applying first-order methods to solve large, general, conic optimization problems. PhD students will test this framework as part of their careers formation, in consultation with optimization experts from both academia and industry. The result should be better analytics in business, government, healthcare and education for making decisions based on data.

分析的一个关键组成部分，即将数据转化为更好决策的科学过程，是优化，它产生满足给定约束的最佳解决方案-最大化所选“目标”函数的解决方案。 目标和约束一起形成“优化模型”。“求解模型的难度取决于目标函数和约束函数的类型，以及函数中变量的数量。 由于庞大、复杂、真实世界的模型可能包含许多变量，所需的计算机内存量成为经典算法求解的瓶颈。 现代算法通过计算必须存储在内存中的更少的结构来避免这个瓶颈。例如，一些现代算法仅计算函数的一阶导数，而旧算法还将二阶导数存储在内存中。 这些现代算法被称为“一阶方法”（大致意思是“仅使用一阶导数的算法”）。 一阶方法可以处理复杂的目标函数，但如何处理复杂的约束函数一直是未知的。 该项目的重点是一个新的框架，使许多具有复杂约束的优化模型可以轻松地转换为仅具有简单约束的等效模型，从而可以应用现有的一阶方法。该项目的目标是彻底测试使用新框架是否可以常规地解决以前无法解决的重要大型模型。 如果是这样的话，依赖分析的实体可能会受益，因为他们涉及复杂约束的庞大模型实际上可能可以通过现有的一阶方法来解决。新的框架将任何凸，圆锥优化问题转化为一个等价的优化问题，其唯一的约束是线性方程组，一个方程比原来的问题。 实际上任何次梯度法都可以应用于等价问题。此外，对于一类广泛的锥优化问题（双曲规划），等价问题的目标函数可以被“平滑”，从而允许应用加速梯度法。 该项目的目标是彻底测试新方法在应用一阶方法解决大型，一般，圆锥优化问题中的实用性。博士生将测试这个框架作为他们职业生涯形成的一部分，与来自学术界和工业界的优化专家进行磋商。 其结果应该是更好地分析商业，政府，医疗保健和教育，以便根据数据做出决策。