Séance de cours

La dualité lagrangienne : théorie et applications

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Dans cours

MGT-418: Convex optimization

This course introduces the theory and application of modern convex optimization from an engineering perspective. ...

Description

Cette séance de cours couvre la dualité lagrangienne dans l'optimisation convexe, en commençant par les problèmes de forme conique et leur équivalence à la programmation linéaire. Il explore la relation entre les problèmes convexes et les problèmes coniques, en introduisant le concept de dualité forte et l'importance de la dualité des solutions. L'instructeur explique la fonction lagrangienne et son rôle dans la transformation du problème primaire en un problème min-max. La séance de cours se penche sur la formulation du double problème, la dualité faible et les conditions d'une dualité forte. Il traite également de la hiérarchie des problèmes d'optimisation convexe, du concept des cônes doubles et des applications pratiques de la dualité lagrangique dans les programmes de cônes de second ordre et les programmes quadratiques.

Cette vidéo est disponible exclusivement sur Mediaspace pour un public restreint. Veuillez vous connecter à Mediaspace pour y accéder si vous disposez des autorisations nécessaires.

Regarder sur Mediaspace

Enseignant·e

Daniel Kuhn

Source officielle

Proximité ontologique

Informatique théorique

Algorithmes et structures de données: Optimisation combinatoire

Concepts associés (30)

Dualité (optimisation)

En théorie de l'optimisation, la dualité ou principe de dualité désigne le principe selon lequel les problèmes d'optimisation peuvent être vus de deux perspectives, le problème primal ou le problème dual, et la solution du problème dual donne une borne inférieure à la solution du problème (de minimisation) primal. Cependant, en général les valeurs optimales des problèmes primal et dual ne sont pas forcément égales : cette différence est appelée saut de dualité. Pour les problèmes en optimisation convexe, ce saut est nul sous contraintes.

Optimisation convexe

vignette|320x320px|Optimisation convexe dans un espace en deux dimensions dans un espace contraint L'optimisation convexe est une sous-discipline de l'optimisation mathématique, dans laquelle le critère à minimiser est convexe et l'ensemble admissible est convexe. Ces problèmes sont plus simples à analyser et à résoudre que les problèmes d'optimisation non convexes, bien qu'ils puissent être NP-difficile (c'est le cas de l'optimisation copositive). La théorie permettant d'analyser ces problèmes ne requiert pas la différentiabilité des fonctions.

Optimisation linéaire

thumb|upright=0.5|Optimisation linéaire dans un espace à deux dimensions (x1, x2). La fonction-coût fc est représentée par les lignes de niveau bleues à gauche et par le plan bleu à droite. L'ensemble admissible E est le pentagone vert. En optimisation mathématique, un problème d'optimisation linéaire demande de minimiser une fonction linéaire sur un polyèdre convexe. La fonction que l'on minimise ainsi que les contraintes sont décrites par des fonctions linéaires, d'où le nom donné à ces problèmes.

Dualité (mathématiques)

thumb|Dual d'un cube : un octaèdre. En mathématiques, le mot dualité a de nombreuses utilisations. Une dualité est définie à l'intérieur d'une famille d'objets mathématiques, c'est-à-dire qu'à tout objet de on associe un autre objet de . On dit que est le dual de et que est le primal de . Si (par = on peut sous-entendre des relations d'isomorphies complexes), on dit que est autodual. Dans de nombreux cas de dualité, le dual du dual est le primal. Ainsi, par exemple, le concept de complémentaire d'un ensemble pourrait être vu comme le premier des concepts de dualité.

Optimisation non linéaire

En optimisation, vue comme branche des mathématiques, l'optimisation non linéaire (en anglais : nonlinear programming – NLP) s'occupe principalement des problèmes d'optimisation dont les données, i.e., les fonctions et ensembles définissant ces problèmes, sont non linéaires, mais sont aussi différentiables autant de fois que nécessaire pour l'établissement des outils théoriques, comme les conditions d'optimalité, ou pour la bonne marche des algorithmes de résolution qui y sont introduits et analysés.

Afficher plus

Séances de cours associées (64)

Programmation linéaire : correspondance bipartite pondérée

Couvre la programmation linéaire, la correspondance bipartite pondérée et les problèmes de couverture de sommet en optimisation.

Dualité de programmation linéaire

Explore la dualité de programmation linéaire, couvrant la dualité faible, la dualité forte, l'interprétation des multiplicateurs de Lagrange et les contraintes d'optimisation.

La dualité dans la programmation linéaire

Explore le concept de dualité dans la programmation linéaire, en discutant de la relation entre les problèmes primaires et duaux.

Optimisation Primal-dual: Théorie et Calcul

Explore l'optimisation primaire-duelle, la conjugaison des fonctions, la dualité forte, et les méthodes de pénalité quadratique en mathématiques de données.

Techniques de programmation linéaire dans l'apprentissage par renforcement

Couvre l'approche de programmation linéaire de l'apprentissage par renforcement, en se concentrant sur ses applications et ses avantages dans la résolution des processus décisionnels de Markov.

Afficher plus

Concepts associés (30)

Dualité (optimisation)

Optimisation convexe

Optimisation linéaire

Dualité (mathématiques)

Optimisation non linéaire

Afficher plus