-

 

 

 




Optimization Online





 

Nonlinear optimization for matroid intersection and extensions

Yael Berstein(yaelber***at***tx.technion.ac.il)
Jon Lee(jonlee***at***us.ibm.com)
Shmuel Onn(onn***at***ie.technion.ac.il)
Robert Weismantel(weismantel***at***imo.math.uni-magdeburg.de)

Abstract: 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.

Keywords: matroid intersection, well-described polytope, nonlinear optimization

Category 1: Combinatorial Optimization

Category 2: Nonlinear Optimization

Citation:

Download: [PDF]

Entry Submitted: 07/22/2008
Entry Accepted: 07/31/2008
Entry Last Modified: 07/22/2008

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society