Certificates of optimality explained for broad types of mathematical problems
When Can One Obtain Certificates of Optimality Using Positivstellensaetze?
Artificial Intelligence
Summary
Some math problems involve finding the best solution given certain rules, but those problems don’t always use simple polynomial equations. The researchers studied a way to prove when a solution is the best by focusing on core mathematical principles behind Positivstellensätze, which are tools that help show when certain functions are positive. They created a general framework that separates how the problem is built from how certificates of optimality are constructed. Their work applies to many types of functions, even in tricky cases where usual assumptions don’t hold, and helps verify solutions' quality without relying on traditional polynomial tools.
Positivstellensätzecertificates of optimalityfunction algebrasordered fieldsnon-polynomial functionscontinuous functionsdefinable functionsglobal optimalityclosure axiomsmathematical certificates
Authors
Nayoon Kim, Allen Gehret, Shenyuan Ma, Jakub Marecek
Abstract
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ä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.