Projet d'optimisation

par **MacManus** » 14 Nov 2010, 17:13

Bonjour

Je suis amené à réaliser un projet en "Optimisation". En fait, ce projet n'existe pas pour le moment car c'est à moi de le définir... et ce n'est pas si simple. Mon cours aborde des notions d'analyse convexe et traite des techniques d'optimisation (méthodes de descente du gradient). J'ai donc quelques algorithmes sous la main (gradient à pas fixe, à pas optimal, conjugué ...). Mon projet devra comporter au moins une implémentation de l'un de ces algorithmes.

Mon probème, c'est que je ne trouve pas de cadre, de contexte à partir duquel je peux développer mon projet. Je me doute bien qu'il y a une variété d'applications à ce sujet, mais je n'en trouve pas.
Quelqu'un pourrait-il me fournir des références de livres, d'articles (même en anglais), pour que je puisse avoir une idée d'un type de projet que l'on peut développer à partir de mes connaissances ?

En gros j'ai les outils, mais je n'ai pas de champs d'applications.
Merci à vous.

par **fatal_error** » 14 Nov 2010, 18:37

salut,

j'ai une idée un peu crapuleuse mais qui a le mérite d'etre intéressante (enfin, je pense).
Supposons qu'on ait un drone qu'on pilote.
On veut le diriger d'un point A vers un point B, le plus vite possible.
Seulement, sur le parcours, il y a du vent.
Le problème, c'est que lorsqu'on veut faire "tourner" le drone pour qu'il prenne une autre direction, celui-ci met un certain temps avant de pouvoir s'adapter.
Ce qui nous amène à la recherche d'une heuristique, compromis entre optimiser la direction théorique, et essayer de percevoir les problèmes physiques (le drone réagit pas instantanément).

La première partie consisterait à rechercher la trajectoire optimale en supposant que le drone réagit instantanément.
La seconde à fixer des poids en fonction des actions prises par le drone pour nuancer le fait que celui-ci met plus de temps à réagir.
La dernière d'optimiser les directions prises en fonction de la trajectoire théorique à suivre.

Je développe ce dernier point :
donc on a un trajectoire discrétisée théorique : p1,p2,p3,p4,p5, ...etc qui sont des points pris aux instants t, et qui sont censés etre les points "parfaits".
De l'autre coté, ya ton drone, en q1. Le but, ca serait que par exemple, q5=p5, (en n'oubliant pas l'orientation et la vitesse du drone mais bon, faisons simple pour commencer).
Nous avons donc plusieurs composantes qui entrent en jeu :
le temps que met le drone pour etre en p5
l'orientation du drone une fois en p5
la position du drone par rapport à p5 (il est ptet pas positionné parfaitement).
Tu l'auras compris, l'idéal serait de trouver une fonction qui minimise le temps, l'écart de position, et l'écart d'orientation.
Donc avant d'optimiser, faut fixer trouver un modèle satisfaisant. Par exemple
lorsque tu orientes ton drone, tu fais un écart de position. Lorsque tu diminues le temps (ie tu accélères), tu t'orientes mal, et tu t'écartes de la position.
Au pif on peut supposer une fonction f(acceleration, orientation) = -acceleration+(orientationActuelle-orientationVoulue)^2
Le but étant de trouver cette fonction.
Voilà la tappliques ton gradient, tu deduis de combien faut accélérer, et avec quelle orientation.

Au début t'as des trucs abérrant, après, le principal du projet est de trouver la bonne heuristique (fonction f).

Mais pe que ton projet se limite juste à employer tous les algo et voir lequel est le mieux...

par **MacManus** » 14 Nov 2010, 22:48

Merci beaucoup pour ta réponse fatal !
C'est tout à fait le genre de truc auquel je pense et qui m'intéresse.
En tout cas tu m'a éclairé dans ma recherche.

Dans le même ordre d'idée, j'ai trouvé ceci. Si tu as le temps d'y jetter un oeil, je voulais savoir ce que tu en penses, d'un point de vue théorique et pratique. J'ai l'impression que ce sujet fait appel à des notions de contrôle optimal. J'ai peur de m'embraquer sur qqchose de délicat...je ne suis pas certain de pouvoir tout comprendre. Ce qui est apréciable, c'est que le problème est modélisé par des équations que je ne prendrai pas la peine de contester. Mais j'ai peur de ne pas tout bien maîtriser. Penses-tu que ce soit trop fastidieux ou bien réalisable ? merci encore !!

par **fatal_error** » 14 Nov 2010, 23:35

ué le controle optimale c'est un peu délicat, mais ca reste abordable je pense.
Voici un poly qui a l'air pas mal

par **houda 20** » 16 Nov 2010, 19:31

Bonsoir
pour l'optimisation, j'avais un livre très intéressant à propos, mais malheureusement je ne me rappelle pas de l'auteur, j'essayerai de le rechercher...
sinon voilà un livre intéressant aussi
optimisation et contrôle optimal des système linéaires
Maitine Bergounioux

pour le contrôle, j'en fais encore mes premiers pas, ça parait amusant et très intéressants, voilà un livre extraordinaire, il est simple et plein d'exemples

Les mathématiques du mieux faire
volume 2
la commande optimale pour les débutants
Jean-Baptiste HIRIART-URRUTY

par **houda 20** » 16 Nov 2010, 19:38

en fait l'auteur du livre dont je t'ai parlé est canadienne....
il y a aussi ce livre en anglais.... celui là je te conseille vraiment de le chercher
Numerical optimization
Jorge Nocedal
Stephen J.Wright

tout est détaillé d'une façon exemplaire
Bonne chance.

par **Sylviel** » 16 Nov 2010, 19:48

Je t'envoie par MP un lien vers un projet d'optimisation...

par **houda 20** » 16 Nov 2010, 20:04

je viens de jeter un coup d'oeil sur le projet que vous avez posé
alors voilà
pour le contrôle optimale je n'en vois pas de grande difficultés là, car c'est vraiment classique
ça revient après à un problème d'optimisation normale sauf qu'on minimisera sur un ensemble de fonctions
un pb de contrôle optimale consiste à chercher
1-la fonction d'état, c'est la fonction décrivant l'état du système, en gle elle est donnée par des equations diffs. dépendant du contrôle, on a existence et unicité de la solution par le th de Cauchy-Lipschitz
2- on veut agir sur le système en agissant sur sa fonction d'état, et par là vient après la fonctionnelle à minimiser ou à maximiser, tu auras donc un pb d'optimisation habituel à résoudre "on a pas encore fait les méthodes de résolutions mais c'est ça le principe des pbs de contrôle optimal"....
en trouvant ton contr$ole ou commande, tu remplaces et tu auras ta solution

le projet ne parait pas si délicat, cherche le livre du contrôle optimal que je t'ai indiqué, tu comprendras très vite et tu trouveras tous ce que tu cherches ...

par **houda 20** » 16 Nov 2010, 20:17

le problème que tu as est un pb de Mayer
il y a trois formulations des pbs du contrôle optimal
lagrange, Bolza, Mayer

par **windows7** » 16 Nov 2010, 20:21

tu veux vraiment utiliser le gradient a pas constant/ optimal ?? c'est vraiment pas tres performant comme algo

par **Sylviel** » 16 Nov 2010, 20:40

Je pense que c'est bien de commencer par coder le gradient à pas constant, puis à pas optimal (une recherche 1D c'est bien de la coder au moins une fois). Mais c'est dommage d'en rester là : gradient conjugué ou quasi Newton me semble être de rigueur pour faire un bon projet (histoire d'avoir une "vraie méthode", et pas que celles à but pédagogique)

par **MacManus** » 16 Nov 2010, 21:02

Bonsoir à tous!

Eh bien je suis vraiment content de voir toutes ces réponses de votre part.
Je dois dire que j'ai hâte de me positionner par rapport à tout ça : en effet, c'est tout frais pour moi car j'ai commencé à voir certains algo depuis qq jours seulement et je dois mettre tout ça au clair.
En tout cas je vous remercie pour toutes ces propositions. Merci notamment Houda pour tes références et Sylviel pour ton MP. Bon je vais y aller progressivement et je vous tiens au courant de mon évolution, qd moi même je serai un peu plus déterminé.

:happy3:

Projet d'optimisation

projet d'optimisation

Qui est en ligne