SDP approach for solving LQ control problem subject to implicit system.
Semidefinite characterisation of invariant measures for one-dimensional discrete dynamical systems
Using recent results on measure theory and algebraic geometry, we show how semidefinite programming can be used to construct invariant measures of one-dimensional discrete dynamical systems (iterated maps on a real interval). In particular we show that both discrete measures (corresponding to finite cycles) and continuous measures (corresponding to chaotic behavior) can be recovered using standard software.
Semidefinite geometry of the numerical range.
Semi-definite positive programming relaxations for graph K-coloring in frequency assignment
In this paper we will describe a new class of coloring problems, arising from military frequency assignment, where we want to minimize the number of distinct -uples of colors used to color a given set of -complete-subgraphs of a graph. We will propose two relaxations based on Semi-Definite Programming models for graph and hypergraph coloring, to approximate those (generally) NP-hard problems, as well as a generalization of the works of Karger et al. for hypergraph coloring, to find good feasible...
Semi-Definite positive Programming Relaxations for Graph Kn-Coloring in Frequency Assignment
In this paper we will describe a new class of coloring problems, arising from military frequency assignment, where we want to minimize the number of distinct n-uples of colors used to color a given set of n-complete-subgraphs of a graph. We will propose two relaxations based on Semi-Definite Programming models for graph and hypergraph coloring, to approximate those (generally) NP-hard problems, as well as a generalization of the works of Karger et al. for hypergraph coloring, to find good feasible...
Semidefinite Programming Based Algorithms for the Sparsest Cut Problem
In this paper we analyze a known relaxation for the Sparsest Cut problem based on positive semidefinite constraints, and we present a branch and bound algorithm and heuristics based on this relaxation. The relaxed formulation and the algorithms were tested on small and moderate sized instances. It leads to values very close to the optimum solution values. The exact algorithm could obtain solutions for small and moderate sized instances, and the best heuristics obtained optimum or near optimum...
Semidefinite Programming Based Algorithms for the Sparsest Cut Problem
In this paper we analyze a known relaxation for the Sparsest Cut problem based on positive semidefinite constraints, and we present a branch and bound algorithm and heuristics based on this relaxation. The relaxed formulation and the algorithms were tested on small and moderate sized instances. It leads to values very close to the optimum solution values. The exact algorithm could obtain solutions for small and moderate sized instances, and the best heuristics obtained optimum or near optimum...
Semidefinite Relaxations of The Traveling Salesman Problem
Shape and topology optimization of the robust compliance via the level set method
The goal of this paper is to study the so-called worst-case or robust optimal design problem for minimal compliance. In the context of linear elasticity we seek an optimal shape which minimizes the largest, or worst, compliance when the loads are subject to some unknown perturbations. We first prove that, for a fixed shape, there exists indeed a worst perturbation (possibly non unique) that we characterize as the maximizer of a nonlinear energy. We also propose a stable algorithm to compute it....
Shape and topology optimization of the robust compliance via the level set method
The goal of this paper is to study the so-called worst-case or robust optimal design problem for minimal compliance. In the context of linear elasticity we seek an optimal shape which minimizes the largest, or worst, compliance when the loads are subject to some unknown perturbations. We first prove that, for a fixed shape, there exists indeed a worst perturbation (possibly non unique) that we characterize as the maximizer of a nonlinear energy. We also propose a stable algorithm to compute...