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

CERTIFYING OPTIMALITY OF BELL INEQUALITY VIOLATIONS: NONCOMMUTATIVE POLYNOMIAL OPTIMIZATION THROUGH semidefinite programming AND LOCAL OPTIMIZATION\ast

引用

SIAM JOURNAL ON OPTIMIZATION 2024年第2期34卷 1341-1373页

作者： Hrga, Timotej Klep, Igor Povh, Janez Univ Ljubljana Fac Math & Phys Ljubljana Slovenia Inst Math Phys & Mech Ljubljana Slovenia Univ Ljubljana Fac Mech Engn Ljubljana Slovenia Rudolfovo Sci & Technol Ctr Novo Mesto Slovenia

Bell inequalities are pillars of quantum physics in that their violations imply that certain properties of quantum physics (e.g., entanglement) cannot be represented by any classical picture of physics. In this article Bell inequalities and their violations are considered through the lens of noncommutative polynomial optimization. Optimality of these violations is certified for a large majority of a set of standard Bell inequalities, denoted A2--A89 in the literature. The main techniques used in the paper include the NPA hierarchy, i.e., the noncommutative version of the Lasserre semidefinite programming (SDP) hierarchies based on the Helton-McCullough Positivstellensatz, the Gelfand--Naimark--Segal (GNS) construction with a novel use of the Artin-Wedderburn theory for rounding and projecting, and nonlinear programming (NLP). A new ``Newton chip"-like technique for reducing sizes of SDPs arising in the constructed polynomial optimization problems is presented. This technique is based on conditional expectations. Finally, noncommutative Gro"\bner bases are exploited to certify when an optimizer (a solution yielding optimum violation) cannot be extracted from a dual SDP solution.

关键词： noncommutative polynomial Bell inequality violation Gro" bner basis semidefinite programming eigenvalue optimization GNS construction Artin-Wedderburn theory

来源：评论

学校读者我要写书评

暂无评论

Weak notions of nondegeneracy in nonlinear semidefinite programming

引用

MATHEMATICAL programming 2024年第1-2期205卷 1-32页

作者： Andreani, Roberto Haeser, Gabriel Mito, Leonardo M. Ramirez, Hector Univ Estadual Campinas Dept Appl Math Campinas Brazil Univ Sao Paulo Dept Appl Math Sao Paulo Brazil Univ Chile Dept Math Engn Santiago Chile Univ Chile Ctr Math Modeling CNRS IRL 2807 Santiago Chile

The constraint nondegeneracy condition is one of the most relevant and useful constraint qualifications in nonlinear semidefinite programming. It can be characterized in terms of any fixed orthonormal basis of the, let us say, l-dimensional kernel of the constraint matrix, by the linear independence of a set of l(l + 1)/2 derivative vectors. We show that this linear independence requirement can be equivalently formulated in a smaller set, of l derivative vectors, by considering all orthonormal bases of the kernel instead. This allows us to identify that not all bases are relevant for a constraint qualification to be defined, giving rise to a strictly weaker variant of nondegeneracy related to the global convergence of an external penalty method. We use some of these ideas to revisit an approach of Forsgren (Math Program 88, 105-128, 2000) for exploiting the sparsity structure of a transformation of the constraints to define a constraint qualification, which led us to develop another relaxed notion of nondegeneracy using a simpler transformation. If the zeros of the derivatives of the constraint function at a given point are considered, instead of the zeros of the function itself in a neighborhood of that point, we obtain an even weaker constraint qualification that connects Forsgren's condition and ours.

关键词： semidefinite programming Constraint qualifications Constraint nondegeneracy

来源：评论

学校读者我要写书评

暂无评论

Beamformer Design for MIMO Interference Broadcast Channels With semidefinite programming

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2018年第17期66卷 4504-4515页

作者： Razavi, S. Morteza Univ Edinburgh Inst Digital Commun Sch Engn Edinburgh EH9 3JL Midlothian Scotland

We consider beamformer design for multiuser multiple-input multiple-output (MIMO) interference channels where each transmitter communicates to its intended receivers while sharing the same spectro-temporal resources with some other unintended receivers. This scenario is often referred to as MIMO interference broadcast channel (IBC) where by using interference alignment (IA), it is possible to cancel out inter and intracell interferences so that the achievable degrees of freedom could be linearly scaled up with the number of users. In this paper, we propose two distinct and novel IA algorithms, one of which is IA via signal matching (SIGMA) that revolves around interference leakage minimization and further takes the desired signal subspaces into account to output higher sum rates. The second algorithm is called bipartite rank fitting, which is founded on the prior knowledge of the rank of receive beamformers and interference matrices. Therefore, this algorithm is quite a unique approach towards interference alignment in MIMO IBCs since it performs the optimization over only receive beamformers. Furthermore, we propose a robust design of SIGMA algorithm to achieve better performance in the presence of imperfect channel state information (CSI). The key tenet of our design is that we formulate the optimization problems involved in these two algorithms as plain semidefinite programs. It is shown that the proposed algorithms are able to outperform state-of-the-art IA techniques under perfect and imperfect CSI, and the suitability of each algorithm for different network configurations is further discussed.

关键词： Degree of freedom interference alignment interference broadcast channel multiuser MIMO system semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

A proximal augmented method for semidefinite programming problems

引用

APPLIED NUMERICAL MATHEMATICS 2021年 169卷 321-333页

作者： Huang, Aiqun Huazhong Univ Sci & Technol Sch Math & Stat Wuhan 430074 Peoples R China Huazhong Univ Sci & Technol Hubei Key Lab Engn Modeling & Sci Comp Wuhan 430074 Peoples R China

A proximal augmented method for solving semidefinite programs is introduced. This method is based on the Augmented Lagrangian method. We study the theoretical properties and show the convergence of the new approach under weaker conditions. Numerical results on some semidefinite programming problems are reported and show that the new method is potentially efficient. (C) 2021 IMACS. Published by Elsevier B.V. All rights reserved.

关键词： Linear programming semidefinite programming Augmented Lagrangian method Approximate method

来源：评论

学校读者我要写书评

暂无评论

Symmetric primal-dual path-following algorithms for semidefinite programming

引用

APPLIED NUMERICAL MATHEMATICS 1999年第3期29卷 301-315页

作者： Sturm, JF Zhang, SZ Tinbergen Inst Rotterdam NL-3000 DR Rotterdam Netherlands Erasmus Univ NL-3000 DR Rotterdam Netherlands

We propose a framework for developing and analyzing primal-dual interior point algorithms for semidefinite programming. This framework is an extension of the v-space approach that was developed by Kojima et al. (1991) for linear complementarity problems. The extension to semidefinite programming allows us to interpret Nesterov-Todd type directions (Nesterov and Todd 1995, 1997) as Newton search directions. Our approach does not involve any barrier function. Several primal-dual path-following algorithms for semidefinite programming are analyzed. The treatment of these algorithms for semidefinite programming in our setting bears great similarity to the linear programming case. (C) 1999 Published by Elsevier Science B.V. and IMACS. All rights reserved.

关键词： semidefinite programming Primal-dual transformation Primal-dual interior point method

来源：评论

学校读者我要写书评

暂无评论

SOME GEOMETRIC RESULTS IN semidefinite programming

引用

JOURNAL OF GLOBAL OPTIMIZATION 1995年第1期7卷 33-50页

作者： RAMANA, M GOLDMAN, AJ RUTGERS STATE UNIV CTR OPERAT RESNEW BRUNSWICKNJ 08903 JOHNS HOPKINS UNIV DEPT MATH SCIBALTIMOREMD 21218

The purpose of this paper is to develop certain geometric results concerning the feasible regions of semidefinite Programs, called here Spectrahedra. We first develop a characterization for the faces of spectrahedra. More specifically, given a point x in a spectrahedron, we derive an expression for the minimal face containing x. Among other things, this is shown to yield characterizations for extreme points and extreme rays of spectrahedra. We then introduce the notion of an algebraic polar of a spectrahedron, and present its relation to the usual geometric polar.

关键词： semidefinite programming CONVEX GEOMETRY

来源：评论

学校读者我要写书评

暂无评论

Certified Roundoff Error Bounds Using semidefinite programming

引用

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 2017年第4期43卷 1–31页

作者： Magron, Victor Constantinides, George Donaldson, Alastair CNRS Verimag St Martin Dheres France Imperial Coll Circuits & Syst South Kensington Campus London SW7 2AZ England Verimag Batiment ImagOff 2053 700 Ave Cent F-38401 St Martin Dheres France

Roundoff errors cannot be avoided when implementing numerical programs with finite precision. The ability to reason about rounding is especially important if one wants to explore a range of potential representations, for instance, for FPGAs or custom hardware implementations. This problem becomes challenging when the program does not employ solely linear operations as non-linearities are inherent to many interesting computational problems in real-world applications. Existing solutions to reasoning possibly lead to either inaccurate bounds or high analysis time in the presence of nonlinear correlations between variables. Furthermore, while it is easy to implement a straightforward method such as interval arithmetic, sophisticated techniques are less straightforward to implement in a formal setting. Thus there is a need for methods that output certificates that can be formally validated inside a proof assistant. We present a framework to provide upper bounds on absolute roundoff errors of floating-point nonlinear programs. This framework is based on optimization techniques employing semidefinite programming and sums of squares certificates, which can be checked inside the Coq theorem prover to provide formal roundoff error bounds for polynomial programs. Our tool covers a wide range of nonlinear programs, including polynomials and transcendental operations as well as conditional statements. We illustrate the efficiency and precision of this tool on non-trivial programs coming from biology, optimization, and space control. Our tool produces more accurate error bounds for 23% of all programs and yields better performance in 66% of all programs.

关键词： Correlation sparsity pattern floating-point arithmetic formal verification polynomial optimization proof assistant roundoff error semidefinite programming transcendental functions

来源：评论

学校读者我要写书评

暂无评论

Interval Enclosures of Upper Bounds of Roundoff Errors Using semidefinite programming

引用

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 2018年第4期44卷 1–18页

作者： Magron, Victor CNRS Verimag 700 Ave Cent F-38401 St Martin Dheres France CNRS LIP6 PolSys Team 4 Pl Jussieu F-75252 Paris 05 France

A long-standing problem related to floating-point implementation of numerical programs is to provide efficient yet precise analysis of output errors. We present a framework to compute lower bounds on largest absolute roundoff errors, for a particular rounding model. This method applies to numerical programs implementing polynomial functions with box constrained input variables. Our study is based on three different hierarchies, relying respectively on generalized eigenvalue problems, elementary computations, and semidefinite programming (SDP) relaxations. This is complementary of over-approximation frameworks, consisting of obtaining upper bounds on the largest absolute roundoff error. Combining the results of both frameworks allows one to get enclosures for upper bounds on roundoff errors. The under-approximation framework provided by the third hierarchy is based on a new sequence of convergent robust SDP approximations for certain classes of polynomial optimization problems. Each problem in this hierarchy can be solved exactly via SDP. By using this hierarchy, one can provide a monotone non-decreasing sequence of lower bounds converging to the absolute roundoff error of a program implementing a polynomial function, applying for a particular rounding model. We investigate the efficiency and precision of our method on nontrivial polynomial programs coming from space control, optimization, and computational biology.

关键词： Roundoff error polynomial optimization semidefinite programming floating-point arithmetic generalized eigenvalues robust optimization

来源：评论

学校读者我要写书评

暂无评论

A STOCHASTIC SMOOTHING ALGORITHM FOR semidefinite programming

引用

SIAM JOURNAL ON OPTIMIZATION 2014年第3期24卷 1138-1177页

作者： D'Aspremont, Alexandre El Karoui, Noureddine Ecole Normale Super CNRS Paris France Ecole Normale Super DI UMR 8548 F-75231 Paris France Univ Calif Berkeley Dept Stat Berkeley CA 94720 USA

We use rank one Gaussian perturbations to derive a smooth stochastic approximation of the maximum eigenvalue function. We then combine this smoothing result with an optimal smooth stochastic optimization algorithm to produce an efficient method for solving maximum eigenvalue minimization problems, and detail a variant of this stochastic algorithm with monotonic line search. Overall, compared to classical smooth algorithms, this method runs a larger number of significantly cheaper iterations and, in certain precision/dimension regimes, its total complexity is lower than that of deterministic smoothing algorithms.

关键词： semidefinite programming Gaussian smoothing eigenvalue problems

来源：评论

学校读者我要写书评

暂无评论

WORST-CASE CONVERGENCE ANALYSIS OF INEXACT GRADIENT AND NEWTON METHODS THROUGH semidefinite programming PERFORMANCE ESTIMATION

引用

SIAM JOURNAL ON OPTIMIZATION 2020年第3期30卷 2053-2082页

作者： De Klerk, Etienne Glineur, Francois Taylor, Adrien B. Tilburg Univ NL-5037 AB Tilburg Netherlands UCL CORE Louvain La Neuve Belgium ICTEAM Louvain La Neuve Belgium PSL Res Univ Ecole Normale Super INRIA Dept Informat ENSCNRS Paris France

We provide new tools for worst-case performance analysis of the gradient (or steepest descent) method of Cauchy for smooth strongly convex functions, and Newton's method for self-concordant functions, including the case of inexact search directions. The analysis uses semidefinite programming performance estimation, as pioneered by Drori and Teboulle [it Math. Program., 145 (2014), pp. 451-482], and extends recent performance estimation results for the method of Cauchy by the authors [it Optim. Lett., 11 (2017), pp. 1185-1199]. To illustrate the applicability of the tools, we demonstrate a novel complexity analysis of short step interior point methods using inexact search directions. As an example in this framework, we sketch how to give a rigorous worst-case complexity analysis of a recent interior point method by Abernethy and Hazan [it PMLR, 48 (2016), pp. 2520-2528].

关键词： performance estimation problems gradient method inexact search directions semidefinite programming interior point methods

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：