Jean-Baptiste Delorme MOD 2005 Programmation quadratique et semidéfinie 1. Introduction : du linéaire au non-linéaire Classiquement, parmi les premiers problèmes rencontrés en optimisation se trouvent les problèmes linéaires. Il s’agit de maximiser (ou de minimiser) une fonction objectif linéaire de ses paramètres tout en se conformant à des conditions, elles aussi, linéaires. Ceci peut être formalisé de la manière suivante : nMaximiser (ou minimiser) f (x ,..., x ) = a x 1 n ∑ i ii =1nSous les contraintes : g (x ,..., x ) = b x ≤ 0 ∀j ∈1..m j 1 n ∑ i, j ii =1 La résolution de ce style de problème peut être comprise aisément de manière graphique : 706050Contraintes40Optimum30Objectif201000 5 10 15 20 25 Les contraintes forment un polygone P de solutions acceptables. C’est dans cet ensemble qu’il faut chercher les solutions au problème. Ainsi, l’optimisation correspond à trouver le point de P qui maximise la fonction objectif. Nous pouvons observer que la solution optimale se trouve sur un des sommets de P, ici dans le carré noir. Mais cette configuration est évidemment un cas particulier des problèmes rencontrés en optimisation. Les fonctions étudiées peuvent, bien sur, sortir du cadre linéaire. 605040Contraintes30Optimum201000 5 10 15 20 25 Par exemple, dans le cas représenté ci-dessus, c’est la contrainte qui a été changée pour devenir non linéaire. De même, il est possible de rencontrer des ...
Voir