Séance de cours

Problème Max-Cut : Relaxation SDP et arrondi randomisé

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 le problème Max-Cut, un problème d'optimisation combinatoire qui est complet NP. L'instructeur explique comment détendre le problème à l'aide d'un QP entier et d'un SDP, puis utilise l'arrondi randomisé pour trouver des solutions approximatives. La séance de cours se penche également sur l'optimisation polynôme, en discutant des polynômes non négatifs, de la somme des polynômes carrés et de la difficulté de vérifier la non-négativité. Différents théorèmes et exemples sont présentés pour illustrer les concepts.

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

Concepts associés (32)

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.

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 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 SDP

En mathématiques et en informatique théorique, l'optimisation SDP ou semi-définie positive, est un type d'optimisation convexe, qui étend l'optimisation linéaire. Dans un problème d'optimisation SDP, l'inconnue est une matrice symétrique que l'on impose d'être semi-définie positive. Comme en optimisation linéaire, le critère à minimiser est linéaire et l'inconnue doit également satisfaire une contrainte affine. L'optimisation SDP se généralise par l'optimisation conique, qui s'intéresse aux problèmes de minimisation d'une fonction linéaire sur l'intersection d'un cône et d'un sous-espace affine.

Optimization problem

In mathematics, computer science and economics, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories, depending on whether the variables are continuous or discrete: An optimization problem with discrete variables is known as a discrete optimization, in which an object such as an integer, permutation or graph must be found from a countable set.

Afficher plus

Séances de cours associées (64)

Programmation semi-définie

Couvre la programmation et l'optimisation semi-définies sur des cônes semi-définis positifs.

Introduction à l’optimisation

Couvre les bases de l'optimisation, y compris les perspectives historiques, les formulations mathématiques et les applications pratiques dans les problèmes de prise de décision.

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.

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.

Algorithmes d'approximation

Couvre les algorithmes d'approximation pour les problèmes d'optimisation, la relaxation LP et les techniques d'arrondi aléatoire.

Afficher plus

Concepts associés (32)

Optimisation combinatoire

Optimisation (mathématiques)