Scholarlink

<p>The ability to compute tight convex and concave relaxations of the parametric solutions of ordinary differential equations (i.e., <i>state relaxations</i>) is essential for efficiently solving global dynamic optimization (GDO) problems using spatial branch-and-bound (B&amp;B). The use of cutting planes derived through various techniques is often critical for obtaining tight relaxations for conventional nonlinear programs (NLPs), but has not previously been proposed for GDO (without prior approximation as an NLP). This paper considers the use of <i>dynamic cuts</i> to tighten state relaxations. We present new theoretical results that enable the use of refinements based on dynamic cuts within an existing state-of-the-art state relaxation method, resulting in substantially tighter relaxations. We then develop a specific numerical implementation of this theory for the case of affine cuts. Numerical experiments on two examples show that using dynamic cuts can lead to much tighter relaxations with a moderate increase in computational cost. The results show good potential for the improved accuracy to outweigh the increased cost when implemented in B&amp;B solvers for GDO. Such an implementation, however, requires further work to develop a method for evaluating subgradients of the proposed relaxations, which is not addressed herein.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Tightening state relaxations for global dynamic optimization using dynamic cuts

  • 期刊论文

  • 发表日期：

    2025年1月29日

查看全文
  • Jason Ye,
  • Joseph K. Scott

摘要

The ability to compute tight convex and concave relaxations of the parametric solutions of ordinary differential equations (i.e., state relaxations) is essential for efficiently solving global dynamic optimization (GDO) problems using spatial branch-and-bound (B&B). The use of cutting planes derived through various techniques is often critical for obtaining tight relaxations for conventional nonlinear programs (NLPs), but has not previously been proposed for GDO (without prior approximation as an NLP). This paper considers the use of dynamic cuts to tighten state relaxations. We present new theoretical results that enable the use of refinements based on dynamic cuts within an existing state-of-the-art state relaxation method, resulting in substantially tighter relaxations. We then develop a specific numerical implementation of this theory for the case of affine cuts. Numerical experiments on two examples show that using dynamic cuts can lead to much tighter relaxations with a moderate increase in computational cost. The results show good potential for the improved accuracy to outweigh the increased cost when implemented in B&B solvers for GDO. Such an implementation, however, requires further work to develop a method for evaluating subgradients of the proposed relaxations, which is not addressed herein.