Persistency in Multilinear Optimization

We define a multilinear program to be persistent if every variable realizing a value at either its lower or upper bound in an optimum to a specified linear relaxation persists in retaining that same value in an optimum to the original problem. Few persistency results are known, and all deal with binary or mixed 0-1 problems, reformulating nonlinear instances as equivalent mixed 0-1 linear programs and showing the preference of a binary variable over its complement. We extend the knowledge of persistency in two respects: we present the most general known family of constraints that allows persistency for 0-1 polynomial programs, and we provide sufficient conditions for recognizing more general multilinear problems as persistent. Our approach differs from previous work in that (i) as opposed to the binary case, we show the preference of a variable value over all permissible realizations, here sometimes infinitely many of them, and (ii) our linearizations are not required to be equivalent.

Funding: The research of the first author was supported in part by the Air Force Office of Scientific Research [Grant FA9550-19-1-0339].