Coupe maximumEn théorie des graphes et en algorithmique, une coupe maximum est une coupe contenant au moins autant d'arêtes que n'importe quelle autre coupe. Une extension de la définition consiste à considérer des poids associés aux arêtes. On considère alors la coupe ayant le poids total maximum. Les coupes maximums sont des objets utiles notamment en physique théorique et en électronique. Mais elles sont surtout connues pour le problème algorithmique qui consiste à trouver une coupe maximum, appelé couramment MAX-CUT, un problème relativement bien étudié, notamment dans le contexte de l'approximation.
Closure problemIn graph theory and combinatorial optimization, a closure of a directed graph is a set of vertices C, such that no edges leave C. The closure problem is the task of finding the maximum-weight or minimum-weight closure in a vertex-weighted directed graph. It may be solved in polynomial time using a reduction to the maximum flow problem. It may be used to model various application problems of choosing an optimal subset of tasks to perform, with dependencies between pairs of tasks, one example being in open pit mining.
Scenario optimizationThe scenario approach or scenario optimization approach is a technique for obtaining solutions to robust optimization and chance-constrained optimization problems based on a sample of the constraints. It also relates to inductive reasoning in modeling and decision-making. The technique has existed for decades as a heuristic approach and has more recently been given a systematic theoretical foundation. In optimization, robustness features translate into constraints that are parameterized by the uncertain elements of the problem.
Algorithme du lagrangien augmentéLes algorithmes du lagrangien augmenté sont une certaine classe d'algorithmes pour résoudre des problèmes d'optimisation sous contraintes. Elles présentent des similitudes avec les méthodes de pénalité dans le sens où elles remplacent un problème d'optimisation sous contraintes par une série de problèmes sans contrainte et ajoutent un terme de pénalité à l'objectif ; la différence est qu'une méthode du lagrangien augmenté ajoute encore un autre terme, conçu pour agir comme un multiplicateur de Lagrange.
Slater's conditionIn mathematics, Slater's condition (or Slater condition) is a sufficient condition for strong duality to hold for a convex optimization problem, named after Morton L. Slater. Informally, Slater's condition states that the feasible region must have an interior point (see technical details below). Slater's condition is a specific example of a constraint qualification. In particular, if Slater's condition holds for the primal problem, then the duality gap is 0, and if the dual value is finite then it is attained.
Barrier functionIn constrained optimization, a field of mathematics, a barrier function is a continuous function whose value on a point increases to infinity as the point approaches the boundary of the feasible region of an optimization problem. Such functions are used to replace inequality constraints by a penalizing term in the objective function that is easier to handle. The two most common types of barrier functions are inverse barrier functions and logarithmic barrier functions.
Constrained optimizationIn mathematical optimization, constrained optimization (in some contexts called constraint optimization) is the process of optimizing an objective function with respect to some variables in the presence of constraints on those variables. The objective function is either a cost function or energy function, which is to be minimized, or a reward function or utility function, which is to be maximized.
High school diplomaA high school diploma (or high school degree) is a diploma awarded upon graduation of high school. A high school diploma is awarded after completion of courses of studies lasting four years, typically from grade 9 to grade 12. It is the school leaving qualification in the United States and Canada. The diploma is awarded by the school in accordance with the requirements of the local state or provincial government. Requirements for earning the diploma vary by jurisdiction, and there may be different requirements for different streams or levels of high school graduation.
Stochastic programmingIn the field of mathematical optimization, stochastic programming is a framework for modeling optimization problems that involve uncertainty. A stochastic program is an optimization problem in which some or all problem parameters are uncertain, but follow known probability distributions. This framework contrasts with deterministic optimization, in which all problem parameters are assumed to be known exactly. The goal of stochastic programming is to find a decision which both optimizes some criteria chosen by the decision maker, and appropriately accounts for the uncertainty of the problem parameters.
Inégalité matricielle linéaireEn optimisation convexe, une inégalité matricielle linéaire (Linear matricial inequality ou LMI) est une expression de la forme où est un vecteur réel, sont dans l'ensemble des matrices symétriques, signifie que est une matrice semi-définie positive appartenant au sous-ensemble de l'ensemble des matrices symétriques . Cette inégalité matricielle linéaire caractérise un ensemble convexe selon y. Il existe des méthodes numériques de résolution des LMI performantes pour déterminer notamment leur faisabilité (ie, s'il existe au moins un vecteur tel que ), ou pour effectuer une optimisation convexe sous contrainte LMI.
