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

Convexifying multilinear sets with cardinality constraints: Structural properties, nested case and extensions

DISCRETE OPTIMIZATION 2023年 50卷

作者： Chen, Rui Dash, Sanjeeb Gunluk, Oktay Cornell Univ Ithaca NY 14850 USA IBM Res Boeblingen DE USA

The problem of minimizing a multilinear function of binary variables is a wellstudied NP-hard problem. The set of solutions of the standard linearization of this problem is called the multilinear set. We study a cardinality constrained version of it with upper and lower bounds on the number of nonzero variables. We call the set of solutions of the standard linearization of this problem a multilinear set with cardinality constraints. We characterize a set of conditions on these multilinear terms (called properness) and observe that under these conditions the convex hull description of the set is tractable via an extended formulation. We then give an explicit polyhedral description of the convex hull when the multilinear terms have a nested structure. Our description has an exponential number of inequalities which can be separated in polynomial time. Finally, we generalize these inequalities to obtain valid inequalities for the general case. (c) 2023 Elsevier B.V. All rights reserved.

关键词： multilinear functions Valid inequalities Mixing inequalities Polyhedral combinatorics

来源：评论

学校读者我要写书评

暂无评论

ADMM for multiaffine constrained optimization

引用

OPTIMIZATION METHODS & SOFTWARE 2020年第2期35卷 257-303页

作者： Gao, Wenbo Goldfarb, Donald Curtis, Frank E. Columbia Univ Dept Ind Engn & Operat Res New York NY 10027 USA Lehigh Univ Dept Ind & Syst Engn Bethlehem PA 18015 USA

We expand the scope of the alternating direction method of multipliers (ADMM). Specifically, we show that ADMM, when employed to solve problems with multiaffine constraints that satisfy certain verifiable assumptions, converges to the set of constrained stationary points if the penalty parameter in the augmented Lagrangian is sufficiently large. When the Kurdyka-Lojasiewicz (K-L) property holds, this is strengthened to convergence to a single constrained stationary point. Our analysis applies under assumptions that we have endeavoured to make as weak as possible. It applies to problems that involve nonconvex and/or nonsmooth objective terms, in addition to the multiaffine constraints that can involve multiple (three or more) blocks of variables. To illustrate the applicability of our results, we describe examples including nonnegative matrix factorization, sparse learning, risk parity portfolio selection, nonconvex formulations of convex problems and neural network training. In each case, our ADMM approach encounters only subproblems that have closed-form solutions.

关键词： ADMM nonconvex optimization multilinear functions

来源：评论

学校读者我要写书评

暂无评论

Cardinality Constrained multilinear Sets 6th

Cardinality Constrained Multilinear Sets

引用

6th International Symposium on Combinatorial Optimization

作者： Chen, Rui Dash, Sanjeeb Gunluk, Oktay Univ Wisconsin Madison Madison WI 53706 USA IBM TJ Watson Res Ctr Yorktown Hts NY 10598 USA Cornell Univ Sch ORIE Ithaca NY 14853 USA

ISBN: (纸本)9783030532611;9783030532628

The problem of minimizing a multilinear function of binary variables is a well-studied NP-hard problem. The set of solutions of the standard linearization of this problem is called the multilinear set, and many valid inequalities for its convex hull are available in the literature. Motivated by a machine learning application, we study a cardinality constrained version of this problem with upper and lower bounds on the number of nonzero variables. We call the set of solutions of the standard linearization of this problem a cardinality constrained multilinear set, and give a complete polyhedral description of its convex hull when the multilinear terms in the problem have a nested structure.

关键词： multilinear functions Valid inequalities Mixing

来源：评论

学校读者我要写书评

暂无评论

On decomposability of multilinear sets

引用

MATHEMATICAL PROGRAMMING 2018年第2期170卷 387-415页

作者： Del Pia, Alberto Khajavirad, Aida Univ Wisconsin Dept Ind & Syst Engn Madison WI 53706 USA Univ Wisconsin Wisconsin Inst Discovery Madison WI 53706 USA Carnegie Mellon Univ Dept Chem Engn Pittsburgh PA 15213 USA

We consider the multilinear set defined as the set of binary points (x, y) satisfying a collection of multilinear equations of the form , , where denotes a family of subsets of of cardinality at least two. Such sets appear in factorable reformulations of many types of nonconvex optimization problems, including binary polynomial optimization. A great simplification in studying the facial structure of the convex hull of the multilinear set is possible when is decomposable into simpler multilinear sets ,;namely, the convex hull of can be obtained by convexifying each , separately. In this paper, we study the decomposability properties of multilinear sets. Utilizing an equivalent hypergraph representation for multilinear sets, we derive necessary and sufficient conditions under which is decomposable into , , based on the structure of pair-wise intersection hypergraphs. Our characterizations unify and extend the existing decomposability results for the Boolean quadric polytope. Finally, we propose a polynomial-time algorithm to optimally decompose a multilinear set into simpler subsets. Our proposed algorithm can be easily incorporated in branch-and-cut based global solvers as a preprocessing step for cut generation.

关键词： multilinear functions Convex hull Decomposition Zero-one polynomial optimization Factorable relaxations Polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

A Polyhedral Study of Binary Polynomial Programs

引用

MATHEMATICS OF OPERATIONS RESEARCH 2017年第2期42卷 389-410页

We study the polyhedral convex hull of a mixed-integer set S defined by a collection of multilinear equations over the unit hypercube. Such sets appear frequently in the factorable reformulation of mixed-integer nonlinear optimization problems. In particular, the set S represents the feasible region of a linearized unconstrained binary polynomial optimization problem. We define an equivalent hypergraph representation of the mixed-integer set S, which enables us to derive several families of facet-defining inequalities, structural properties, and lifting operations for its convex hull in the space of the original variables. Our theoretical developments extend several well-known results from the Boolean quadric polytope and the cut polytope literature, paving a way for devising novel optimization algorithms for nonconvex problems containing multilinear sub-expressions.

关键词： binary polynomial optimization polyhedral relaxations multilinear functions cutting planes lifting

来源：评论

学校读者我要写书评

暂无评论

Further results on the strong stability of difference equations of continuous time

引用

IFAC-PapersOnLine 2017年第1期50卷 13318-13323页

作者： Ma, Qian Gu, Keqin Choubedar, Narges School of Automation Nanjing University of Science and Technology NanjingJiangsu210094 China Department of Mechanical and Industrial Engineering Southern Illinois University Edwardsville EdwardsvilleIL62025 United States

This article studies the strong stability of scalar difference equations of continuous time in which the delays are sums of a number of independent parameters τii = 1, 2,… K. The characteristic quasipolynomial of such an equation is a multilinear function of e-Tis. It is known that the characteristic quasipolynomial of any difference equation set in the form of one-delay-per-scalar-channel (ODPSC) model is also in such a multilinear form. However, it is shown in this article that some multilinear forms of quasipolynomials are not characteristic quasipolynomials of any ODPSC difference equation set. The equivalence between local strong stability the exponential stability of a fixed set of rationally independent delays, and the stability for all positive delays is shown. © 2017

关键词： Stability Continuous time systems Convergence of numerical methods Difference equations Time delay Continuous time Independent delays Independent parameters multilinear forms multilinear functions Quasi poly nomial Quasipolynomials Strong stability

来源：评论

学校读者我要写书评

暂无评论

Valid inequalities and convex hulls for multilinear functions

引用

Electronic Notes in Discrete Mathematics 2010年第C期36卷 805-812页

作者： Belotti, Pietro Miller, Andrew J. Namazifar, Mahdi Department of Industrial and Systems Engineering Lehigh University United States Institut de Mathématiques de Bordeaux Université Bordeaux 1 RealOpt INRIA Bordeaux Sud-Ouest France Department of Industrial and Systems Engineering University of Wisconsin-Madison United States

We study the convex hull of the bounded, nonconvex set Mn = {(x1,...,xn , xn+1) ∈ Rn+1: xn+1 = πi=1 n xi;li≤ xi≤ ui , i = 1, ... ,n+1} for any n ≥ 2. We seek to derive strong valid linear inequalities for Mn;this... 详细信息

We study the convex hull of the bounded, nonconvex set M_n = {(x₁,...,x_n , x_n+1) ∈ Rⁿ⁺¹: x_n+1 = π_i=1 ⁿ x_i;l_i≤ x_i≤ u_i , i = 1, ... ,n+1} for any n ≥ 2. We seek to derive strong valid linear inequalities for Mn;this is motivated by the fact that many exact solvers for nonconvex problems use polyhedral relaxations so as to compute a lower bound via linear programming *** present a class of linear inequalities that, together with the well-known McCormick inequalities, defines the convex hull of M₂. This class of inequalities, which we call lifted tangent inequalities, is uncountably infinite, which is not surprising given that the convex hull of M₂ is not a polyhedron. This class of inequalities generalizes directly to M_n for n>2, allowing us to define strengthened relaxations for these higher dimensional sets as well. © 2010.

关键词： Convex hulls Mixed integer nonlinear programming multilinear functions Polyhedral analysis Strong formulation

来源：评论

学校读者我要写书评

暂无评论

Global optimization of nonconvex problems with multilinear intermediates

引用

MATHEMATICAL PROGRAMMING COMPUTATION 2015年第1期7卷 1-37页

作者： Bao, Xiaowei Khajavirad, Aida Sahinidis, Nikolaos V. Tawarmalani, Mohit IBM Corp San Francisco Bay Area NY 10504 USA IBM Corp Thomas J Watson Res Ctr Business Analyt & Math Sci Yorktown Hts NY 10598 USA Carnegie Mellon Univ Dept Chem Engn Pittsburgh PA 15213 USA Purdue Univ Krannert Sch Management W Lafayette IN 47907 USA

We consider global optimization of nonconvex problems containing multilinear functions. It is well known that the convex hull of a multilinear function over a box is polyhedral, and the facets of this polyhedron can be obtained by solving a linear optimization problem (LP). When used as cutting planes, these facets can significantly enhance the quality of conventional relaxations in general-purpose global solvers. However, in general, the size of this LP grows exponentially with the number of variables in the multilinear function. To cope with this growth, we propose a graph decomposition scheme that exploits the structure of a multilinear function to decompose it to lower-dimensional components, for which the aforementioned LP can be solved very efficiently by employing a customized simplex algorithm. We embed this cutting plane generation strategy at every node of the branch-and-reduce global solver BARON, and carry out an extensive computational study on quadratically constrained quadratic problems, multilinear problems, and polynomial optimization problems. Results show that the proposed multilinear cuts enable BARON to solve many more problems to global optimality and lead to an average 60 % CPU time reduction.

关键词： multilinear functions Global optimization Convex envelope Polyhedral relaxations

来源：评论

学校读者我要写书评

暂无评论

The reliability importance of components and prime implicants in coherent and non-coherent systems including total-order interactions

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2010年第3期204卷 485-495页

作者： Borgonovo, E. Bocconi Univ ELEUSI Res Ctr I-20135 Milan Italy Bocconi Univ Dept Decis Sci I-20135 Milan Italy

In the management of complex systems, knowledge of how components contribute to system performance is essential to the correct allocation of resources. Recent works have renewed interest in the properties of the joint (J) and differential (D) reliability importance measures. However, a common background for these importance measures has not been developed yet. In this work, we build a unified framework for the utilization of J and D in both coherent and non-coherent systems. We show that the reliability function of any system is multilinear and its Taylor expansion is exact at an order T. We then introduce a total order importance measure (D-T) that coincides with the exact portion of the change in system reliability associated with any (finite or infinitesimal) change in component reliabilities. We show that D-T synthesizes the Birnbaum, joint and differential importance of all orders in one unique indicator. We propose an algorithm that enables the numerical estimation of D-T by varying one probability at a time, making it suitable in the analysis of complex systems. Findings demonstrate that the simultaneous utilization of D-T and J provides reliability analysts with a complete dissection of system performance. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Reliability Importance measures Joint reliability importance multilinear functions

来源：评论

学校读者我要写书评

暂无评论

Existence and sum decomposition of vertex polyhedral convex envelopes

引用

OPTIMIZATION LETTERS 2008年第3期2卷 363-375页

作者： Tardella, Fabio Univ Roma La Sapienza Fac Econ Dipartimento Matemat Decis Econ Finanziarie & Ass I-00161 Rome Italy

Convex envelopes are a very useful tool in global optimization. However finding the exact convex envelope of a function is a difficult task in general. This task becomes considerably simpler in the case where the domain is a polyhedron and the convex envelope is vertex polyhedral, i.e., has a polyhedral epigraph whose vertices correspond to the vertices of the domain. A further simplification is possible when the convex envelope is sum decomposable, i.e., the convex envelope of a sum of functions coincides with the sum of the convex envelopes of the summands. In this paper we provide characterizations and sufficient conditions for the existence of a vertex polyhedral convex envelope. Our results extend and unify several results previously obtained for special cases of this problem. We then characterize sum decomposability of vertex polyhedral convex envelopes, and we show, among else, that the vertex polyhedral convex envelope of a sum of functions coincides with the sum of the vertex polyhedral convex envelopes of the summands if and only if the latter sum is vertex polyhedral.

关键词： Convex envelope Global optimization Convex analysis multilinear functions Edge-concavity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：