Space Decomposition Methods in Nonsmooth Optimization

罗伯特Mifflin摘要DMS-9703952非光滑优化中的空间分解方法摘要拟议的研究涉及开发理论和方法，隐式结合多面体和二次近似，以产生一个快速收敛的算法，用于最小化多变量的非光滑函数。这个想法是使用束方法来确定所谓的VU-空间分解，使得在V-空间上，束的切割平面方面快速工作，并且在U-空间上可以采用U-拉格朗日的Hessian的拟牛顿近似。这种方法可以通过分离变量或约束来求解大型或复杂的优化模型。例如，通过分离变量，可以解决水压控制问题，即找到流量和泵压间隙的值，以使泵送成本最小化，同时将管网中所有点处的水压保持在允许范围内。如果流量是固定的，那么寻找压力间隙的最佳值的子问题是一个容易解决的线性最小化问题。采用这种方法，找到最佳值的流量变量的外部问题是一个非光滑的问题，其解决方案可以有效地找到通过技术开发。提出的计算方法的发展是有意义的，因为它们可以应用于许多实际的决策情况。这些包括大型或复杂模型的分解，例如在稀缺资源分配，交通分配，制造，结构工程，物流和战略规划中发生的模型。第一段中的管网问题是民用基础设施设计中的一个重要实例。它说明了需要作出权衡决定时，考虑冲突的设计标准，如同时具有高可靠性和低成本。另一个应用领域是受环境保护约束的电力系统规划。随着能源供应部门放松管制的生效，这些决策模型的重要性将增加。这些问题自然地分解成决定建造何种类型和大小的发电厂的较高水平的问题和决定如何最好地操作各种单元以满足日常能量需求的较低水平的问题。此外，这项研究非常适合高性能计算的持续努力，因为它的方法将利用并行处理来解决比目前可能解决的更大或更复杂的决策问题。

Robt. Mifflin Abstract for DMS-9703952 Abstract for Space Decomposition Methods in Nonsmooth Optimization The proposed research concerns developing theory and methods for implicitly combining polyhedral and quadratic approximation to produce a rapidly convergent algorithm for minimizing a nonsmooth function of many variables. The idea is to use a bundle method to determine a so-called VU-space decomposition such that on V-space the cutting-plane aspect of bundling works fast and on U-space a quasi-Newton approximation of a Hessian of a U-Lagrangian can be employed. Such methods can be used to solve large or complicated optimization models via separation of variables or constraints. For example, a water pressure control problem of finding values for flow rates and pump pressure gaps to minimize pumping cost subject to maintaining water pressures in allowable ranges at all points in a pipe network can be solved via separation of the variables. If the flow rates are fixed then the subproblem of finding optimal values for the pressure gaps is an easy-to- solve linear minimization problem. With this approach the outer problem of finding optimal values for the flow variables is a nonsmooth problem whose solution can be found efficiently via the techniques to be developed. The computational methods proposed for development are significant because they can be applied in many practical decision-making situations. These include decomposition of large or complicated models such as those occurring in allocation of scarce resources, traffic assignment, manufacturing, structural engineering, logistics and strategic planning. The pipe network problem in the first paragraph is an important example occurring in civil infrastructure design. It illustrates the need to make trade-off decisions when considering conflicting design criteria such as simultaneously having high reliability and low cost. Another area of applica tion is in power system planning subject to environmental protection constraints. These decision models will increase in importance as deregulation of the energy supply sector takes effect. These problems naturally decompose into higher level problems of deciding which types and sizes of power generation plants to build and lower level problems of deciding how best to operate the various units to meet daily energy demand. Additionally, this research fits in well with ongoing efforts in high-performance computing, because its methods will utilize parallel processing to solve larger or more complex decision- making problems than are currently possible to solve.