Optimisation linéaire avec contraintes non linéaire

[thomas5701]

Bonjour à tous,

Dans le cadre d'un projet, je bloque devant un problème d'optimisation. Le but est d'optimiser la somme u+v (en cherchant le minimum) sachant que:

u²+v²<R²
(u-a)²+(v-b)²<R²

Par la suite, j'aurais sans doute d'autres contraintes non linéaires qui compliqueront le problème. Hélas, je ne vois pas comment partir, par quelle méthode.
J'utilise Scilab pour programmer, mais je n'ai pas réussi à trouver une fonction répondant à mes attentes.

Quelqu'un aurait des pistes de réflexion?

Merci !

Cordialement,
thomas5701
-----

[Bruno]

Salut,

Regarde ici: http://en.wikipedia.org/wiki/Quadrat...dratic_program

[Dlzlogic]

Bonjour,
En regardant l'inéquation, si on considère u et v comme des coordonnées, cela définit la surface comprise à l'intérieur d'un cercle de rayon R. Pour la seconde inéquation, c'est le même cercle avec une translation (a,b).
La somme u+v est ce qu'on appelle la "distance de Manhattan".
A propos de cette distance, est est souvent utilisée en SIG, une approximation avec la distance Euclidienne est intéressante.

[thomas5701]

Merci pour ces réponses ! J'ai pu faire quelques recherches sur le sujet.

On m'a proposé, pour simplifier la programmation (le temps de calcul) de linéariser les cercles (ensemble de droite) et se ramener à un problème linéaire. Je le rappelle, la suite du problème contiendra plusieurs inéquations non linéaire, j'ai tout intérêt à me ramener à un système du type linéaire !

Cordialement,
thomas5701

[A voir en vidéo sur Futura]

[Dlzlogic]

En fait, pour moi, la question n'est pas claire.

[Bruno]

Tu peux linéariser mais va falloir s'assurer que ta méthode converge vers la bonne valeur... Quelles sont les contraintes suivantes ? Si elles sont quadratiques ou convexes, tu devrais les laisser ainsi et exploiter les algos listés dans le lien de mon 1er post. Ces derniers seront très probablement plus rapides que ton code...