  The discovery of scientific formulae that parsimoniously explain natural
phenomena and align with existing background theory is a key goal in science.
Historically, scientists have derived natural laws by manipulating equations
based on existing knowledge, forming new equations, and verifying them
experimentally. In recent years, data-driven scientific discovery has emerged
as a viable competitor in settings with large amounts of experimental data.
Unfortunately, data-driven methods often fail to discover valid laws when data
is noisy or scarce. Accordingly, recent works combine regression and reasoning
to eliminate formulae inconsistent with background theory. However, the problem
of searching over the space of formulae consistent with background theory to
find one that fits the data best is not well-solved. We propose a solution to
this problem when all axioms and scientific laws are expressible via polynomial
equalities and inequalities and argue that our approach is widely applicable.
We further model notions of minimal complexity using binary variables and
logical constraints, solve polynomial optimization problems via mixed-integer
linear or semidefinite optimization, and prove the validity of our scientific
discoveries in a principled manner using Positivestellensatz certificates.
Remarkably, the optimization techniques leveraged in this paper allow our
approach to run in polynomial time with fully correct background theory, or
non-deterministic polynomial (NP) time with partially correct background
theory. We demonstrate that some famous scientific laws, including Kepler's
Third Law of Planetary Motion, the Hagen-Poiseuille Equation, and the Radiated
Gravitational Wave Power equation, can be derived in a principled manner from
background axioms and experimental data.
