Algorithms for Nonlinear Nonconvex Optimization under Uncertainty

不确定性下的非线性非凸优化算法

• 批准号: 1522747
• 负责人: Andreas Waechter
• 金额: $ 21万
• 依托单位: Northwestern University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-15 至 2019-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1522747&HistoricalAwards=false
• 关键词: Algorithms; Nonlinear; Nonconvex; Optimization; under

The investigator will develop computational methods that seek to find optimal decisions when not all information is known exactly. This situation arises when future events cannot be predicted with high accuracy or when quantities can only be estimated from limited data. A similar setting occurs when computer programs are employed to simulate processes. In that case, the computer output can be noisy, due to limited precision of the underlying numerical algorithms or due to randomness inherent in the simulation. An illustrative example is the deployment of solar or wind energy: Electricity demand estimates based on past observations are uncertain, and weather forecast models are started from random perturbations of the initial conditions. Computational optimization algorithms exist that address data uncertainty, but current methods are not able to handle difficult nonlinear relationships in the mathematical optimization model. This research will overcome this limitation on two fronts. The first research project will result in optimization algorithms for problems in which constraints need to be satisfied only with a given probability. These methods will permit a much wider range of these constraints than the present state-of-the-art. The second project will produce methods that optimize computer simulations by explicitly addressing the nature of the output noise. In contrast to existing approaches, these algorithms will not stagnate at spurious solutions induced by the noise. All new methods will be implemented in software and evaluated on real-life problems, and new mathematical theory will be developed that proves the convergence of these methods.In this project, new algorithms for continuous chance-constrained optimization will be developed. In current approaches, the objective and constraint functions are required to be linear or convex, and the nonconvexity induced by the chance-constraints is handled either by conservative convex approximations or by the global solution of discrete formulations via combinatorial branch-and-bound enumeration. The new methods will permit problem statements that involve nonlinear and nonconvex objective functions and include joint chance constraints with nonconvex probabilistic constraints. This is made possible by seeking only local optima, which can be found more easily than global minima but are still highly valuable in practice. As a result, established techniques from nonconvex nonlinear optimization can be built upon and extended. The new sequential quadratic chance-constrained programming framework requires the introduction of new chance-constrained trust-region subproblem solvers and convergence theory for chance-constrained penalty functions which will be developed in this project. The PI will also develop a derivative-free optimization method for objective functions with deterministic noise caused by numerical error in computer simulations. The approach is based on a smoothed objective function obtained via convolution with a Gaussian kernel. The integral in the new objective is approximated by Monte-Carlo sample average approximation. Adaptive multiple importance sampling permits the reuse of the expensive function evaluations computed in all previous iterations.

研究人员将开发计算方法，在并非所有信息都准确已知的情况下寻求最佳决策。 当无法高精度预测未来事件或只能根据有限的数据估计数量时，就会出现这种情况。 当使用计算机程序来模拟过程时，会发生类似的情况。在这种情况下，由于底层数值算法的精度有限或由于模拟固有的随机性，计算机输出可能会有噪声。一个说明性的例子是太阳能或风能的部署：基于过去观测的电力需求估计是不确定的，天气预报模型是从初始条件的随机扰动开始的。存在解决数据不确定性的计算优化算法，但当前的方法无法处理数学优化模型中困难的非线性关系。这项研究将从两个方面克服这一限制。第一个研究项目将针对仅需要满足给定概率的约束的问题产生优化算法。这些方法将允许比目前最先进的技术更广泛的限制。第二个项目将通过明确解决输出噪声的性质来产生优化计算机模拟的方法。与现有方法相比，这些算法不会停滞在噪声引起的虚假解上。 所有新方法都将在软件中实现并针对现实问题进行评估，并且将开发新的数学理论来证明这些方法的收敛性。在该项目中，将开发用于连续机会约束优化的新算法。在当前的方法中，目标函数和约束函数需要是线性的或凸的，并且由机会约束引起的非凸性通过保守的凸近似或通过组合分支定界枚举的离散公式的全局解来处理。 新方法将允许涉及非线性和非凸目标函数的问题陈述，并包括具有非凸概率约束的联合机会约束。这是通过仅寻求局部最优来实现的，局部最优比全局最小值更容易找到，但在实践中仍然具有很高的价值。因此，可以建立和扩展非凸非线性优化的既定技术。新的顺序二次机会约束规划框架需要引入新的机会约束信任域子问题求解器和机会约束罚函数的收敛理论，这些将在本项目中开发。 PI 还将开发一种无导数优化方法，用于具有由计算机模拟中的数值误差引起的确定性噪声的目标函数。该方法基于通过与高斯核卷积获得的平滑目标函数。 新目标中的积分通过蒙特卡罗样本平均近似来近似。自适应多重重要性采样允许重用在所有先前迭代中计算的昂贵函数评估。