Nonlinear Optimization for Matroid Intersection and Extensions

Abstract

We address optimization of nonlinear functions of the form $f(W_x)$ , where $f : \mathbb{R}^d \to \mathbb{R}$ is a nonlinear function, $W$ is a $d \times n$ matrix, and feasible $x$ are in some large finite set $\mathcal{F}$ of integer points in $\mathbb{R}^n$ . Generally, such problems are intractable, so we obtain positive algorithmic results by looking at broad natural classes of $f$, $W$ and $ \mathcal{F}$. One of our main motivations is multi-objective discrete optimization, where $f$ trades off the linear functions given by the rows of $W$ . Another motivation is that we want to extend as much as possible the known results about polynomial-time linear optimization over trees, assignments, matroids, polymatroids, etc. to nonlinear optimization over such structures. We assume that the convex hull of $\mathcal{F}$ is well-described by linear inequalities (i.e., we have an efficient separation oracle). For example, the set of characteristic vectors of common bases of a pair of matroids on a common ground set satisfies this property for $\mathcal{F}$. In this setting, the problem is already known to be intractable (even for a single matroid), for general $f$ (given by a comparison oracle), for (i) $d = 1$ and binary-encoded $W$, and for (ii) $d = n$ and $W = I$.