<p>We present a new relaxation based on separable edge-concave underestimator (SEC) for general <i>n</i>-dimensional signomial problems. While the vertex polyhedral convex envelope of an edge-concave underestimator is constructed with multiple linear facets requiring function evaluations at all <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(2^n\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mi>n</mi> </msup> </math></EquationSource> </InlineEquation> domain vertices, the SEC underestimator uses a single linear hyperplane constructed at only <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\((n+1)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> linearly independent vertices. This is possible because of the existence of a single <i>n</i>-dimensional hyperplane passing through all <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(2^n\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mi>n</mi> </msup> </math></EquationSource> </InlineEquation> vertices of any separable function defined over a box. We provide an explicit form of the linear hyperplane representing the convex envelope of the SEC underestimator. Having an explicit form of the hyperplane leads to an efficient linear programming (LP) relaxation of the original problem with high-dimensional signomials. We test the efficacy of the relaxation for both low- and high-dimensional signomials through a set of test problems.</p>

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

Separable Edge-Concave Underestimator for High-Dimensional Signomials in Nonnegative Orthant

  • Bimol Nath Roy,
  • M. M. Faruque Hasan

摘要

We present a new relaxation based on separable edge-concave underestimator (SEC) for general n-dimensional signomial problems. While the vertex polyhedral convex envelope of an edge-concave underestimator is constructed with multiple linear facets requiring function evaluations at all \(2^n\) 2 n domain vertices, the SEC underestimator uses a single linear hyperplane constructed at only \((n+1)\) ( n + 1 ) linearly independent vertices. This is possible because of the existence of a single n-dimensional hyperplane passing through all \(2^n\) 2 n vertices of any separable function defined over a box. We provide an explicit form of the linear hyperplane representing the convex envelope of the SEC underestimator. Having an explicit form of the hyperplane leads to an efficient linear programming (LP) relaxation of the original problem with high-dimensional signomials. We test the efficacy of the relaxation for both low- and high-dimensional signomials through a set of test problems.