In this paper, we use fixed point theory and semidefinite programming to compute the performance bounds on convex block-sparsity recovery algorithms. As a prerequisite for optimal sensing matrix design, computable per...
详细信息
In this paper, we use fixed point theory and semidefinite programming to compute the performance bounds on convex block-sparsity recovery algorithms. As a prerequisite for optimal sensing matrix design, computable performance bounds would open doors for wide applications in sensor arrays, radar, DNA microarrays, and many other areas where block-sparsity arises naturally. We define a family of quality measures for arbitrary sensingmatrices as the optimal values of certain optimization problems. The reconstruction errors of convex recovery algorithms are bounded in terms of these quality measures. We demonstrate that as long as the number of measurements is relatively large, these quality measures are bounded away from zero for a large class of random sensing matrices, a result parallel to the probabilistic analysis of the block restricted isometry property. As the primary contribution of this work, we associate the quality measures with the fixed points of functions defined by a series of semidefinite programs. This relation with fixed point theory yields polynomia-ltime algorithms with global convergence guarantees to compute the quality measures.
We address the exact semidefinite programming feasibility problem (SDFP) consisting in checking that intersection of the cone of positive semidefinite matrices and some affine subspace of matrices with rational entrie...
详细信息
We address the exact semidefinite programming feasibility problem (SDFP) consisting in checking that intersection of the cone of positive semidefinite matrices and some affine subspace of matrices with rational entries is not empty. SDFP is a convex programming problem and is often considered as tractable since some of its approximate versions can be efficiently solved, e.g. by the ellipsoid algorithm. We prove that SDFP can decide comparison of numbers represented by the arithmetic circuits, i.e. circuits that use standard arithmetical operations as gates. Our reduction may give evidence to the intrinsic difficulty of SDFP (contrary to the common expectations) and clarify the complexity status of the exact SDP - an old open problem in the field of mathematical programming. (C) 2007 Elsevier B.V. All rights reserved.
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 transfo...
详细信息
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.
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 wel...
详细信息
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.
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 the...
详细信息
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.
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 provi...
详细信息
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.
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 (SD...
详细信息
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.
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 de...
详细信息
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.
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 gr...
详细信息
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
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 ...
详细信息
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.
暂无评论