Optimisation Globale

sous estimation quadratique convexe et branch and bound pour optimisation globale uni variante avec une contrainte non convexe

2 Résolvant problèmes de l'optimisation globaux avec simples :

Nous développons dans cette section l'algorithme de branch and bound pour résoudre le Problème (P). Avant de décrire l'algorithme et prouver sa convergence nous devons spécifier les bornant et se branchent opérations

2.1 Bornant procédures:

2.1.1 un affine qui sous-estime la fonction :

Soit {s_1,s_2,...,s_m} un discrétisation constant avec h de la dimension de la maille de S = [a,b] où s1=a et s_m = b. Soit {w_1,w_2,...,w_m} une séquence finie de fonctions définie comme ([3], [5]) (m≥2)

(s-s_(i-1))/(s_i-s_(i-1) ) si s_(i-1)≤s≤s_i

〖 w〗_i (s)= (s_(i+1)-s)/(s_(+1i)-s_i ) si s_i≤s≤s_(i+1) (1)

0 autrement,

Où s_0=s_1 et s_(m+1)=s_m. Nous avons ([3], [5])

∑_(i=1)^(i=m)▒〖w_i (s)=1,∀s∈S et w_i (s_j )=0 si i≠j, 1 autrement〗

Soit L_h f le piecewise interpolant linéaire à f aux points s_1,...,s_m ([3], [5])

L_h f(s)=∑_(i=1)^m▒〖f〖(s〗_i)w_i (s)〗 (2)

L'évaluation de l'erreur célèbre suivante (à qui preuve est basée sur les différences divisées) est utile pour construire un affine qui sous-estime fonction de f:

Théorème 1 ([3]) Nous avons ⎸L_h f(s)⎹≤1/8 kh^2 , ∀s∈S.

Preuve. Voyez [3].

Remarque1: De ce théorème nous voyons ce L_h f(s) est un ε-piecewise estimation linéaire de f quand □(1/8) kh^2≤ε cela tient quand h=(b-a)/(m-1)≤√((8ε )/k),or m≥(b-a) √((k )/8ε)+1. En d'autres termes, avec un discrétisation constant aimez précité nous avons besoin m=⌊(b-a) √((k )/8ε)⌋+1 fonctionnez évaluations à m le discrétise pointe (⌊x⌋dénote la partie entière dex)pour déterminer un ε-piecewise estimation linéaire de f.

Au pas courant k de l'algorithme branch and bound nous devons calculer une borne inférieure de f sur l'intervalle T^k≔[a_K,b_k ]. Utilisant Théorème1 nous obtenons un l_k du minorisation de l'affine de f sur [a_K,b_k ]. cela est défini comme, pour tout s∈[a_K,b_k ] (h=b_k-a_K)

l_k (s)=L_h f(s)-1/8 kh^2=f(a_K ) (b_K-s)/(b_K 〖-a〗_K )+f(b_K ) (s-a_K)/(b_K 〖-a〗_K )-1/8 k(b_k-a_K )^2

=1/h (f(b_k )-f(a_K ) )(s-b_k )+f(b_k )-1/8 kh^2

2.1.2 Une sous-estimant fonction du second degré convexe

Nous pouvons introduire un autre minorisation convexe de f sur [a_K,b_k ] lequel est meilleur que l_k:

Théorème 2 Nous avons:

〖 L〗_h f(s)-1/8 kh^2≤q_k (s)≔L_h f(s)-1/2 k(s-a_K )(b_K-s)≤f(s),∀ s∈[a_K,b_k ]. (3)

Preuve.

E(s)≔L_h f(s)-1/8 kh^2-q_K (s)=-1/8 k(b_k-a_K )^2+k/2 (s-a_K )(b_K-s)

=k/2[〖-s〗^2+(a_K+b_K )s-a_K b_K-1/4 (b_K-a_K )].

La fonction E est concave sur [a_K,b_K], et son dérivé est égal à zéro à s^*= (1 )/2 (a_K+b_K).

Par conséquent, pour tout s∈ [a_K,b_K] nous avons

E(s)≤max{E(s):s∈[a_K,b_K ] }=E(s^* )=0

et la première inégalité de (3) est vérifiée.

Pour justifier la deuxième inégalité, considérez maintenant la fonction ϕ définie sur S par

ϕ(s)≔f(s)-q_K (s)=f(s)-L_h f(s)+1/2 k(s-a_K )(b_K-s).

Clairement ce ϕ^'' (s)=f^''-k≤0 pour tout s ∈ S. D'où f est fonction concave, et par conséquent pour tout le s ∈ [a_K,b_K ] nous avons

ϕ(s)≥min⁡〖{ϕ(s):s∈[a_K,b_K ] }=ϕ(a_K )=ϕ(b_K )=0〗

La deuxième inégalité de (3) est aussi prouvée.

Remarque 2. Pour chaque intervalle T^k=[a_K,b_K] nous pouvons utiliser les résultats précités avec k_K au lieu de k, où k_K est un nombre positif tel que |f^'' (s)|≤k_K pour tout s∈[a_K,b_K ]. De point de vue numérique, si un tel k_K peut être calculé facilement, alors c'est intéressant de remplacer le k par k_K sur〖 T〗^k , depuis que plus petit k_K est, le meilleur les q_K de la borne inférieure seront.

Une borne inférieure de f sur 〖 T〗^k, dénoté LB(T^k), est calculé alors en résolvant le prochain programme convexe

LB(T^k )≔min⁡{q_K (s):a_K≤s≤b_K }. (4)

Depuis que le q_K est une fonction du second degré dans la forme

q_K (s)≔k/2 s^2+[(f(b_K )-f(a_K))/(b_(K-) a_K )-k/2(b_K 〖+a〗_K)]s+k/2 a_K b_K+(f(a_K ) b_K-f(b_K)a_K)/(b_K-a_K ) (5)

la solution optimale s_k^* de (4) est définie explicitement comme suit:

s_k^*={█(μ≔1/2 (a_K 〖+b〗_K )+1/k_h (f(b_K )-f(a_K ) ) si μ∈[a_K 〖,b〗_K ],@ a_K si μ<a_K,@ b_K si 〖μ>b〗_K,)┤ (6)

Remarque 3. Si s_k^*∉]a_K 〖,b〗_K [ alors

min⁡〖 {q_K (s):〖 a〗_K≤s≤b_K }〗=min {f(s):a_K≤s≤b_K }=min {f(a_K ),f(b_K)}.

Dans un tel cas nous avons une évaluation exacte sur l'intervalle 〖 T〗^k (voyez la figure 1b). Par conséquent

...