Semi-definite Programming

On Time-Invariant Purified-Output-Based Discrete Time Control

  • Aharon Ben-Tal
  • Stephen Boyd
  • Arkadi Nemirovski
    • Categories Control Applications, Convex Optimization, Semi-definite Programming Tags , ,

    In http://www.optimizationonline.org/DB_HTML/2005/05/1136.html 05/25/05, we have demonstrated that the family of all affine non-anticipative output-based control laws in a discrete time linear dynamical system affected by uncertain disturbances is equivalent, as far as state-control trajectories are concerned, to the family of all affine non-anticipative “purified-output-based” control laws. The advantage of the latter representation of affine controls … Read more

    Variational Two-electron Reduced Density Matrix Theory for Many-electron Atoms and Molecules: Implementation of the Spin- and Symmetry-adapted T2 Condition through First-order Semidefinite Programming

  • David A. Mazziotti
    • Categories Constrained Nonlinear Optimization, Semi-definite Programming Tags , ,

    The energy and properties of a many-electron atom or molecule may be directly computed from a variational optimization of a two-electron reduced density matrix (2-RDM) that is constrained to represent many-electron quantum systems. In this paper we implement a variational 2-RDM method with a representability constraint, known as the $T_2$ condition. The optimization of the … Read more

    Embedded in the Shadow of the Separator

  • Frank Göring
  • Christoph Helmberg
  • Markus Wappler
    • Categories Graphs and Matroids, Semi-definite Programming Tags , , , , ,

    We study the problem of maximizing the second smallest eigenvalue of the Laplace matrix of a graph over all nonnegative edge weightings with bounded total weight. The optimal value is the \emph{absolute algebraic connectivity} introduced by Fiedler, who proved tight connections of this value to the connectivity of the graph. Using semidefinite programming techniques and … Read more

    A copositive programming approach to graph partitioning

  • Janez Povh
  • Franz Rendl
    • Categories Approximation Algorithms, Semi-definite Programming Tags , , , ,

    We consider 3-partitioning the vertices of a graph into sets $S_1, S_2$ and $S_3$ of specified cardinalities, such that the total weight of all edges joining $S_1$ and $S_2$ is minimized. This problem is closely related to several NP-hard problems like determining the bandwidth or finding a vertex separator in a graph. We show that … Read more

    Approximation Algorithms for Indefinite Complex Quadratic Maximization Problems

  • Yongwei Huang
  • Shuzhong Zhang
    • Categories Approximation Algorithms, Semi-definite Programming Tags , , ,

    In this paper we consider the following two types of complex quadratic maximization problems: (i) maximize $z^{\HH} Q z$, subject to $z_k^m=1$, $k=1,…,n$, where $Q$ is a Hermitian matrix with $\tr Q=0$ and $z\in \C^n$ is the decision vector; (ii) maximize $\re y^{\HH}Az$, subject to $y_k^m=1$, $k=1,…,p$, and $z_l^m=1$, $l=1,…,q$, where $A\in \C^{p\times q}$ and … Read more

    Complex Matrix Decomposition and Quadratic Programming

  • Yongwei Huang
  • Shuzhong Zhang
    • Categories Semi-definite Programming Tags , , ,

    This paper studies the possibilities of the Linear Matrix Inequality (LMI) characterization of the matrix cones formed by nonnegative complex Hermitian quadratic functions over specific domains in the complex space. In its real case analog, such studies were conducted in Sturm and Zhang in 2003. In this paper it is shown that stronger results can … Read more

    Sparse Covariance Selection via Robust Maximum Likelihood Estimation

  • Onureena Banerjeee
  • Alexandre d'Aspremont
  • Laurent El Ghaoui
    • Categories Convex Optimization, Semi-definite Programming, Statistics Tags , ,

    We address a problem of covariance selection, where we seek a trade-off between a high likelihood against the number of non-zero elements in the inverse covariance matrix. We solve a maximum likelihood problem with a penalty term given by the sum of absolute values of the elements of the inverse covariance matrix, and allow for … Read more

    Analyticity of weighted central path and error bound for semidefinite programming

  • Chek Beng Chua
    • Categories Convex Optimization, Semi-definite Programming Tags , , ,

    The purpose of this paper is two-fold. Firstly, we show that every Cholesky-based weighted central path for semidefinite programming is analytic under strict complementarity. This result is applied to homogeneous cone programming to show that the central paths defined by the known class of optimal self-concordant barriers are analytic in the presence of strictly complementary … Read more

    Semidefinite Bounds for the Stability Number of a Graph via Sums of Squares of Polynomials

  • N. Gvozdenovic
  • Monique Laurent
    • Categories Graphs and Matroids, Semi-definite Programming Tags , ,

    Lov\’ asz and Schrijver [1991] have constructed semidefinite relaxations for the stable set polytope of a graph $G=(V,E)$ by a sequence of lift-and-project operations; their procedure finds the stable set polytope in at most $\alpha(G)$ steps, where $\alpha(G)$ is the stability number of $G$. Two other hierarchies of semidefinite bounds for the stability number have … Read more

    Semidefinite-Based Branch-and-Bound for Nonconvex Quadratic Programming

  • Samuel Burer
  • Dieter Vandenbussche
    • Categories Global Optimization, Quadratic Programming, Semi-definite Programming Tags , , , ,

    This paper presents a branch-and-bound algorithm for nonconvex quadratic programming, which is based on solving semidefinite relaxations at each node of the enumeration tree. The method is motivated by a recent branch-and-cut approach for the box-constrained case that employs linear relaxations of the first-order KKT conditions. We discuss certain limitations of linear relaxations when handling … Read more