Computation and Theory in Decentralized Optimization

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

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.