Axiomatic Positivstellensaetze for Function Algebras over Ordered Fields
Nayoon Kim, Allen Gehret, Shenyuan Ma, Jakub Marecek
原文摘要
Positivstellensaetze furnish algebraic certificates of positivity, and hence of lower bounds and of global optimality, but the classical ones concern polynomials, whereas many problems of current interest, among them the training of neural networks, involve functions that are neither polynomial nor smooth. We isolate an axiomatic core of the constructive Positivstellensaetze of Fischer. The setting consists of an ordered field expanded by five auxiliary function symbols, subject to a few first-order axioms, together with an algebra of functions on an arbitrary set, subject to closure axioms. In this setting we prove a strict and a weak Positivstellensatz in which the witnesses are obtained by substituting the data into fixed terms that depend only on the number of constraints. The framework recovers Fischer's theorems for definable $C^r$-functions, and yields new instances: algebras of definable functions with arbitrary auxiliary functions, such as the binary step function; algebras of continuous functions, for which we give simple sufficient criteria and auxiliary functions derived from common activation functions; and algebras of continuous functions with values in an ordered field that is not closed under square roots, such as $\mathbb{Q}$. We derive certificates of lower bounds and of global optimality, and show that their expanded term length is cubic in the number of constraints for the strict certificate and quadratic for the weak one.
cs.AI