|
 Bas
Ecole
CIMPA-UNESCO-PHILIPPINES
Programmation semidéfinie en
combinatoire algébrique
Objectifs :
Dans les années 70, une contribution fondamentale de
Philippe Delsarte a été une méthode de Combinatoire Algébrique qui procure
des bornes sur la taille des codes correcteurs de distance minimale donnée
comme solutions d’un problème de Programmation
Linéaire. La méthode de Delsarte aussi connue sous
le nom méthode polynomiale fut développée dans le cadre des
Schémas d’association, qui est
le cadre le plus général pour traiter les espaces métriques finis. Cette
méthode donne aussi des bornes dans des situations plus générales comme des
bornes sur la taille des designs (combinatoires ou sphériques). Elle permet
de traduire des problèmes d’espaces métriques finis ayant de fortes
propriétés de régularité/symétrie (comme le schéma de Hamming pour les codes
ou le schéma de Johnson pour les designs) en problèmes spectraux d’algèbre
linéaire. Lesdits problèmes peuvent s’approcher par des méthodes de
fonctions spéciales en particulier certain des familles de polynômes
orthogonaux en une variable discrète (Krawtchouk pour les codes, Hahn pour
les designs) et leurs zéros extrémaux. L’algèbre de matrices pertinente dans
ce cas est l’algèbre de Bose Mesner. Depuis les années 90 une autre algèbre
est a la mode pour les schémas d’association : l’algèbre de
Terwilliger. La
Programation SemiDéfinie
(abrégé SDP) constitue une famille de problèmes d'optimisation qui sont
maintenant solvables en temps polynomial. De nouveaux algorithmes fondés sur
des méthodes de point intérieur sont d’une efficacité raisonnable en
pratique. SDP contient LP comme sous classe. Plus précisément un SDP peut se
formuler la manière suivante soient A0,A1,
. . . ,An des
matrices réelles symétriques et b1,
. . . , bn des
réels. On cherche le minimum d’une fonction objectif
b1x1
+. . .+bnxn
sur l’ensemble convexe
A0 +
x1A1
+ . . .
+ xnAn
≥ 0, o`u la notation
A ≥
0 signifie que les valeurs propres de
A sont ≥
0.
L’approche SDP de certains problèmes d’optimisation
combinatoire est connue depuis plusieurs décennies. les nouveaux algorithmes
ont donné lieu à des relaxations solvables en temps polynomial de problèmes
de calculs difficiles d’invariants de graphes comme le nombre de stabilité,
la coloration, la coupe maximum.
Dans cette Ecole d’Eté on se concentrera
sur les problèmes d’empilement de sphères qui ont bénéficié du passage de LP
à SDP. Nous pensons que cette approche se révèlera féconde pour les jeunes
chercheurs d’aujourd’hui.
Organisateurs :
Christine Bachoc (Université de Bordeaux I, France),
William Martin ( Worcester Polytechnic Institute, USA), Patrick Solé (CNRS,
Nice, France)
Organisateur local :
Jose Maria “Joey” Balmaceda (UP, Manille, Philippines)
Langue de travail :
Anglais
Date et lieu :
20 juillet-3 août 2009,
Université des
Philippines,
Manille, Philippines
Programme scientifique : (résumés)
-
Christine Bachoc (Bordeaux I, France) :
Applications des polynômes orthogonaux à plusieurs variables
-
Eiichi Bannai (Kyushu University, Japon) :
Etat de l'art des designs sphériques
- Henry Cohn
(Microsoft Research, USA) : Distribution de points sur
les sphères
- William Martin
(Worcester Polytechnic Institute, USA) :
Programmation linéaire et énumérateur des poids double
- Dimitrii
Pasechnik (Nanyang Technical University, Singapour) :
Introduction à la programmation semidéfinie
- Edward B. Saff
(Vanderbilt University, USA) : Problèmes discrets de minimisation d'énergie
- Frank
Vallentin (CWI, Amsterdam, Pays-Bas) : Applications
de programmation semidéfinie
Prérequis :
Maîtrise de Math ou d’Informatique.
Date limite d'inscription :
30 avril
2009
Modalité d'inscription et
Inscription en ligne
uniquement pour les non locaux.
Les inscriptions des candidats des Philippines doivent se faire localement.
Personne à contacter :
Jose Maria “Joey” Balmaceda
 Haut
CIMPA
Le Dubellay, 4 avenue Joachim - Bât. B, 06100 Nice, FRANCE
Pour toute remarque, écrivez à
cimpa@unice.fr
Copyright © 1999 [CIMPA]. Tous droits réservés.
Révision :
lundi 02 juin 2008 .
|
PHILIPPINES 2009