Scholarlink

<p>When computing bounds, spatial branch-and-bound algorithms often linearly outer approximate convex relaxations for non-convex expressions in order to capitalize on the efficiency and robustness of linear programming solvers. Considering that linear outer approximations sacrifice accuracy when approximating highly nonlinear functions and recognizing the recent advancements in the efficiency and robustness of available methods to solve optimization problems with quadratic objectives and constraints, we contemplate here the construction of quadratic outer approximations of twice-differentiable convex functions for use in deterministic global optimization. To this end, we present a novel cutting-plane algorithm that determines the tightest scaling parameter, <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\alpha \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>α</mi> </math></EquationSource> </InlineEquation>, in the second-order Taylor series approximation quadratic underestimator proposed by&#xa0;Su et al. [<CitationRef CitationID="CR25">25</CitationRef>]. We use a representative set of convex functions extracted from optimization benchmark libraries to showcase–qualitatively and quantitatively–the tightness of the constructed quadratic underestimators and to demonstrate the overall computational efficiency of our algorithm. Furthermore, we extend our construction procedure to generate even tighter quadratic underestimators by allowing overestimation in infeasible polyhedral regions of optimization problems, as informed by the latter’s linear constraints.</p>

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

Constructing Tight Quadratic Relaxations for Global Optimization: I. Outer-Approximating Twice-Differentiable Convex Functions

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年12月8日

查看全文
  • William R. Strahl,
  • Arvind U. Raghunathan,
  • Nikolaos V. Sahinidis,
  • Chrysanthos E. Gounaris

摘要

When computing bounds, spatial branch-and-bound algorithms often linearly outer approximate convex relaxations for non-convex expressions in order to capitalize on the efficiency and robustness of linear programming solvers. Considering that linear outer approximations sacrifice accuracy when approximating highly nonlinear functions and recognizing the recent advancements in the efficiency and robustness of available methods to solve optimization problems with quadratic objectives and constraints, we contemplate here the construction of quadratic outer approximations of twice-differentiable convex functions for use in deterministic global optimization. To this end, we present a novel cutting-plane algorithm that determines the tightest scaling parameter, \(\alpha \) α , in the second-order Taylor series approximation quadratic underestimator proposed by Su et al. [25]. We use a representative set of convex functions extracted from optimization benchmark libraries to showcase–qualitatively and quantitatively–the tightness of the constructed quadratic underestimators and to demonstrate the overall computational efficiency of our algorithm. Furthermore, we extend our construction procedure to generate even tighter quadratic underestimators by allowing overestimation in infeasible polyhedral regions of optimization problems, as informed by the latter’s linear constraints.