Nonlinear optimization for matroid intersection and extensions

We address optimization of nonlinear functions of the form $f(Wx)$~, where $f:\R^d\rightarrow \R$ is a nonlinear function, $W$ is a $d\times n$ matrix, and feasible $x$ are in some large finite set $\calF$ of integer points in $\R^n$~. Generally, such problems are intractable, so we obtain positive algorithmic results by looking at broad natural classes of $f$~, $W$ and $\calF$~. 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 $\calF$ 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 $\calF$~. 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$~. Our main results (a few technicalities suppressed): 1- When $\calF$ is well described, $f$ is convex (or even quasiconvex), and $W$ has a fixed number of rows and is unary encoded or with entries in a fixed set, we give an efficient deterministic algorithm for maximization. 2- When $\calF$ is well described, $f$ is a norm, and binary-encoded $W$ is nonnegative, we give an efficient deterministic constant-approximation algorithm for maximization. 3- When $\calF$ is well described, $f$ is ``ray concave'' and non-decreasing, and $W$ has a fixed number of rows and is unary encoded or with entries in a fixed set, we give an efficient deterministic constant-approximation algorithm for minimization. 4- When $\calF$ is the set of characteristic vectors of common bases of a pair of vectorial matroids on a common ground set, $f$ is arbitrary, and $W$ has a fixed number of rows and is unary encoded, we give an efficient randomized algorithm for optimization.

Article

Download

View Nonlinear optimization for matroid intersection and extensions