ADMM for 0/1 D-Opt and MESP relaxations

2024/11/05 by Ponte, Gabriel, Fampa, Marcia, Lee, Jon +1 · 1 citation
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2411.03461

Abstract

The 0/1 D-optimality problem and the Maximum-Entropy Sampling problem are two well-known NP-hard discrete maximization problems in experimental design. Algorithms for exact optimization (of moderate-sized instances) are based on branch-and-bound. The best upper-bounding methods are based on convex relaxation. We present ADMM (Alternating Direction Method of Multipliers) algorithms for solving these relaxations and experimentally demonstrate their practical value.

Cited by

• Finding Maximum Determinant Principal Submatrices via Hadamard Bounds and Projection Methods

Related

• On the relationship between MESP and 0/1 D-Opt and their upper bounds
• Tuning Over-Relaxed ADMM
• Optimizing ADMM and Over-Relaxed ADMM Parameters for Linear Quadratic Problems
• Branch-and-bound for integer D-Optimality with fast local search and variable-bound tightening
• Convergence rate bounds for a proximal ADMM with over-relaxation stepsize parameter for solving nonconvex linearly constrained problems