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

Complexity aspects of local minima and related notions

ADVANCES IN MATHEMATICS 2022年 397卷 108119-108119页

作者： Ahmadi, Amir Ali Zhang, Jeffrey Princeton Univ Dept Operat Res & Financial Engn Princeton NJ 08544 USA

We consider the notions of (i) critical points, (ii) second-order points, (iii) local minima, and (iv) strict local minima for multivariate polynomials. For each type of point, and as a function of the degree of the polynomial, we study the complexity of deciding (1) if a given point is of that type, and (2) if a polynomial has a point of that type. Our results characterize the complexity of these two questions for all degrees left open by prior literature. Our main contributions reveal that many of these questions turn out to be tractable for cubic polynomials. In particular, we present an efficiently-checkable necessary and sufficient condition for local minimality of a point for a cubic polynomial. We also show that a local minimum of a cubic polynomial can be efficiently found by solving semidefinite programs of size linear in the number of variables. By contrast, we show that it is strongly NP-hard to decide if a cubic polynomial has a critical point. We also prove that the set of second-order points of any cubic polynomial is a spectrahedron, and conversely that any spectrahedron is the projection of the set of second-order points of a cubic polynomial. In our final section, we briefly present a potential application of finding local minima of cubic polynomials to the design of a third-order Newton method.(c) 2021 Elsevier Inc. All rights reserved.

关键词： Local minima Critical and second-order points Computational complexity Polynomial optimization Sum of squares polynomials semidefinite programming Local minima Critical and second-order points Computational complexity Polynomial optimization Sum of squares polynomials semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

ON RELAXATIONS APPLICABLE TO MODEL PREDICTIVE CONTROL FOR SYSTEMS WITH BINARY CONTROL SIGNALS

引用

IFAC Proceedings Volumes 2007年第12期40卷 585-590页

作者： Daniel Axehill Lieven Vandenberghe Anders Hansson Div. of Automatic Control Linköpings universitet 581 83 Linköping Sweden Dept. of Electrical Engineering University of California Los Angeles Los Angeles California 90095-1594 USA

In this work, different relaxations applicable to an MPC problem with binary control signals are compared. The relaxations considered are the QP relaxation, the standard SDP relaxation and an alternative equality constrained SDP relaxation. The relaxations are related theoretically, and both the tightness of the bounds and the computational complexities are compared in numerical experiments. The result is that for long prediction horizons, the equality constrained SDP relaxation proposed in this paper provides a good trade-off between the quality of the relaxation and the computational time.

关键词： Predictive control Hybrid systems Binary control Integer programming semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

semidefinite Representation of Sequential Rate-Distortion Function for Stationary Gauss-Markov Processes

Semidefinite Representation of Sequential Rate-Distortion Fu...

引用

IEEE Conference on Control and Applications (CCA)

作者： Tanaka, Takashi MIT Lab Informat & Decis Syst Cambridge MA 02139 USA

ISBN: (纸本)9781479977871

We consider an information-theoretic performance limitation of zero-delay source coding schemes for multidimensional stationary Gauss-Markov sources. In particular, the sequential rate-distortion (SRD) problem is formulated in which the average rate per stage is minimized subject to a constraint on the average mean-square distortion per stage. We prove that there exists an optimal test channel that is linear and time invariant, which can be efficiently constructed by semidefinite programming (SDP). This result indicates that the exponentiated sequential rate-distortion function admits a semidefinite representation.

关键词： Gaussian processes Markov processes information theory mathematical programming SDP SRD function exponentiated sequential rate-distortion function information-theoretic performance limitation multidimensional stationary Gauss-Markov sources semidefinite programming zero-delay source coding schemes Covariance matrices Kernel Linear systems Optimization Rate-distortion Standards Stochastic processes Markov chain Rate distortion Service Discovery Protocol Gaussian processes Information Theory Linear system variance covariance matrix Kernel Covariance matrix Stochastic Processes Optimization methods mathematical programming

来源：评论

学校读者我要写书评

暂无评论

Convex relaxation for maximum-likelihood network localization using distance and direction data 19

Convex relaxation for maximum-likelihood network localizatio...

引用

19th IEEE International Workshop on Signal Processing Advances in Wireless Communications (SPAWC)

作者： Naseri, Hassan Koivunen, Visa Aalto Univ Aalto Finland

ISBN: (纸本)9781538635124

A reliable and accurate positioning technology is crucial for a large variety of wireless services and applications. High-resolution estimates of distance and direction data are available in most current and emerging wireless systems. Combining these two sensing modalities can improve the estimation performance and identifiability of the localization problem. However, the problem of cooperative localization using joint distance and direction estimates is still a largely unexplored problem. A novel convex relaxation of the maximum likelihood (ML) estimator for this problem called semidefinite programming Hybrid Localization (SDHL) algorithm is proposed in this paper. Numerical results are presented showing that the localization error is significantly reduced in almost every simulation scenario compared to the state of the art. This improvement in localization performance is due to the close approximation of the ML estimator.

关键词： Positioning Cooperative Localization semidefinite programming Hybrid Localization

来源：评论

学校读者我要写书评

暂无评论

The Hankel-Type L q /L p Induced Norms of Positive Systems Across Switching

引用

IFAC-PapersOnLine 2020年第2期53卷 4719-4724页

作者： Y. Ebihara D. Peaucelle D. Arzelier Graduate School of Information Science and Electrical Engineering Kyushu University 744 Motooka Nishi-ku Fukuoka 819-0395 Japan LAAS-CNRS Univ. Toulouse CNRS Toulouse France

The Hankel-type L q /L p induced norms across a single switching over two linear time-invariant (LTI) positive systems are discussed. The norms are defined as the induced norms from vector-valued L p -past inputs to vector valued L q -future outputs across a switching at the time instant zero. The Hankel-type L 2 /L 2 induced norm across a single switching for general LTI systems is studied in details to evaluate the performance deterioration caused by switching. Thanks to the strong positivity property, we successfully characterize the Hankel-type L q /L p induced norms for the positive system switching even for p, q being 1, 2, ∞. In particular, we will show that some of them are given in the form of linear program and semidefinite program (SDP). The SDP-based characterizations are useful for the analysis of the Hankel-type L q /L p induced norms where the systems of interest are affected by parametric uncertainties.

关键词： positive system switching Hankel-type L q /L p induced norm linear programming semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

Sum-of-squares certificates for Vizing's conjecture via determining Grobner bases

引用

JOURNAL OF SYMBOLIC COMPUTATION 2024年 120卷

作者： Gaar, Elisabeth Siebenhofer, Melanie Johannes Kepler Univ Linz Inst Prod & Logist Management Linz Austria Alpen Adria Univ Klagenfurt Klagenfurt Austria

The famous open Vizing conjecture claims that the domination number of the Cartesian product graph of two graphs G and H is at least the product of the domination numbers of G and H. Recently Gaar, Krenn, Margulies and Wiegele used the graph class g of all graphs with ng vertices and domination number kg and reformulated Vizing's conjecture as the problem that for all graph classes g and 7-t the Vizing polynomial is sum-of-squares (SOS) modulo the Vizing ideal. By solving semidefinite programs (SDPs) and clever guessing they derived SOS-certificates for some values of kg, ng, kn, and nn. In this paper, we consider their approach for kg = kn= 1. For this case we are able to derive the unique reduced Grobner basis of the Vizing ideal. Based on this, we deduce the minimum degree (ng +nn -1)/2 of an SOS-certificate for Vizing's conjecture, which is the first result of this kind. Furthermore, we present a method to find certificates for graph classes g and 7-t with ng +nn -1 = d for general d, which is again based on solving SDPs, but does not depend on guessing and depends on much smaller SDPs. We implement our new method in SageMath and give new SOS certificates for all graph classes g and 7-t with kg = kn= 1 and ng +nn & LE;15.& COPY;2023 The Author(s). Published by Elsevier Ltd. This is an open access article under the CC BY license (http:// creativecommons .org /licenses /by /4 .0/).

关键词： Vizing's conjecture Grobner basis Algebraic model Sum-of-squares programming semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

Conditions for optimal input states for discrimination of quantum channels

引用

JOURNAL OF MATHEMATICAL PHYSICS 2016年第12期57卷 122203-122203页

作者： Jencova, Anna Plavala, Martin Slovak Acad Sci Math Inst Bratislava 81104 Slovakia

We find optimality conditions for testers in discrimination of quantum channels. These conditions are obtained using semidefinite programming and are similar to optimality conditions for discrimination of quantum states. We get a simple condition for existence of an optimal tester with any given input state with maximal Schmidt rank, in particular with a maximally entangled input state. In the case when maximally entangled state is not optimal, an upper bound on the optimal success probability is obtained. The results for discrimination of two channels are applied to covariant channels, qubit channels, unitary channels, and simple projective measurements. Published by AIP Publishing.

关键词： QUANTUM states QUANTUM entanglement semidefinite programming PROBABILITY theory BOUNDS (Mathematics)

来源：评论

学校读者我要写书评

暂无评论

Higher-order Newton methods with polynomial work per iteration

引用

ADVANCES IN MATHEMATICS 2024年 452卷

作者： Ahmadi, Amir Ali Chaudhry, Abraar Zhang, Jeffrey Princeton Univ Operat Res & Financial Engn Princeton NJ 08544 USA Yale Univ Dept Biomed Informat & Data Sci New Haven CT USA

We present generalizations of Newton's method that incorporate derivatives of an arbitrary order d but maintain a polynomial dependence on dimension in their cost per iteration. At each step, our d th-order method uses semidefinite programming to construct and minimize a sum of squaresconvex approximation to the d th-order Taylor expansion of the function we wish to minimize. We prove that our d th-order method has local convergence of order d. This results in lower oracle complexity compared to the classical Newton method. We show on numerical examples that basins of attraction around local minima can get larger as d increases. Under additional assumptions, we present a modified algorithm, again with polynomial cost per iteration, which is globally convergent and has local convergence of order d. (c) 2024 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

关键词： Newton's method Tensor methods semidefinite programming Sum of squares methods Convergence analysis

来源：评论

学校读者我要写书评

暂无评论

Corrigendum: Behavior of the NORTA method for correlated random vector generation as the dimension increases

引用

ACM Transactions on Modeling and Computer Simulation 2009年第4期19卷 1–3页

作者： Soumyadip Ghosh Shane G. Henderson IBM Research Yorktown Heights NY Cornell University Ithaca NY

This note corrects an error in Ghosh and Henderson [2003].

关键词： NORTA method onion method sampling random matrices semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

The analytic center cutting plane method with semidefinite cuts

引用

SIAM JOURNAL ON OPTIMIZATION 2003年第4期13卷 1029-1053页

作者： Oskoorouchi, MR Goffin, JL Calif State Univ San Marcos Coll Business Adm San Marcos CA 92096 USA McGill Univ Fac Management GERAD Montreal PQ H3A 1G5 Canada

We analyze an analytic center cutting plane algorithm for convex feasibility problems with semidefinite cuts. The problem of interest seeks a feasible point in a bounded convex set, which contains a full-dimensional ball with epsilon ( < 1) radius and is contained in a compact convex set described by matrix inequalities, known as the set of localization. At each iteration, an approximate analytic center of the set of localization is computed. If this point is not in the solution set, an oracle is called to return a p-dimensional semidefinite cut. The set of localization is then updated by adding the semidefinite cut through the center. We prove that the analytic center is recovered after adding a p(k)-dimensional semidefinite cut in O (p(k) log(p(k) + 1)) damped Newton's iteration and that the algorithm stops with a point in the solution set when the dimension of the accumulated block diagonal cut matrix reaches the bound of O* (p(2) m(3)/μ(2) ε(2)), where p is the maximum dimension of the cut matrices and μ > 0 is a condition number of the field of cuts.

关键词： analytic center cutting plane method semidefinite programming semidefinite cut

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：