Scholarlink

<p>We consider polynomial optimization problems (POP) on a semialgebraic set contained in the nonnegative orthant (every POP on a compact set can be put in this format by a simple translation of the origin). Such a POP can be converted to an equivalent POP by squaring each variable. Using even symmetry and the concept of <i>factor width</i>, we propose a hierarchy of semidefinite relaxations based on the extension of Pólya’s Positivstellensatz by Dickinson–Povh. As its distinguishing and crucial feature, the maximal matrix size of each resulting semidefinite relaxation can be chosen <i>arbitrarily</i> and in addition, we prove that the sequence of values returned by the new hierarchy converges to the optimal value of the original POP at the rate <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\mathcal {O}(\varepsilon ^{-{\mathfrak {c}}})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msup> <mi>ε</mi> <mrow> <mo>-</mo> <mi mathvariant="fraktur">c</mi> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> if the semialgebraic set has nonempty interior. When applied to (i) robustness certification of multi-layer neural networks and (ii) computation of positive maximal singular values, our method based on Pólya’s Positivstellensatz provides better bounds and runs several hundred times faster than the standard Moment-SOS hierarchy .</p>

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

Tractable hierarchies of convex relaxations for polynomial optimization on the nonnegative orthant

  • 期刊论文

  • 发表日期：

    2026年3月28日

查看全文
  • Ngoc Hoang Anh Mai,
  • Victor Magron,
  • Jean-Bernard Lasserre,
  • Kim-Chuan Toh

摘要

We consider polynomial optimization problems (POP) on a semialgebraic set contained in the nonnegative orthant (every POP on a compact set can be put in this format by a simple translation of the origin). Such a POP can be converted to an equivalent POP by squaring each variable. Using even symmetry and the concept of factor width, we propose a hierarchy of semidefinite relaxations based on the extension of Pólya’s Positivstellensatz by Dickinson–Povh. As its distinguishing and crucial feature, the maximal matrix size of each resulting semidefinite relaxation can be chosen arbitrarily and in addition, we prove that the sequence of values returned by the new hierarchy converges to the optimal value of the original POP at the rate \(\mathcal {O}(\varepsilon ^{-{\mathfrak {c}}})\) O ( ε - c ) if the semialgebraic set has nonempty interior. When applied to (i) robustness certification of multi-layer neural networks and (ii) computation of positive maximal singular values, our method based on Pólya’s Positivstellensatz provides better bounds and runs several hundred times faster than the standard Moment-SOS hierarchy .