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

semidefinite programming for optimizing convex bodies under width constraints

OPTIMIZATION METHODS & SOFTWARE 2012年第6期27卷 1073-1099页

作者： Bayen, Terence Henrion, Didier Univ Montpellier 2 Inst Math & Modelisat Montpellier F-34095 Montpellier France CNRS LAAS F-31077 Toulouse France Univ Toulouse LAAS UPS INSAINPISAE F-31077 Toulouse France Czech Tech Univ Fac Elect Engn Dept Control Engn CZ-16626 Prague Czech Republic

We consider the problem of minimizing a functional (such as the area, perimeter and surface) within the class of convex bodies whose support functions are trigonometric polynomials. The convexity constraint is transformed via the Fejer-Riesz theorem on positive trigonometric polynomials into a semidefinite programming problem. Several problems such as the minimization of the area in the class of constant-width planar bodies, rotors and space bodies of revolution are revisited. The approach seems promising to investigate more difficult optimization problems in the class of three-dimensional convex bodies.

关键词： convexity optimization semidefinite programming support function

来源：评论

学校读者我要写书评

暂无评论

semidefinite programming for discrete optimization and matrix completion problems

引用

DISCRETE APPLIED MATHEMATICS 2002年第1-3期123卷 513-577页

作者： Wolkowicz, H Anjos, MF Univ Waterloo Fac Math Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada

semidefinite programming (SDP) is currently one of the most active areas of research in optimization. SDP has attracted researchers from a wide variety of areas because of its theoretical and numerical elegance as well as its wide applicability. In this paper we present a survey of two major areas of application for SDP, namely discrete optimization and matrix completion problems. In the first part of this paper we present a recipe for finding SDP relaxations based on adding redundant constraints and using Lagrangian relaxation. We illustrate this with several examples. We first show that many relaxations for the max-cut problem (MC) are equivalent to both the Lagrangian and the well-known SDP relaxation. We then apply the recipe to obtain new strengthened SDP relaxations for MC as well as known SDP relaxations for several other hard discrete optimization problems. In the second part of this paper we discuss two completion problems, the positive semidefinite matrix completion problem and the Euclidean distance matrix completion problem. We present some theoretical results on the existence of such completions and then proceed to the application of SDP to find approximate completions. We conclude this paper with a new application of SDP to find approximate matrix completions for large and sparse instances of Euclidean distance matrices. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： semidefinite programming discrete optimization Lagrangian relaxation max-cut problem Euclidean distance matrix matrix completion problem

来源：评论

学校读者我要写书评

暂无评论

semidefinite programming in combinatorial optimization

引用

MATHEMATICAL programming 1997年第1-3期79卷 143-161页

作者： Goemans, MX MIT DEPT MATH ROOM 2-392 CAMBRIDGE MA 02139 USA

We discuss the use of semidefinite programming for combinatorial optimization problems. The main topics covered include (i) the Lovasz theta function and its applications to stable sets, perfect graphs, and coding theory, (ii) the automatic generation of strong valid inequalities, (iii) the maximum cut problem and related problems, and (iv) the embedding of finite metric spaces and its relationship to the sparsest cut problem. (C) 1997 The Mathematical programming Society, Inc. Published by Elsevier Science B.V.

关键词： semidefinite programming combinatorial optimization stable set maximum cut coding theory

来源：评论

学校读者我要写书评

暂无评论

semidefinite programming relaxations and algebraic optimization in control

引用

EUROPEAN JOURNAL OF CONTROL 2003年第2-3期9卷 307-321页

作者： Parrilo, PA Lall, S Swiss Fed Inst Technol Automat Control Lab CH-8092 Zurich Switzerland Stanford Univ Dept Aeronaut & Astronaut Stanford CA 94305 USA

We present an overview of the essential elements of semidefinite programming as a computational tool for the analysis of systems and control problems. We make particular emphasis on general duality properties as providing suboptimality or infeasibility certificates. Our focus is on the exciting developments which have occured in the last few nears, including robust optimization, combinatorial optimization, and algebraic methods such as sum-of-squares. These developments are illustrated with examples of applications to control systems.

关键词： control theory duality linear matrix inequalities semidefinite programming sum of squares

来源：评论

学校读者我要写书评

暂无评论

semidefinite programming solution of economic dispatch problem with non smooth, non-convex cost functions

引用

ELECTRIC POWER SYSTEMS RESEARCH 2018年 164卷 178-187页

作者： Alawode, K. O. Jubril, A. M. Kehinde, L. O. Ogunbona, P. O. Osun State Univ Dept Elect & Elect Engn Osogbo Nigeria Obafemi Awolowo Univ Dept Elect & Elect Engn Ife Nigeria Univ Wollongong Sch Comp & Informat Technol Wollongong NSW Australia

The paper presents a solution to economic dispatch (ED) problems with non-convex, non-smooth fuel cost functions, which characterize practical generating units. A method involving a unified semidefmite programming (SDP) formulation of different ED problems through cost function decomposition was presented. The solution of the resulting rank-relaxed SDP problem was refined to achieve the rank constraint using the method of convex iteration and branch-and-bound technique. The SDP method was investigated on some test problems in the literature. The results showed that the SDP method compared favorably with other methods, and can efficiently solve non-convex and non-smooth ED problems.

关键词： Economic dispatch semidefinite programming Non-convex Non-smooth cost function Convex iteration Branch-and-bound

来源：评论

学校读者我要写书评

暂无评论

semidefinite programming for optimal power flow problems

引用

INTERNATIONAL JOURNAL OF ELECTRICAL POWER & ENERGY SYSTEMS 2008年第6-7期30卷 383-392页

作者： Bai, Xiaoqing Wei, Hua Fujisawa, Katsuki Wang, Yong Guangxi Univ Coll Elect Engn Guangxi Peoples R China Tokyo Denki Univ Dept Math Sci Saitama Japan Univ N Carolina Dept Math & Stat Charlotte NC 28223 USA

This paper presents a new solution using the semidefinite programming (SDP) technique to solve the optimal power flow problems (OPF). The proposed method involves reformulating the OPF problems into a SDP model and developing an algorithm of interior point method (IPM) for SDP. That is said, OPF in a nonlinear programming (NP) model, which is a nonconvex problem, has been accurately transformed into a SDP model which is a convex problem. Based on SDP, the OPF problem can be solved by primal-dual interior point algorithms which possess superlinear convergence. The proposed method has been tested with four kinds of objective functions of OPF. Extensive numerical simulations on test systems with sizes ranging from 4 to 300 buses have shown that this method is promising for OPF problems due to its robustness. (C) 2008 Published by Elsevier Ltd.

关键词： optimal power flow interior point method semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

semidefinite programming and matrix scaling over the semidefinite cone

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2003年第1-3期375卷 221-243页

作者： Kalantari, B Rutgers State Univ Dept Comp Sci Hill Ctr Math Sci New Brunswick NJ 08903 USA

Let E be the Hilbert space of real symmetric matrices with block diagonal form diag(A, M), where A is n x n, and M is an l x l diagonal matrix, with the inner product (x, y) equivalent to Trace(xy). We assume n + l greater than or equal to 1, i.e. allow n = 0 or l = 0. Given x epsilon E, we write x greater than or equal to 0 (x > 0) if it is positive semidefinite (positive definite). Let Q : E --> E be a symmetric positive semidefinite linear operator, and mu = min{phi(x) = 0.5 Trace(xQx) : parallel toxparallel to = 1, x greater than or equal to 0}. The problem of testing if mu = 0 is a significant problem called Homogeneous programming. On the one hand the feasibility problem in semidefinite programming (SDP) can be formulated as a Homogeneous programming problem. On the other hand it is related to the generalization of the classic problem of Matrix Scaling. Let epsilon is an element of (0, 1) be a given accuracy, u = Qe - e, e the identity matrix in E, and N = n + l. We describe a path-following algorithm that in case mu = 0, in O(rootN ln[Nparallel touparallel to/epsilon]) Newton iterations produces d greater than or equal to 0, parallel todparallel to = 1 such that phi(d) less than or equal to epsilon. If mu > 0, in O(rootN ln[Nparallel touparallel to/mu] + ln ln(1/epsilon)) Newton iterations the algorithm produces d > 0 such that parallel toDQDe - eparallel to less than or equal to epsilon, where D is the operator that maps w epsilon E to d(1/2)wd(1/2). Moreover, we use the algorithm to prove: mu > 0, if and only if there exists d > 0 such that DQDe = e, if and only if there exists d > 0 such that Qd > 0. Thus via this duality the Matrix Scaling problem is a natural dual to the feasibility problem in SDP. This duality also implies that in Blum et al. [Bull. AMS 21 (1989) 1] real number model of computation the decision problem of testing the solvability of Matrix Scaling is both in NP and Co-NP. Although the above complexities can be deduced from our path-follo

关键词： semidefinite programming matrix scaling Newton's method interior-point method positive semidefinite linear operators

来源：评论

学校读者我要写书评

暂无评论

semidefinite programming and eigenvalue bounds for the graph partition problem

引用

MATHEMATICAL programming 2015年第2期151卷 379-404页

作者： van Dam, Edwin R. Sotirov, Renata Tilburg Univ Dept Econometr & OR Warandelaan 2 NL-5000 LE Tilburg Netherlands

The graph partition problem is the problem of partitioning the vertex set of a graph into a fixed number of sets of given sizes such that the sum of weights of edges joining different sets is optimized. In this paper we simplify a known matrix-lifting semidefinite programming relaxation of the graph partition problem for several classes of graphs and also show how to aggregate additional triangle and independent set constraints for graphs with symmetry. We present an eigenvalue bound for the graph partition problem of a strongly regular graph, extending a similar result for the equipartition problem. We also derive a linear programming bound of the graph partition problem for certain Johnson and Kneser graphs. Using what we call the Laplacian algebra of a graph, we derive an eigenvalue bound for the graph partition problem that is the first known closed form bound that is applicable to any graph, thereby extending a well-known result in spectral graph theory. Finally, we strengthen a known semidefinite programming relaxation of a specific quadratic assignment problem and the above-mentioned matrix-lifting semidefinite programming relaxation by adding two constraints that correspond to assigning two vertices of the graph to different parts of the partition. This strengthening performs well on highly symmetric graphs when other relaxations provide weak or trivial bounds.

关键词： Graph partition problem semidefinite programming Eigenvalues Strongly regular graph Symmetry

来源：评论

学校读者我要写书评

暂无评论

semidefinite programming-based localisation and tracking algorithm using Gaussian mixture modelling

引用

IET COMMUNICATIONS 2017年第16期11卷 2514-2523页

作者： Zhang, Yueyue Zhu, Yaping Xia, Weiwei Yan, Feng Shen, Lianfeng Southeast Univ Natl Mobile Commun Res Lab Nanjing 210096 Jiangsu Peoples R China Beijing Univ Posts & Telecommun State Key Lab Networking & Switching Technol Beijing Peoples R China

In this study, the authors propose a semidefinite programming (SDP)-based localisation and tracking algorithm, which mitigates the non-line-of-sight (NLOS) error of range measurement and calibrates the accumulative error within the inertial sensing data. Both the range measurement in a mixed line-of-sight/NLOS environment and the step length estimated from inertial sensing information are approximated parametrically using Gaussian mixture modelling, and a maximum-likelihood estimator (MLE) is formulated to obtain the optimal position estimation. Since the Gaussian mixture models are non-linear functions of positions, the MLE is a non-convex problem, which global optimum is difficult to attain. Then, the non-convex MLE is transformed into an SDP-based localisation and tracking problem, relying on Jensen's inequality and semidefinite relaxation. Thus, a sub-optimal solution to the original MLE can be achieved. Moreover, the Cramer-Rao lower bound is also derived to serve as a performance indicator for localisation errors. The simulation and experimental results demonstrate the performance of the proposed algorithm. Compared with the existing algorithms, the proposed algorithm owns the best localisation accuracy, and can achieve a sub-metre level accuracy to a root mean square error of 0.46m in the real deployments.

关键词： mathematical programming Gaussian processes mixture models maximum likelihood estimation mean square error methods semidefinite programming tracking algorithm localisation algorithm Gaussian mixture modelling SDP NLOS error inertial sensing data maximum-likelihood estimator MLE optimal position estimation nonlinear functions Jensen's inequality semidefinite relaxation root mean square error

来源：评论

学校读者我要写书评

暂无评论

semidefinite programming hierarchies for constrained bilinear optimization

引用

MATHEMATICAL programming 2022年第1-2期194卷 781-829页

作者： Berta, Mario Borderi, Francesco Fawzi, Omar Scholz, Volkher B. Imperial Coll London Dept Comp London ON Canada Univ Lyon ENS Lyon CNRS UCBLLIP F-69342 Lyon 07 France Univ Ghent Dept Phys Ghent Belgium

We give asymptotically converging semidefinite programming hierarchies of outer bounds on bilinear programs of the form Tr[H(D circle times E)], maximized with respect to semidefinite constraints on D and E. Applied to the problem of approximate error correction in quantum information theory, this gives hierarchies of efficiently computable outer bounds on the success probability of approximate quantum error correction codes in any dimension. The first level of our hierarchies corresponds to a previously studied relaxation (Leung and Matthews in IEEE Trans Inf Theory 61(8):4486, 2015) and positive partial transpose constraints can be added to give a sufficient criterion for the exact convergence at a given level of the hierarchy. To quantify the worst case convergence speed of our sum-of-squares hierarchies, we derive novel quantum de Finetti theorems that allow imposing linear constraints on the approximating state. In particular, we give finite de Finetti theorems for quantum channels, quantifying closeness to the convex hull of product channels as well as closeness to local operations and classical forward communication assisted channels. As a special case this constitutes a finite version of Fuchs-Schack-Scudo's asymptotic de Finetti theorem for quantum channels. Finally, our proof methods answer a question of Brandao and Harrow (Proceedings of the forty-fourth annual ACM symposium on theory of computing, STOC'12, p 307, 2012) by improving the approximation factor of de Finetti theorems with no symmetry from O(d(k/2)) tp poly (d, k), where d denotes local dimension and k the number of copies.

关键词： Quantum error correction De Finetti theorems semidefinite programming Separability problem Bilinear optimization Sum-of-squares hierarchies

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：