Optimization problemIn 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.
Dualité (optimisation)En théorie de l'optimisation, la dualité ou principe de dualité désigne le principe selon lequel les problèmes d'optimisation peuvent être vus de deux perspectives, le problème primal ou le problème dual, et la solution du problème dual donne une borne inférieure à la solution du problème (de minimisation) primal. Cependant, en général les valeurs optimales des problèmes primal et dual ne sont pas forcément égales : cette différence est appelée saut de dualité. Pour les problèmes en optimisation convexe, ce saut est nul sous contraintes.
Contrainte (mathématiques)En mathématiques, une contrainte est une condition que doit satisfaire la solution d'un problème d'optimisation. On distingue deux types de contraintes : les contraintes d'égalité et les contraintes en inégalité. L'ensemble des solutions satisfaisant toutes les contraintes est appelé l'ensemble admissible. On considère un problème d'optimisation classique : avec et et désigne le vecteur . Dans cet exemple, la première ligne montre la fonction à minimiser (appelée fonction objectif ou fonction-coût) mais aussi l'ensemble où la solution doit être recherché, ici C.
Optimisation linéairethumb|upright=0.5|Optimisation linéaire dans un espace à deux dimensions (x1, x2). La fonction-coût fc est représentée par les lignes de niveau bleues à gauche et par le plan bleu à droite. L'ensemble admissible E est le pentagone vert. En optimisation mathématique, un problème d'optimisation linéaire demande de minimiser une fonction linéaire sur un polyèdre convexe. La fonction que l'on minimise ainsi que les contraintes sont décrites par des fonctions linéaires, d'où le nom donné à ces problèmes.
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.
Optimisation convexevignette|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 linéaire en nombres entiersL'optimisation linéaire en nombres entiers (OLNE) (ou programmation linéaire en nombres entiers (PLNE) ou integer programming (IP) ou Integer Linear Programming (ILP)) est un domaine des mathématiques et de l'informatique théorique dans lequel on considère des problèmes d'optimisation d'une forme particulière. Ces problèmes sont décrits par une fonction de coût et des contraintes linéaires, et par des variables entières.
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 non linéaireEn optimisation, vue comme branche des mathématiques, l'optimisation non linéaire (en anglais : nonlinear programming – NLP) s'occupe principalement des problèmes d'optimisation dont les données, i.e., les fonctions et ensembles définissant ces problèmes, sont non linéaires, mais sont aussi différentiables autant de fois que nécessaire pour l'établissement des outils théoriques, comme les conditions d'optimalité, ou pour la bonne marche des algorithmes de résolution qui y sont introduits et analysés.
Feasible regionIn mathematical optimization, a feasible region, feasible set, search space, or solution space is the set of all possible points (sets of values of the choice variables) of an optimization problem that satisfy the problem's constraints, potentially including inequalities, equalities, and integer constraints. This is the initial set of candidate solutions to the problem, before the set of candidates has been narrowed down.
Optimisation combinatoireL’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.
Algorithme du simplexeLalgorithme du simplexe est un algorithme de résolution des problèmes d'optimisation linéaire. Il a été introduit par George Dantzig à partir de 1947. C'est probablement le premier algorithme permettant de minimiser une fonction sur un ensemble défini par des inégalités. De ce fait, il a beaucoup contribué au démarrage de l'optimisation numérique. L'algorithme du simplexe a longtemps été la méthode la plus utilisée pour résoudre les problèmes d'optimisation linéaire.
Constraint logic programmingConstraint logic programming is a form of constraint programming, in which logic programming is extended to include concepts from constraint satisfaction. A constraint logic program is a logic program that contains constraints in the body of clauses. An example of a clause including a constraint is . In this clause, is a constraint; A(X,Y), B(X), and C(Y) are literals as in regular logic programming. This clause states one condition under which the statement A(X,Y) holds: X+Y is greater than zero and both B(X) and C(Y) are true.
Dualité (mathématiques)thumb|Dual d'un cube : un octaèdre. En mathématiques, le mot dualité a de nombreuses utilisations. Une dualité est définie à l'intérieur d'une famille d'objets mathématiques, c'est-à-dire qu'à tout objet de on associe un autre objet de . On dit que est le dual de et que est le primal de . Si (par = on peut sous-entendre des relations d'isomorphies complexes), on dit que est autodual. Dans de nombreux cas de dualité, le dual du dual est le primal. Ainsi, par exemple, le concept de complémentaire d'un ensemble pourrait être vu comme le premier des concepts de dualité.
Relaxation continueEn informatique théorique et en recherche opérationnelle, la relaxation continue est une méthode qui consiste à interpréter de façon continue un problème combinatoire ou discret. Cette méthode est utilisée afin d'obtenir des informations sur le problème discret initial et parfois même pour obtenir sa solution. Les problèmes discrets ou combinatoires sont en effet très difficiles à traiter en raison de l'explosion combinatoire et il est courant de les traiter par une méthode de séparation et évaluation (branch and bound en anglais) : la relaxation continue fait partie des algorithmes d'évaluation nécessaire à la mise en œuvre de cette méthode.
Algorithmethumb|Algorithme de découpe d'un polygone quelconque en triangles (triangulation). Un algorithme est une suite finie et non ambiguë d'instructions et d’opérations permettant de résoudre une classe de problèmes. Le domaine qui étudie les algorithmes est appelé l'algorithmique. On retrouve aujourd'hui des algorithmes dans de nombreuses applications telles que le fonctionnement des ordinateurs, la cryptographie, le routage d'informations, la planification et l'utilisation optimale des ressources, le , le traitement de textes, la bio-informatique L' algorithme peut être mis en forme de façon graphique dans un algorigramme ou organigramme de programmation.
Verdier dualityIn mathematics, Verdier duality is a cohomological duality in algebraic topology that generalizes Poincaré duality for manifolds. Verdier duality was introduced in 1965 by as an analog for locally compact topological spaces of Alexander Grothendieck's theory of Poincaré duality in étale cohomology for schemes in algebraic geometry. It is thus (together with the said étale theory and for example Grothendieck's coherent duality) one instance of Grothendieck's six operations formalism.
Programmation par contraintesLa programmation par contraintes (PPC, ou CP pour constraint programming en anglais) est un paradigme de programmation apparu dans les années 1970 et 1980 permettant de résoudre des problèmes combinatoires de grande taille tels que les problèmes de planification et d'ordonnancement. En programmation par contraintes, on sépare la partie modélisation à l'aide de problèmes de satisfaction de contraintes (ou CSP pour Constraint Satisfaction Problem), de la partie résolution dont la particularité réside dans l'utilisation active des contraintes du problème pour réduire la taille de l'espace des solutions à parcourir (on parle de propagation de contraintes).
Méthodes de points intérieursvignette|Visualisation de la méthode des points intérieur : le chemin reste à l’intérieur du polyèdre. vignette|Visualisation de la méthode du simplexe : le chemin suit les arêtes du polyèdre vignette|Visualisation de la méthode par ellipsoïde : l’ellipse se rétrécit Les méthodes de points intérieurs forment une classe d’algorithmes qui permettent de résoudre des problèmes d’optimisation mathématique.
Constraint Handling RulesConstraint Handling Rules (CHR) is a declarative, rule-based programming language, introduced in 1991 by Thom Frühwirth at the time with European Computer-Industry Research Centre (ECRC) in Munich, Germany. Originally intended for constraint programming, CHR finds applications in grammar induction, type systems, abductive reasoning, multi-agent systems, natural language processing, compilation, scheduling, spatial-temporal reasoning, testing, and verification.
