检索结果-内蒙古大学图书馆

maximum-entropy sampling and the Boolean quadric polytope

JOURNAL OF GLOBAL OPTIMIZATION 2018年第4期72卷 603-618页

作者： Anstreicher, Kurt M. Univ Iowa Dept Management Sci Iowa City IA 52242 USA

We consider a bound for the maximum-entropy sampling problem (MESP) that is based on solving a max-det problem over a relaxation of the Boolean quadric polytope (BQP). This approach to MESP was first suggested by Christoph Helmberg over 15years ago, but has apparently never been further elaborated or computationally investigated. We find that the use of a relaxation of BQP that imposes semidefiniteness and a small number of equality constraints gives excellent bounds on many benchmark instances. These bounds can be further tightened by imposing additional inequality constraints that are valid for the BQP. Duality information associated with the BQP-based bounds can be used to fix variables to 0/1 values, and also as the basis for the implementation of a strong branching strategy. A branch-and-bound algorithm using the BQP-based bounds solves some benchmark instances of MESP to optimality for the first time.

关键词： maximum-entropy sampling Semidefinite programming Semidefinite optimization Boolean quadric polytope

来源：评论

学校读者我要写书评

暂无评论

Tridiagonal maximum-entropy sampling and tridiagonal masks

引用

DISCRETE APPLIED MATHEMATICS 2023年第1期337卷 120-138页

作者： Al-Thani, Hessa Lee, Jon Univ Michigan IOE Dept Ann Arbor MI 48109 USA

The NP-hard maximum-entropy sampling problem (MESP) seeks a maximum (log-) determinant principal submatrix, of a given order, from an input covariance matrix C. We give an efficient dynamic-programming algorithm for MESP when C (or its inverse) is tridiagonal and generalize it to the situation where the support graph of C (or its inverse) is a spider graph with a constant number of legs (and beyond). We give a class of arrowhead covariance matrices C for which a natural greedy algorithm solves MESP. A mask M for MESP is a correlation matrix with which we pre-process C, by taking the Hadamard product M degrees C. Upper bounds on MESP with M degrees C give upper bounds on MESP with C. Most upper-bounding methods are much faster to apply, when the input matrix is tridiagonal, so we consider tridiagonal masks M (which yield tridiagonal M degrees C). We make a detailed analysis of such tridiagonal masks, and develop a combinatorial local-search based upper-bounding method that takes advantage of fast computations on tridiagonal matrices.(c) 2023 Elsevier B.V. All rights reserved.

关键词： Nonlinear combinatorial optimization Covariance matrix Differential entropy maximum-entropy sampling Dynamic programming Local search Spider Arrowhead Tridiagonal Mask Correlation matrix

来源：评论

学校读者我要写书评

暂无评论

An outer-approximation algorithm for maximum-entropy sampling

引用

DISCRETE APPLIED MATHEMATICS 2024年 347卷 271-284页

作者： Fampa, Marcia Lee, Jon Univ Fed Rio de Janeiro Rio De Janeiro Brazil Univ Michigan Ann Arbor MI 48109 USA

We apply the well-known outer-approximation algorithm (OA) of convex mixed-integer nonlinear optimization to the maximum-entropy sampling problem (MESP), using convex relaxations for MESP from the literature. We discuss possible methodologies to accelerate the convergence of OA, by combining the use of the different relaxations and by selecting additional linearization points using a local-search procedure, disjunctive cuts, a regularization method, and a second-order approximation of the objective of the MESP. We discuss our findings through numerical experiments with a benchmark test problem. (c) 2024 Elsevier B.V. All rights reserved.

关键词： maximum-entropy sampling Mixed-integer nonlinear optimization Outer approximation Disjunctive cuts No-good Local search Regularization Second-order approximation

来源：评论

学校读者我要写书评

暂无评论

Efficient Solution of maximum-entropy sampling Problems

引用

OPERATIONS RESEARCH 2020年第6期68卷 1826-1835页

作者： Anstreicher, Kurt M. Univ Iowa Dept Business Analyt Tippie Coll Business Iowa City IA 52242 USA

We consider a new approach for the maximum-entropy sampling problem (MESP) that is based on bounds obtained by maximizing a function of the form ldet M(x) over linear constraints, where M(x) is linear in the n-vector x. These bounds can be computed very efficiently and are superior to all previously known bounds for MESP on most benchmark test problems. A branch-and-bound algorithm using the new bounds solves challenging instances of MESP to optimality for the first time.

关键词： maximum-entropy sampling convex programming nonlinear integer programming

来源：评论

学校读者我要写书评

暂无评论

Mixing convex-optimization bounds for maximum-entropy sampling

引用

MATHEMATICAL PROGRAMMING 2021年第2期188卷 539-568页

作者： Chen, Zhongzhu Fampa, Marcia Lambert, Amelie Lee, Jon Univ Michigan Ann Arbor MI 48109 USA Univ Fed Rio de Janeiro Rio De Janeiro Brazil Conservatoire Natl Arts & Metiers Paris France

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.

关键词： maximum-entropy sampling Convex optimization Mixing

来源：评论

学校读者我要写书评

暂无评论

Using continuous nonlinear relaxations to solve constrained maximum-entropy sampling problems

引用

MATHEMATICAL PROGRAMMING 1999年第2期85卷 221-240页

作者： Anstreicher, KM Fampa, M Lee, J Williams, J Univ Iowa Dept Management Sci Iowa City IA 52242 USA Catholic Univ Louvain Ctr Operat Res & Econometr Louvain Belgium Univ Fed Rio de Janeiro COPPE Inst Math Rio De Janeiro Brazil Univ Kentucky Dept Math Lexington KY 40506 USA

We consider a new nonlinear relaxation for the Constrained maximum-entropy sampling Problem - the problem of choosing the s x s principal submatrix with maximal determinant from a given n x n positive definite matrix, subject to linear constraints. We implement a branch-and-bound algorithm for the problem, using the new relaxation. The performance on test problems is far superior to a previous implementation using an eigenvalue-based relaxation. A parallel implementation of the algorithm exhibits approximately linear speed-up for up to 8 processors, and has successfully solved problem instances that were heretofore intractable.

关键词： maximum-entropy sampling branch and bound nonlinear programming

来源：评论

学校读者我要写书评

暂无评论

A linear integer programming bound for maximum-entropy sampling

引用

MATHEMATICAL PROGRAMMING 2003年第2-3期94卷 247-256页

作者： Lee, J Williams, J IBM Corp Thomas J Watson Res Ctr Dept Math Sci Yorktown Hts NY 10598 USA Avaya Inc Westminster CO 80234 USA

We introduce a new upper bound for the maximum-entropy sampling problem. Our bound is described as the solution of a linear integer program. The bound depends on a partition of the underlying set of random variables. For the case in which each block of the partition has bounded cardinality, we describe an efficient dynamic-programming algorithm to calculate the bound. For the very special case in which the blocks have no more than two elements, we describe an efficient algorithm for calculating the bound based on maximum-weight matching. This latter formulation has particular value for local-search procedures that seek to find a good partition. We relate our bound to recent bounds of Hoffman, Lee and Williams. Finally, we report on the results of some computational experiments.

关键词： experimental design design of experiments entropy maximum-entropy sampling matching integer program spectral bound Fischer's inequality branch-and-bound dynamic programming

来源：评论

学校读者我要写书评

暂无评论

An Outer-Approximation Algorithm for maximum-entropy sampling 7th

An Outer-Approximation Algorithm for Maximum-Entropy Samplin...

引用

7th International Symposium on Combinatorial Optimization (ISCO)

作者： Fampa, Marcia Lee, Jon Univ Fed Rio de Janeiro Rio De Janeiro Brazil Univ Michigan Ann Arbor MI USA

We apply the well-known MINLO outer-approximation algorithm (OA) to the maximum-entropy sampling problem (MESP), using the linx and NLP convex relaxations for MESP. We enhance our approach using disjunctive cuts.

ISBN: (纸本)9783031185298;9783031185304

关键词： maximum-entropy sampling Mixed-integer nonlinear optimization Outer approximation Disjunctive cuts No-good

来源：评论

学校读者我要写书评

暂无评论

An R Package for Generating Covariance Matrices for maximum-entropy sampling from Precipitation Chemistry Data

引用

Operations Research Forum 2020年第3期1卷 1-21页

作者： Al-Thani, Hessa Lee, Jon Department of Industrial and Operations Engineering University of Michigan Ann Arbor 48109 MI United States

We present an open-source R package (MESgenCov v 0.1.0) for temporally fitting multivariate precipitation chemistry data and extracting a covariance matrix for use in the MESP (maximum-entropy sampling problem). We provide multiple functionalities for modeling and model assessment. The package is tightly coupled with NADP/NTN (National Atmospheric Deposition Program/National Trends Network) data from their set of 379 monitoring sites, 1978–present. The user specifies the sites, chemicals, and time period desired, fits an appropriate user-specified univariate model for each site and chemical selected, and the package produces a covariance matrix for use by MESP algorithms. © 2020, Springer Nature Switzerland AG.

关键词： Covariance matrix Environmental monitoring Environmetrics maximum-entropy sampling NADP NTN

来源：评论

学校读者我要写书评

暂无评论

Technical Note-Masking Anstreicher's linx Bound for Improved entropy Bounds

引用

OPERATIONS RESEARCH 2024年第2期72卷 591页

作者： Chen, Zhongzhu Fampa, Marcia Lee, Jon Univ Michigan Dept Ind & Operat Engn Ann Arbor MI 48109 USA Univ Fed Rio de Janeiro Alberto Luiz Coimbra Inst Grad Studies & Res Engn Programa Engn Sistemas & Comp BR-21941972 Rio De Janeiro RJ Brazil

The maximum-entropy sampling problem is the NP-hard problem of maximizing the (log) determinant of an order-s principal submatrix of a given order n covariance matrix C. Exact algorithms are based on a branch-and-bound framework. The problem has wide applicability in spatial statistics and in particular in environmental monitoring. Probably the best upper bound for the maximum empirically is Anstreicher???s scaled ???linx??? bound. An earlier methodology for potentially improving any upper-bounding method is by masking, that is, applying the bounding method to C ??? M, where M is any correlation matrix. We establish that the linx bound can be improved via masking by an amount that is at least linear in n, even when optimal scaling parameters are used. We also extend an earlier result that the linx bound is convex in the logarithm of a scaling parameter, making a full characterization of its behavior and providing an efficient means of calculating its limiting behavior in all cases.

关键词： differential entropy maximum-entropy sampling environmental monitoring nonlinear combinatorial optimization nonlinear integer optimization convex relaxations

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：