Discussion Group

every tuesday morning, at 10:00, in the conference room MIP (second floor, building 1R3)

=======

2010

=======

  • June, 22nd (GT A2OC): Xiaoming Yuan (university Baptiste, Hong Kong) - Recovering Low-rank and Sparse Components of Matrices
    • Abstract: "Many applications arising in a variety of fields (e.g. Image Processing, Statistics, Computer Visualization) can be well illustrated by the task of recovering the low-rank and sparse components of a given matrix. We consider both the easy case where all entries of the matrix to be recovered are known without noise, and the general case where only a fraction of entries of the matrix to be recovered can be observed and the observation is corrupted by both impulsive and Gaussian noise. We present convex relaxation models of these NP-hard problems and propose some augmented-Lagrangian-based algorithms to achieve the recovery task efficiently and effectively. "
  • June, 18th: Regis Cereghino and Eric Tabacchi (Ecolab) - Ecologie des communautés et théorie des graphes : questions et perspectives (2)
  • June, 17th: Marcel Mongeau - The averaged problem (joint work with Ken McKinnon, University of Edinburgh)
    • Abstract: "We consider in this talk a particular global optimization problem whose special structure permits the use of a decomposition algorithm optimizing globally only in search spaces of lower dimension. We call this problem the averaged problem. Roughly speaking, this problem involves the optimization of a weighted average of objective function values, subject to the same weighted average of constraints, where the weights are to be determined. This problem was introduced by Whittle four decades ago in order to take into account Lagrangian duality when convexity is lacking. Various applications motivate our study. Special instances of the averaged problem are the phase and chemical equilibrium problem in chemical engineering, and resource allocation among many processes for producing a material. Classical linear programming is itself a special case of the averaged problem. The algorithm GILO (Global Improvement Local Optimization) was introduced by McKinnon and Mongeau as an alternative to solving the difficult phase and chemical equilibrium problem as a single global optimization problem in high dimension. GILO rather iterates between a local minimization problem and a global search in a lower dimensional space, taking advantage of the special structure of the problem. Under mild assumptions, the GILO algorithm is guaranteed to find the global minimum. Incidentally, the algorithm GILO can be viewed as an extension of the simplex method for linear programming as presented by Dantzig in its fundamental book when evoking the simplex interpretation of the simplex method. The global optimization algorithm we shall present is a further generalization. The proofs behind GILO relied on specific properties of the thermodynamical functions (involved in the objective function) that are not readily extendable to the more general case of the averaged problem. In this talk , we shall present the theoretical results that yield to the GILO algorithm and we shall introduce its extension to the more general averaged problem. I would be happy to hear about a potential application of this work to economy..."
  • June, 8th (GT A2OC): Paul Armand (University of Limoges) - Local path-following property of inexact interior methods in nonlinear programming
    • Abstract: "we study the local behavior of a primal-dual inexact interior point methods for solving systems arising from the solution of nonlinear optimization problems or more generally from nonlinear complementarity problems. The algorithm is based on the Newton method applied to a sequence of perturbed systems that follows by perturbation of the complementarity equations of the original system. In case of an exact solution of the Newton system, it has been shown that the sequence of iterates is asymptotically tangent to the central path (Armand and Benoist, Math Program 115:199{222, 2008). The purpose of the present talk is to extend this result to an inexact solution of the Newton system. We give quite general conditions on the different parameters of the algorithm, so that this asymptotic property is satisfied. We illustrate our theoretical results by means of some numerical results."
  • June, 4th: Bertrand Jouve (IMT) - Tournois critiquement primitifs
  • June, 1st: Li-Da Tong (University of Sun Yat-sen, Kaohsiung, Taiwan) - Non-blocking interconnection networks and graph colorings - slides Δ
    • Abstract: "The Banyan-type networks are built by basic 2x2 directional couplers with the network structure topology derived from a horizontal expansion and vertical stacking of 2x2 Banyan networks. Some necessary and sufficient conditions of Banyan-type networks which are rearrangeably nonblocking that haves been proposed for optical interconnection network fabrics, where these rearrangeably nonblocking conditions are well-supported assuming that all the connections are not allowed to have any crosstalk. In this talk, we use the coloring methods to study the necessary and sufficient conditions for Banyan-type networks, which are rearrangeable nonblocking by considering all possible degrees of crosstalk constraints."
  • May, 21th: demi-journée Tournois indécomposables et primitifs - Abstract Δ (french)
    • Pierre Ille (CNRS IML) - Sur la décomposition des tournois
    • Abderrahim Boussairi (University of Casablanca) - C3-structure des tournois
  • May, 18th: Eric Tabacchi(approve sites) (Ecolab) - Ecologie des communautés et théorie des graphes : questions et perspectives
    • Abstract (french): "Notre objectif étant plus une prise de contact qu'un exposé formel : L'application de la théorie des graphes à l'Ecologie est relativement récente en tant que méthode d'investigation, bien que la représentation en graphe soit utilisée de longue date dans cette discipline. Dans cette prise de contact avec les Mathématiques Appliquées, l'équipe CIRCE du laboratoire Ecolab (UMR 5245) souhaite proposer quelques réflexions autour de leur objet d'étude, la communauté écologique. Cette dernière correspond à un assemblage interactif d'espèces d'organismes vivants exploitant des ressources environnementales d'un même habitat. Ce concept s'avère très approprié à la représentation sous forme de graphe, dont les sommets sont les espèces et les liens correspondent aux relations écologiques (compétition, flux d'échange, communication...). L'a présentation vise à exposer brièvement les concepts afférents à la communauté écologique, et à ouvrir une discussion sur les possibilités d'application de la théorie des graphes pour résoudre quelques questions centrales en écologie fondamentale et appliquée. Les perspectives de collaboration inter-disciplinaire sont également évoquées. "
  • May, 11th (GT A2OC): Vincent Baudoui (ONERA) - Modèles réduits pour l'optimisation robuste multidisciplinaire
    • Abstract (french): "La prise en compte d'incertitudes dans l'optimisation d'un système complexe peut se révéler problématique, car elle ajoute une difficulté supplémentaire à un problème qui est déjà loin d'être simple. Nous proposons un compromis permettant d'introduire un certain degré de robustesse au sein d'une optimisation sans nécessiter de trop grandes modifications du processus de résolution initial. Des méthodes d'estimation de la robustesse basées sur des modèles réduits (ou modèles de substitution) seront comparées, puis une application à un cas-test en optimisation multidisciplinaire de design d'avion sera finalement présentée."
  • March, 30th: Jacqueline Lacaze - Démontages - slides Δ
    • Abstract (french) - La notion de démontabilité est apparue dans des contextes très diffrérents liés, par exemple, à l'étude de certaines propriétés de graphes ou bien à l'étude homotopique des posets. On décrira le rapport entre ces différentes approches ainsi qu'avec la notion de "strong collapse" introduite par Barmak et Minian en 2009, dans le cadre des complexes simpliciaux.
  • March, 12th: Mohamed Masmoudi - Le gradient topologique et son application à la théorie des graphes
    • Abstract (french): Je commence par présenter le gradient topologique et ses applications à la recherche d'une forme optimale. Ensuite, je montre que l'algorithme de transport, bien connu en théorie des graphes et en recherche opérationnelle, est un cas particulier du gradient topologique. L'algorithme de transport peut être utilisé pour résoudre le problème de transport optimal qui mobilise de nombreux chercheurs à l'échelle internationale et à l'IMT.
  • March, 5th: Petru Valicov - MPQ-arbres pour les problèmes de placement orthogonal
    • Abstract (french):Le problème de placement orthogonal bi-dimensionnel consiste à décider si un ensemble d'items rectangulaires peut être placé dans un conteneur rectangulaire sans dépassement et sans chevauchement. Nous allons présenter un nouvel algorithme résolvant ce problème. L'algorithme est basé sur la caractérisation des placements réalisables avec les graphes d'intervalles, du à Fekete et Schepers. Dans un premier temps je vais expliquer le modèle de Fekete et Schepers pour continuer sur les détails de notre travail consistant à exploiter les MPQ-arbres, structures combinatoires utilisée pour la reconnaissance des graphes d'intervalles en temps O(|V|+|E|) [pour G=(V,E)].
  • February 12th: Giles Baroin - Invention d’un modèle géométrique original de représentation de relations harmoniques musicales par la théorie des graphes (2e Partie : Quaternions, Graphes et Musique)
    • Abstract (french):
      • Mots clefs: Musique, Quaternions, Décomposition spectrale, Graphes de Cayley, Géométrie euclidienne multi- dimensionnelle, Théorème de Nöther, Visualisation 4D
      • Résumé de la 1ére Partie: Nous avons montré au cours d’un raisonnement pas à pas, illustré d’exemples musicaux, que l’ensemble des 12 notes peut se représenter pertinemment par un graphe que j’ai baptisé «Planet Graph». La représentation d’un de ses espaces propres étant connue depuis longtemps, bien avant les graphes, et utilisée pour certaines compositions musicales.
      • Résumé de la 2éme Partie
        • Trois applications musicales du théorème de Nöther - Perception appréciable aussi par le non mélomane
        • Recherche d’un modèle par quaternions - Transformation en graphe d’un ensemble de quaternions répondant aux conditions initiales, puis visualisation des projections spectrales de ce graphe.
        • Présentation musicale du modèle 4D -Dualité espace des notes / espace des accords, écoute des espaces. Cycles triviaux C3 et C4. Graphes et Cycles sous jacents.
      • La présentation sera illustrée d’exemples sonores et de films en images de synthèse.
  • February 5th: Frédéric Messine - Les Trois Petits Octogones
    • Abstract (french): En 2009 avec Charles Audet et Pierre Hansen, nous avons publié dans Pour la Science un article dont voici le résumé : Là où le raisonnement géométrique s'épuise, l'ordinateur supplée, comme l'illustre l'histoire des trois petits octogones.
      Quel octogone de diamètre unité (ou petit octogone) possède la plus grande surface ou le plus grand périmètre? Serait-ce l'octogone régulier? Eh! non, il n'en est rien. Nous convions donc le lecteur à une passionnante chasse aux petits octogones, expédition qui débute en 1922 avec les travaux de Karl Reinhardt, de l'Université de Frankfurt am Main, se poursuit en 1950 grâce à l'octogone de la mystérieuse femme de Stephen Vincze (lui même de l'Université de Budapest), reprend vigueur en 1975 lorsque Ron Graham, de AT\&T Bell Labs, découvre le petit hexagone le plus étendu et aboutit ces dernières années par la conjonction de méthodes géométriques et d'algorithmes d'optimisation globale.
      C'est à la suite d'une conférence de Ron Graham sur le rôle de l'ordinateur en mathématique, présentée à l'Université Rutgers à la fin des années 1980, que le second auteur (P. Hansen) s'est intéressé aux petits polygones. Au cours d'une discussion avec le conférencier, fort sceptique, il a émis l'hypothèse que le petit octogone de surface maximale pourrait être déterminé à l'aide de méthodes d'optimisation globale. C'est bien ce qui s'est passé... plus de 10 ans plus tard.
      Notre intérêt pour les petits octogones est triple: d'abord relever le défit de résoudre des problèmes ouverts depuis fort longtemps; ensuite, de disposer de problèmes tests pour évaluer les performances d'algorithmes d'optimisation globale; enfin, d'améliorer la résolution de problèmes pratiques. Pour illustrer ce dernier point, citons l'étude de petits polygones permettant d'obtenir une pièce de un dollar idéale, due à Michael Mossinghoff, du Davidson College, En Caroline du Nord. En fin d'article, nous discuterons d'une autre application dans l'industrie verrière.
      Le fait de centrer le discours sur les 3 petits octogones donnera une introduction aux problemes plus generaux aux sujets des proprietes des polygones convexes ou non, réguliers ou non.
    • February 5th, 16h (Le Mirail): Giles Baroin - De Newton à Riemann, Graphes et Graphisme, Interactions Mathématico-Musico-Plastiques.
  • January 29th: Bilal Said (PhD defense) - Réécriture de graphes pour la construction de modèles en logique modale
  • January 22nd: Gilles Baroin - Invention d'un modèle géométrique original de représentation de relations harmoniques par la théorie des graphes
  • January 8th: Jordan Ninin - Méthode de Branch&Bound par intervalles
    • Abstract (french): Depuis quelques années, les algorithmes de branch and bound par intervalles ont montré leur intérêt pour la résolution exacte de problèmes contraints d’optimisation globale ; en effet, le caractère robuste aux erreurs numériques de ces algorithmes permet de garantir l’obtention de l’optimum global à la précision souhaitée par l’utilisateur. Cependant, ces méthodes nécessitent parfois beaucoup de temps CPU, c’est pourquoi l’intégration de méthode d’accélération s’avère généralement indispensable. Nous reviendrons sur différentes techniques de réduction de boites basées sur la propagation des contraintes, ainsi que des techniques de calcul de borne basées sur des relaxations linéaires.

=======

2009

=======

  • December 11th: Philippe Toint - Une nouvelle méthode d'optimisation sans dérivées
    • Abstract (french): Une classe importante de méthodes d'optimisation sans dérivées se base sur l'interpolation locale pour construire une modèle de la fonction objective. La géométrie de ces points d'interpolation est un paramètre crucial pour obtenir une méthode numérique efficace. Nous discuterons de la façon dont ils peuvent causer problème, ainsi que d'une propriété d'"auto-réparation" de cette géométrie. Une nouvelle méthode d'optimisation basée sur les régions de confiance en est alors dérivée.
  • December 4th: PhD defense of Yaël Champclaux - Un modèle de recherche d'information basé sur les graphes et les similarités structurelles pour l'amélioration du processus de recherche d'information
  • November 27th, 12:15 : Arnaud Pêcher - Graphs, tilings and near-factorizations of groups - slides Δ
    • Abstract: the Strong Perfect Graph Conjecture is a famous conjecture stated in the early sixties. It was solved in 2002 by Chudnovsky, Robertson, Seymour and Thomas. On the road to the proof of the conjecture, the family of partitionable graphs was introduced. It turns out that Cayley partitionable graphs may be seen as an algebraic concept, called near-factorizations of finite groups. Near-factorizations of cyclic groups have been well-studied and Grinstead gave a conjecture characterizing them in the eighties. Little is known about near-factorizations of non abelian groups and it seems that most of them do not have near-factorizations (excluding trivial near-factorizations). In this talk, we will give an overview of the main results on Grinstead's conjecture and give some hints explaining why non-abelian groups do not have near-factorizations in general.
  • November 13th : Etiene Fieux - Graphs and homotopy
    • Abstract (french): ces dernières années plusieurs notions d'homotopie sur les graphes sont apparues. On reviendra sur ces différentes approches. En particulier, elles posent naturellement des questions de nature géométrique sur des complexes simpliciaux et on insistera davantage sur ce dernier aspect.
  • October 23rd - Mr Vidaluc (Laboratoires Fabre) - Analyse de l'espace chimique et "library design"
    • Abstract (french): Le design de chimiothèques (= collection de molécules) de criblage (screening libraries) de haute qualité est une thématique qui recueille un intérêt croissant dans la recherche amont de molécules à visée thérapeutique. Le problème, qui peut sembler trivial par certains aspects (ex : recherche de la diversité structurale), apparaît dans toute sa complexité dès qu'il s'agit de créer des chimiothèques ayant une grande capacité à générer des molécules actives lors d'une première évaluation par contact avec sa cible protéique réceptrice. L'objectif de réduction de l'immensité de l'espace chimique, en vue d'identifier des régions à fort potentiel pharmacologique, semble requérir une analyse convergente multi-disciplinaire, notamment mathématique. Le but du présent exposé est d'essayer d'en dessiner les contours.
  • October 16th - Bertrand Jouve - CCF-indecomposability of tournaments (joint work with Jean-François Culus)
    • Abstract (french): Un clan d'un tournoi est un sous-ensemble de sommets qui induisent un sous-tournoi convexe et transitif. Nous caractérisons les tournois qui n'ont que des clans triviaux (0 ou 1 sommet) et qui sont critiques pour cette propriété. Des généralisations sont possibles via les 2-structures.
  • October 9 - Romain Boulet, Que nous cachent les spectres de graphes ?
    • Abstract (french): Plusieurs matrices peuvent être associées à un graphe et leur spectre représentent des invariants du graphe mais ces invariants ne suffisent pas à déterminer un graphe à isomorphisme près. Cependant ces valeurs propres contiennent plusieurs informations concernant la structure du graphe comme le nombre de marches fermées de longueur donnée et certaines classes de graphes sont entièrement déterminées par leur spectre.
      Nous exposerons ces propriétés structurelles contenues dans les différents spectres et en particulier celles utiles pour obtenir une caractérisation de certains graphes. Différents graphes déterminés par leur spectre seront abordés et des questions ouvertes seront présentées. Enfin, une partie de cet exposé sera consacrée aux valeurs propres de graphes et digraphes circulants.
  • October 1 - Arnaud Pêcher - Polyhedral graph theory and superclasses of perfect graphs