Previous Page 2

Displaying 21 – 34 of 34

Showing per page

Representations of non-negative polynomials via KKT ideals

Dang Tuan Hiep (2011)

Annales Polonici Mathematici

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.

Semidefinite characterisation of invariant measures for one-dimensional discrete dynamical systems

Didier Henrion (2012)

Kybernetika

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.

Semi-definite positive programming relaxations for graph K 𝐧 -coloring in frequency assignment

Philippe Meurdesoif, Benoît Rottembourg (2001)

RAIRO - Operations Research - Recherche Opérationnelle

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...

Semi-Definite positive Programming Relaxations for Graph Kn-Coloring in Frequency Assignment

Philippe Meurdesoif, Benoît Rottembourg (2010)

RAIRO - Operations Research

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

Luis A.A. Meira, Flávio K. Miyazawa (2011)

RAIRO - Operations Research

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

Luis A.A. Meira, Flávio K. Miyazawa (2011)

RAIRO - Operations Research

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...

Shape and topology optimization of the robust compliance via the level set method

François Jouve, Grégoire Allaire, Frédéric de Gournay (2008)

ESAIM: Control, Optimisation and Calculus of Variations

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

Frédéric de Gournay, Grégoire Allaire, François Jouve (2010)

ESAIM: Control, Optimisation and Calculus of Variations

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...

Use of semidefinite programming for solving the LQR problem subject to rectangular descriptor systems

Muhafzan (2010)

International Journal of Applied Mathematics and Computer Science

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.

Currently displaying 21 – 34 of 34

Previous Page 2