Search Results
Nonlinear matroid optimization and experimental design
We study the problem of optimizing nonlinear objective functions over matroids presented by oracles or explicitly. Such functions can be interpreted as the balancing of multi-criteria optimization. We provide a combinatorial polynomial time algorithm for arbitrary oracle-presented matroids, that makes repeated use of matroid intersection, and an algebraic algorithm for vectorial matroids. Our work is partly motivated by applications to minimum-aberration model-fitting in experimental design in statistics, which we discuss and demonstrate in detail.
Nonlinear optimization for matroid intersection and extensions
We address optimization of nonlinear functions of the form f(Wx) , where f : Rd ! R is a nonlinear function, W is a d × n matrix, and feasible x are in some large finite set F of integer points in Rn . Generally, such problems are intractable, so we obtain positive algorithmic results by looking at broad natural classes of f , W and 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 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 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 . Our main results (a few technicalities suppressed): 1- When F 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 F 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 F 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 F 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.
Nonlinear optimization over a weighted independence system
We consider the problem of optimizing a nonlinear objective function over a weighted independence system presented by a linear-optimization oracle. We provide a polynomial-time algorithm that determines an r-best solution for nonlinear functions of the total weight of an independent set, where r is a constant that depends on certain Frobenius numbers of the individual weights and is independent of the size of the ground set. In contrast, we show that finding an optimal (0-best) solution requires exponential time even in a very special case of the problem.
On test sets for nonlinear integer maximization
A finite test set for an integer maximization problem enables us to verify whether a feasible point attains the global maximum. We estabish in the paper several general results that apply to integer maximization problems wthe monlinear objective functions.