algo non linéaire avec borne

Salut tous,

j'ai un systeme non lineaire à résoudre et je dos trouver la solution entre deux bornes (0 et A) qui encadre ma solution.

=> pourriez vous me donenr des pistes d'algorithmes pour faire cela.

1°) Moi j'ai tout d'abord pensé à Newton et j'accepte le pas de calcul que si le prochain itéré se trouve bien dans les bornes sinon je divise le pas de calcul par deux.

2°) sinon pour éviter les divergence qu'on peut avoir avec Newton avec des fonctions qui présentes des dérivées nulles j'ai pensé à quasi-newton...

Avez vous d'autres pistes s'il vous plait ?

merci d'avance pour les psites que vous pourriez me donner :ccool:

ps: j'ai entendu parlé de gradient conjugué non linéaire mais je n'ai pas trouvé beaucoup de doc là dessus -> pourriez vous m'expliquer le principe et me dire si la gestion des bornes est possible ?

Salut!

Citation:

---

j'ai un systeme non lineaire à résoudre et je dos trouver la solution entre deux bornes (0 et A) qui encadre ma solution.

---

Si tu as un système non linéaire de n équations à n inconnues, chaque solution est un vecteur de n composantes et non une valeur unique. Parler de deux bornes encadrant la solution n'a donc aucun sens.
Jean-Marc Blanc

Bonjour. Les méthodes de Brent et de Dekker pourraient t'intéresser.

Cdlt,

oui, je connais la methode de Brent-dekker ( elle est super :) )
mais en fait je veux bien résoudre un systeme et non une seule equation :calim2:

en fait je veux que les composantes de mon vecteur résultat (qui a bien n composantes) soit comprises entre deux vecteurs A et B.

=> connaissez vous des méthodes (donc vectorielles) qui puissent permettre de faire ceci ?

merci

Salut!

Citation:

---

je veux que les composantes de mon vecteur résultat (qui a bien n composantes) soit comprises entre deux vecteurs A et B.

---

Qu'est-ce que ça signifie qu'une composante est comprise entre deux vecteurs?
Jean-Marc Blanc

Désolé, je me suis mal exprimé. Voici ce que je veux :

le vecteur réponse :
X=[X1 X2 X3 X4 X5]
doit être compris entre :
borneInf=[A1 A2 A3 A4 A5];
et :
borneSup=[B1 B2 B3 B4 B5];

ou, autrement dit :
A1 < X1 < B1
A2 < X2 < B2
A3 < X3 < B3
A4 < X4 < B4
A5 < X5 < B5

Je ne vois pas trop comment imposer ceci dans la résolution... peut être transformant la résolution du système en un problème d'optimisation et en appliquant des algo d'optimisation non linéaire contraints ?

Si tu veux tu peux regarder sur la page du module scipy.optimize, à la section
'constrained'.

http://docs.scipy.org/doc/scipy/reference/optimize.html

Il y a la liste des algos implémentés:

- l bgfs bounded
- truncated newton in C
- Constrained Optimization BY Linear Approximation
- Least SQuares Programming

et les références pour chacun d'entre eux

merci beaucoup Alexis ! ça à l'air super intéressant ce site !!!
=> de quoi s'agit il exactement ? une bibliothèque fortran ?

Au fait, je voulais vous poser une question car je ne suis pas certain de moi :
=> un problème de résolution de système non linéaire peut toujours ce ramener à un problème de minimisation ?

Par exemple si je dois résoudre ce système:
f(x,t)=0
g(x,t)=0

c'est equivalent à minimiser une fonction dans ce genre ?
F(x,t)=0.5*f(x,t)²+0.5*g(x,t)²

J'ai une dernière question :
d'après ce que j'ai compris les algo de minimisation avec bornes (comme dans mon cas) utilise l'implémentation des conditions de Kuhn et Tucker.

Pourriez vous m'expliquer le principe de fonctionnement car je n'ai pas trop compris ce truc.... on a apparement des multiplicateurs de Lagrange mais qui deviennent nuls dans certaines conditions et parfois ils ne sont pas nul pour pouvoir chercher dans la bonne direction...

bref, je ne vois pas comment faire pour programmer soit meme ce genre de chose dans le cas où l'on a deux contraintes d'inegalités et j'aimerai bien avoir une explication dessus s'il vous plait...

Ils s'agit d'un packetage python pour le calcul scientifique qui, entre autre, enveloppe des bibliothèques fortran

Citation:

---

Envoyé par Alexis.M

Ils s'agit d'un packetage python pour le calcul scientifique qui, entre autre, enveloppe des bibliothèques fortran

---

ok, merci :)

ps: tu connais quelque chose d'equivalenet en C ou C++ ?

Bonsoir,

si je ne me trompe pas, il y a une manière triviale de transformer un problème non-linéaire en problème de minimisation. Etant donné une norme ||.||, résoudre F(x)=0 équivaut à chercher le minimum de ||F(x)|| (je n'ai pas précisé les domaines de départ et d'arrivée de F mais il n'y a pas de piège de ce point de vue). Il y a un sens trivial à l'équivalence. L'autre s'obtient par définie-positivité de la norme.

Pour tenir compte des inégalités que tu mentionnes, tu peux utiliser des multiplicateurs de Lagrange. En cherchant un cours sur la toile, tu devrais trouver ton bonheur. Je ne connais pas suffisamment les méthodes par régions de confiance pour te les expliquer clairement et proprement mais tu devrais également pouvoir trouver sans problème un bon cours là-dessus si tu lis l'anglais. En tous les cas, elles ont bonne réputation.

merci Aleph pour ta participation egalement :)

Citation:

---

Envoyé par Aleph69

si je ne me trompe pas, il y a une manière triviale de transformer un problème non-linéaire en problème de minimisation. Etant donné une norme ||.||, résoudre F(x)=0 équivaut à chercher le minimum de ||F(x)|| (je n'ai pas précisé les domaines de départ et d'arrivée de F mais il n'y a pas de piège de ce point de vue). Il y a un sens trivial à l'équivalence. L'autre s'obtient par définie-positivité de la norme.

---

ah oui ! en effet : c'est pas bête ça :ccool:
sinon, juste pour info : ce que j'avais marqué ci dessus est egalement juste non ?
(minimiser f²+g²)

Citation:

---

Envoyé par Aleph69

Pour tenir compte des inégalités que tu mentionnes, tu peux utiliser des multiplicateurs de Lagrange. En cherchant un cours sur la toile, tu devrais trouver ton bonheur. Je ne connais pas suffisamment les méthodes par régions de confiance pour te les expliquer clairement et proprement mais tu devrais également pouvoir trouver sans problème un bon cours là-dessus si tu lis l'anglais. En tous les cas, elles ont bonne réputation.

---

d'accord, je regarderai des sites en anglais (en fait dans le cas d'inégalités les multiplicateurs de Lagrange sont remplacé par une forme général qui est les conditions de Kuhn et Tucker). J'ai déjà regardé sur des pages françaises et j'ai un peu de mal à comprendre car je n'ai pas trouvé un exemple détaillé entièrement pas à pas...donc si quelqu'un peut m'expliquer....

Si tu peux lire l'anglais, il y a l'excellent livre de Nocedal et Wright "Numerical Optimization" qui fait le tour de toutes les méthodes classiques d'optimization.

Une des possibilités pour résoudre ce problème c'est de remplacer chaque contrainte par une fonction de pénalité.

C'est déjà ce que tu fais quand tu minimise 0.5*(f(x)^2 + g(x)^2)
mais tu peux également rajouter le même genre de pénalité pour les contraintes de type:

ci(x) >0 en utilisant (min(ci(x),0))^2

donc tu aurais 0.5*(f(x)^2 + g(x)^2) + mu * 0.5 * \sum_i (min(ci(x),0))^2

tu peux alors appliquer n'importe qu'elle méthode d'optimisation non linéaire (mais attention aux minima locaux qui ne vérifient pas les contraintes)

Dans l'approche précédente il s'agissait de pénalités quadratiques mais il est parfois intéressant d'utiliser d'autre pénalités basée sur la norme L1
|f(x)| + |g(x)| + mu * 0.5 * \sum_i max(-ci(x),0)

mais comme ces fonctions ne sont pas dérivables près de leur solutions on utilise plutôt des approximations lisses:

|x| -> log(cosh(b*x))/b
max(0,-x) -> log( 1 + exp(-b*x))/b

merci pour toute ces infos !
:ccool::ccool::ccool: