Séance de cours

Algorithme Metropolis : Optimisation et approche probabiliste

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.

Description

Cette séance de cours introduit l'algorithme Metropolis, visant à fournir une solution approximative et probabiliste aux problèmes d'optimisation discrète en cherchant le minimum d'une fonction. L'algorithme implique l'évolution d'une chaîne Markov avec un espace d'état et une distribution limitative. Différentes idées sont explorées, comme définir une distribution sur l'espace d'état et rendre la chaîne paresseuse. L'instructeur explique le processus de création d'une chaîne à partir d'un état de base, en la laissant évoluer vers une distribution approximative d'une cible. Diverses stratégies sont discutées pour rendre la chaîne paresseuse et explorer efficacement l'espace d'état à différentes températures, conduisant à la fois à des minima locaux et mondiaux.

Source officielle

Concepts associés (29)

Optimisation (mathématiques)

L'optimisation est une branche des mathématiques cherchant à modéliser, à analyser et à résoudre analytiquement ou numériquement les problèmes qui consistent à minimiser ou maximiser une fonction sur un ensemble. L’optimisation joue un rôle important en recherche opérationnelle (domaine à la frontière entre l'informatique, les mathématiques et l'économie), dans les mathématiques appliquées (fondamentales pour l'industrie et l'ingénierie), en analyse et en analyse numérique, en statistique pour l’estimation du maximum de vraisemblance d’une distribution, pour la recherche de stratégies dans le cadre de la théorie des jeux, ou encore en théorie du contrôle et de la commande.

Optimisation combinatoire

L’optimisation combinatoire, (sous-ensemble à nombre de solutions finies de l'optimisation discrète), est une branche de l'optimisation en mathématiques appliquées et en informatique, également liée à la recherche opérationnelle, l'algorithmique et la théorie de la complexité. Dans sa forme la plus générale, un problème d'optimisation combinatoire (sous-ensemble à nombre de solutions finies de l'optimisation discrète) consiste à trouver dans un ensemble discret un parmi les meilleurs sous-ensembles (ou solutions) réalisables, la notion de meilleure solution étant définie par une fonction objectif.

Global optimization

Global optimization is a branch of applied mathematics and numerical analysis that attempts to find the global minima or maxima of a function or a set of functions on a given set. It is usually described as a minimization problem because the maximization of the real-valued function is equivalent to the minimization of the function . Given a possibly nonlinear and non-convex continuous function with the global minima and the set of all global minimizers in , the standard minimization problem can be given as that is, finding and a global minimizer in ; where is a (not necessarily convex) compact set defined by inequalities .

Discrete optimization

Discrete optimization is a branch of optimization in applied mathematics and computer science. As opposed to continuous optimization, some or all of the variables used in a discrete mathematical program are restricted to be discrete variables—that is, to assume only a discrete set of values, such as the integers. Three notable branches of discrete optimization are: combinatorial optimization, which refers to problems on graphs, matroids and other discrete structures integer programming constraint programming These branches are all closely intertwined however since many combinatorial optimization problems can be modeled as integer programs (e.

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.

Afficher plus

Séances de cours associées (64)

Optimisation et simulation

Couvre les techniques d'optimisation et de simulation pour dessiner à partir de distributions multivariées et traiter des corrélations.

Méthodes d'optimisation : discussion théorique

Explore les méthodes d'optimisation, y compris les problèmes sans contraintes, la programmation linéaire et les approches heuristiques.

Stratégies d'optimisation de l'énergie

Couvre les options de brainstorming pour les changements de fonctionnement intelligents, la récupération de chaleur, et les performances du panneau PV.

Optimisation avec contraintes : conditions KKT

Couvre les conditions KKT pour l'optimisation avec des contraintes, essentielles pour résoudre efficacement les problèmes d'optimisation.

Optimisation des systèmes énergétiques

Explore la modélisation, l'optimisation et l'analyse des coûts des systèmes énergétiques pour des opérations efficaces.

Afficher plus

Concepts associés (29)

Optimisation (mathématiques)

Optimisation combinatoire

Global optimization

Discrete optimization

Optimisation convexe

Afficher plus