Space Decomposition Methods in Nonsmooth Optimization

非光滑优化中的空间分解方法

• 批准号: 0071459
• 负责人: Robert Mifflin
• 金额: --
• 依托单位: Washington State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-07-15 至 2004-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0071459&HistoricalAwards=false
• 关键词: Space; Decomposition; Methods; Nonsmooth; Optimization

Abstract for Space Decomposition Methods in Nonsmooth Optimization DMS 0071459 The proposed research concerns developing theory and methods for 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 theoretical research is concerned with properly defining a class of functions which is special enough for the members to have U-Hessians and general enough to include functions from many applications.The computational methods proposed for development are significant because they can be applied in many practical decision-making situations. These include the determination of values of parameters for fitting models to data such as in topographic or geophysical modeling. They also include application of decomposition techniques to 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 application 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 on-going efforts in high-performance computing, because its methods will utilize parallel processing for solving very large and/or very complex decision-makingproblems.

摘要对于非光滑优化决策支持系统0071459中的空间分解方法，所提出的研究涉及发展多面体和二次逼近相结合的理论和方法，以产生一个快速收敛的多变量非光滑函数的最小化算法。其思想是使用集束方法来确定所谓的VU-空间分解，以便在V-空间上，捆绑的割平面方面快速工作，并且在U-空间上可以采用U-拉格朗日的海森的拟牛顿近似。这种方法可以通过分离变量或约束来求解大型或复杂的优化模型。例如，在将管网中所有点的水压保持在允许范围内的情况下，找到流量和泵压差的值以最小化抽水成本的水压控制问题可以通过分离变量来解决。如果流量是固定的，那么寻找压差的最佳值的子问题就是一个容易解决的线性最小化问题。在这种方法下，寻找流动变量最优值的外部问题是一个非光滑问题，它的解可以通过待开发的技术有效地找到。理论研究关注于正确地定义一类函数，这类函数足够特殊，足以使成员具有U-Hessians，并且足够广泛，足以包含来自许多应用的函数。所提出的计算方法具有重要意义，因为它们可以应用于许多实际决策情况。这包括确定使模型与数据相适应的参数值，例如在地形或地球物理模拟中。它们还包括将分解技术应用于大型或复杂模型，例如在稀缺资源分配、交通分配、制造、结构工程、物流和战略规划中出现的模型。第一段中的管网问题是土木工程基础设施设计中的一个重要例子。它说明了在考虑冲突的设计标准时需要做出权衡的决定，例如同时具有高可靠性和低成本。另一个应用领域是受环境保护约束的电力系统规划。随着能源供应部门放松管制的生效，这些决策模型将变得更加重要。这些问题自然分解为较高层次的问题，即决定建设哪些类型和规模的发电厂，以及较低层次的问题，即决定如何最好地运行各种机组，以满足日常能源需求。此外，这项研究与高性能计算中正在进行的努力非常吻合，因为它的方法将利用并行处理来解决非常大和/或非常复杂的决策问题。