Exploiting Natural Structure of Functions in Optimization

这个项目是解决困难的优化问题。有效地解决这类问题需要利用两种自然发生的结构中的至少一种，一种是隐式的，另一种是显式的。这些结构的相关结果是，具有显式已知可分离结构的问题可以通过复合技术（涉及独立子问题优化）转化为具有隐式u形结构的等效非光滑问题。对于许多具有后一种结构的目标，研究者和他的同事正在进一步开发一种基于捆绑的方法，该方法使用目标的v模型和相关拉格朗日的u模型。这种快速收敛的算法利用了过去的研究，该研究定义了一个结构，该结构足够特殊，可以为最小化者提供“原始对偶轨道”，并且足够通用，可以包含许多应用。新的工作涉及对实际问题的数值测试，其中亚梯度捆绑的切割平面性质以及U-Hessian估计允许我们的算法遵循原始对偶轨道，而不必明确知道它。该工作的一个重要组成部分是将该方法扩展到非凸函数上并具有可证明的收敛性。这里开发的计算方法很重要，因为它们可以应用于许多实际情况，包括一些具有广泛社会影响的情况。一个新的应用涉及一个复杂的目标，在许多应用中使用，如经济和地球物理建模，计算机辅助设计和图像分析。非平滑优化的发展也使得分解技术在大型或复杂模型中的应用成为可能，例如在运营管理、电信和交通分配、制造、土木基础设施设计、结构工程、金融和战略规划等领域。这些模型说明，在考虑诸如同时具有高可靠性和低成本等相互冲突的标准时，需要做出权衡决策。这样的应用领域是受环境保护约束的电力系统规划。这些问题自然分解为决定建造哪种类型的发电厂的高级问题和决定如何最好地运行各种单元以满足日常能源需求的低级问题。此外，这个项目非常适合高性能计算领域的持续努力，因为未来的分解应用将利用并行处理或计算机网络来解决非常大的复杂决策问题。

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.