title: Sogolon Kondé

text: L'enfance de Soundiata est cependant malheureuse : paralysé des jambes, l'enfant reste incapable de marcher jusqu'à un âge avancé, dix-sept ans dans la version de Wa Kamissoko. Pendant ce temps, Sogolon Kèdjougou est en butte à la jalousie et à la haine de Sassouma Bérété (ou Tassouma), la précédente épouse du roi, qui a elle aussi des fils. Un jour, Manden Bogori, fils de Sassouma, va chercher pour sa mère des feuilles de baobab ; Sogolon, dont le fils est incapable de lui rendre le même genre de services, est contrainte de quémender quelques feuilles auprès de sa rivale, mais Sassouma les lui refuse et l'insulte publiquement. Devant les lamentations de Sogolon, le jeune Soundiata décide de se lever : il demande à son père de commander aux forgerons (dont l'ancêtre mythique est Noun Fayiri) de couler une énorme barre de fer pour la lui livrer. Soundiata s'appuie à cette barre de fer, qu'il courbe sous sa force, et parvient ainsi à se mettre debout et à marcher. C'est la fin de sa paralysie : aussitôt, il va jusqu'à un baobab et arrache l'arbre entier pour le remettre à Sogolon.


title: Sogolon Kondé

text: Après la mort de Fara-Koro Makan Kègni, Sogolon est exilée avec toute sa famille, dont Soundiata. Après plusieurs étapes, tous trouvent un accueil durable et bienveillant à Mèma (ou Nèma), auprès du roi Faran Tounkara. Ils y résident jusqu'à l'arrivée de messagers venus du Manden pour demander secours à Soundiata, seul capable de tenir tête à Soumaworo Kanté, roi du Sosso, qui a conquis le Manden et le dépouille de ses richesses. Sogolon rencontre les messagers au marché et reconnaît leur origine aux variétés de légumes qu'ils sont venus vendre et qui sont typiques du Manden (le grand gombo, l'aubergine et le haricot dit "mògòtigi", « le populaire ») : elle les amène alors au palais, où ils transmettent leur message à Soundiata et le pressent de rentrer au Manden. Sogolon donne alors des indications à Soundiata qui lui permettent de prédire la tournure que prendra sa guerre contre Soumaworo en accomplissant un rite divinatoire devant un karité mort ; Soundiata accomplit le rite, qui augure de sa victoire, et il décide de partir le lendemain. Dans la nuit, Sogolon meurt. Le lendemain, Soundiata veut l'enterrer sur place, mais le roi Faran Tounkara s'y oppose dans un premier temps, puis tente de lui faire payer le prix de la terre où la reine serait enterrée. Soundiata réplique à cette demande inique par une menace, et, sur l'avis de ses conseillers, le roi finit par accepter que Sogolon soit enterrée à Nèma.


title: Sogolon Kondé

text: Sogolon apparaît dans plusieurs des réécritures et adaptations de l'épopée de Soundiata. Au cinéma, elle apparaît dans le film "Keïta ! L'Héritage du griot" réalisé par le cinéaste burkinabé Dani Kouyaté en 1995, où elle est jouée par Blandine Yaméogo. Au théâtre, elle donne son nom à un spectacle de la compagnie ivoirienne Ki Yi M'Bock, "Sogolon, l'épopée panafricaine", créé en 2006.


title: Kaya Magan Cissé

text: Kaya Magan Cissé était un roi soninké du Ouagadou.


title: Kaya Magan Cissé

text: Il est, au , le fondateur de la dynastie des Cissé Tounkara, qui domineront le royaume du Ouagadou, noyau de l'Empire du Ghana (). L'or est le fondement de la richesse du royaume et « kaya magan » signifierait « roi (ou maître) de l'or ».


title: Algorithme émergent

text: Un algorithme émergent est un processus de résolution de problème qui s'appuie sur un ensemble de règles simples pour faire émerger un comportement global plus complexe sans que ce dernier n'ait été explicitement détaillé.


title: Algorithme émergent

text: Un réseau de neurones artificiels est par exemple constitué d'agents simples, mais c'est leur nombre et leurs interconnexions qui leur permettent de résoudre des problèmes d'ordres de complexité bien supérieurs.


title: Ligne de Vieilleville à Bourganeuf

text: La ligne de Vieilleville à Bourganeuf est une ligne ferroviaire française, entièrement située sur le territoire du département de la Creuse. Elle relie les gares de Vieilleville et de Bourganeuf.


title: Ligne de Vieilleville à Bourganeuf

text: Elle constitue la ligne du réseau ferré national.


title: Ligne de Vieilleville à Bourganeuf

text: C'est une ligne « non exploitée » depuis l'arrêt du trafic fret en 2004.Cette ligne déclarée d'utilité publique le est destinée à relier Bourganeuf, alors sous-préfecture de la Creuse, à la ligne de Montluçon à Saint-Sulpice-Laurière. Elle est construite par l'administration des chemins de fer de l'État qui n'avait pas trouvé de concessionnaire. Une loi du autorise le ministère des Travaux Publics à entamer les travaux de construction de cette ligne.


title: Ligne de Vieilleville à Bourganeuf

text: La Compagnie du chemin de fer de Paris à Orléans obtient par une convention signée avec le Ministre des travaux publics le la concession à titre éventuel d'une ligne de « Bourganeuf à Felletin (Bosmoreau à Moutier-Rozeilles) ». Cette convention a été entérinée par une loi le . Toutefois cette ligne n'a pas été réalisée, et sa concession est annulée par une convention signée entre le ministre des Travaux publics et la compagnie le . Cette convention est approuvée par une loi le .


title: Ligne de Vieilleville à Bourganeuf

text: À la fin de sa construction, la ligne est cédée par l'État à la Compagnie du chemin de fer de Paris à Orléans (PO) par une convention signée entre le ministre des Travaux publics et la compagnie le . Cette convention est approuvée par une loi le suivant. Le , elle est inaugurée puis mise en service par la compagnie PO.


title: Ligne de Vieilleville à Bourganeuf

text: La ligne desservait les gares intermédiaires de Bosmoreau-les-Mines, Saint-Dizier-Leyrenne et Bourdaleix-Cornat.


title: Ligne de Vieilleville à Bourganeuf

text: Elle est fermée au service des voyageurs le , puis fermée au fret à en 2004.


title: Ligne de Vieilleville à Bourganeuf

text: Établie à voie unique, elle possède un profil très médiocre avec des déclivités de 20 ‰. Cette ligne non exploitée fait toujours partie du réseau ferré national.


title: Ligne de Vieilleville à Bourganeuf

text: Outre la gare de bifurcation de Vieilleville la ligne dispose d'une halte et trois gares.


title: Ligne de Vieilleville à Bourganeuf

text: Elle dispose d'un pont sur le Taurion situé sur le circuit du vélo-rail.


title: Ligne de Vieilleville à Bourganeuf

text: Le "Vélorail de la mine" utilise l'ancienne ligne sur cinq kilomètres en direction de Bourganeuf. Le voyage est un aller retour de dix kilomètres avec pour base de départ et d'arrivée l'ancienne gare de Bosmoreau-les-Mines.


title: Ligne de Vieilleville à Bourganeuf

text: En 2013, Réseau ferré de France (RFF) a signé une convention, avec Jean-Luc Fouriaud (apiculteur), de mise à disposition de l'emprise de la ligne pendant cinq ans afin d'y installer des ruches et donc permettre à ses abeilles de butiner. Il est prévu une protection des riverains en limitant à plus de des habitations l'installation des ruches.


title: Ngoné Latyr Fall

text: Ngoné Latyr Fall, de son vrai nom Ngoné Latyr Absa est la fille du Damel Meissa Teinde Dior. Elle était une linguère (princesse) wolof de l'empire du Cayor. Elle est la mère du damel Lat Dior Diop (Lat Dior Ngoné Latyr héros sénégalais de la résistance à la pénétration coloniale). Elle est aussi la mère du Damel Birima Ngoné Latyr Fall né de son union avec le Damel Macodou Coumba Yandé Fall.


title: Cathédrale Saint-Jean-l'Évangéliste de Salford

text: La cathédrale Saint-Jean-l’Évangéliste de Salford est la cathédrale du diocèse catholique de Salford en Angleterre, dont le siège, tenu depuis 2014 par Arnold, est à Salford près de Manchester. Elle est consacrée à saint Jean. Elle donne sur Chapel Street, non loin du centre-ville de Manchester.


text: L'édifice a été construit entre 1844 et 1848, en majeure partie sur des plans de Matthew Ellison Hadfield (1812–1885).


text: La cathédrale est plus connue sous le nom de « cathédrale de Salford ». Le style architectural est néogothique, elle est classée comme monument de par l’English Heritage.


title: Palmier (pâtisserie)

text: Le palmier est une viennoiserie à base de pâte feuilletée, en forme de cœur, largement saupoudrée de sucre qui caramélise à la cuisson. Il est fait d'une double roulade de pâte coupée en tranches, ce qui lui donne sa forme caractéristique évoquant le feuillage du palmier.


title: Palmier (pâtisserie)

text: Le palmier existe sous forme de gâteau individuel ou de petit four sec (en accompagnements des glaces et des entremets). En Suisse romande, le palmier est connu sous le nom de Cœur de France.


title: Championnats du monde de gymnastique rythmique 2003

text: Les XXVI Championnats du monde de gymnastique rythmique se sont tenus à Budapest du 24 au .


title: Geórgios Daloúkas

text: Geórgios Daloúkas (en grec : ), souvent appelé Yórgos Daloúkas ( ; né le ) est un arbitre grec de football.


title: Geórgios Daloúkas

text: Il officie dans le championnat de Grèce. Faisant partie de la catégorie 3, il obtient une promotion au début de la saison 2010-2011 devenant arbitre de la catégorie 2, cela lui permet d'arbitrer des matchs en Ligue Europa.


title: Geórgios Daloúkas

text: Son premier match européen dans une phase de poule est la confrontation en les Red Bull Salzbourg et Manchester City (0-2) où il ne sort que deux fois le carton jaune.


title: Geórgios Daloúkas

text: Il officia aussi pour le Championnat chypriote le pour le match APOEL Nicosie/Apollon Limassol (3-2), c'est son seul match à Chypre.


title: Vernay

text: Vernay dérive du gaulois "verna", « aulne » (lui-même formé sur une racine préceltique "vara", « eau »), suivi du suffixe collectif "-etum" ou "-etam", « lieu occupé par - ». Il désigne un bois de "vernes", d'aulnes, une aulnaie.


title: Championnats du monde de gymnastique rythmique 2002

text: Les XXV Championnats du monde de gymnastique rythmique se sont tenus à La Nouvelle-Orléans aux États-Unis du 10 au . La compétition n'était ouverte qu'aux exercices en groupes, il n'y a pas eu de compétition individuelle ni par équipe.


text: Des gymnastes provenant de 25 pays (Allemagne, Biélorussie, Brésil, Bulgarie, Canada, Chine, Corée du Sud, Cuba, Espagne, États-Unis, France, Grèce, Hongrie, Italie, Japon, Pologne, Russie, Slovaquie, Suisse et Ukraine) participent à ces championnats du monde.


title: Cindy Daniel

text: Cindy Daniel, née le à Montréal (Canada), est une chanteuse et actrice québécoise.


title: Cindy Daniel

text: Originaire de Montréal, Cindy Daniel s'intéresse à la musique très jeune et commence à prendre des cours de chant et de piano afin d'entreprendre très tôt une carrière de chanteuse. Alors qu'elle n'a pas encore 16 ans, elle croise le chemin des dirigeants de l'étiquette Tox qui prennent sa carrière en main. À l'âge de 16 ans, elle enregistre son premier album, "La petite indienne", qui paraît en 2002.


title: Cindy Daniel

text: La même année, elle est retenue pour tenir le rôle d'Elvira dans la comédie musicale "Don Juan", qui est présentée au Québec et en France. Au terme de la tournée, Mario Pelchat, avec qui elle chantait dans la comédie musicale, lui offre un contrat avec sa maison de production MP3.


title: Cindy Daniel

text: En , elle lance l'album "J'avoue", qui est produit par Mario Pelchat et sur lequel elle cosigne six titres. Suivra en son troisième opus, "Le tout premier jour", toujours avec l'aide de Pelchat.


title: Cindy Daniel

text: En 2009, avec Philippe Berghella, elle participe au spectacle intitulé "Accro".


title: Cindy Daniel

text: Depuis la parution de son dernier album et la tournée subséquente, elle demeure active en participant à divers projets, dont "Quand le country dit bonjour".


title: Cindy Daniel

text: En 2017 elle participe à l'émission télévisée La Voix, au Québec. Elle est concurrente dans l'équipe d'Éric Lapointe. Elle est éliminée lors des quarts de finale. Une polémique naît du fait qu'elle était professionnelle et qu'elle n'avait pas sa place dans le télécrochet selon certains téléspectateurs.


title: Championnats du monde de gymnastique rythmique 2001

text: Les XXIV Championnats du monde de gymnastique rythmique se sont tenus à Madrid en Espagne du 18 au .


title: Rajka (pomme)

text: Rajka est le nom d'un cultivar de pommier domestique et par extension celui de sa pomme. RAJKA est une variété enregistrée par l'Union Européenne:Variété obtenue en 1983 en Europe (Station expérimentale de Střížovice, Tchéquie).


title: Rajka (pomme)

text: Le cultivar Rajka résulte du croisement Sampion × Katka.


title: Rajka (pomme)

text: Variété diploïde


title: Rajka (pomme)

text: Groupe de pollinisation: D


title: Rajka (pomme)

text: Pomme fécondée par Santana, Topaz, ... Grâce à sa résistance génétique aux races communes de tavelure, cette variété de pommier est très appropriée aux petits jardins familiaux où les traitements chimiques ne sont pas systématiques.


title: Fantasy! Jūichi

text: L'album "Fantasy! Jūichi" sort le au Japon sur le label zetima. Il est écrit, composé et produit par Tsunku. Il sort moins de neuf mois après le précédent album du groupe, "10 My Me", sorti en début d'année. Il atteint la du classement des ventes de l'oricon, et reste classé pendant trois semaines, pour un total de exemplaires vendus durant cette période.


title: Fantasy! Jūichi

text: Il sort également dans une édition limitée au format "CD+DVD", avec une pochette différente et un DVD en supplément contenant huit versions alternatives du clip du dernier single d'alors "Onna to Otoko no Lullaby Game" (soit une version consacrée à chacune des membres) et une annonce filmée lors d'un concert.


title: Fantasy! Jūichi

text: L'album contient onze titres, dont seulement deux sortis précédemment en singles, dans l'année : "Seishun Collection" et "Onna to Otoko no Lullaby Game" ; ce dernier titre, sorti en single un mois avant l'album, est cependant remanié sur celui-ci. L'album ne contient pas le titre "Appare Kaiten Zushi!" sorti deux mois auparavant par le groupe sous le nom "Muten Musume" dans le cadre d'une campagne publicitaire. Deux des autres chansons de l'album sont interprétées entièremement en solo par Ai Takahashi et Reina Tanaka ; les trois autres membres les plus anciennes interprètent le chant principal de trois titres, et un autre titre est dédié aux trois dernières membres de la " génération".


title: Fantasy! Jūichi

text: C'est le dernier album du groupe avec Eri Kamei (arrivée en 2003), et avec les deux membres chinoises Jun Jun et Lin Lin, dont les départs simultanés du groupe et du Hello! Project sont alors annoncés pour le , deux semaines après la sortie du disque. Kamei part pour des problèmes de santé, tandis que la participation des deux membres étrangères était présentée comme une expérience temporaire.


title: Fantasy! Jūichi

text: Membres du groupe créditées sur l'album :


title: Palmier (homonymie)

text: Le mot palmier peut désigner :


title: Katja (pomme)

text: Katja est le nom d'un cultivar de pommier domestique. Aussi connu sous le nom Katy.


title: Katja (pomme)

text: Obtenu à Balsgärd en Suède en 1947 et distribué en 1996.


title: Katja (pomme)

text: La pomme Katja résulte du croisement James Grieve × Worcester Pearmain.


title: DVJ-1000

text: La Pioneer DVJ-1000 est une platine CD et DVD de la gamme DVJ  capable de lire des données vidéo sur DVD, ainsi que les CD-Audio, MP3 et audio sur des CD et DVD. Créée par la société japonaise Pioneer en 2006,  elle peut imiter les platines vinyle, dont la possibilité du scratch. Elle est le successeur du Pioneer DVJ-X1.


title: DVJ-1000

text: Contrairement à la DVJ-X1, la DVJ-1000 a les mêmes dimensions que les platines Pioneer CD audio (CDJ-1000), et peut être installé dans les compartiments existants avec une relative facilité, permettant une mise à niveau facile pour les propriétaires de club et les ingénieurs du son.


title: DVJ-1000

text: Étant donné que l'appareil lit les DVD, plusieurs sorties ont été ajoutées, y compris S/PDIF, sorties composite, une sortie vidéo de prévisualisation, qui sert également comme un « tableau de bord » pour la recherche par le biais du contenu vidéo et MP3, ainsi que des sorties de contrôle pour mélangeurs DJ Pioneer compatible.


title: DVJ-1000

text: L'appareil est multi-système, la sortie PAL et NTSC pour les signaux vidéo a une compatibilité mondiale.


title: DVJ-1000

text: Dans le cadre de sa stratégie marketing, Pioneer a équipé plusieurs DJs noté avec cette nouvelle unité, comme Sander Kleinenberg et DVJ Bazuka.


title: Gábor Szabó

text: Gábor Szabó, né Gábor István Szabó le et mort le , est un guitariste hongrois de jazz connu pour son mélange de jazz, musique pop rock et musique folklorique hongroise. Il a joué aussi occasionnellement du sitar.


title: Gábor Szabó

text: Gábor Szabó est né à Budapest. Il commence l'apprentissage de la guitare à quatorze ans, inspiré par le jazz qu'il écoute sur la radio Voice of America. Il rejoint les États-Unis en 1956 et entre à la Berklee School of Music à Boston. En 1958 il se produit au Newport Jazz Festival, et fait partie du quintet de Chico Hamilton de 1961 à 1965. À la fin des années 1960, Gábor Szabó fonde avec Cal Tjader et Gary McFarland le label éphémère "Skye Records", chez qui il enregistre son album avec Lena Horne, en octobre et . Il faisait déjà partie de son orchestre lorsqu'elle chantait au "Nugget's" dans le Nevada en , et avec Harry Belafonte) au Caesars Palace à Las Vegas en .


title: Gábor Szabó

text: Son jeu comporte certains éléments repris à la musique folklorique hongroise, ainsi que des effets larsen inspirés par le rock. Sa composition "Gypsy Queen" est devenue célèbre après que Carlos Santana l'a reprise en 1970 dans son album "Abraxas". Son album pour Impulse!, "Wind, Sky And Diamonds", est enregistré en 1967 avec le groupe "The California Dreamers", un ensemble vocal avec , Al Capps, Loren Farber, , , Ian Freebairn-Smith, Sally Stevens, Sue Allen et . Au cours de sa carrière solo, il a joué avec de nombreux artistes comme Ron Carter, Paul Desmond, Lena Horne, Charles Lloyd, Gary McFarland et Bobby Womack.


title: Gábor Szabó

text: Gábor Szabó avait le sentiment d'être difficilement accepté dans le milieu du jazz américain. Lors d'un concert en 1977 au "Catamaran Hotel" à San Diego, il se plaint du succès de George Benson, "Breezin'" (composé par Bobby Womack) ; il expliqua au public qu'il avait enregistré cette chanson bien avant Benson, et que ce dernier lui avait tout simplement volé ses arrangements. On peut écouter sa version sur l'album "High Contrast" (1971) avec Bobby Womack.


title: Gábor Szabó

text: Il meurt en 1982 à Budapest, de retour chez lui à la suite de problèmes rénaux et hépatiques.


title: Communauté de communes Haut-Berry - Val de Loire

text: La communauté de communes Haut-Berry - Val de Loire est une ancienne communauté de communes française, située dans le département du Cher et l'arrondissement de Bourges.


text: En , la communauté de communes Pays Fort Sancerrois Val de Loire est créée à partir de la fusion des trois intercommunalités Cœur du Pays Fort, Haut-Berry - Val de Loire et du Sancerrois.


title: Diana Tanaka

text: Diana Tanaka ou Dian Tanaka est une actrice japonaise.


title: Michel Launay

text: Michel Launay (né en et mort le ) est un scénographe français.


title: Michel Launay

text: Il a travaillé en France avec des metteurs en scène renommés : Peter Brook, Antoine Vitez, Charles Tordjman, Victor Garcia, André-Louis Perinetti, Michel Didym. Ses scénographies ont notamment été créées à Paris au Théâtre de la Ville et au Théâtre national de Chaillot, ainsi qu’au Théâtre national de Strasbourg et au Centre dramatique national de Nancy.


title: Michel Launay

text: Michel Launay est le scénographe qui a le plus travaillé avec Mehmet Ulusoy. Il a conçu pour lui la scénographie de huit spectacles :


title: Michel Launay

text: Michel Launay a reçu le prix Afife (le meilleur scénographie de l'année) en 2002 pour la scénographie de "Pourquoi Benerdji s'est-il suicidé ?".


title: Rio delle Torreselle

text: Le rio delle Torreselle ("en vénitien: rio de le Toresele; "canal des tourelles") est un canal de Venise dans le sestiere de Dorsoduro. Dans sa partie longue au sud, il est parfois appelé Rio Piccolo del Legname et dans sa partie nord, parallèle au Grand Canal, le Rio Pietre Bianche ("en vénitien Rio delle Piere Bianche).


title: Rio delle Torreselle

text: Un ancien palais coiffé d'une tour, maintenant détruit, fut appelé "dalla Torresella", ce qui se mua ensuite en dalle Torreselle, surnom de la branche de la famille "Venier", qui en fut propriétaire. Ce palais disposa d'une façade sur le Grand Canal et se situa à l'embouchure du rio. Au il fut divisé entre diverses parties de la famille Venier : en 1571 "Girolamo Venier" légua à "Laura", épouse de "Polo Trevisan", et à "Pietro Donà", pendant qu'une autre partie fut léguée en 1586 par la veuve du premier à l’archiconfrérie de San Rocco. Comme finalement tout l'immeuble tomba entre les mains des "Donà", ceux-ci finirent par se surnommer aussi "dalle Torreselle".


title: Rio delle Torreselle

text: Ce rio fut aussi appelé Rio delle Piere Bianche, probablement à cause de la blancheur des pierres de la rive qui le bordait (appelée jadis "Fondamenta Zorzi o Bragadin", de nos jours "fondamenta Ospedaleto") et sur laquelle se trouva l'hôpital "della Frescada".


title: Rio delle Torreselle

text: Le rio du Toresele a une longueur d'environ 380 mètres. Il part du canal de la Giudecca vers le nord sur environ 350 mètres avant de faire un coude de 90° vers l'est dans sa partie "Pietre Bianche" et finalement de refaire un coude de 90° vers le nord juste avant son embouchure dans le Grand Canal.


title: Rio delle Torreselle

text: Ce rio débouche sur le Grand Canal entre le et le palais Dario.


title: Rio delle Torreselle

text: Il longe :


title: Rio delle Torreselle

text: Ce rio est traversé par trois ponts (du nord au sud) :


title: Smrekari

text: Smrekari est une localité de Croatie située dans la municipalité de Čabar, dans le comitat de Primorje-Gorski Kotar. En 2001, la localité comptait 15 habitants.


title: Conditions d'optimalité

text: En optimisation mathématique, les conditions d'optimalité sont un ensemble d'équations, d'inéquations (c'est-à-dire des inégalités) et d'expressions diverses (par exemple, la copositivité de matrices) vérifiées par une solution d'un problème d'optimisation (on parle alors de conditions nécessaires d'optimalité) ou qui permettent d'affirmer qu'un point qui les vérifie est solution du problème d'optimisation considéré (on parle alors de conditions suffisantes d'optimalité). Ces expressions analytiques de l'optimalité sont utiles entre autres pour :


title: Conditions d'optimalité

text: Cet article se limite aux conditions d'optimalité des problèmes d'optimisation "différentiable" et de "dimension finie".


title: Conditions d'optimalité

text: Les plus importantes sont les conditions KKT.


title: Conditions d'optimalité

text: Cet article se limite aux conditions d'optimalité des problèmes d'optimisation "différentiable" et de "dimension finie". Le terme "différentiable" signale que les fonctions définissant le problème sont supposées "différentiables" au sens classique (celui de Fréchet). Lorsque la différentiabilité a lieu dans un sens plus faible on parle d"optimisation non lisse" ou d"optimisation non différentiable", discipline dans laquelle on établit des conditions d'optimalité plus fines que celles présentées dans cet article. Il ne sera donc pas non plus question ici des problèmes d"optimisation combinatoire" dans lesquels les variables prennent des valeurs discrètes, si bien que la différentiabilité requise n'a pas de sens. Quant aux termes "dimension finie", ils font référence au fait que l'on cherche la valeur optimale d'un nombre fini de paramètres (mais ceux-ci doivent pouvoir varier continûment). Le système à optimiser peut, quant à lui, être de dimension infinie, comme c'est le cas de l'optimisation d'une forme géométrique (de dimension infinie) décrite par des splines (représentés par un nombre fini de paramètres). Les conditions d'optimalité des problèmes d'optimisation de dimension infinie sont considérées ailleurs.


title: Conditions d'optimalité

text: On parle de conditions du premier ordre si ces conditions font intervenir les dérivées premières des objets définissant le problème (il faudra définir ce que l'on entend par la "dérivée" de l'ensemble admissible du problème), mais pas les dérivées d'ordre supérieur, et de conditions du second ordre si ces conditions font intervenir les dérivées secondes des objets définissant le problème, mais pas les dérivées d'ordre supérieur.


title: Conditions d'optimalité

text: Les conditions d'optimalité d'un problème d'optimisation avec contraintes introduisent des "variables cachées", les multiplicateurs ou variables duales, qui n'apparaissent pas dans l'énoncé du problème et qui sont donc difficiles à appréhender (elles appartiennent à un autre espace que celui des variables à optimiser). Elles jouent cependant un rôle crucial dans la compréhension du problème, notamment parce qu'elles s'interprètent comme des "coûts marginaux", très utiles en pratique ; il est donc important de s'y familiariser.


title: Conditions d'optimalité

text: Les conditions d'optimalité sont présentées ci-dessous pour des problèmes d'optimisation de généralité (et de difficulté) croissante. Celles énoncées pour un problème d'une certaine généralité peuvent être utilisées pour exprimer les conditions d'optimalité d'un problème qui l'est moins, car celui-ci pourra toujours être vu comme un cas particulier du premier problème. Le lecteur pressé peut donc directement aborder le cas du problème le plus abstrait, mais il lui manquera alors certaines notions coutumièrement utilisées à des niveaux d'abstraction moindres.


title: Conditions d'optimalité

text: Connaissances supposées : le calcul différentiel, l'algèbre linéaire, les bases de l'analyse convexe (en particulier le lemme de Farkas).


title: Conditions d'optimalité

text: Soit formula_1 un espace vectoriel sur formula_2 de dimension finie, qui désigne l'ensemble auquel appartiennent les paramètres que l'on cherche à optimiser. Étant de dimension finie, il n'y a pas de restriction à supposer que cet espace vectoriel est muni d'un produit scalaire, noté formula_3, qui en fait un espace euclidien. La norme associée à ce produit scalaire est notée formula_4. Le problème d'optimisation considéré s'exprime mathématiquement comme celui qui consiste à minimiser une fonction formula_5 sur une partie formula_6 de formula_1. La fonction formula_8 a de nombreuses appellations, ce qui permet de varier le vocabulaire : fonction-coût, coût, fonction-objectif, objectif, critère, "etc". L'ensemble formula_6 est appelé l'ensemble admissible du problème et un point lui appartenant est appelé point admissible. Ce problème, désigné ci-après formula_10, s'écrit au choix comme suit : formula_11. Une solution ou minimum ou minimiseur de ce problème est un point formula_12 de l'espace vectoriel formula_1 vérifiant deux conditions : il doit être admissible et minimiser le critère sur l'ensemble admissible. Ceci s'écrit formula_14. On adjoint souvent le qualificatif global à cette notion de solution pour la distinguer d'autres notions présentées ci-dessous. Signalons également que l'on remplace parfois ‘‘formula_15’’ par ‘‘formula_16’’ dans l'écriture du problème d'optimisation formula_10 lorsqu'il est certain que ce problème a une solution.


title: Conditions d'optimalité

text: Dans certaines sous-disciplines de l'optimisation, on utilise parfois la locution malheureuse "solution optimale" qui, avec le sens de "solution" donné ci-dessus, est un pléonasme (dans cette locution, le mot "solution" signifie en réalité "point admissible", mais il nous semble préférable de laisser au mot "solution" son sens habituel de "solution d'un problème").


title: Conditions d'optimalité

text: On introduit aussi d'autres notions de solutions. Ainsi on dit que formula_12 est une solution locale ou minimum local ou minimiseur local du problème formula_10 s'il existe un voisinage formula_20 de formula_12 tel que formula_12 minimise formula_8 sur formula_24. Par ailleurs, on dit que formula_12 est une solution stricte [resp. une solution locale stricte] si formula_12 est admissible et si formula_27 (inégalité stricte) pour tout formula_28 différent de formula_12 [resp. pour tout formula_30 différent de formula_12 où formula_20 est un voisinage de formula_12].


title: Conditions d'optimalité

text: Lorsqu'une fonction atteint un minimum en un point, elle varie peu dans le voisinage de ce point. Mathématiquement, cette observation se traduit par le fait que sa dérivée y est nulle. Ceci est une condition d'optimalité du premier ordre bien connue pour un problème sans contrainte (ces conditions sont présentées à la section "problèmes sans contrainte" ci-dessous). Si l'on veut établir une expression similaire dans le cas des problèmes avec contrainte, il est nécessaire de dire ce qu'est l'approximation au premier ordre de l'ensemble admissible en un point, de linéariser cet ensemble en ce point, comme on peut le faire pour la fonction-coût. Ceci conduit à la notion de cône tangent, développée dans un autre article.


title: Conditions d'optimalité

text: Rappelons quand même ici qu'une partie formula_34 de formula_1 (un espace vectoriel suffit pour cette notion) est un "cône" si formula_36, ce qui signifie que formula_37 doit appartenir à formula_34 chaque fois que formula_39 est un réel strictement positif (i.e., formula_40) et formula_41. Un cône n'est pas un objet de l'algèbre linéaire, mais de l'analyse convexe. On rencontre donc ici une première manifestation de l'importance de cette dernière théorie en optimisation.


title: Conditions d'optimalité

text: Nous utiliserons ici la notion de cône tangent au sens de Bouligand, qui suffit en dimension finie. Précisons que ce "cône tangent" à formula_6 en formula_43, noté formula_44 ci-dessous, est l'ensemble des directions tangentes à formula_6 en formula_43, c'est-à-dire des directions formula_47 pour lesquelles il existe des suites formula_48 d'éléments de formula_1 et formula_50 d'éléments de formula_2 telles que


title: Conditions d'optimalité

text: formula_52 La notion de cône tangent permet d'obtenir aisément une condition nécessaire d'optimalité du premier ordre pour le problème générique formula_10 — on suppose donc ici que le critère de ce problème est différentiable. Cette condition exprime que la fonction-coût formula_8 croît depuis un minimum local formula_12 en suivant une direction tangente, ce qui se traduit mathématiquement par formula_56 C'est ce que nous appellerons la "forme géométrique" de l'optimalité au premier ordre. Ce résultat avait déjà été exprimé par Peano dès 1887, puis par Kantorovitch en 1940, mais il est passé inaperçu ou a été oublié. On peut en donner une expression plus compacte en introduisant les notions de "gradient" et de "cône dual". Avec ces deux concepts, l'expression géométrique de l'optimalité donnée ci-dessus devient formula_73 Cette condition est générique et c'est elle qui sera particularisée ci-dessous à des problèmes dont l'ensemble admissible a une structure plus précise. Le travail sera dans chaque cas celui de trouver une expression plus pratique, plus accessible au calcul, du cône dual du cône tangent, conduisant ainsi à la "forme analytique" de l'optimalité.


title: Conditions d'optimalité

text: Résumons le résultat obtenu. On utilise l'abréviation CN1 pour désigner une condition nécessaire d'optimalité du premier ordre.


title: Conditions d'optimalité

text: On dit que formula_12 est un point stationnaire ou un point critique du problème formula_10, si ce point est admissible et s'il vérifie la condition d'optimalité du premier ordre donnée dans le résultat ci-dessus.


title: Conditions d'optimalité

text: Lorsque l'ensemble admissible est convexe, on dispose d'une CN1 ne faisant pas intervenir le cône tangent. On y a noté formula_76 la dérivée directionnelle de formula_8 en formula_43 dans la direction formula_47, c'est-à-dire la limite lorsque formula_80 du quotient différentiel formula_81.


title: Conditions d'optimalité

text: Enfin, lorsque à la fois l'ensemble admissible est convexe et le critère est convexe sur l'ensemble admissible, la condition précédente est une condition nécessaire et suffisante d'optimalité du premier ordre, une propriété que l'on résume par l'abréviation CNS1. Il n'y a alors plus de distinction entre minimum local et global.


title: Conditions d'optimalité

text: Pour les problèmes convexes, il n'y a donc pas de distinction entre un minimum local et global : tous les minima locaux sont globaux. C'est une seconde manifestation de l'importance de l'analyse convexe en optimisation.


title: Conditions d'optimalité

text: Le problème que l'on considère dans cette section est celui de minimiser la fonction formula_8 sur formula_1 tout entier, problème que l'on écrit formula_84 Dès lors, l'ensemble admissible formula_6 est l'espace vectoriel formula_1.


title: Conditions d'optimalité

text: Le cône tangent à formula_1 en formula_88 est l'espace formula_1 tout entier. Comme le dual de formula_1 est formula_91, la CN1 générique exprime que le gradient formula_92 est nul en un minimum local formula_12 de formula_8 sur formula_1. Cette condition d'optimalité est parfois appelée « équation de Fermat » pour rappeler une condition similaire trouvée, dans le cas d'un polynôme réel d'une variable réelle, par Pierre de Fermat vers 1629, c'est-à-dire environ quarante ans avant l'invention du calcul différentiel par Newton et Leibniz.


title: Conditions d'optimalité

text: Lorsque formula_8 est convexe, ces conditions deviennent des conditions nécessaires et suffisantes d'optimalité "globale" de formula_12.


title: Conditions d'optimalité

text: Nous désignons ci-dessous par formula_98 la dérivée seconde de formula_8 en formula_43, qui est une application bilinéaire symétrique de formula_101 dans formula_2, et par formula_103 la hessienne de formula_8 en formula_105 pour le produit scalaire formula_3 de l'espace euclidien formula_1, qui est l'unique opérateur linéaire auto-adjoint sur formula_1 vérifiant formula_109 Rappelons également les notions de semi-définie positivité et définie positivité d'un opérateur auto-adjoint formula_110 sur formula_1, associées au produit scalaire de formula_1, qui sont utilisées dans les résultats ci-dessous :


title: Conditions d'optimalité

text: Les résultats suivants résument les conditions nécessaires du second ordre (CN2) et les conditions suffisantes du second ordre (CS2) pour les problèmes d'optimisation sans contrainte.


title: Conditions d'optimalité

text: On peut se servir de ces conditions du second ordre comme suit. La CN1 de Fermat est un système non linéaire qui a quelques chances d'être bien posé. Par exemple si formula_119 est équipé du produit scalaire euclidien, ce système est formé de formula_120 équations (les dérivées partielles du critère) à formula_120 inconnues. Si on calcule toutes les solutions de l'équation de Fermat (ceci est rarement une tâche aisée), on dispose, par définition, de tous les points stationnaires du critère. Ceux-ci ne sont pas nécessairement des minimiseurs de formula_8. Les conditions du deuxième ordre permettent souvent de sélectionner parmi ces points stationnaires ceux qui sont des minima locaux. En effet, d'après ces conditions


title: Conditions d'optimalité

text: On ne recouvre pas ainsi tous les cas, puisque l'on pourrait avoir un point stationnaire formula_12 avec une hessienne formula_124 semi-défini positif, mais non défini positif (il a un noyau non trivial, une valeur propre nulle). L'ambiguïté de tels cas peut parfois être levée en examinant des conditions d'ordre plus élevé.


title: Conditions d'optimalité

text: L'ensemble admissible du problème d'optimisation considéré dans cette section n'est pas l'espace formula_1 tout entier, comme pour les problèmes sans contrainte de la section précédente, mais une partie de celui-ci, définie par un nombre fini de contraintes d'égalité : formula_132 Ces contraintes sont spécifiées au moyen d'une fonction formula_133 où formula_134 est, tout comme formula_1, un espace euclidien (de dimension finie) dont le produit scalaire est aussi noté formula_3. Les dimensions des espaces sont notées formula_137 Il sera souvent approprié de supposer qu'en la solution formula_12 recherchée, la jacobienne formula_139 de la contrainte vérifie formula_139 est surjective. Ceci requiert certainement d'avoir formula_141, c'est-à-dire d'avoir moins de contraintes que de variables à optimiser. Lorsque cette hypothèse est vérifiée, l'ensemble admissible formula_142 est, dans un voisinage de formula_12, une variété (concept de base de la géométrie différentielle que l'on peut voir comme une surface ayant des propriétés de représentation particulières) de dimension formula_144. Le problème d'optimisation considéré dans cette section s'écrit donc formula_145 où formula_146 en est le critère.


title: Conditions d'optimalité

text: L'ensemble admissible formula_142 d'un problème formula_148 convexe est donc un sous-espace affine de formula_1, donc un convexe.


title: Conditions d'optimalité

text: Comme le montre le cas générique, les conditions nécessaires d'optimalité du premier ordre peuvent s'obtenir en trouvant une représentation convenable du cône tangent à l'ensemble admissible formula_142 et en prenant ensuite son cône dual.


title: Conditions d'optimalité

text: On note formula_151 le noyau et formula_152 l'image d'une application linéaire formula_153 entre deux espaces euclidiens formula_1 et formula_134. L'adjointe de formula_110 est l'application linéaire formula_157 définie par la relation formula_158, pour tout formula_159 et tout formula_160. On rappelle qu'en dimension finie, on a formula_161. Cette identité joue un rôle-clé dans le passage de la forme géométrique (utilisant la partie gauche de l'identité) à la forme analytique (utilisant sa partie droite) des conditions d'optimalité du premier ordre.


title: Conditions d'optimalité

text: Le résultat suivant montre que le cône tangent est inclus dans un sous-espace vectoriel ; il lui sera égal dans les bons cas.


title: Conditions d'optimalité

text: Dans l'inclusion formula_162, le cône tangent formula_163 ne dépend que de l'ensemble admissible formula_142, alors que formula_165 dépend de la fonction formula_166 utilisée pour définir formula_142. Il peut y avoir plusieurs fonctions formula_166 définissant le même ensemble formula_142. Du point de vue de l'optimisation, toutes ne conviennent pas. Celles qui permettent d'obtenir des conditions d'optimalité sont celles pour lesquelles l'égalité formula_170 a lieu. On dit alors que la "contrainte" formula_166 (léger abus de langage, il faudrait dire la "fonction formula_166 utilisée pour définir formula_142") est qualifiée en formula_43 (sous-entendu «pour représenter formula_142»).


title: Conditions d'optimalité

text: Voici le résultat principal assurant que la contrainte formula_166 est qualifiée en un point. On y retrouve la condition mentionnée ci-dessus assurant que formula_142 est une variété dans le voisinage formula_43.


title: Conditions d'optimalité

text: Voici une conséquence pratique de la notion de qualification de contrainte. Au lieu d'utiliser la fonction formula_166 pour représenter l'ensemble admissible formula_142, on pourrait utiliser la fonction formula_181, définie par formula_182, puisque formula_183 si, et seulement si, formula_184. Ceci paraît attrayant puisque l'on a ainsi remplacé toutes les contraintes d'égalité, en nombre potentiellement grand, par une seule contrainte. Cependant, la contrainte formula_185 a encore moins de chance d'être qualifiée que formula_166 puisque formula_187 en un point formula_188 et donc formula_189, qui est le plus souvent trop grand. Il n'est donc, en général, pas recommandé de remplacer formula_166 par formula_185.


title: Conditions d'optimalité

text: Lorsque la contrainte est qualifiée, le cône tangent est le "sous-espace vectoriel" formula_165, dont le dual est alors son orthogonal formula_193. Par la CN1 générique, le gradient de formula_8 en un minimum local de formula_8 sur formula_142 appartient à ce dernier ensemble, ce qui conduit aux conditions nécessaires d'optimalité du premier ordre (CN1) de Lagrange.


title: Conditions d'optimalité

text: Ce résultat, parfois appelé méthode du multiplicateur de Lagrange, est attribué à Lagrange qui l'énonça dans sa "Méchanique analytique" (1788). On en trouve toutefois déjà des traces dans des travaux d'Euler sur les problèmes isopérimétriques (1744). Lagrange utilisa d'abord cette méthode pour résoudre un problème de calcul des variations sous contraintes et plus tard, dans sa "Théorie des fonctions analytiques" (1797), il l'applique aux problèmes de la forme formula_197


title: Conditions d'optimalité

text: En l'absence de qualification de la contrainte, l'existence du multiplicateur n'est plus assurée, si bien que la condition nécessaire d'optimalité de Lagrange peut ne pas avoir lieu. Un exemple est donné dans la section suivante.


title: Conditions d'optimalité

text: En pratique, il est souvent commode de retrouver la condition de Lagrange en introduisant le lagrangien du problème.


title: Conditions d'optimalité

text: La variable formula_43 est aussi appelée variable primale ; quant au couple formula_199, on lui donne parfois le nom de variable(s) primale(s)-duale(s).


title: Conditions d'optimalité

text: Le lagrangien joue un rôle essentiel en optimisation avec contraintes. Le multiplicateur porte ce nom car il multiplie les contraintes dans le lagrangien, par l'intermédiaire du produit scalaire de formula_134. Sous les hypothèses du résultat ci-dessus, les conditions nécessaires d'optimalité du premier ordre peuvent maintenant s'écrire comme suit formula_201 Nous avons noté formula_202 [resp. formula_203] le gradient par rapport à formula_43 [resp. à formula_199]. Ce système (non linéaire, en toute généralité) permet souvent de calculer une "solution" du problème d'optimisation formula_148. En réalité, cette "solution" est ce que nous avons appelé un "point stationnaire". Ce n'est pas nécessairement un minimum local du problème (ce point peut être un "maximum local", qui n'est "a priori" pas ce que l'on cherche !), sauf si celui-ci est convexe.


title: Conditions d'optimalité

text: Pour les problèmes non convexes, ce sont les conditions du second ordre qui permettrons de sélectionner les minima locaux parmi les points stationnaires calculés.


title: Conditions d'optimalité

text: Il est utile de spécifier les conditions d'optimalité de Lagrange lorsque formula_119, formula_208 et que l'on munit ces espaces du produit scalaire euclidien


Conditions d'optimalité


title: Conditions d'optimalité

text: Il y a alors formula_120 variables formula_211 à optimiser et les formula_212 contraintes du problème formula_148 sont données explicitement au moyen de formula_212 fonctions formula_215 :


title: Conditions d'optimalité

text: Le lagrangien du problème s'écrit


title: Conditions d'optimalité

text: Observons que le multiplicateur de Lagrange formula_218 a autant de composantes qu'il y a de contraintes ; chacune des composantes formula_219 étant associée à une contrainte formula_220 ; on dit d'ailleurs que le multiplicateur formula_219 est associé à la contrainte formula_220. Si on utilise formula_223 pour désigner le gradient d'une fonction réelle de formula_120 variables par rapport au produit scalaire euclidien, c'est-à-dire le vecteur de ses dérivées partielles, les conditions d'optimalité s'écrivent sous la forme d'un système de formula_225 équations à formula_225 inconnues formula_227 :


title: Conditions d'optimalité

text: On voit donc qu'en la solution le gradient du critère est combinaison linéaire des gradients des contraintes (on se rappelle qu'en optimisation sans contrainte le gradient du critère est nul).


title: Conditions d'optimalité

text: Voici un exemple de problème avec 2 variables et 2 contraintes, avec solution, mais sans multiplicateur optimal et donc sans condition de Lagrange (c'est l'absence de qualification des contraintes qui produit cet effet) :


title: Conditions d'optimalité

text: formula_229 L'unique point admissible est le point formula_230, qui est donc l'unique solution du problème. Cependant les contraintes ne sont pas qualifiées en ce point car le cône tangent est réduit à formula_231 alors que le noyau de la jacobienne des contraintes est formula_232 (on note par ailleurs que cette jacobienne, qui est une matrice formula_233 ne saurait alors être surjective). Dans cet exemple, les conditions de Lagrange ne sont pas vérifiées (il n'y a pas de multiplicateur optimal), puisque le gradient de formula_8 en la solution ne peut être combinaison linéaire des gradients des contraintes (ces derniers sont linéairement dépendants) :


title: Conditions d'optimalité

text: Comme en optimisation sans contrainte, les conditions d'optimalité du second ordre permettent de sélectionner les éventuelles solutions parmi les points stationnaires (i.e., les points vérifiant la condition de Lagrange). Ces conditions du second ordre des problèmes avec contraintes d'égalité diffèrent de celles des problèmes sans contrainte sur deux points : D'où proviennent ces différences ?


title: Conditions d'optimalité

text: En optimisation sans contrainte, les conditions nécessaires du second ordre résultent du fait que dans le voisinage d'une solution, le critère prend une valeur supérieure à celle qu'il prend en la solution. Un développement de Taylor du critère autour d'une solution et l'utilisation du fait que son gradient est nul en la solution impliquent alors immédiatement que la hessienne du critère doit être semi-définie positive en la solution. Dans le cas des problèmes avec contraintes d'égalité, utiliser la même démarche ne conduirait nulle part, car le gradient du critère n'est pas nécessairement nul en une solution (selon la condition de Lagrange, il est dans l'image de l'adjointe de la jacobienne de la contrainte). En réalité, c'est le gradient du lagrangien qui s'annule en une solution. C'est donc un développement de Taylor de cette fonction qui pourra apporter de l'information sur sa hessienne. "Ceci explique le premier point ci-dessus". Par ailleurs, il est clair que sur l'ensemble admissible le lagrangien prend les mêmes valeurs que le critère, si bien qu'il prend aussi des valeurs supérieures à celle qu'il a en une solution. C'est la relation de monotonie recherchée qui conduira à la semi-définie positivité de la hessienne du lagrangien. Cependant, ce n'est que sur la variété des contraintes que cette relation de monotonie a lieu, si bien que la semi-définie positivité de la hessienne du lagrangien ne sera vérifiée que sur la variété linéarisée qu'est le cône tangent. "Ceci explique le second point ci-dessus".


title: Conditions d'optimalité

text: On devrait à présent mieux comprendre les conditions nécessaires du second ordre (CN2) pour un problème avec contraintes d'égalité, que voici.


title: Conditions d'optimalité

text: Ce résultat donne-t-il suffisamment de conditions ou aurait-on pu en obtenir d'autres ? Ce sont les bonnes conditions car, comme en optimisation sans contrainte, si l'on remplace la semi-définie positivité par la définie positivité, on obtient des conditions suffisantes d'optimalité du second ordre (abrégées par CS2).


title: Conditions d'optimalité

text: On notera que les CS2 ne requièrent pas d'hypothèse de qualification de contrainte.


title: Conditions d'optimalité

text: Vérifier la (semi-)définie positivité de la hessienne du lagrangien formula_237 dans le noyau de formula_139 ne pose pas de difficulté, pourvu que l'on puisse calculer une base de ce noyau. On peut en effet voir ce noyau comme l'image d'une application linéaire injective formula_239 tel que formula_240 avec formula_241 Il suffit alors de vérifier la (semi-)définie positivité de formula_242, ce qui peut se faire en temps polynomial par des techniques d'algèbre linéaire.


title: Conditions d'optimalité

text: Soit formula_1 un espace euclidien muni d'un produit scalaire noté formula_3 ; on note formula_4 la norme associée. On s'intéresse aux vecteurs propres d'une application linéaire formula_246 "auto-adjointe". Par exemple, on pourrait avoir formula_119, muni du produit scalaire euclidien, et formula_110 une matrice symétrique.


title: Conditions d'optimalité

text: Le problème d'optimisation


title: Conditions d'optimalité

text: Dans ce but, on considère le quotient de Rayleigh formula_249, défini en formula_250 par


title: Conditions d'optimalité

text: Comme formula_252 est constant le long des rayons issus de zéro, il revient au même de minimiser la fonction quadratique formula_253 définie en formula_105 par


Conditions d'optimalité


title: Conditions d'optimalité

text: sur la sphère unité formula_256 On considère donc le problème d'optimisation avec une unique contrainte d'égalité suivant


title: Conditions d'optimalité

text: Ce problème a toujours une solution (le critère est continu et, comme formula_1 est de dimension finie, formula_259 est compact). Calculons les points stationnaires du problème d'optimisation.


title: Conditions d'optimalité

text: Conditions d'optimalité du premier ordre


title: Conditions d'optimalité

text: La fonction formula_260 est non différentiable en zéro, mais cela n'a pas trop d'importance, car la solution est de norme un. On préfère toutefois définir l'ensemble admissible au moyen de la contrainte formula_261, qui se dérive plus facilement. Cette contrainte est qualifiée en tout point admissible, car sa jacobienne formula_262 est surjective si formula_263. Pour calculer la solution du problème d'optimisation, on introduit son lagrangien, qui prend en formula_264 la valeur


title: Conditions d'optimalité

text: Comme il y a une seule contrainte, il y a un seul multiplicateur formula_266.


title: Conditions d'optimalité

text: Les conditions d'optimalité de Lagrange s'écrivent


title: Conditions d'optimalité

text: Dès lors, formula_268 est un point stationnaire de multiplicateur formula_269 si, et seulement si, formula_268 est un vecteur propre unitaire de formula_110, de valeur propre formula_269. Ce multiplicateur est aussi la valeur du critère en formula_268, puisque formula_274. Dès lors, une solution du problème d'optimisation est un vecteur propre unitaire de valeur propre minimale. Si au lieu de minimiser formula_275, on minimisait formula_276 ou on "maximisait" formula_275, une solution du problème d'optimisation serait un vecteur propre unitaire de valeur propre maximale.


title: Conditions d'optimalité

text: Conditions d'optimalité du deuxième ordre


title: Conditions d'optimalité

text: La hessienne du lagrangien en une solution primale-duale formula_278 du problème d'optimisation est l'opérateur auto-adjoint formula_279 sur formula_280 Comme formula_269 est la valeur minimale de formula_282 sur la sphère unité, on a formula_283 pour tout vecteur unitaire formula_284 On peut en déduire que formula_285 pour tout vecteur formula_286 ce qui signifie que la hessienne du lagrangien formula_287 est semi-définie positive dans tout l'espace formula_1, pas seulement dans l'espace tangent à la contrainte comme l'assurent les CN2. C'est le caractère quadratique du critère et des contraintes qui permet d'avoir cette propriété.


title: Conditions d'optimalité

text: Si un couple formula_278 vérifie les CS2, alors formula_268 est un vecteur propre de formula_110 de valeur propre formula_269 ; de plus formula_293, pour tout vecteur unitaire formula_43, voisin mais différent de formula_268. On en déduit aisément que formula_296 pour tout formula_43 unitaire différent de formula_298 (on peut par exemple prendre formula_299 assez petit pour que formula_300, avec formula_301, soit voisin mais différent de formula_268 et développer la relation formula_303 qui en résulte). On en déduit que formula_269 est la valeur propre minimale et est simple (i.e., l'espace propre associé est de dimension 1). La réciproque est également vraie : si la plus petite valeur propre de formula_110 est simple, les CS2 sont vérifiées.


title: Conditions d'optimalité

text: Résultats obtenus


title: Conditions d'optimalité

text: Dans cette section, on considère le problème d'optimisation avec contraintes d'égalité et d'inégalité, que l'on écrit sous la forme suivante


title: Conditions d'optimalité

text: Cette écriture exprime le fait que l'on cherche à minimiser un critère formula_5 défini sur un espace euclidien formula_1 dont l'argument formula_43, qui est le vecteur des variables à optimiser, l'inconnue de ce problème, est contraint de respecter un nombre fini de contraintes spécifiées par des fonctions formula_310. Le produit scalaire de l'espace euclidien est noté formula_3. On y trouve des contraintes d'égalité et d'inégalité en nombre fini, repérées par des ensembles finis d'indices formula_312 et formula_313, dont le cardinal est noté


title: Conditions d'optimalité

text: Le nombre total de contraintes est noté formula_315.


title: Conditions d'optimalité

text: Il est commode de supposer que les ensembles d'indices formula_312 et formula_313 forment une partition de l'ensemble des formula_212 premiers entiers formula_319 :


title: Conditions d'optimalité

text: Si formula_321, on note formula_322 le vecteur de formula_323 formé des composantes formula_324 de formula_325 avec formula_326. De même pour formula_327. On peut alors rassembler les fonctions réelles formula_220 en une seule fonction formula_329, dont les composantes formula_330 et formula_331 sont utilisées pour définir les contraintes d'égalité et d'inégalité.


title: Conditions d'optimalité

text: L'ensemble admissible de formula_332 est noté


Conditions d'optimalité


title: Conditions d'optimalité

text: Ici et ci-dessous, les "inégalités vectorielles" doivent être comprises composante par composante : pour un vecteur formula_325, formula_335 signifie que formula_336 pour tout indice formula_337. Si en un point admissible formula_43, formula_339 est surjective, cet ensemble se présente autour de formula_43 comme une partie de la variété formula_341 formée des points qui vérifient aussi l'inégalité formula_342.


title: Conditions d'optimalité

text: L'ensemble admissible formula_343 d'un problème formula_332 convexe est clairement convexe.


title: Conditions d'optimalité

text: Comme la CN1 générique l'a montré, l'écriture des conditions d'optimalité du premier ordre passe par la détermination du cône tangent à l'ensemble admissible. Ce cône tangent en formula_43 est un concept "local", dans le sens où une modification de l'ensemble admissible en dehors d'un voisinage de formula_43 n'aura pas d'incidence sur le cône tangent en ce point. Dès lors si une contrainte d'inégalité prend une valeur strictement négative en formula_43, disons formula_348, une perturbation de cette contrainte ne modifiera pas l'ensemble admissible dans le voisinage de formula_284 Il est donc nécessaire de pouvoir nommer les contraintes d'inégalité qui sont nulles au point considéré, ce qui conduit à la notion suivante.


title: Conditions d'optimalité

text: Les problèmes d'optimisation avec contraintes d'inégalité sont considérablement plus difficiles à analyser et à résoudre numériquement (un calcul analytique, sur papier, est rarement possible et d'ailleurs souvent difficile lui aussi) que les problèmes rencontrés jusqu'ici. Lorsqu'il n'y a que des contraintes d'égalité, la compréhension du problème repose sur l'analyse mathématique classique, en particulier sur le théorème des fonctions implicites, ce qui explique que les conditions de Lagrange sont en général vues dans un cours de calcul différentiel et font ainsi partie du bagage de beaucoup de mathématiciens ou d'autres scientifiques. La situation est différente lorsque des contraintes d'inégalité sont présentes, car il faut alors faire appel à des outils spécifiques, essentiellement ceux de l'analyse convexe, moins souvent enseignés. Par ailleurs, numériquement, la difficulté principale provient du fait que, d'une manière ou d'une autre, le calcul de la solution détermine forcément les contraintes qui sont actives en cette solution. Si ces contraintes actives étaient connues, on pourrait se ramener au cas des problèmes avec seulement des contraintes d'égalité lisses. Or il y a formula_350 manières de rendre les formula_351 contraintes d'inégalité actives. C'est à ce nombre exponentiel que l'on fait allusion lorsque l'on parle de la combinatoire des problèmes d'optimisation avec contraintes d'inégalité. Celle-ci est redoutable et en rapport direct avec la conjecture "P = NP", puisqu'un problème d'optimisation quadratique non convexe (i.e., un problème avec un critère quadratique non convexe et des contraintes affines) est NP ardu. On est donc en présence d'un problème pour lequel il est vraisemblable que le principe de conservation des ennuis s'applique ; on veut dire par là que la difficulté du problème ne peut être éliminée en lui trouvant une autre formulation équivalente. Ainsi, on pourrait penser simplifier le problème en reformulant les contraintes d'inégalité par l'une des contraintes d'égalité apparemment plus simples et équivalentes suivantes


title: Conditions d'optimalité

text: Cependant la première contrainte est non lisse et la seconde, bien qu'une fois différentiable, n'est en général pas qualifiée dans le sens discuté ci-dessous.


title: Conditions d'optimalité

text: Si les conditions nécessaires d'optimalité des problèmes avec contraintes d'égalité ont été établies au , celles des problèmes avec contraintes d'inégalité sont beaucoup plus récentes, puisqu'elles datent du milieu du . Il est vraisemblable que le besoin d'une analyse fine de ces questions ait été stimulé par l'augmentation des moyens de calcul. Le développement de l'analyse convexe a aussi permis de poser la théorie sur des bases solides ; nous pensons en particulier au lemme de Farkas qui sera ci-dessous une des clés permettant de passer de la version géométrique à la version analytique des conditions d'optimalité du premier ordre.


title: Conditions d'optimalité

text: Le résultat suivant nous informe que le cône tangent est inclus dans le cône linéarisant, noté formula_353 et défini ci-dessous ; il lui sera égal dans les bons cas.


title: Conditions d'optimalité

text: Observons que, comme annoncé, seules les contraintes d'inégalité "actives" interviennent dans l'estimation du cône tangent qu'est le cône linéarisant. On retrouverait le noyau de la jacobienne des contraintes s'il n'y avait que des contraintes d'égalité.


title: Conditions d'optimalité

text: On peut faire, sur l'inclusion précédente, les mêmes remarques que celles que nous avons faites sur l'estimation du cône tangent à des contraintes d'égalité par le noyau de la jacobienne de ces contraintes : formula_354 ne dépend que de l'ensemble admissible formula_343, pas de la manière de le décrire par la fonction formula_166, alors que formula_357 dépend manifestement de formula_166. Il peut y avoir plusieurs fonctions formula_166 définissant le même ensemble admissible et, du point de vue de l'optimisation, toutes ne conviennent pas. Celles qui permettent d'obtenir des conditions d'optimalité sont celles pour lesquelles l'égalité formula_360 a lieu ; d'ailleurs le premier cône est difficile à calculer s'il n'est égal au second, alors que l'on dispose d'une formule explicite pour le second. On introduit donc la notion de qualification de (fonctions définissant les) contraintes suivante.


title: Conditions d'optimalité

text: En général, le cône tangent et le cône linéarisant diffèrent, car le premier n'est pas nécessairement convexe, alors que le second l'est (c'est un cône polyédrique convexe). Par ailleurs, la notion de qualification "des" contraintes a un aspect "global", dans le sens où elle porte sur toutes les fonctions définissant le problème d'optimisation ; il n'est pas question d'utiliser cette notion fonction par fonction parce que le cône tangent à une intersection d'ensembles n'est pas égal à l'intersection des cônes tangents à ces ensembles (voir l'article sur le cône tangent).


title: Conditions d'optimalité

text: Comme pour les problèmes avec contraintes d'égalité, il n'est presque jamais judicieux de remplacer les contraintes de formula_332 par l'unique contrainte d'égalité équivalente formula_183, où formula_181 est définie par


title: Conditions d'optimalité

text: même si le fait de n'avoir qu'une seule contrainte est "a priori" attrayant. Cette dernière contrainte a, en effet, l'inconvénient de n'être pratiquement jamais qualifiée, puisque formula_365 est nul en tout point admissible. Dès lors, pour cette contrainte, formula_366, qui est pratiquement toujours trop grand, plus grand que formula_367.


title: Conditions d'optimalité

text: Vérifier si les contraintes sont qualifiées est une tâche difficile. Cela requiert le calcul du cône tangent, que l'on voudrait surtout éviter s'il n'est pas identique au cône linéarisant. On connaît un certain nombre de conditions "suffisantes" de qualification de contraintes, qui sont plus subtiles que lorsque seules des contraintes d'égalité sont présentes. Elles sont présentées dans l'article Qualification de contraintes.


title: Conditions d'optimalité

text: On suppose dans cette section que les contraintes du problème formula_332 sont qualifiés, au sens précisé dans la section précédente. Si l'on veut trouver une expression plus explicite de la condition nécessaire d'optimalité du première ordre en formula_43, à savoir formula_370, il faut calculer le cône dual du cône tangent, que l'on suppose donc égal au cône dual du cône linéarisant formula_371. Il s'agit donc de calculer le dual d'un cône convexe polyédrique. Le lemme de Farkas fournit une réponse à cette question. Nous en donnons une version légèrement généralisée ci-dessous.


title: Conditions d'optimalité

text: On ne peut pas se passer de l'adhérence dans le membre de droite de l'identité car le cône formula_372 n'est pas nécessairement fermé (même si formula_34 est fermé) alors que, en tant que cône dual, le cône du membre de gauche est toujours fermé. Signalons que si formula_34 est un cône convexe "polyédrique" (comme l'orthant positif d'un certain formula_375), alors formula_372 est un polyèdre convexe, donc un fermé ; dans ce cas, on peut ôter l'adhérence dans le membre de droite.


title: Conditions d'optimalité

text: Simplifions les notations en posant formula_377, formula_378 et formula_379. On peut établir une expression "duale" du cône


Conditions d'optimalité


title: Conditions d'optimalité

text: en utilisant le lemme de Farkas généralisé avec On a noté formula_385. On vérifie facilement que


title: Conditions d'optimalité

text: Par le lemme de Farkas, on trouve alors la représentation duale du cône linéarisant suivante (il n'est pas nécessaire de prendre l'adhérence de l'ensemble obtenu, car il est fermé par sa polyédricité)


title: Conditions d'optimalité

text: On en déduit les conditions nécessaires d'optimalité du premier ordre suivantes, dites de Karush, Kuhn et Tucker (KKT). Elles sont fondamentales.


title: Conditions d'optimalité

text: Un point formula_12 vérifiant les conditions (KKT) ci-dessus est dit stationnaire pour le problème formula_332.


title: Conditions d'optimalité

text: Les conditions nécessaires d’optimalité ci-dessus ont longtemps été attribuées à Kuhn et Tucker (1951). Après bien des années, on constata que ces conditions avaient déjà été données par Karush (1939) dans une thèse qui ne fut jamais publiée, mais qui est décrite dans le compte rendu historique de Kuhn. Une approche différente conduisant au même résultat a été suivie par John (1948), également avant les travaux de Kuhn et Tucker.


title: Conditions d'optimalité

text: Avant de discuter le système (KKT), introduisons le lagrangien du problème, qui a la même forme que pour les problèmes d'optimisation avec contraintes d'égalité.


title: Conditions d'optimalité

text: La variable formula_43 est aussi appelée variable primale ; quant au couple formula_199, on lui donne parfois le nom de variable(s) primale(s)-duale(s).


title: Conditions d'optimalité

text: Voici quelques commentaires sur les conditions de Karush, Kuhn et Tucker.


title: Conditions d'optimalité

text: Les conditions de KKT sont compliquées et difficiles à résoudre numériquement (elles ne le sont analytiquement que pour de rares problèmes à la structure particulière ; des exemples sont donnés ci-dessous). Il n'y a cependant ni trop ni trop peu de conditions, comme le montre la démonstration de la propriété suivante, stipulant que, si le problème est convexe, ces conditions sont suffisantes pour impliquer l'optimalité globale.


title: Conditions d'optimalité

text: Soit formula_414 un multiplicateur optimal (ou solution duale) associé à une solution formula_88 du problème formula_332. Il sera utile d'introduire les ensembles d'indices suivants : formula_417 Ce sont donc des ensembles d'indices qui dépendent à la fois de formula_12 et formula_419. Les contraintes d'indices formula_420 sont dites fortement actives et celles d'indices formula_421 sont dites faiblement actives. Ces dernières, bien qu'actives (formula_407), peuvent être ôtées du problème sans modifier la stationnarité de formula_12 (formula_406).


title: Conditions d'optimalité

text: Il peut y avoir plus d'une solution duale formula_419 associée à une solution primale formula_12. L'ensemble des multiplicateurs associés à formula_12 est noté formula_428 La solution formula_12 étant fixée, les conditions d'optimalité de KKT montrent que formula_430 est un polyèdre convexe de formula_431 : formula_432 En particulier, formula_430 est fermé. Il est non vide si les contraintes sont qualifiées en formula_12 (théorème d'optimalité de KKT). Par ailleurs, formula_435 est un sommet de formula_430 si formula_437 est surjective. En particulier, formula_430 n'a pas de sommet si formula_439 n'est pas surjective.


title: Conditions d'optimalité

text: Cet ensemble formula_430 est clairement réduit à un seul multiplicateur si les conditions de qualification (QC-IL) (indépendance linéaire des gradients des contraintes actives) sont vérifiées en formula_12. Mais, l'unicité du multiplicateur optimal a lieu, en fait, sous une condition plus faible que (QC-IL), mais plus forte que la qualification de Mangasarian-Fromovitz (QC-MF), celle que donne le résultat suivant. Cette condition est aussi nécessaire et suffisante et est parfois appelée la condition de qualification de Mangasarian-Fromovitz stricte (QC-MFS).


title: Conditions d'optimalité

text: Mais en toute généralité, formula_430 peut ne pas être réduit à un point. En ce qui concerne le caractère borné de formula_430, on a le résultat suivant.


title: Conditions d'optimalité

text: Les conditions d'optimalité de Karush, Kuhn et Tucker nous apprennent que, sous certaines conditions, en particulier de qualification des contraintes, une solution locale de formula_332 est un point stationnaire de ce problème, ce qui veut dire qu'elle vérifie l'ensemble des relations que nous avons désignées par (KKT) ci-dessus. Pour calculer les solutions de formula_332, on pourra donc, dans un premier temps, calculer les solutions du système d'optimalité (KKT). Toutefois, ce calcul est beaucoup plus difficile que lorsqu'il n'y a que des contraintes d'égalité. La difficulté vient de la présence d'inégalités et, en particulier, des conditions de complémentarité. Comme nous allons le voir, nous y retrouverons la "combinatoire des problèmes d'optimisation avec contraintes d'inégalité", confirmant ainsi le "principe de conservation des ennuis" dont nous avons déjà parlé.


title: Conditions d'optimalité

text: En général, il faut utiliser des algorithmes spécifiques pour résoudre ce système d'optimalité (c'est ce à quoi est consacré une grande partie de l'optimisation numérique). Dans certains cas, cependant, en particulier pour des problèmes de petite taille ayant peu de contraintes d'inégalité ou des problèmes très structurés, on peut chercher les solutions de ce système (KKT) analytiquement en considérant l'une après l'autre toutes les manières de satisfaire les contraintes d'inégalité. Dans chaque cas considéré, on suppose qu'un certain nombre de contraintes d'inégalité sont actives et que les autres ne le sont pas. Soit formula_446, l'ensemble des indices des contraintes d'inégalité supposées actives en la solution : formula_447 et formula_448 (on a noté formula_449 le complémentaire de formula_450 dans formula_313). Du fait de la complémentarité, formula_452 et on est donc conduit à chercher les solutions du système de formula_453 équations à formula_453 inconnues suivant


title: Conditions d'optimalité

text: Si une solution formula_456 de ce système vérifie formula_457 et formula_458, le couple formula_459 est une solution de (KKT). Sinon cette solution doit être écartée. En examinant ainsi tous les ensembles formula_446 possibles, on peut trouver tous les points stationnaires du problème.


title: Conditions d'optimalité

text: La méthode présentée ci-dessus est fastidieuse et, répétons-le, n'est utilisée que dans de rares cas. On notera en effet qu'avec formula_351 contraintes d'inégalité, il y a formula_350 cas à examiner, et donc formula_350 systèmes non linéaires à résoudre. C'est une tâche considérable dès que formula_351 dépasse quelques unités ! C'est ici que l'on retrouve la "combinatoire des problèmes d'optimisation". Le but des algorithmes d'optimisation pour problèmes avec contraintes d'inégalité est précisément de trouver des solutions du système d'optimalité (KKT), en gérant de manière efficace cette combinatoire, c'est-à-dire en évitant d'explorer toutes les possibilités. L'algorithme du simplexe en a été un des premiers exemples.


title: Conditions d'optimalité

text: Comme pour les problèmes d'optimisation avec contraintes d'égalité, tous les points stationnaires (les solutions de (KKT)) ne sont pas solutions de formula_332. Pour déterminer si un point stationnaire est solution de formula_332, on pourra utiliser les conditions d'optimalité du second ordre décrites ci-dessous, de la manière suivante : Ces deux cas recouvrent un grand nombre de situations, mais pas toutes, car les CN2 et les CS2 ne sont pas identiques. Le cas est indéterminé lorsqu'un point stationnaire vérifie les CN2, mais pas les CS2. Alors les résultats donnés dans cet article ne sont pas suffisants et il faut recourir à des conditions d'optimalité d'ordre supérieur pour pouvoir dire si le point stationnaire est solution de formula_332.


title: Conditions d'optimalité

text: Les conditions d'optimalité du second ordre en présence de contraintes d'inégalité ne s'obtiennent ni ne s'écrivent aussi aisément que lorsqu'il n'y a que des contraintes d'égalité. D'abord, ce n'est pas le cône tangent qui intervient comme pour les problèmes avec contraintes d'égalité, mais un cône plus petit que l'on appelle le "cône critique". Par ailleurs, le multiplicateur optimal qui intervient dans la hessienne du lagrangien doit être déterminé en fonction de la direction choisie dans le cône critique. Nous commencerons la présentation des conditions du deuxième ordre du problème formula_332 par deux sous-sections donnant un premier éclairage sur ces changements importants. Ensuite viendront les conditions nécessaires puis les conditions suffisantes du second ordre.


title: Conditions d'optimalité

text: Il est tentant d'essayer de généraliser les conditions nécessaires du second ordre du problème formula_148 au problème formula_332, en cherchant à montrer qu'en une solution primale-duale formula_227, on doit avoir formula_474 positif pour toute direction tangente formula_475. Comme précédemment, on a noté formula_476 la hessienne du lagrangien en formula_227. Ce résultat n'est pas correct, car le cône tangent formula_478 n'est pas celui qui convient, comme le montre le problème suivant formula_479 Ce problème a pour unique solution primale-duale formula_480 et le cône tangent en la solution s'écrit formula_481 si bien que l'on peut prendre formula_482 comme direction tangente, mais formula_483 n'est pas positif. Nous verrons que formula_474 est positif, mais pour des directions formula_47 dans un cône plus petit que le cône tangent.


title: Conditions d'optimalité

text: À la recherche d'un cône plus petit, on peut observer que, comme toute solution formula_12 du problème formula_332 minimise aussi formula_8 sur formula_489 les conditions du second ordre des problèmes avec contraintes d'égalité nous apprennent que formula_474 est positif pour toute direction formula_491 et toute solution duale formula_435 (celles-ci sont aussi solutions duales du problème minimisant formula_8 sur formula_494). Nous verrons cependant que le cône formula_495 est trop petit, dans le sens où il ne permet pas d'établir des conditions suffisantes d'optimalité du second ordre. Considérons en effet le problème formula_496 Si formula_497, formula_498, si bien que formula_499 et la hessienne du lagrangien formula_500 est bien définie positive sur formula_501, mais formula_12 n'est pas un minimum local du problème.


title: Conditions d'optimalité

text: Le bon cône s'avérera être le cône linéarisant formula_503 de l'ensemble formula_504 sur lequel formula_8 est également minimisée en une solution formula_12 du problème formula_332. Ce cône est plus petit que le cône tangent à l'ensemble admissible en formula_12, mais suffisamment grand pour permettre d'avoir des conditions suffisantes d'optimalité du second ordre. On l'appelle le cône critique du problème.


title: Conditions d'optimalité

text: Dans le premier exemple ci-dessus, formula_509 est plus petit que le cône tangent formula_510. Dans le second exemple ci-dessus, formula_511 est plus grand que le cône tangent formula_499. Il est remarquable que l'optimalité au second ordre puisse être synthétisée au moyen de l'unique cône critique, alors que les deux problèmes précédents recouvrent des situations très différentes.


title: Conditions d'optimalité

text: En un point stationnaire formula_12, de multiplicateur formula_419, le cône critique en formula_12 s'écrit aussi formula_516 où les ensembles d'indices formula_517 et formula_518 ont été introduits ci-dessus. Ces expressions s'obtiennent en utilisant les conditions d'optimalité de KKT. Observons enfin que si les conditions de complémentarité stricte sont satisfaites, le cône critique s'écrit simplement formula_519 qui est donc le cône linéarisant formula_520 (un sous-espace vectoriel). En l'absence de complémentarité stricte, ce dernier sous-espace vectoriel est contenu dans formula_521, lui-même contenu dans formula_522.


title: Conditions d'optimalité

text: Une autre difficulté dans l'établissement des conditions d'optimalité du second ordre du problème formula_332 provient du fait que l'on doit prendre le multiplicateur optimal formula_419 intervenant dans la hessienne du lagrangien formula_525 en fonction de la direction critique choisie. Les trois exemples suivant devraient permettre de mieux comprendre pourquoi il en est ainsi et d'apprendre à sélectionner correctement les quantificateurs qui s'appliquent à formula_526 et formula_435.


title: Conditions d'optimalité

text: Considérons d'abord le problème à deux variables réelles formula_528 dont la solution est formula_230. Il y a un unique multiplicateur optimal associé à la contrainte, valant formula_530. La contrainte étant active, formula_227 est aussi la solution primale-duale du problème avec contrainte d'égalité formula_532, si bien que la hessienne du lagrangien formula_533 doit être semi-définie positive dans l'espace tangent à la contrainte (voir ci-dessus) : formula_534 pour toute direction formula_47 dans formula_536. C'est le cas le plus simple qui peut se présenter. On dira plus loin que l'on a des "conditions d'optimalité du deuxième ordre fortes" : quel que soit le multiplicateur optimal (il n'y en a qu'un seul ici), formula_537 est semi-défini positif dans le cône critique. Ces conditions sont vérifiées s'il y a un unique multiplicateur, comme ici, ou comme lorsque la condition de qualification (QC-A) ou (QC-IL) a lieu.


title: Conditions d'optimalité

text: Considérons à présent une variante du problème précédent où l'on ajoute une contrainte superflue formula_538 La seconde contrainte ne modifie pas la solution primale qui est toujours formula_230, mais il y a maintenant plusieurs multiplicateurs optimaux formant l'ensemble formula_540 formula_541. En prenant comme multiplicateur formula_542, un sommet de formula_430, on ignore la seconde contrainte (comme il se doit) et on a le résultat précédent sur la semi-définie positivité de formula_544 dans formula_536. Par contre, avec formula_546, l'autre sommet de formula_430, la hessienne du lagrangien formula_548 est définie "négative" dans formula_536. C'est normal ; le lagrangien ne voit que la seconde contrainte, ignorant la première, et formula_550 n'est qu'un point stationnaire du problème formula_551, pas un minimum local. On dira plus loin que l'on a des "conditions d'optimalité du deuxième ordre semi-fortes" : il existe un multiplicateur optimal tel que formula_537 est semi-défini positif dans le cône critique.


title: Conditions d'optimalité

text: Considérons enfin le problème à trois variables formula_553 On voit que, quel que soit formula_554 non nul, un des membres de droite des contraintes est strictement positif. Dès lors, l'unique solution de ce problème est formula_497. D'autre part, l'ensemble des multiplicateurs optimaux est le simplexe unité formula_556. Enfin, la hessienne du lagrangien s'écrit formula_557 Quelle que soit la valeur de formula_435, formula_537 n'est pas semi-définie positive sur le cône critique, qui est ici le sous-espace formula_560 (en effet, l'élément formula_561 vaut formula_562 et l'élément (2,2) vaut formula_563, si bien qu'il faudrait que formula_564 soit supérieur à 3/4 et inférieur à 2/3). On dira plus loin que l'on a des "conditions d'optimalité du deuxième ordre faibles" : pour toute direction critique formula_47, il existe un multiplicateur optimal formula_419 (dépendant de formula_47) tel que formula_568.


title: Conditions d'optimalité

text: Voici des conditions nécessaires d'optimalité du second ordre lorsque la qualification Mangasarian-Fromovitz (QC-MF) a lieu en la solution formula_12 du problème.


title: Conditions d'optimalité

text: Les conditions nécessaires d'optimalité du second ordre (CN2) énoncées dans ce résultat sont dites faibles, car le multiplicateur optimal est choisi en fonction de la direction critique. Dans certains problèmes, on a la condition plus forte (mois souvent vérifiée) suivante formula_570 On dit alors que l'on a des conditions nécessaires d'optimalité du second ordre semi-fortes. Dans certains cas, l'on a des conditions encore plus fortes, à savoir formula_571 On dit alors que l'on a des conditions nécessaires d'optimalité du second ordre fortes. Comme l'affirme le résultat suivant, ce dernier cas est vérifié lorsque la qualification (QC-A) ou (QC-IL) a lieu.


title: Conditions d'optimalité

text: La vérification numérique des conditions nécessaires d'optimalité du second ordre n'est pas aisée. Déjà, lorsque les conditions semi-fortes ont lieu pour un multiplicateur optimal formula_419, il s'agit de vérifier que la forme quadratique formula_573 associée à la hessienne du lagrangien est semi-définie positive sur le cône critique formula_521, qui est polyédrique, c'est-à-dire que formula_537 est formula_521-copositive. En toute généralité, une telle vérification est un problème NP-ardu. Maintenant, s'il y a aussi complémentarité stricte, le cône critique devient un sous-espace vectoriel et la vérification de la semi-définie positivité de formula_573 sur ce sous-espace est alors une opération simple d'algèbre linéaire.


title: Conditions d'optimalité

text: Les conditions suffisantes du second ordre (CS2) s'obtiennent comme pour les problèmes plus simples en requérant que formula_474 soit "strictement" positif pour un multiplicateur dépendant d'une direction critique formula_47 choisie dans le cône critique. Le fait que le cône critique intervienne aussi dans ces conditions suffisantes d'optimalité est une garantie de sa pertinence.


title: Conditions d'optimalité

text: L'inégalité obtenue en conclusion du résultat précédent est connue sous le nom de propriété de croissance quadratique. Elle montre que formula_8 croît au moins quadratiquement lorsqu'on se déplace de formula_12 vers l'«intérieur» de l'ensemble admissible formula_343.


title: Conditions d'optimalité

text: Les inégalités de Hölder généralisent l'inégalité de Cauchy-Schwarz, dans le sens où elles donnent une majoration du produit scalaire euclidien de deux vecteurs formula_43 et formula_584 par leur norme formula_585 et formula_586, plutôt que par leur norme euclidienne. Dans cette majoration, les scalaires formula_587 et formula_588 doivent être pris dans formula_589 et vérifier


Conditions d'optimalité


title: Conditions d'optimalité

text: Cette relation accepte les valeurs infinies, si bien que formula_591 si, et seulement si, formula_592. Pour de tels formula_587 et formula_588, l'inégalité de Hölder s'écrit : Cette inégalité se généralise aux espaces formula_585 des suites de puissance formula_587 sommables et aux espaces formula_597 des fonctions de puissance formula_587 intégrables. Dans formula_396, elles peuvent être démontrées à partir d'une solution du problème de minimisation d'une fonction linéaire sur la boule unité fermée associée à la norme formula_585, à savoir formula_601, problème qui s'écrit


title: Conditions d'optimalité

text: Par la compacité de formula_603 (en dimension finie), ce problème a clairement une solution ; elle est unique si formula_604, qui s'écrit


title: Conditions d'optimalité

text: se décompose en formula_120 problèmes indépendants, à savoir


title: Conditions d'optimalité

text: dont les solutions formula_608 sont triviales :


title: Conditions d'optimalité

text: L'inégalité de Hölder correspondante s'obtient alors en observant que, quels que soient formula_609 et formula_584, on a si l'on note formula_611 le signe de formula_612 :


title: Conditions d'optimalité

text: si bien que formula_614. On met ensuite formula_43 à l'échelle si ce vecteur n'est pas dans la boule unité formula_616, ce qui conduit à formula_617.


title: Conditions d'optimalité

text: Si formula_618, tout formula_619 est solution et l'inégalité de Hölder est triviale.


title: Conditions d'optimalité

text: Supposons à présent que formula_620. En écrivant la contrainte formula_621 de manière à la rendre différentiable et éviter le facteur formula_587 après différentiation, le lagrangien du problème formula_623 s'écrit


title: Conditions d'optimalité

text: Comme la contrainte est qualifiée (par les conditions suffisantes de Slater par exemple) et le problème est convexe, formula_268 en est solution si, et seulement si, il existe un multiplicateur optimal formula_626 tel que les conditions de KKT suivantes soient vérifiées :


title: Conditions d'optimalité

text: Comment résoudre ce système compliqué ? Comme le suggère la méthode générale présentée ci-dessus, il est souvent judicieux de commencer par considérer les conditions de complémentarité (la ), qui ont ici une "combinatoire" particulièrement réduite. Il y a seulement deux possibilités (parce que le problème n'a qu'une seule contrainte) : soit le multiplicateur est nul, soit la contrainte est active. Lorsque formula_620, la première condition montre clairement que le multiplicateur ne peut être nul ; la contrainte est donc active, ce qui résout du même coup la seconde condition. Gardons en mémoire que le multiplicateur optimal est positif () en exploitant la première condition. En prenant la norme formula_586 de formula_630, on obtient la valeur du multiplicateur optimal


title: Conditions d'optimalité

text: qui est donc strictement positif. En observant que formula_608 et formula_633 sont de signe contraire et en se rappelant que formula_620, la première condition donne alors


title: Conditions d'optimalité

text: où on a noté formula_611 le signe de formula_612. En particulier, formula_637 si formula_638.


title: Conditions d'optimalité

text: L'inégalité de Hölder correspondante se déduit de ces résultats comme dans le cas formula_639. Quels que soient formula_619 et formula_584, on a :


title: Conditions d'optimalité

text: si bien que formula_643. On met ensuite formula_43 à l'échelle si ce vecteur n'est pas dans la boule unité formula_603, ce qui conduit à formula_646.


title: Conditions d'optimalité

text: Le cas où formula_618 étant trivial, on considère ci-dessous que formula_620.


title: Conditions d'optimalité

text: Il n'est pas nécessaire de résoudre formula_649 si l'on ne cherche qu'à obtenir l'inégalité de Hölder correspondante puisque celle-ci est identique au cas formula_639 déjà considéré. En réalité, ce qui nous intéresse ici est de savoir comment résoudre formula_649 en utilisant les conditions d'optimalité de KKT. Donc poursuivons !


title: Conditions d'optimalité

text: La première difficulté à surmonter est de récrire la contrainte formula_652 de manière différentiable (la norme formula_653 ne l'est pas). On vérifiera sans peine que formula_652 si, et seulement si, il existe un vecteur formula_655 tel que formula_656 et formula_657, si bien que le problème formula_649 est «équivalent» au problème en formula_659 suivant


Conditions d'optimalité


title: Conditions d'optimalité

text: Ayant un domaine admissible compact et non vide, ce problème a aussi une solution ; de plus formula_268 est solution de formula_649 si, et seulement si, formula_663 est solution de formula_664. Le lagrangien du problème formula_664 s'écrit


title: Conditions d'optimalité

text: Comme les contraintes de formula_664 sont qualifiées (par affinité locale par exemple) et comme le problème est convexe, formula_663 en est une solution si, et seulement si, il existe des multiplicateurs optimaux formula_669 tels que les conditions de KKT suivantes soient vérifiées :


title: Conditions d'optimalité

text: où formula_671 est un vecteur dont toutes les composantes valent 1. Voici un système avec une "combinatoire" importante : formula_672 manières de réaliser les conditions de complémentarité (f). La méthode générale présentée ci-dessus est ici de peu d'utilité ; pour s'en sortir, il faut être astucieux ! On remarque d'abord que, par (a) et (b), l'on peut écrire formula_673 et formula_674 en fonction de formula_269 :


title: Conditions d'optimalité

text: Par (e), on en déduit que formula_677. Mais si formula_678, formula_673 et formula_674 seraient strictement positifs et on déduirait de (f) que formula_681, en contradiction avec (c). Dès lors


title: Conditions d'optimalité

text: comme lorsque formula_683, alors formula_684, formula_685, puis formula_686 par (e), donc formula_687, On déduit de ces observations que les solutions formula_268 de formula_649 vérifient


title: Conditions d'optimalité

text: où formula_698, formula_699 est son complémentaire et formula_700 désigne le produit de Hadamard. Inversement, on vérifie que si formula_268 satisfait les conditions encadrées, si formula_702, si formula_703, si formula_704 et si formula_705, alors formula_706 satisfait les conditions d'optimalité (a)-(f), si bien qu'alors formula_268 est une solution de formula_649.


title: Conditions d'optimalité

text: L'inégalité de Hölder correspondante se déduit de ces résultats comme dans le cas formula_709 et formula_584, on a :


title: Conditions d'optimalité

text: si bien que formula_712. On met ensuite formula_43 à l'échelle si ce vecteur n'est pas dans la boule unité formula_714, ce qui conduit à formula_715.


title: Conditions d'optimalité

text: Dans cette section, on considère le problème d'optimisation avec contraintes plus générales, que l'on écrit sous la forme suivante formula_716 Cette écriture exprime le fait que l'on cherche à minimiser un "critère" formula_5 défini sur un espace euclidien formula_1 dont l'argument formula_43, qui est le vecteur des variables à optimiser, l'inconnue de ce problème, est contraint de respecter des contraintes spécifiées par l'expression formula_720. Celle-ci signifie que l'image de formula_43 par la "fonction" formula_722 doit appartenir au "convexe fermé non vide" formula_723 de l'espace euclidien formula_134. Le produit scalaire des espaces euclidiens formula_1 et formula_134 sont tous deux notés formula_3.


title: Conditions d'optimalité

text: On désigne par formula_728 l'ensemble admissible du problème formula_729.


title: Conditions d'optimalité

text: Le problème formula_729 est bien une généralisation du problème formula_332, puisqu'on retrouve ce dernier en prenant formula_732 Un des intérêts de cette formulation générale est d'avoir tout son sens en dimension infinie, ce qui n'est pas le cas de formula_332. Il est en effet malaisé de spécifier ce qu'est un ensemble infini de contraintes d'inégalité à valeurs dans un espace de dimension infinie. On peut donc voir la généralisation proposée comme un premier pas dans l'étude des problèmes d'optimisation de dimension infinie. Les résultats obtenus sont cependant aussi utiles pour résoudre certains problèmes de dimension finie à la structure différente de celle de formula_332. Un autre avantage de cette généralisation est de mieux faire ressortir la structure des objets manipulés, ainsi que celle des raisonnements employés.


title: Conditions d'optimalité

text: On sait que la convexité joue un rôle crucial en optimisation. On est donc conduit à définir ce qu'est un problème formula_729 convexe.


title: Conditions d'optimalité

text: On a la propriété attendue suivante formula_736 Dans le cas du problème formula_332, formula_738 et la convexité de formula_739 revient à dire que formula_330 est affine et formula_331 a toutes ses composantes convexes.


title: Conditions d'optimalité

text: Des conditions d'optimalité du premier ordre pour formula_729 peuvent s'obtenir comme pour les problèmes précédents, par l'intermédiaire de la condition du premier ordre générique de Peano-Kantorovitch. Cette condition requiert le calcul du cône tangent formula_743 à l'ensemble admissible formula_744. Comme précédemment, on cherche à exprimer ce cône tangent en «linéarisant» les objets formula_166 et formula_723 qui définissent l'ensemble admissible. Cette linéarisation se fait en formula_43 pour formula_166, qui est définie sur formula_1, et en formula_750 pour formula_723, qui est défini sur formula_134. Cette opération conduit au cône formula_753, plus grand que formula_754, que l'on appelle le cône linéarisant de formula_744.


title: Conditions d'optimalité

text: On n'a pas nécessairement l'égalité entre les deux cônes, car formula_753 est convexe (c'est l'image réciproque par l'application linéaire formula_339 du cône tangent formula_758, qui est convexe par la convexité de formula_723) alors que formula_754 ne l'est pas nécessairement (on n'a pas imposé à la fonction formula_166 définissant formula_744 d'être affine et donc l'ensemble admissible formula_744 n'est pas nécessairement convexe). C'est gênant, car c'est le cône tangent formula_743 qui intervient dans la condition nécessaire d'optimalité générique de Peano-Kantorovitch alors que le cône linéarisant formula_765 a l'avantage d'avoir une expression analytique que l'on aimerait pouvoir exploiter. Comme pour le problème formula_332, la notion de qualification des contraintes définissant formula_744 est liée au fait de pouvoir avoir l'égalité entre les deux cônes, "mais pas seulement". La technique de démonstration conduisant aux conditions d'optimalité du premier ordre de Karush, Kuhn et Tucker, technique qui sera aussi utilisée pour obtenir la condition du premier ordre ci-dessous, cherche à montrer que le gradient formula_92 appartient à un cône que l'on peut expliciter. Deux ingrédients interviennent dans cette approche : Ici formula_765 n'est pas polyédrique, parce que l'on ne veut pas imposer cette propriété restrictive de polyédricité à formula_723. De manière à sélectionner les problèmes non convexes pour lesquels on peut utiliser l'approche proposée pour établir les conditions d'optimalité du premier ordre, on introduit une hypothèse, dite "de qualification", qui assure précisément l'égalité entre le cône tangent et le cône linéarisant (c'est la première condition ci-dessous), mais aussi le caractère fermé de l'image par formula_771 du dual du cône linéarisant (c'est la seconde condition ci-dessous).


title: Conditions d'optimalité

text: Vérifier que formula_166 est qualifié pour représenter formula_744 est une tâche difficile. Cela requiert le calcul du cône tangent, que l'on voudrait surtout éviter s'il n'est pas identique au cône linéarisant. La condition "suffisante" de qualification la plus utilisée, généralisant au problème formula_729 la condition de Mangasarian-Fromovitz du problème formula_332, est celle de Robinson. On y note formula_776 l'intérieur d'un ensemble formula_68


title: Conditions d'optimalité

text: Cette condition de Robinson est davantage examinée dans la section Condition suffisante de qualification de Robinson.


title: Conditions d'optimalité

text: Précisons quelques notations qui seront utilisées dans l'énoncé des conditions du premier ordre. Comme ci-dessus, formula_778 est le gradient de formula_8 en formula_12 et formula_781 est l'opérateur adjoint de la dérivée formula_782 (c'est un opérateur linéaire) pour les produits scalaires donnés sur formula_1 et formula_134 ; si formula_68 est un ensemble, formula_786 est le cône dual négatif de formula_68 ; enfin, la notation formula_788 signifie les trois conditions suivantes : formula_789


title: Conditions d'optimalité

text: Un point formula_88 tel que formula_227 vérifie les conditions d'optimalité du premier ordre ci-dessus pour un certain formula_792 est qualifié de stationnaire.


title: Conditions d'optimalité

text: Dans la première condition d'optimalité formula_793, on reconnaît le gradient du lagrangien du problème formula_729 qui est la fonction formula_795 définie en formula_796 par formula_797 Dans le cas où formula_798 est un cône convexe, on reconnait dans la seconde condition d'optimalité formula_799, des conditions de complémentarité généralisées, déjà présentent dans les conditions de KKT.


title: Conditions d'optimalité

text: Lorsque le problème formula_729 est convexe dans le sens précisé précédemment, les conditions nécessaires du premier ordre deviennent suffisantes, comme pour le problème formula_332.


title: Conditions d'optimalité

text: Désignons par formula_802 l'ensemble des multiplicateurs optimaux associés à un point stationnaire formula_88 de formula_729 et par formula_805 son cône asymptotique.


title: Sokoli

text: Sokoli est une localité de Croatie située dans la municipalité de Čabar, dans le comitat de Primorje-Gorski Kotar. En 2001, la localité comptait 20 habitants.


title: Jacques Saglier

text: Jacques Saglier, né à Paris le et mort le , est un chirurgien cancérologue et plasticien français, spécialiste des maladies du sein.


title: Jacques Saglier

text: Jacques Saglier commence ses études médicales au CHU Broussais-Hôtel-Dieu en 1970. Reçu au concours 1975 de l'internat des hôpitaux de Paris, il se forme en chirurgie générale et soutient en 1982 une thèse de médecine sur les cystectomies partielles pour tumeurs de vessie.


title: Jacques Saglier

text: En 1977-1978, il effectue un séjour d'un an au Gabon comme coopérant, suivie en 1979 d'un séjour au Tchad dans le cadre de Médecins sans frontières. Il est nommé chef de clinique des universités-assistant des hôpitaux de Paris en 1982.


title: Jacques Saglier

text: Sa formation spécialisée, particulièrement axée sur la pathologie mammaire, s'est poursuivie en post-universitaire et lui permet d'être titulaire d'une triple qualification ordinale, en chirurgie générale, cancérologie, et chirurgie plastique reconstructrice et esthétique.


title: Jacques Saglier

text: Il est membre de la Société française de sénologie et pathologie mammaire et du conseil scientifique de la Société française de cancérologie privée, et collabore au Réseau francilien d'oncologie (ONCORIF) comme corédacteur du référentiel consacré au cancer du sein. Son activité est exclusivement consacrée à la chirurgie du sein, particulièrement axée sur la convergence entre cancérologie et chirurgie plastique (chirurgie oncoplastique, chirurgie de reconstruction du sein). Il a également une activité de chirurgie plastique et esthétique du sein et de la silhouette.


title: Srednja Draga

text: Srednja Draga est une localité de Croatie située dans la municipalité de Čabar, dans le comitat de Primorje-Gorski Kotar. En 2001, la localité comptait 33 habitants.


title: Tropeti

text: Tropeti est une localité de Croatie située dans la municipalité de Čabar, dans le comitat de Primorje-Gorski Kotar. En 2001, la localité comptait 13 habitants.


title: Championnat de Finlande de football 1993

text: La saison 1993 du Championnat de Finlande de football était la de la première division finlandaise à poule unique, la "Veikkausliiga". Les douze meilleurs clubs du pays jouent les uns contre les autres à deux reprises durant la saison. À la fin de cette première phase, les 8 premiers disputent la poule pour le titre tandis que les 4 derniers affrontent les 4 premiers de deuxième division au sein d'une poule de promotion-relégation. Pour permettre le passage de la "Veikkausliiga" de 12 à 14 équipes, les 6 premiers de cette poule de barrage participeront à la première division la saison prochaine.


text: Le FC Jazz Pori remporte le tout premier titre de son histoire en terminant en tête de la première phase puis de la poule pour le titre, avec 4 points d'avance sur le MyPa 47 Anjalankoski et 9 sur le tenant du titre, le HJK Helsinki. Le HJK perd son titre de champion mais remporte un trophée cette saison après sa victoire en finale de la Coupe de Finlande face au RoPS Rovaniemi.


text: Le barème de points servant à établir les classements se décompose ainsi :


text: Les clubs conservent les points et résultats acquis lors de la première phase et rencontrent une fois chacun des adversaires de la poule.


text: Les clubs provenant de Ykkonen sont indiqués en italique. Les 6 premiers accèdent ou se maintiennent en première division.


title: Tršće (Čabar)

text: Tršće est une localité de Croatie située dans la municipalité de Čabar, dans le comitat de Primorje-Gorski Kotar. En 2001, la localité comptait 428 habitants.


title: Vode

text: Vode est une localité de Croatie située dans la municipalité de Čabar, dans le comitat de Primorje-Gorski Kotar. En 2001, la localité comptait 41 habitants.