Nonlinear Matroid Optimization and Experimental Design

DOI10.1137/070696465MaRDI QIDQ3393425zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Yael Berstein, Jon Lee, Hugo Maruri-Aguilar, Shmuel Onn, Eva Riccomagno, Robert Weismantel, Henry P. Wynn

Publication date 20 August 2009

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0707.4618

zbMATH Keywords

aberrationalgebraic statisticsBinet-Cauchy identitycombinatorial optimizationexact matchingexperimental designinteger programminginterpolationlearningmatchingmatroidmatroid intersectionnonlinear discrete optimizationregressionspanning tree

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Characterization and structure theory for multivariate probability distributions; copulas (62H05) Factorial statistical designs (62K15) Numerical optimization and variational techniques (65K10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Integer programming (90C10) Combinatorial optimization (90C27)

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

Recommendations

• Parametric nonlinear discrete optimization over well-described sets and matroid intersections
• Matroid optimization problems with monotone monomials in the objective
• Nonlinear Optimization over a Weighted Independence System
• Nonlinear discrete optimization. An algorithmic theory
• Matroid optimisation problems with nested non-linear monomials in the objective function

Cited in

(16)

• Matroid optimisation problems with nested non-linear monomials in the objective function
• Shifted matroid optimization
• Matroid optimization problems with monotone monomials in the objective
• Convex integer optimization by constantly many linear counterparts
• Minimal average degree aberration and the state polytope for experimental designs
• Parametric nonlinear discrete optimization over well-described sets and matroid intersections
• Approximate nonlinear optimization over weighted independence systems
• Nonlinear Optimization over a Weighted Independence System
• Concentration inequalities for nonlinear matroid intersection
• Intractability of approximate multi-dimensional nonlinear optimization on independence systems
• Computation in multicriteria matroid optimization
• The algebraic method in quadrature for uncertainty quantification
• Concentration inequalities for nonlinear matroid intersection
• Efficient high-precision matrix algebra on parallel architectures for nonlinear combinatorial optimization
• Minimizing Lipschitz-continuous strongly convex functions over integer points in polytopes
• A short history of algebraic statistics

This page was built for publication: Nonlinear Matroid Optimization and Experimental Design

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3393425)