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

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

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.