Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Double transformation : Formulation détendue

Description

Cette séance de cours couvre le concept de double transformation, axée sur la formulation détendue et la résolution du double problème à l'aide de méthodes d'oracle et de subgradient de séparation. L'instructeur explique le processus étape par étape, fournissant des informations sur les techniques d'optimisation et des preuves de maximisation uniques.

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

Source officielle

Concepts associés (11)

Méthode de l'ellipsoïde

En optimisation mathématique, la méthode de l'ellipsoïde est une méthode itérative utilisée pour minimiser des fonctions convexes. En informatique théorique, cette méthode est connue comme étant le premier algorithme de complexité polynomiale découvert pour résoudre les problèmes d'optimisation linéaire. L'algorithme construit une suite d'ellipsoïdes de plus en plus petits, qui enserrent à chaque étape le minimum de la fonction objectif.

Sous-différentiel

En mathématiques, et plus précisément en analyse convexe, le sous-différentiel est un concept permettant de décrire la variation locale d'une fonction convexe (à valeurs réelles donc) non nécessairement différentiable dans un sens classique, celui auquel on attache aujourd'hui le nom de Fréchet. Au lieu d'être la pente de l'application linéaire tangente (c'est-à-dire, la dérivée) au point considéré, qui n'existe pas nécessairement, le sous-différentiel d'une fonction convexe est l'ensemble des pentes de toutes les minorantes affines de la fonction, qui sont exactes en ce point, c'est-à-dire qui ont en ce point la même valeur que la fonction convexe qu'elles minorent.

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.

Fonction quasi-convexe

En mathématiques, une fonction quasi-convexe est une fonction à valeurs réelles, définie sur un ensemble convexe d'un espace vectoriel réel, telle que l' de tout ensemble de la forme est convexe ou encore telle que, sur tout segment, la plus grande valeur de la fonction est atteinte à l'une des extrémités. L'opposée d'une fonction quasi-convexe est dite quasi-concave. Toute fonction convexe est quasi-convexe mais la réciproque est fausse : par exemple, toute fonction monotone sur un intervalle réel est quasi-linéaire, c'est-à-dire à la fois quasi-convexe et quasi-concave.

Méthode des plans sécants

vignette|Application de la méthode des plans sécants au problème du voyageur de commerce. En mathématiques, et spécialement en optimisation linéaire en nombres entiers, la méthode des plans sécants, ou cutting plane method, est une méthode utilisée pour trouver une solution entière d'un problème d'optimisation linéaire. Elle fut introduite par Ralph E. Gomory puis étudiée par Gomory et Václav Chvátal. Le principe de la méthode est d'ajouter des contraintes au programme linéaire pour le raffiner, et le rapprocher des solutions intégrales.

Afficher plus

Séances de cours associées (50)

Méthodes d'optimisation : Convexité et descente progressive

Explore les méthodes d'optimisation, y compris la convexité, la descente en gradient et la minimisation non convexe, avec des exemples comme l'estimation de la probabilité maximale et la régression des crêtes.

Optimisation : descente de gradient et sous-gradients

Explore des méthodes d'optimisation telles que la descente de gradient et les sous-gradients pour la formation de modèles d'apprentissage automatique, y compris des techniques avancées telles que l'optimisation d'Adam.

Descente proximale et sous-gradiente : techniques d’optimisation

Discute des méthodes de descente proximale et sous-gradiente pour l'optimisation dans l'apprentissage automatique.

Descente progressive stochastique: Techniques d'optimisation

Explore la descente progressive stochastique avec la moyenne, la comparant avec la descente progressive, et discute des défis dans l'optimisation non convexe et les techniques de récupération clairsemées.

Gradient Descent Méthodes

Couvre les méthodes de descente de gradient pour les problèmes convexes et non convexes, y compris la minimisation convexe lisse sans contrainte, lestimation de la vraisemblance maximale, et des exemples comme la régression de crête et la classification dimage.

Afficher plus

Concepts associés (11)

Méthode de l'ellipsoïde

Sous-différentiel

Optimisation convexe

Fonction quasi-convexe

Méthode des plans sécants

Afficher plus