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还将开发一种无导数优化方法，用于计算机模拟中数值误差引起的确定性噪声的目标函数。该方法是基于一个平滑的目标函数通过卷积高斯核。 新目标中的积分采用蒙特-卡罗样本平均近似。自适应多重要性采样允许重用在所有先前迭代中计算的昂贵函数评估。