Research

Research Interests

mixed-integer programming, larger-scale optimization, trustworthy AI

Mixing convex-optimization bounds for maximum-entropy sampling

The maximum-entropy sampling problem is a fundamental and challenging combinatorial-optimization problem, with application in spatial statistics. It asks to find a maximum-determinant order-s principal submatrix of an order-n covariance matrix. Exact solution methods for this NP-hard problem are based on a branch-and-bound framework. Many of the known upper bounds for the optimal value are based on convex optimization. We present a methodology for “mixing” these bounds to achieve better bounds.

Paper

Zhongzhu Chen, Marcia Fampa, Amélie Lambert, Jon Lee. (2021). "Mixing convex-optimization bounds for maximum-entropy sampling". Published in Mathematical Programming, Series B.

Talks

Engineering Research Symposium, 2021, University of Michigan

Masking Anstreicher’s linx bound for improved entropy bounds

Exact algorithms for maximum-entropy sampling problem are based on branch -and-bound framework. Possibly the best upper bound for the maximum-entropy sampling problem is the Anstreicher's scaled "linx" bound. An earlier methodology for potentially improving any upper-bounding method is by masking. We establish that the linx bound can be improved via masking by an amount that is at least linear in the order of data matrix, even when the optimal scaling parameters are employed.

Paper

"Technical Note—Masking Anstreicher’s linx Bound for Improved Entropy Bounds". Published in Operations Research.

A Limited-memory Quasi-Newton Method for Mask Optimization on Anstreicher’s linx bound

Mask optimization on Anstreicher’s linx bound is a large-scale, non-convex, and typically non-differentiable problem, incorporating a positive-semidefinite constraint. We show that for almost all data matrix, the linx bound is differentiable almost everywhere and give a fast L-BFGS method for computing a good to the optimal solution, which presents many nice properties. Furthermore, our method of analyzing the masking parameter sensitivity and design algorithm can be applied to applying a general technique to improving a general upper bound.

Paper

(Working) Zhongzhu Chen, Marcia Fampa, Jon Lee. (2021+). "A Limited-memory Quasi-Newton Method for Mask Optimization on Anstreicher’s linx bound"

On computing with some convex relaxations for the maximum-entropy sampling problem

Based on a factorization of an input covariance matrix, we define a mild generalization of an upper bound of Nikolov (2015) and Li and Xie (2020) for the NP-Hard constrained maximum-entropy sampling problem (CMESP). We demonstrate that this factorization bound is invariant under scaling and also independent of the particular factorization chosen. We give a variable-fixing methodology that could be used in a branch-and-bound scheme based on the factorization bound for exact solution of CMESP. We report on successful experiments with a commercial nonlinear-programming solver. We further demonstrate that the known "mixing" technique can be successfully used to combine the factorization bound with the factorization bound of the complementary CMESP, and also with the "linx bound" of Anstreicher (2020).

Paper

(Submitted) Zhongzhu Chen, Marcia Fampa, Jon Lee. (2021+). "On computing with some convex relaxations for the maximum-entropy sampling problem".

Talks

Informs Optimization Society, 2022.

Page updated

Report abuse