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

experimental designinterpolationregressioncombinatorial optimizationlearningmatchingalgebraic statisticsinteger programmingmatroid intersectionmatroidspanning treenonlinear discrete optimizationexact matchingaberrationBinet-Cauchy identity

Mathematics Subject Classification ID

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

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)

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