Scholarlink

<p>This note demonstrates that, for all compact convex sets, high-precision linear minimization can be performed via a single evaluation of the projection and a scalar-vector multiplication. In consequence, if <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\varepsilon \)</EquationSource> </InlineEquation>-approximate linear minimization takes at least <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(L(\varepsilon )\)</EquationSource> </InlineEquation> real vector-arithmetic operations and projection requires <i>P</i> operations, then <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\mathcal {O}(P)\ge \mathcal {O}(L(\varepsilon ))\)</EquationSource> </InlineEquation> is guaranteed. This concept is expounded with examples, an explicit error bound, and an exact linear minimization result for polyhedral sets.</p>

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

High-precision linear minimization is no slower than projection

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年1月5日

查看全文
  • Zev Woodstock

摘要

This note demonstrates that, for all compact convex sets, high-precision linear minimization can be performed via a single evaluation of the projection and a scalar-vector multiplication. In consequence, if \(\varepsilon \) -approximate linear minimization takes at least \(L(\varepsilon )\) real vector-arithmetic operations and projection requires P operations, then \(\mathcal {O}(P)\ge \mathcal {O}(L(\varepsilon ))\) is guaranteed. This concept is expounded with examples, an explicit error bound, and an exact linear minimization result for polyhedral sets.