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

New complexity analysis of a Mehrotra-type predictor-corrector algorithm for semidefinite programming

OPTIMIZATION METHODS & SOFTWARE 2013年第6期28卷 1179-1194页

作者： Liu, Hongwei Liu, Changhe Yang, Ximei Xidian Univ Dept Math Xian Peoples R China Henan Univ Sci & Technol Dept Appl Math Luoyang Peoples R China

In this paper, we propose a new Mehrotra-type predictor-corrector interior-point algorithm for semidefinite programming. This algorithm is an extension of the variant of Mehrotra-type algorithm that was proposed by Salahi et al. [On Mehrotra-type predictor-corrector algorithms, SIAM J. Optim. 18 (2007), pp. 1377-1397] for linear programming problems. We modify the step sizes lightly in the predictor step of Koulaei and Terlaky [On the complexity analysis of a Mehrotra-type primal-dual feasible algorithm for semidefinite optimization, Optim. Methods Softw. 25 (2010), pp. 467-485]. In such a way, we obtain O(nlog(Tr((XS0)-S-0)/E)) iteration complexity of the algorithm, where (X-0, y(0), S-0) is the initial feasible point and E is the required precision.

关键词： semidefinite programming interior-point methods predictor-corrector algorithm Mehrotra-type algorithm polynomial complexity 65K05 90C22 90C51

来源：评论

学校读者我要写书评

暂无评论

CSDP, a C library for semidefinite programming

引用

OPTIMIZATION METHODS & SOFTWARE 1999年第1-4期11-2卷 613-623页

作者： Borchers, B New Mexico Tech Dept Math Socorro NM 87801 USA

This paper describes CSDP, a library of routines that implements a predictor corrector variant of the semidefinite programming algorithm of Helmberg, Rendl, Vanderbei, and Wolkowicz. The main advantages of this code are that it can be used as a stand alone solver or as a callable subroutine, that it is written in C for efficiency, that it makes effective use of sparsity in the constraint matrices, and that it includes support for linear inequality constraints in addition to linear equality constraints. We discuss the algorithm used, its computational complexity, and storage requirements. Finally, we present benchmark results for a collection of test problems.

关键词： semidefinite programming interior point method predictor-corrector method

来源：评论

学校读者我要写书评

暂无评论

A direct formulation for sparse PCA using semidefinite programming

引用

SIAM REVIEW 2007年第3期49卷 434-448页

作者： d'Aspremont, Alexandre El Ghaoui, Laurent Jordan, Michael I. Lanckriet, Gert R. G. Princeton Univ Dept Operat Res & Financial Engn Princeton NJ 08544 USA Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94720 USA Univ Calif Berkeley Dept EECS & Stat Berkeley CA 94720 USA Univ Calif San Diego Dept Elect & Comp Engn La Jolla CA 92093 USA

Given a covariance matrix, we consider the problem of maximizing the variance explained by a particular linear combination of the input variables while constraining the number of nonzero coefficients in this combination. This problem arises in the decomposition of a covariance matrix into sparse factors or sparse principal component analysis (PCA), and has wide applications ranging from biology to finance. We use a modification of the classical variational representation of the largest eigenvalue of a symmetric matrix, where cardinality is constrained, and derive a semidefinite programming-based relaxation for our problem. We also discuss Nesterov's smooth minimization technique applied to the semidefinite program arising in the semidefinite relaxation of the sparse PCA problem. The method has complexity O(n(4) root log(n)/epsilon), where n is the size of the underlying covariance matrix and e is the desired absolute accuracy on the optimal value of the problem.

关键词： principal component analysis Karhunen-Loeve transform factor analysis semidefinite relaxation Moreau-Yosida regularization semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

Low-rank exploitation in semidefinite programming for control

引用

INTERNATIONAL JOURNAL OF CONTROL 2011年第12期84卷 1975-1982页

作者： Falkeborn, Rikard Lofberg, Johan Hansson, Anders Linkoping Univ Dept Elect Engn Div Automat Control SE-58183 Linkoping Sweden

Many control-related problems can be cast as semidefinite programs. Even though there exist polynomial time algorithms and excellent publicly available solvers, the time it takes to solve these problems can be excessive. What many of these problems have in common, in particular in control, is that some of the variables enter as matrix-valued variables. This leads to a low-rank structure in the basis matrices which can be exploited when forming the Newton equations. In this article, we describe how this can be done, and show how our code, called STRUL, can be used in conjunction with the semidefinite programming solver SDPT3. The idea behind the structure exploitation is classical and is implemented in LMI Lab, but we show that when using a modern semidefinite programming framework such as SDPT3, the computational time can be significantly reduced. Finally, we describe how the modelling language YALMIP has been changed in such a way that our code, which can be freely downloaded, can be interfaced using standard YALMIP commands. This greatly simplifies modelling and usage.

关键词： optimization semidefinite programming linear matrix inequalities interior point methods modeling software

来源：评论

学校读者我要写书评

暂无评论

Uniqueness of codes using semidefinite programming

引用

DESIGNS CODES AND CRYPTOGRAPHY 2019年第8期87卷 1881-1895页

作者： Brouwer, Andries E. Polak, Sven C. Univ Amsterdam Korteweg De Vries Inst Math Amsterdam Netherlands

Forn,d,wN, letA(n,d,w) denote the maximum size of a binary code of word lengthn, minimum distanced and constant weightw. Schrijver recently showed using semidefinite programming that A(23,8,11)=1288, and the second author thatA(22,8,11)=672 andA(22,8,10)=616. Here we show uniqueness of the codes achieving these bounds. LetA(n,d) denote the maximum size of a binary code of word lengthn and minimum distanced. Gijswijt et al. showed thatA(20,8)=256. We show that there are several nonisomorphic codes achieving this bound, and classify all such codes with all distances divisible by 4.

关键词： Code Binary code Uniqueness semidefinite programming Golay

来源：评论

学校读者我要写书评

暂无评论

Applications of gauge duality in robust principal component analysis and semidefinite programming

引用

Science China Mathematics 2016年第8期59卷 1579-1592页

作者： MA ShiQian YANG JunFeng Department of Systems Engineering and Engineering Management The Chinese University of Hong Kong Department of Mathematics Nanjing University

Gauge duality theory was originated by Preund （1987）, and was recently further investigated by Friedlander et al. （2014）. When solving some matrix optimization problems via gauge dual, one is usually able to avoid full matrix decompositions such as singular value and/or eigenvalue decompositions. In such an approach, a gauge dual problem is solved in the first stage, and then an optimal solution to the primal problem can be recovered from the dual optimal solution obtained in the first stage. Recently, this theory has been applied to a class of semidefinite programming （SDP） problems with promising numerical results by Friedlander and Mac^to （2016）. We establish some theoretical results on applying the gauge duality theory to robust principal component analysis （PCA） and general SDP. For each problem, we present its gauge dual problem, characterize the optimality conditions for the primal-dual gauge pair, and validate a way to recover a primal optimal solution from a dual one. These results are extensions of Friedlander and Macedo （2016） from nuclear norm regularization to robust PCA and from a special class of SDP which requires the coefficient matrix in the linear objective to be positive definite to SDP problems without this restriction. Our results provide further understanding in the potential advantages and disadvantages of the gauge duality theory.

关键词： gauge optimization gauge duality polar function antipolar set singular value decomposition robust principal component analysis semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

An exact duality theory for semidefinite programming and its complexity implications

引用

MATHEMATICAL programming 1997年第2期77卷 129-162页

作者： Ramana, MV Center for Applied Optimization 303 Weil Hall Department of Industrial and Systems Engineering University of Florida Gainesville USA

In this paper, an exact dual is derived for semidefinite programming (SDP), for which strong duality properties hold without any regularity assumptions. Its main features are: (i) The new dual is an explicit semidefinite program with polynomially many variables and polynomial size coefficient bitlengths. (ii) If the primal is feasible, then it is bounded if and only if the dual is feasible. (iii) When the primal is feasible and bounded, then its optimum value equals that of the dual, or in other words, there is no duality gap. Further, the dual attains this common optimum value. (iv) It yields a precise theorem of the alternative for semidefinite inequality systems, i.e. a characterization of the infeasibility of a semidefinite inequality in terms of the feasibility of another polynomial size semidefinite inequality. The standard duality for linear programming satisfies all of the above features, but no such explicit gap-free dual program of polynomial size was previously known for SDP, without Slater-like conditions being assumed. The dual is then applied to derive certain complexity results for SDP. The decision problem of semidefinite Feasibility (SDFP), which asks to determine if a given semidefinite inequality system is feasible, is the central problem of interest, he complexity of SDFP is unknown, but we show the following: (i) In the Turing machine model, the membership or nonmembership of SDFP in NP and Co-NP is simultaneous;hence SDFP is not NP-Complete unless NP = Co-NP. (ii) In the real number model of Blum, Shub and Smale, SDEP is in NP boolean AND Co-NP. (C) 1997 The Mathematical programming Society, Inc. Published by Elsevier Science B.V.

关键词： semidefinite programming strong duality complexity classes theorems of the alternative

来源：评论

学校读者我要写书评

暂无评论

A note on semidefinite programming relaxations for polynomial optimization over a single sphere

引用

Science China Mathematics 2016年第8期59卷 1543-1560页

作者： HU Jiang JIANG Bo LIU Xin WEN ZaiWen Beijing International Center for Mathematical Research Peking University Research Center for Management Science and Data Analytics School of Information Management and EngineeringShanghai University of Finance and Economics LSEC Institute of Computational Mathematics and Scientific/Engineering ComputingAcademy of Mathematics and Systems Science Chinese Academy of Sciences

We study two instances of polynomial optimization problem over a single sphere. The first problem is to compute the best rank-1 tensor approximation. We show the equivalence between two recent semidefinite relaxations methods. The other one arises from Bose-Einstein condensates(BEC), whose objective function is a summation of a probably nonconvex quadratic function and a quartic term. These two polynomial optimization problems are closely connected since the BEC problem can be viewed as a structured fourth-order best rank-1 tensor approximation. We show that the BEC problem is NP-hard and propose a semidefinite relaxation with both deterministic and randomized rounding procedures. Explicit approximation ratios for these rounding procedures are presented. The performance of these semidefinite relaxations are illustrated on a few preliminary numerical experiments.

关键词： polynomial optimization over a single sphere semidefinite programming best rank-1 tensor ap-proximation Bose-Einstein condensates

来源：评论

学校读者我要写书评

暂无评论

A semidefinite programming approach to optimal unambiguous discrimination of quantum states

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2003年第2期49卷 446-456页

作者： Eldar, YC MIT Elect Res Lab Cambridge MA 02139 USA

In this paper, we consider the problem. of unambiguous discrimination between a set of linearly independent pure quantum states. We show that the design of the optimal measurement that minimizes the probability of an inconclusive result can be formulated as a semidefinite programming problem. Based on this formulation, we develop a set of necessary and sufficient conditions for an optimal quantum measurement. We show that the optimal measurement can be computed very efficiently in polynomial time by exploiting the many well-known algorithms for solving semidefinite programs, which are guaranteed to converge to the global optimum. Using the general conditions for optimality, we derive necessary and sufficient conditions so that the measurement that results in an equal probability of an inconclusive result for each one of the quantum states is optimal. We refer to this measurement as the equal-probability measurement (EPM). We then show that for any state set, the prior probabilities of the states can be chosen such that the EPM is optimal. Finally, we consider state sets with strong symmetry properties and equal prior probabilities for which the EPM is optimal. We first consider geometrically uniform (GU) state sets that are defined over a group of unitary matrices and are generated by a single generating vector. We then consider compound GU state sets which are generated by a group of unitary matrices using multiple generating vectors, where the generating vectors satisfy a certain (weighted) norm constraint.

关键词： compound geometrically uniform (CGU) quantum states equal-probability measurement (EPM) geometrically uniform (GU) quantum states quantum detection semidefinite programming unambiguous discrimination

来源：评论

学校读者我要写书评

暂无评论

An improved semidefinite programming relaxation for the satisfiability problem

引用

MATHEMATICAL programming 2005年第3期102卷 589-608页

作者： Anjos, MF Univ Waterloo Waterloo ON N2L 3G1 Canada

The satisfiability (SAT) problem is a central problem in mathematical logic, computing theory, and artificial intelligence. An instance of SAT is specified by a set of boolean variables and a propositional formula in conjunctive normal form. Given such an instance, the SAT problem asks whether there is a truth assignment to the variables such that the formula is satisfied. It is well known that SAT is in general NP-complete, although several important special cases can be solved in polynomial time. semidefinite programming (SDP) refers to the class of optimization problems where a linear function of a matrix variable X is maximized (or minimized) subject to linear constraints on the elements of X and the additional constraint that X be positive semidefinite. We are interested in the application of SDP to satisfiability problems, and in particular in how SDP can be used to detect unsatisfiability. In this paper we introduce a new SDP relaxation for the satisfiability problem. This SDP relaxation arises from the recently introduced paradigm of "higher liftings" for constructing semidefinite programming relaxations of discrete optimization problems. To derive the SDP relaxation, we first formulate SAT as an optimization problem involving matrices. Relaxing this formulation yields an SDP which significantly improves on the previous relaxations in the literature. The important characteristics of the SDP relaxation are its ability to prove that a given SAT formula is unsatisfiable independently of the lengths of the clauses in the formula, its potential to yield truth assignments satisfying the SAT instance if a feasible matrix of sufficiently low rank is computed, and the fact that it is more amenable to practical computation than previous SDPs arising from higher liftings. We present theoretical and computational results that support these claims.

关键词： semidefinite programming satisfiability discrete optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：