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

Self-Dual Embedding for SDP Using ELSD and Its Lagrangian Dual

Self-Dual Embedding for SDP Using ELSD and Its Lagrangian Du...

The Third International Joint Conference on Computational Science and Optimization(第三届计算科学与优化国际大会 CSO 2010)

作者： Qinghong Zhang Ting Zhang Gang Chen Department of Mathematics and Computer Science Northern Michigan University Marquette MI 49855USA Department of Mathematics Nantong Vocational College Nantong 226007P.R.China

This paper is devoted to the study of an embedding method for semidefinite programming problems using Extended Lagrange-Slater dual (ELSD) and its Lagrangian dual. A theorem proved by de Klerk et al. in 1996 is revisited. A new proof is provided utilizing a result regarding the weak feasibility of a conic linear programming problem.

关键词： semidefinite programming Embedding methods Extended Lagrange-Slater dual Interior-point methods

来源：评论

学校读者我要写书评

暂无评论

Computing the controllability radius: a semi-definite programming approach

引用

IET CONTROL THEORY AND APPLICATIONS 2009年第6期3卷 654-660页

作者： Dumitrescu, B. Sicleru, B. C. Stefan, R. Univ Politehn Bucuresti Dept Automat Control & Comp Bucharest 060042 Romania Tampere Univ Technol Tampere Int Ctr Signal Proc FIN-33101 Tampere Finland

A semi-definite programming (SDP) approach to compute the controllability radius is proposed in this paper. The initial nonconvex optimisation problem is transformed into the minimisation of the smallest eigenvalue of a bivariate real or trigonometric polynomial with matrix coefficients. A sum-of-squares relaxation leads to the SDP formulation. A similar technique is used for the computation of the stabilisability radius. The approach is extended to the computation of the worst-case controllability radius for systems that depend polynomially on a small number of parameters. Experimental results show that the proposed methods compete well with previous ones in a complexity/accuracy trade-off.

关键词： worst-case controllability radius Optimisation techniques eigenvalues and eigenfunctions controllability stability trigonometric polynomial Stability in control theory Linear algebra (numerical analysis) sum-of-square relaxation smallest bivariate real eigenvalue minimisation stabilisability radius concave programming matrix coefficient semidefinite programming nonconvex optimisation problem polynomial matrices

来源：评论

学校读者我要写书评

暂无评论

On Verified Numerical Computations in Convex programming

引用

JAPAN JOURNAL OF INDUSTRIAL AND APPLIED MATHEMATICS 2009年第2-3期26卷 337-363页

作者： Jansson, Christian Hamburg Univ Technol Inst Reliable Comp D-21071 Hamburg Germany

This survey contains recent developments for computing verified results of convex constrained optimization problems, with emphasis on applications. Especially, we consider the computation of verified error bounds for non-smooth convex conic optimization in the framework of functional analysis, for linear programming, and for semidefinite programming. A discussion of important problem transformations to special types of convex problems and convex relaxations is included. The latter are important for handling and for reliability issues in global robust and combinatorial optimization. Some remarks on numerical experiences, including also large-scale and ill-posed problems, and software for verified computations concludes this survey.

关键词： linear programming semidefinite programming conic programming convex programming combinatorial optimization rounding errors ill-posed problems interval arithmetic branch-bound-and-cut

来源：评论

学校读者我要写书评

暂无评论

Knowledge-based semidefinite linear programming classifiers

引用

OPTIMIZATION METHODS & SOFTWARE 2006年第5期21卷 693-706页

作者： Jeyakumar, V. Ormerod, J. Womersley, R. S. Univ New S Wales Sch Math Sydney NSW 2052 Australia

In this paper, we present knowledge-based support vector machine (SVM) classifiers using semidefinite linear programming. SVMs are an optimization-based solution method for large-scale data classification problems. Knowledge-based SVM classifiers, where prior knowledge is in the form of ellipsoidal constraints, result in a semidefinite linear programme with a set containment constraint. These problems are reformulated as standard semidefinite linear programming problems by the application of a dual characterization of the set containment under a mild regularity condition. The reformulated semidefinite linear programme is solved by the publicly available solvers. Computational results show that prior knowledge can often improve correctness of the classifier.

关键词： set containment characterizations support vector machines ellipsoidal knowledge sets semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

On the convergence of the entropy-exponential penalty trajectories and generalized proximal point methods in semidefinite optimization

引用

JOURNAL OF GLOBAL OPTIMIZATION 2009年第2期45卷 211-227页

作者： Ferreira, O. P. Oliveira, P. R. Silva, R. C. M. Univ Fed Amazonas DM ICE BR-69077000 Manaus Amazonas Brazil Univ Fed Rio de Janeiro COPPE Sistemas BR-21945970 Rio De Janeiro Brazil Univ Fed Goias IME BR-74001970 Goiania Go Brazil

The convergence of primal and dual central paths associated to entropy and exponential functions, respectively, for semidefinite programming problem are studied in this paper. It is proved that the primal path converges to the analytic center of the primal optimal set with respect to the entropy function, the dual path converges to a point in the dual optimal set and the primal-dual path associated to this paths converges to a point in the primal-dual optimal set. As an application, the generalized proximal point method with the Kullback-Leibler distance applied to semidefinite programming problems is considered. The convergence of the primal proximal sequence to the analytic center of the primal optimal set with respect to the entropy function is established and the convergence of a particular weighted dual proximal sequence to a point in the dual optimal set is obtained.

关键词： Generalized proximal point methods Bregman distances Central path semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method

引用

DISCRETE APPLIED MATHEMATICS 2009年第6期157卷 1185-1197页

作者： Billionnet, Alain Elloumi, Sourour Plateau, Marie-Christine Conservatoire Natl Arts & Metiers Lab CEDRIC F-75141 Paris France Inst Informat Entreprise Lab CEDRIC F-91025 Evry France

Let (QP) be a 0-1 quadratic program which consists in minimizing a quadratic function subject to linear equality constraints. In this paper, we present QCR, a general method to reformulate (QP) into an equivalent 0-1 program with a convex quadratic objective function. The reformulated problem can then be efficiently solved by a classical branch-and-bound algorithm, based on continuous relaxation. This idea is already present in the literature and used in standard solvers such as CPLEX. Our objective in this work was to find a convex reformulation whose continuous relaxation bound is, moreover, as tight as possible. From this point of view, we show that QCR is optimal in a certain sense. State-of-the-art reformulation methods mainly operate a perturbation of the diagonal terms and are valid for any {0, 1} vector. The innovation of QCR comes from the fact that the reformulation also uses the equality constraints and is valid on the feasible solution domain only. Hence, the superiority of QCR holds by construction. However, reformulation by QCR requires the solution of a semidefinite program which can be costly from the running time point of view. We carry out a computational experience on three different combinatorial optimization problems showing that the costly Computational time of reformulation by QCR can however result in a drastically more efficient branch-and-bound phase. Moreover, our new approach is competitive with very specific methods applied to particular optimization problems. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Quadratic 0-1 programming Convex quadratic programming semidefinite programming Densest k-subgraph Graph bisection Task allocation Experiments

来源：评论

学校读者我要写书评

暂无评论

SUFFICIENT AND NECESSARY CONDITIONS FOR semidefinite REPRESENTABILITY OF CONVEX HULLS AND SETS

引用

SIAM JOURNAL ON OPTIMIZATION 2009年第2期20卷 759-791页

作者： Helton, J. William Nie, Jiawang Univ Calif San Diego Dept Math La Jolla CA 92093 USA

A set S subset of R-n is called semidefinite programming (SDP) representable or semidefinite representable if S equals the projection of a set in higher dimensional space which is describable by some linear matrix inequality (LMI). Clearly, if S is SDP representable, then S must be convex and semialgebraic (it is describable by conjunctions and disjunctions of polynomial equalities or inequalities). This paper proves sufficient conditions and necessary conditions for SDP representability of convex sets and convex hulls by proposing a new approach to constructing SDP representations. The contributions of this paper are: (i) For bounded SDP representable sets W-1, ... , W-m, we give an explicit construction of an SDP representation for conv(U-k=1(m) W-k). This provides a technique for building global SDP representations from the local ones. (ii) For the SDP representability of a compact convex semialgebraic set S, we prove sufficient: the boundary partial derivative S is nonsingular and positively curved, while necessary is: partial derivative S has nonnegative curvature at each nonsingular point. In terms of de. ning polynomials for S, nonsingular boundary amounts to them having nonvanishing gradient at each point on partial derivative S and the curvature condition can be expressed as their strict versus nonstrict quasi-concavity at those points on partial derivative S where they vanish. The gaps between them are partial derivative S having or not having singular points either of the gradient or of the curvature's positivity. A sufficient condition bypassing the gaps is when some de. ning polynomials of S satisfy an algebraic condition called sos-concavity. (iii) For the SDP representability of the convex hull of a compact nonconvex semialgebraic set T, we find that the critical object is partial derivative T-c, the maximum subset of partial derivative T contained in partial derivative conv(T). We prove sufficient for SDP representability: partial derivative T-c is n

关键词： convex set convex hull irredundancy linear matrix inequality nonsingularity positive curvature semialgebraic set semidefinite programming semidefinite representation (strictly) quasi-concavity singularity smoothness sos-concavity sum of squares

来源：评论

学校读者我要写书评

暂无评论

ON THE IMPLEMENTATION OF INTERIOR POINT DECOMPOSITION ALGORITHMS FOR TWO-STAGE STOCHASTIC CONIC PROGRAMS

引用

SIAM JOURNAL ON OPTIMIZATION 2009年第4期19卷 1846-1880页

作者： Mehrotra, Sanjay Ozevin, M. Gokhan Northwestern Univ Dept Ind Engn & Management Sci Evanston IL 60208 USA ZS Associates Evanston IL 60201 USA

In this paper we develop a practical primal interior decomposition algorithm for two-stage stochastic programming problems. The framework of this algorithm is similar to the framework in [S. Mehrotra and M. G. Ozevin, "Decomposition based interior point methods for two-stage stochastic convex quadratic programs with recourse," to appear in Oper. Res.;S. Mehrotra;and M. G. Ozevin, SIAM J. Optim., 18 (2007), pp. 206-222] and [G. Zhao, Math. Program., 90 (2001), pp. 507-536], however, their algorithm is altered in a simple yet fundamental way to achieve practical performance. In particular, this new algorithm weighs the log-barrier terms in the second stage problems differently from the theoretical algorithms analyzed in [S. Mehrotra and M. G. Ozevin, Oper. Res., to appear], [S. Mehrotra and M. G. Ozevin, SIAM J. Optim., 18 (2007), pp. 206-222], and [G. Zhao, Math. Program., 90 (2001), pp. 507-536]. We give a method for generating a suitable starting point;a method for selecting a good starting barrier parameter;a heuristic for first stage step-length calculation without performing line searches;and a method for adaptive addition of new scenarios over the course of the algorithm. The decomposition algorithm is implemented to solve two-stage stochastic conic programs with recourse whose underlying cones are Cartesian products of linear, second order, and semidefinite cones. The performance of primal decomposition method is studied on a set of randomly generated test problems as well as a two-stage stochastic programming extension of the Markowitz portfolio selection model. The computational results show that an efficient and stable implementation of the primal decomposition method is possible. These results also show that in problems with a large number of scenarios, the adaptive addition of scenarios can yield computational savings of up to 80%.

关键词： stochastic programming conic programming semidefinite programming Benders decomposition interior point methods primal-dual methods

来源：评论

学校读者我要写书评

暂无评论

Symmetry in semidefinite programs

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2009年第1期430卷 360-369页

作者： Vallentin, Frank CWI NL-1098 SJ Amsterdam Netherlands

This paper is a tutorial in a general and explicit procedure to simplify semidefinite programs which are invariant under the action of a symmetry group. The procedure is based on basic notions of representation theory of finite groups. As an example we derive the block diagonalization of the Terwilliger algebra of the binary Hamming scheme in this framework. Here its connection to the orthogonal Hahn and Krawtchouk polynomials becomes visible. (C) 2008 Elsevier Inc. All rights reserved.

关键词： semidefinite programming Block diagonalization Terwilliger algebra Binary Hamming scheme Hahn polynomials

来源：评论

学校读者我要写书评

暂无评论

Efficient Design of Cosine-Modulated Filter Banks via Convex Optimization

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2009年第3期57卷 966-976页

作者： Kha, Ha Hoang Tuan, Hoang Duong Nguyen, Truong Q. Univ New S Wales Sch Elect Engn & Telecommun Sydney NSW 2052 Australia Univ Calif San Diego Dept Elect & Comp Engn La Jolla CA 92093 USA

This paper presents efficient approaches for designing cosine-modulated filter banks with linear phase prototype filter. First, we show that the design problem of the prototype filter being a spectral factor of 2 Mth-band filter is a nonconvex optimization problem with low degree of nonconvexity. As a result, the nonconvex optimization problem can be cast into a semi-definite programming (SDP) problem by a convex relaxation technique. Then the reconstruction error is further minimized by an efficient iterative algorithm in which the closed-form expression is given in each iteration. Several examples are given to illustrate the effectiveness of the proposed method over the existing ones.

关键词： Convex optimization cosine-modulated filter bank prototype filter semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：