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

点击翻译按钮获取中文摘要

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.