This paper studies the representation of a non-negative polynomial f on a non-compact semi-algebraic set K modulo its KKT (Karush-Kuhn-Tucker) ideal. Under the assumption that f satisfies the boundary Hessian conditions (BHC) at each zero of f in K, we show that f can be represented as a sum of squares (SOS) of real polynomials modulo its KKT ideal if f ≥ 0 on K.
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.
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...
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...
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...
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...
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....
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...
This paper deals with the Linear Quadratic Regulator (LQR) problem subject to descriptor systems for which the semidefinite programming approach is used as a solution. We propose a new sufficient condition in terms of primal dual semidefinite programming for the existence of the optimal state-control pair of the problem considered. The results show that semidefinite programming is an elegant method to solve the problem under consideration. Numerical examples are given to illustrate the results.