Conditions de Karush-Kuhn-Tucker

Résumé

En mathématiques, les conditions de Karush-Kuhn-Tucker ou anciennement conditions de Kuhn-Tucker sont une généralisation des multiplicateurs de Lagrange qui permettent de résoudre des problèmes d'optimisation sous contraintes non linéaires d'inégalités. Soit f:\R^n\to\R, une fonction appelée fonction objectif, et des fonctions g_j:\R^n\to\R, 1\le j\le m, appelées contraintes. On suppose que f et les g_j sont de classe C. Le problème à résoudre est le suivant : Théorème Si f admet un minimum en x^sous les contraintes g_j(x^) \le 0 pour tout j, alors il existe (\lambda_j)_{1\le j\le m} \in \R^m vérifiant les conditions suivantes, dites conditions de Kuhn-Tucker. On dit alors que \lambda_j est le multiplicateur de Lagrange associé à la j-ème contrainte. Conditions du premier ordre Le point x^*

Source officielle

https://fr.wikipedia.org/wiki/Conditions_de_Karush-Kuhn-Tucker

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (39)

Publications associées

Chargement

Personnes associées (4)

Personnes associées

Chargement

Unités associées (3)

Unités associées

Chargement

Concepts associés (10)

Concepts associés

Chargement

Cours associés (35)

Cours associés

Chargement

Séances de cours associées (134)

Séances de cours associées

Chargement

We consider high-dimensional random optimization problems where the dynamical variables are subjected to nonconvex excluded volume constraints. We focus on the case in which the cost function is a simple quadratic cost and the excluded volume constraints are modeled by a perceptron constraint satisfaction problem. We show that depending on the density of constraints, one can have different situations. If the number of constraints is small, one typically has a phase where the ground state of the cost function is unique and sits on the boundary of the island of configurations allowed by the constraints. In this case, there is a hypostatic number of marginally satisfied constraints. If the number of constraints is increased one enters a glassy phase where the cost function has many local minima sitting again on the boundary of the regions of allowed configurations. At the phase transition point, the total number of marginally satisfied constraints becomes equal to the number of degrees of freedom in the problem and therefore we say that these minima are isostatic. We conjecture that by increasing further the constraints the system stays isostatic up to the point where the volume of available phase space shrinks to zero. We derive our results using the replica method and we also analyze a dynamical algorithm, the Karush-Kuhn-Tucker algorithm, through dynamical mean-field theory and we show how to recover the results of the replica approach in the replica symmetric phase.

AMER PHYSICAL SOC2022

Chargement

Central limit theorems for multilevel Monte Carlo methods

Hakon Andreas Hoel, Sebastian Krumscheid

In this work, we show that uniform integrability is not a necessary condition for central limit theorems (CLT) to hold for normalized multilevel Monte Carlo (MLMC) estimators and we provide near optimal weaker conditions under which the CLT is achieved. In particular, if the variance decay rate dominates the computational cost rate (i.e., beta > gamma), we prove that the CLT applies to the standard (variance minimizing) MLMC estimator. For other settings where the CLT may not apply to the standard MLMC estimator, we propose an alternative estimator, called the mass-shifted MLMC estimator, to which the CLT always applies. This comes at a small efficiency loss: the computational cost of achieving mean square approximation error O(epsilon(2)) is at worst a factor O(log(1/epsilon)) higher with the mass-shifted estimator than with the standard one. (C) 2019 Elsevier Inc. All rights reserved.

2019

Chargement

Central limit theorems for multilevel Monte Carlo methods

Hakon Andreas Hoel, Sebastian Krumscheid

In this work, we show that uniform integrability is not a necessary condition for central limit theorems (CLT) to hold for normalized multilevel Monte Carlo MLMC estimators, and we provide near optimal weaker conditions under which the CLT is achieved. In particular, if the variance decay rate dominates the computational cost rate (i.e.,

\beta> \gamma

), we prove that the CLT always holds.

2018

Chargement

Central limit theorems for multilevel Monte Carlo methods

Hakon Andreas Hoel, Sebastian Krumscheid

\beta> \gamma

), we prove that the CLT always holds.

2018