提出新方法，为非多项式优化问题生成最优性证明。
When Can One Obtain Certificates of Optimality Using Positivstellensaetze?
- 用抽象代数框架统一处理非多项式目标与约束
- 在非闭合平方根的有序域上获得全局最优下界
- 适合数学优化与形式验证方向的研究者
我们研究学习问题中目标函数与约束条件非多项式情形下的正性与最优性证书。通过提取Fischer构造性严格与弱Positivstellensatz的公理核心，将定理推广至有序域上的抽象函数代数。该框架区分了两类角色：目标与约束可由广义连续或可定义运算构建，而用于构造证书的辅助基元需满足显式的标量与封闭性公理。我们在连续与可定义函数代数上给出实例，包括不闭合于平方根的有序域，推导出下界与全局最优性证书，并分析了展开项长度与共享计算图复杂度。
原文摘要 · Abstract (English)
We study certificates of positivity and optimality for learning problems whose objectives and constraints need not be polynomial. We isolate an axiomatic core of Fischer's constructive strict and weak Positivstellens\"{a}tze and prove the resulting theorems for abstract function algebras over ordered fields. The framework separates two roles that can otherwise be conflated: objective and constraint functions may be built from broad classes of continuous or definable operations, while the auxiliary primitives used to construct a certificate satisfy explicit scalar and closure axioms. We give instances over continuous and definable function algebras, including ordered fields not closed under square roots, derive lower-bound and global-optimality certificates, and analyze both expanded term length and shared computation-graph complexity.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。