Computation and Theory in Decentralized Optimization

这是一个研究开发更好方法的建议， 解决目前特别困难的优化问题，因为 因为它们包含非平滑数据，或者因为 它们包含随机元素。 包括直接开发 算法的测试和理论基础的完善， 支持未来的算法开发。 以前的NSF支持使得开发一种新的，非常 结构凸优化问题的快速分解方法 （基于分解的算法）。 该方法在理论上 合理，并已在大型结构化线性规划上进行了测试 问题与优秀的结果。 这里提出的下一步是在可分解上测试该算法 非线性（凸）规划问题，看看它的计算 线性情况下的有效性延续到非线性问题。 它计划测试特殊结构的问题，如非线性 带边约束的网络，以及块可分离问题 没有任何特定的网络结构。 与此同时，计划开展研究， 加速所使用的基础（束）算法的收敛 在分解方法中。 这种加速不仅会扩大 速度和能力的方法刚刚描述，但也将 使许多其他类型的非光滑凸规划成为可能 更快更容易地解决问题。 制订这种 PI将研究加速方法的有效近似， 非光滑优化问题，主要是那些有一些凸 结构，以及在算法开发中使用这种近似。

This is a proposal for research in developing better methods for solving optimization problems that present special difficulties because of their large size, because they contain nonsmooth data, or because they contain stochastic elements. It includes both direct development and testing of algorithms, and improvement of the theory base to support future algorithmic development. Previous NSF support has made possible the development of a new, very fast, decomposition method for structured convex optimization problems (bundle-based decomposition). The method has been theoretically justified, and has been tested on large structured linear programming problems with excellent results. The next step, proposed here, is to test the algorithm on decomposable nonlinear (convex) programming problems to see if its computational effectiveness in the linear case carries over to nonlinear problems. It is planned to test specially structured problems, such as nonlinear networks with side constraints, as well as block-separable problems without any particular network structure. At the same time, it is planned to carry out research aimed at accelerating the convergence of the underlying (bundle) algorithm used in the decomposition method. Such acceleration would not only extend the speed and capability of the method just described, but would also make it possible for many other kinds of nonsmooth convex programming problems to be solved more quickly and easily. To devise such acceleration methods the PI will study the efficient approximation of nonsmooth optimization problems, primarily those having some convex structure, and the use of such approximations in algorithm development.