Nonlinear Optimization for Matroid Intersection and Extensions

We address optimization of nonlinear functions of the form , where is a
nonlinear function, W is a d × n matrix, and feasible x are in some large finite set of integer points
in . Generally, such problems are intractable, so we obtain positive algorithmic results by looking
at broad natural classes of f , W and .

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 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 . 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 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 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 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 constantapproximation
algorithm for minimization.
4- When 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.

By: Y. Berstein; Jon Lee; S. Onn; R. Weismantel

Published in: RC24610 in 2008

LIMITED DISTRIBUTION NOTICE:

This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.

rc24610.pdf

Questions about this service can be mailed to reports@us.ibm.com .