Exploiting Natural Structure of Functions in Optimization

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

Mifflin0707205 This project is concerned with solution of difficultoptimization problems. Solving such problems efficientlyinvolves exploiting at least one of two types of naturallyoccurring structure, one implicit and the other explicit. Thesestructures are related by the result that problems withexplicitly known separable structure can be transformed viadecomposition techniques (involving independent subproblemoptimization) to equivalent nonsmooth problems with implicitVU-shape structure. For many objectives with the latterstructure the investigator and his colleague undertalesignificant further development of a bundle-based method thatemploys a V-model of the objective and a U-model of an associatedLagrangian. This rapidly convergent algorithm takes advantage ofpast research that defined a structure that is special enough togive "primal-dual tracks" to minimizers and general enough toinclude many applications. The new work involves numericaltesting on practical problems where the cutting-plane nature ofsubgradient bundling along with U-Hessian estimation allows ouralgorithm to follow a primal-dual track without having to know itexplicitly. A significant component of the work is to extend themethod to run on nonconvex functions and have provableconvergence to stationary points. The computational methods developed here are significantbecause they can be applied in many practical situationsincluding some having broad societal impact. A new applicationinvolves a complicated objective that is used in manyapplications such as economic and geophysical modeling,computer-aided design, and image analysis. Nonsmoothoptimization developments also make feasible the application ofdecomposition techniques to large or complicated models such asthose occurring in operations management, telecommunication andtraffic assignment, manufacturing, civil infrastructure design,structural engineering, finance, and strategic planning. Suchmodels illustrate the need to make trade-off decisions whenconsidering conflicting criteria such as simultaneously havinghigh reliability and low cost. Such an area of application is inpower system planning subject to environmental protectionconstraints. These problems naturally decompose into higherlevel problems of deciding which types of power generation plantsto build and lower level ones of deciding how to best operate thevarious units to meet daily energy demand. Additionally, thisproject fits in well with ongoing efforts in high-performancecomputing, because future decomposition applications will utilizeparallel processing or networks of computers to solve very largeor complex decision-making problems.