6. Algoritmi de optimizare pentru probleme fără restricţii...................................................................... 14 6.1 Introducere .................................................................................................................................... 15 6.2 Calculul lungimii pasului .............................................................................................................. 16

6.2.1 Algoritmi de determinare a unui interval pentru lungimea pasului........................................ 16 6.2.2 Algoritmi de reducere a intervalului pentru lungimea pasului ............................................... 19 6.2.3 Algoritmi de determinare a lungimii pasului.......................................................................... 23

6.3 Determinarea direcţiilor de căutare ............................................................................................... 24 6.3.1 Algoritmul de optimizare ciclică pe axele de coordonate ...................................................... 25 6.3.2 Algoritmul de optimizare ciclică pe axele de coordonate şi diagonală .................................. 25 6.3.3 Algoritmul Davies, Swann şi Campey ................................................................................... 26 6.3.4 Algoritmul Powell .................................................................................................................. 27 6.3.5 Algoritmul Zangwill............................................................................................................... 29 6.3.6 Metoda Cauchy ...................................................................................................................... 30 6.3.7 Metode de gradient conjugat .................................................................................................. 30 6.3.8 Metoda Newton ...................................................................................................................... 31 6.3.9 Metode cvasi-Newton............................................................................................................. 32

6.4 Testarea convergenţei.................................................................................................................... 35 7. Transformarea problemelor ................................................................................................................. 36

7.1 Restricţii de semn .......................................................................................................................... 36 7.2 Restricţii margini simple ............................................................................................................... 36 7.3 Restricţii liniare ............................................................................................................................. 37

6. Algoritmi de optimizare pentru probleme fără restricţii

14

6.1 Introducere Problema se formulează astfel:

( ){ }min f x

unde . f R Rn: → Se vor prezenta în continuare numai algoritmi de descreştere adică algoritmi care duc la descreşterea funcţiei obiectiv în fiecare iteraţie. Majoritatea acestor algoritmi se pot schematiza astfel: ALGORITMUL 1. Minimzare fără restricţii. Se cunoaşte x0 o aproximaţie iniţială a minimului. 0. Iniţializare. k ← 0 1. Test de convergenţă. Dacă sunt satisfăcute condiţiile de convergenţă procedura se termină cu soluţia xk. 2. Se determina direcţia de căutare. Se calculează un vector n-dimensional pk, direcţia de căutare. 3. Calculul lungimii pasului. Se calculează un scalarα , lungimea pasului, astfel încât: k

( )f fk k k kx p x+ <α ( )

pk

4. Actualizarea estimaţiei minimului. x xk k k+ ← +1 α k k← +1

15

Se continuă de la pasul 1.

6.2 Calculul lungimii pasului Se urmăreşte determinarea scalarului αk astfel încât

( ) ( )f fk k k kx p x+ <α In mod obişnuit se rezolvă cu o anumită precizie problema de optimizare monodimensională:

( ){ }min f α

unde: ( ) ( )f f k kα α= +x p

Pasul α se calculează de obicei urmând etapele: k

a) se determină un interval pentru αk ; b) se restrânge intervalul; c) se determină valoarea α optimă. k

In mod obişnuit în etapele a) şi b) se utilizează numai valorile funcţiei f(α). In etapa c) se utilizează frecvent şi valorile primei derivate a funcţiei f(α).

6.2.1 Algoritmi de determinare a unui interval pentru lungimea pasului

16

In vederea determinării unui interval pentru lungimea pasului se folosesc metode bazate pe compararea valorilor funcţiei calculate pentru diverse valori α. Aceste metode se numesc metode

de comparaţie. Uneori se folosesc pentru comparaţie şi valorile lui

( )f α

( )′f α . Valorile lui se folosesc

relativ rar în această fază a determinării lui

( )′f α

αk deoarece efortul de a evalua derivata este relativ mare. In ALGORITMUL 2 se caută un interval [ ]a b, şi astfel încât

. In acest algoritm se foloseşte un pas constant ρ pentru α.

[c a b∈ , ]( ) ( ) ( ) ( )f b f a f b f c≤ ≤,

ALGORITMUL 2. Determinarea unui interval pentru pas. Date: - o relaţie pentru calculul funcţiei f(α) - incrementul pentru pas ρ>0. Rezultate: - a < b < c trei valori pentru α care verifică condiţia ( ) ( ) ( ) (f b f a f b f c≤ ≤, ) şi condiţia suplimentară b = (a + c) / 2; - valorile f f ale funcţiei f(α) fa b c, , 0. Se determină a şi b astfel încât ( ) ( )f a f b≥ .

( )a f fa← ←0, a

b ( )b f fb← ←ρ,

17

dacă f atunci fa < b

a b f fa b↔ ↔ ←−, , ρ ρ 1. Se determină c astfel încât ( ) ( )f c f b≥

( )c b f f cc← + ←ρ, dacă f atunci fc ≥ b

mergi la pasul 2 altfel a b f fa b← ←, b c f fb c← ←, Se reia pasul 1 2. Se rearanjează valorile a, b, c astfel încât să fie în ordine crescătoare. dacă ρ < atunci 0 a c f fa c↔ ↔, In ALGORITMUL 3 se caută un interval [ ]a b, şi astfel încât

. Spre deosebire de algoritmul anterior aici se foloseşte un pas variabil ρ

pentru α.

[c a b∈ , ]( ) ( ) ( ) ( )f b f a f b f c≤ ≤,

ALGORITMUL 3. Determinarea unui interval pentru pas.

18

Date: - o relaţie pentru calculul funcţiei f(α) - incrementul pentru pas ρ>0; - coeficientul de creştere a pasului m>1 Rezultate: - a < b < c trei valori pentru α care verifică condiţia ( ) ( ) ( ) (f b f a f b f c≤ ≤, )

- valorile f f ale funcţiei f(α) fa b c, , 0. Identic cu pasul 0 de la ALGORITMUL 2. 1. Se determină c astfel încât ( ) ( )f c f b≥

( )c b f f cc← + ←ρ, dacă f atunci fc ≥ b

mergi la pasul 2 altfel a b f fa b← ←, b c f fb c← ←, ρ ρ ← m Se reia pasul 1 2. Identic cu pasul 2 de la ALGORITMUL 2.

6.2.2 Algoritmi de reducere a intervalului pentru lungimea pasului

19

ALGORITMUL 4. Reducerea intervalului prin metoda injumătăţirii intervalului. Date: - o relaţie pentru calculul funcţiei f(α) - a < b < c trei valori pentru α care verifică condiţia ( ) ( ) ( ) (f b f a f b f c≤ ≤, ) şi condiţia suplimentară b = (a + c) / 2; - valorile f f ale funcţiei f(α) fa b c, , - ε lungimea finală a intervalului; Rezultate: - a < b < c trei valori pentru α care verifică condiţia ( ) ( ) ( ) (f b f a f b f c≤ ≤, ) şi condiţiile suplimentare b = (a + c) / 2 şi c a− ≤ ε - valorile f f ale funcţiei f(α) fa b c, , 0. Testare convergenţă. dacă c a atunci − ≤ ε se iese din algoritm altfel se continuă cu pasul 1. 1. Se calculează v = (a + b) / 2 fv = f(v) 2. Se verifică intervalul a,v,b dacă f atunci fv ≤ b

20

c ← b, fc ← fb

b ← v, fb ← fv se continuă de la pasul 0. altfel se continuă de la pasul 3 3. Se calculează w = (b + c) / 2 fw = f(w) 4. Se verifică intervalul b,w,c dacă f atunci fw ≤ b

a ← b, fa ← fb

b ← w, fb ← fw se continuă de la pasul 0. altfel se continuă de la pasul 5 5. Se trece la intervalul v,b,w a ← v, fa ← fv

c ← w, fc ← fw se continuă de la pasul 0. In algoritmul înjumătăţirii intervalului se reduce într-o iteratie intervalul la 0.5 din intervalul anterior prin efectuarea a două calcule de funcţie. ALGORITMUL 5. Reducerea intervalului prin metoda secţiunii de aur.

21

Date: - o relaţie pentru calculul funcţiei f(α) - a < c două valori pentru α care delimitează intervalul iniţial - ε lungimea finală a intervalului;

- k13 5

2=

−

- k25 12

=−

Rezultate: - a < c două valori pentru α care delimitează intervalul final cu c a− ≤ ε 0. Initializări l = c - a v = a + k1 * l, fv = f(v) w = a + k2 * l, fw = f(w) 1. Testare convergenţa dacă l ≤ ε atunci se iese din algoritm altfel se continuă cu pasul 1. 2. Stabilire interval dacă fv < fw atunci c ← w

22

w ← v, fw ← fv l = c - a v = a + k1 * l, fv = f(v) altfel a ← v v ← w, fv ← fw l = c - a w = a + k2 * l, fw = f(w) se continuă de la pasul 1 In algoritmul secţiunii de aur se reduce într-o iteratie intervalul la 0.618 din intervalul anterior prin efectuarea unui singur calcul de funcţie.

6.2.3 Algoritmi de determinare a lungimii pasului In vederea determinării lungimii pasului se utilizează mai ales metode bazate pe interpolare. Dacă se cunosc valorile funcţiei f(α) în trei puncte se poate utiliza o aproximare parabolică a acestei funcţii şi se poate determina valoarea optimă αk astfel:

( ) ( ) ( )( ) ( ) ( )αk

a b

a b c

b c f c a f a b fb c f c a f a b f

=− + − + −

− + − + −12

2 2 2 2 2 2c

23

Dacă se cunosc valorile funcţiei şi valorile derivatelor de ordinul unu ale funcţiei f(α) în două puncte atunci se poate aproxima f(α) cu o funcţie polinomială de gradul 3 şi se poate determina valoarea optimă α astfel: k

( )αkb

b a

b f w zf f w

b a= −′+ −′− ′+

−2

unde: ( )z

f fb a

f fb aa b=

−−

+ ′+ ′3

w z f fa b= − ′ ′2

Valorile α astfel calculate se poate utiliza direct sau se pot include într-un proces iterativ pentru a abţine o precizie mai bună.

k

6.3 Determinarea direcţiilor de căutare Există numeroşi algoritmi care permit determinarea direcţiilor de căutare. Se prezintă în continuare câţiva dintre cei mai reprezentativi. Se reaminteşte că problema optimizării fără restricţii a fost formulată astfel:

( ){ }min f x

unde . f R Rn: → Se reaminteşte de asemenea că: - pasul curent este k, iar k ia valori de la 0,1, 2, ...

24

- se cunoaşte aproximaţia xk a punctului optim; - se face optimizare pe direcţia pk pentru a determina pe xk+1; Se utilizează notaţiile suplimentare:

( )f fk k= x

( )g xk kf= ∇

y g gk k k− −= −1 1

( )G H xk kf=

s x xk k k= −+1

6.3.1 Algoritmul de optimizare ciclică pe axele de coordonate In acest algoritm se utilizează n direcţii de căutare fixe şi anume direcţiile axelor de coordonate:

p ek k n= ( mod ) unde prin (k mod n) s-a notat restul împărţirii lui k la n. Prin e0, e1,..., en-1, s-au notat direcţiile axelor de coordonate. Algoritmul este caracterizat de un puternic caracter oscilatoriu şi deseori ineficace în determinarea punctului optim.

6.3.2 Algoritmul de optimizare ciclică pe axele de coordonate şi diagonală Şi în acest algoritm se utilizează n direcţii de căutare fixe şi una variabilă. Se utilizează deci în total n+1 direcţii de optimizare. Cele n direcţii fixe sunt direcţiile axelor de coordonate:

25

p ek k n= +( mod )1 unde prin (k mod n+1) s-a notat restul împărţirii lui k la n+1. După efectuarea a n optimizări monodimensionale pe direcţiile axelor de coordonate se face o optimizare pe direcţia diagonală:

x xk k n− − Deci la pasul k direcţia pk, se stabileşte astfel:

pex xk

k n

k k n

k nk n

=+ ≠

− +⎧⎨⎩

+

−

( mod ) , ( mod ),( mod )

1 11

nn=

Utilizând această modificare algoritmul optimizării ciclice pe axe devine în general mai eficient. Acest set de direcţii caracterizează şi algoritmul Hooke şi Jeeves.

6.3.3 Algoritmul Davies, Swann şi Campey In acest algoritm se utilizează un set de n direcţii de căutare variabile. Aceste direcţii de căutare sunt modificate după n iteraţii. Pentru a simplifica relaţiile care urmează se notează:

d pi k= unde:

i k n= mod Paşii principali ai algoritmului sunt: a) Se porneşte cu un set iniţial de n direcţii liniar independente de exemplu:

d ei i i n= = −, , ,...,0 1 1 b) Se efectuează n optimizări unidimensionale pe direcţiile di,

26

c) Presupunând că s-a ajuns la pasul k (adică s-a calculat xk optimizând pe direcţia pk-1) se determină vectorii:

q x xi k k n i= − − + d) Se ortogonalizează vectorii qi şi rezultă noile direcţii di. Pentru ortogonalizare se poate utiliza un proces de ortogonalizare Gram-Schmidt:

d qq dd d

di iiT

j

jT

jj

j

i

← −=

−

∑0

1

Direcţiile di astfel calculate se ortonormează:

d dd d

ii

iT

i

←

e) Se reia de la pasul b). Algoritmul Davies, Swann şi Campey este unul dintre cei mai eficienţi algoritmi de optimizare utilizaţi la rezolvarea problemelor fără restricţii. Direcţii similare se utilizează şi în algoritmul Rosenbrock.

6.3.4 Algoritmul Powell Algoritmul utilizează n direcţii de căutare proprii algoritmului şi direcţia diagonală. Deci în acest algoritm se utilizează un set de n+1 direcţii de căutare variabile. Aceste direcţii de căutare sunt modificate după n+1 iteraţii. Pentru a simplifica relaţiile care urmează se notează:

d pi k= unde:

27

i k n= +mod 1 unde prin k mod n+1 s-a notat restul împărţirii lui k la n+1. Paşii principali ai algoritmului de determinare a direcţiilor sunt: a) Se porneşte cu un set iniţial de n direcţii liniar independente de exemplu:

d ei i i n= = −, , ,...,0 1 1 b) Se efectuează n optimizări unidimensionale pe direcţiile di, c) Presupunând că s-a ajuns la pasul k (adică s-a calculat xk optimizând pe direcţia pk-1) se efectuează o optimizare pe direcţia diagonală

d x xn k k n= − − . d) Se determină noile direcţii di, astfel:

d di i i n← = −+1 0 1 1, , ,..., e) Se reia de la pasul b). Algoritmul Powell este cel mai utilizat algoritm de optimizare fără restricţii dintre algoritmii care nu folosesc derivatele funcţiei obiectiv. Algoritmul are proprietăţi deosebite de convergenţă la optimizarea funcţiilor pătratice .Dacă este aplicat unei funcţii pătratice conduce la soluţie după un număr finit de iteraţii. O funcţie pătratică are forma:

( )f T Tx x Ax b= +12

x

unde A este o matrice constantă, simetrică şi pozitiv definită iar b este un vector constant. Se demonstrează că după un număr de iteraţii m≤n direcţiile di , i = 0, 1, ...,n-1, caracteristice algoritmului Powell devin A-conjugate. Adică:

28

d AdiT

j

i ji j

=≠

> =⎧⎨⎩

00

,,α

Prin iteraţie se înţelege numai aici un grup de n+1 optimizări unidimensionale corespunzătoare paşilor b) şi c). Se demonstrează de asemenea că dacă direcţiile di sunt A-conjugate atunci se poate determina optimul funcţiei pătratice f(x) după cel mult n optimizări unidimensionale pe aceste direcţii. Există, în algoritm, tendinţa ca direcţiile di astfel stabilite să devină liniar dependente. Pentru a evita această dependenţă liniară s-au propus numeroase soluţii. Aceasta este explicaţia pentru care algoritmul este prezent în literatura de specialitate sub mai multe forme. Una dintre aceste soluţii o reprezintă algoritmul Zangwill prezentat în continuare.

6.3.5 Algoritmul Zangwill Algoritmul utilizează n direcţii de căutare proprii, cele n direcţii ale axelor de coordonate şi direcţia diagonală. Algoritmul este foarte asemănător cu algoritmul Powell şi păstrează proprietăţile de convergenţă şi A-conjugarea la limită a direcţiilor di ale acestuia. Paşii principali ai algoritmului de determinare a direcţiilor sunt: a) Se porneşte cu un set iniţial de n direcţii liniar independente de exemplu:

d ei i i n= = −, , ,...,0 1 1 Se iniţializează variabila l la valoarea 1. b) Se efectuează una sau mai multe optimizări unidimensionale pe direcţiile ei, până când se obţine un pas αk ≠ 0. Direcţiile ei sunt parcurse în ordinea l, l+1,..., n-1, 0, 1, 2,..., l-1. Dacă nu există αk ≠ 0 atunci

29

punctul este soluţie. Dacă există αk ≠ 0 atunci se atribuie variabilei l valoarea l+1 mod n şi din punctul obţinut prin optimizare pe direcţiile axelor de coordonate se continuă ca în algoritmul Powell. c) Se reia de la pasul b).

6.3.6 Metoda Cauchy Metoda mai este denumită şi metoda gradientului optimal. Metoda se bazează pe utilizarea unei aproximări liniare a funcţiei obiectiv:

( ) ( ) ( ) ( )f f f fk kT

k k kT

kx x x x x p≅ + − ∇ = + g de unde rezultă că la pasul k o algere potrivită pentru direcţia pk, este direcţia de descreştere maximă şi anume:

( )p xk kf= −∇ = −gk Pentru a simplifica notaţiile s-a utilizat notaţia gk pentru gradientul funcţiei f(x) calculat în x = xk. Metoda gradientului este relativ puţin utilizată datorită instabilităţilor provocate de calculul numeric asupra convergenţei metodei. Micile erori de rotunjire determină o convergenţă neaşteptat de slabă a algoritmului.

6.3.7 Metode de gradient conjugat Metoda gradienţilor conjugaţi a fost introdusă de Hestenes şi Stiefel pentru rezolvarea sistemelor de ecuaţii liniare. Se ştie că minimizarea unei forme pătratice pozitiv definite este echivalentă cu rezolvarea unui sistem de ecuaţii liniare. Metodele de gradient conjugat au fost deci dezvoltate pentru optimizarea funcţiilor pătratice dar se utilizează şi pentru funcţii de formă oarecare (nepătratice). In metodele de gradient conjugat la pasul k se utilizează direcţia:

30

p g pk k k k= − + −β 1 Relaţiile de calcul pentru scalarul βk se deduc pentru funcţiile pătratice pozitiv definite şi se pun sub o formă care nu conţine explicit matricea A a formei pătratice. Aceste relaţii se utilizează apoi la optimizarea funcţiilor de formă generală nepătratică. Câteva dintre cele mai cunoscute relaţii sunt: - metoda Fletcher-Reeves

βkkT

k

kT

k

=− −

g gg g1 1

- metoda Polak - Ribiere

βkkT

k

kT

k

= −

− −

g yg g

1

1 1

- metoda Hestenes-Stiefel

βkkT

k

kT

k

= −

− −

g yy p

1

1 1

In relaţiile de mai sus s-a notat: y g gk k k− −= −1 1

In metodele de gradient conjugat este necesar ca după un număr de paşi l > n să se reiniţializeze algoritmul punând βk = 0. Cea mai utilizată metodă dintre cele citate mai sus este metoda Fletcher-Reeves.

6.3.8 Metoda Newton

31

Metoda se bazează pe utilizarea modelului pătratic obţinut prin aproximarea pătratică a funcţiei obiectiv:

( ) ( ) ( ) ( ) ( ) ( )( )f f f fk kT

k kT

k kx x x x x x x H x x x≅ + − ∇ + − −12

sau cu altă notaţie:

( )f f kT

kT

kx p g p G≅ + +12

p

Se optimizează funcţia pătratică:

( )Φ p p g p G= +Tk

Tk

12

p

Din condiţia de minim: ( )∇Φ =p 0

rezultă sistemul de ecuaţii liniare în necunoscuta pk: G p gk k k= −

Metoda are proprietăţi de convergenţă foarte bune dar are şi dezavantajul utilizării derivatelor de ordinul 2.

6.3.9 Metode cvasi-Newton In metodele cvasi-Newton se folosesc în locul matricelor Gk aproximaţii ale acestora notate BBk. Având în vedere că matricea BkB se foloseşte la rezolvarea unui sistem de ecuaţii există şi algoritmi cvasi-Newton în care se aproximează G în loc de Gk

−1k. Se notează aproximaţia lui cu HGk

−1k.

Direcţia cvasi-Newton se determină din sistemul

32

B p gk k k= − Se porneşte în calcul cu o aproximaţie a matricei hessian sau chiar cu matricea unitate:

B I0 = şi apoi se actualizează BBk+1 la fiecare pas k. In vederea determinării lui Bk+1 B se observă ca în vecinătatea lui xk+1 se poate scrie:

( ) ( ) ( )( )∇ ≅ ∇ + −+ +f f fk k k kx x H x x x1 1 +k 1 Deci BBk+1se determină din sistemul de ecuaţii liniare în necunoscuta Bk+1B :

B s yk k k+ =1

unde s x xk k k= −+1

Evident sistemul de ecuaţii este supra-determinat se de aceea se impun condiţii suplimentare pentru BBk+1 cum ar fi: - să fie apropiată de Bk; - să fie simetrică; - să fie pozitiv definită; Cele mai cunoscute formule de actualizare pentru B sunt: - formula Davidon-Fletcher-Powell (DFP)

( ) ( )( ) ( )( )

B By s

y B s y y y B sy B s s

y sy yk k

kT

kk k k k

Tk k k k

T k k kT

k

kT

k

k kT

+ = + − + − −−

1 21

- formula Broyden-Fletcher-Goldfarb-Shanno (BFGS)

33

B By s

y ys B s

B s s Bk kkT

kk k

T

kT

k kk k k

Tk+ = + −1

1 1

Direcţia cvasi-Newton se poate determina direct din p Hk k gk= −

Hk+1se determină din sistemul de ecuaţii liniare în necunoscuta Hk+1: H y sk k+ k=1

Evident sistemul de ecuaţii este supra-determinat se de aceea se impun şi aici condiţii suplimentare pentru Hk+1. Cele mai cunoscute formule de actualizare pentru H sunt: - formula Davidon-Fletcher-Powell (DFP)

H Hs y

s sy H y

H y y Hk kkT

kk k

T

kT

k kk k k

Tk+ = + −1

1 1

- formula Broyden-Fletcher-Goldfarb-Shanno (BFGS)

( ) ( )( ) ( )( )

H Hs y

s H y s s s H ys H y y

s ys sk k

kT

kk k k k

Tk k k k

T k k kT

k

kT

k

k kT

+ = + − + − −−

1 21

Se preferă în general utilizarea aproximării lui B deoarece permite evitarea unei dificultăţi care apare frecvent în utilizarea aproximării lui H şi anume pierderea pozitiv definirii. Dintre cele două relaţii prezentate pentru calculul lui B se preferă de obicei formula BFGS deoarece formula DFP are tendinţa să construiască mai des aproximaţii singulare pentru B. Efortul mare de calcul necesitat de rezolvarea sistemului de ecuaţii poate fi redus prin factorizarea iniţială a matricei B şi actualizarea factorilor acesteia.

34

6.4 Testarea convergenţei Decizia cu privire la acceptarea unei iterate xk ca o aproximaţie adecvată a soluţiei se bazează pe două teste: - dacă şirul xk este convergent; - dacă xk satisface condiţiile suficiente de optimalitate. Testele de convergenţă a şirului xk se pot formula astfel:

x x xk k x k− ≤−1 ε

f f fk k f k− ≤−1 ε Se observă că aceste teste au un caracter relativ şi sunt potrivite pentru valori ale lui xk sau ale lui fk îndepărtate de zero. La valori ale lui xk sau ale lui fk apropiate de zero este necesar ca testele să aibă un caracter absolut. De exemplu:

x xk k− ≤−1 ε x

f fk k− ≤−1 ε f Testul de satisfacere a condiţiilor suficiente de optimalitate poate fi pus sub forma:

x x xk k n x k− ≤− ε sau x xk k n− ≤− ε x

f f fk k n f− ≤− ε k sau f fk k n− ≤− ε f Dacă se utilizează derivatele atunci testul satisfacere a condiţiilor suficiente capătă forma mai simplă:

gk g≤ ε

35

7. Transformarea problemelor Se tratează în acest paragraf câteva posibilităţi de a transforma problemele cu restricţii în probleme fără restricţii.

7.1 Restricţii de semn Restricţiile de forma:

xi ≥ 0 se pot elimina prin schimbarea de variabilă:

x wi i= 2 Similar restricţiile de forma:

xi ≤ 0 se pot elimina prin schimbarea de variabilă:

x wi i= − 2

7.2 Restricţii margini simple Restricţiile margine simplă de forma:

x ci i≤ se pot elimina prin schimbarea de variabilă:

x c wi i= − 2i

Restricţiile margine simplă de forma:

36

b xi i≤ se pot elimina prin schimbarea de variabilă:

x b wi i= + 2i

i

Restricţiile margini simple bilaterale de forma:

b x ci i≤ ≤ se pot elimina prin schimbarea de variabilă:

( )[ ]x c b w bi i i i i= − + +12

cos ci

sau ( ) ( )x b c b p wi i i i i= + −

unde p(w) este o funcţie definită pe (-∞, +∞) care ia valori în [0,1]. De exemplu: ( )p w w( ) sin= 2

sau

p we w( ) =

+ −

11

7.3 Restricţii liniare Se presupune în continuare că restricţiile sunt de forma:

b c ii iT

i≤ ≤ = ′a x , , ,...,1 2 m.,

a xi

Tic i m m≤ = ′ +, ,..1

Se utilizează transformările:

37

cos , , ,...,wc b

b cc b

i mii i

iT i i

i i

=−

−+−

= ′2 1 2a x

w c i mi i iT2 1= − = ′ +a x, ,.. m.,

w

Se definesc vectorii:

( )v = ′ ′+cos ... cos ...w w wm m m

T

1 12 2

d = −+−

−+−

⎛⎝⎜

⎞⎠⎟′ ′

′ ′′+

c bc b

c bc b

c cm m

m mm m

T

1 1

1 11... ...

şi matricea:

A a a aT

m mm m m

T

c b c b=

−−

−− −

⎛⎝⎜

⎞⎠⎟

′ ′′ ′+

2 2

1 11 1... ... a

Se observă că transformarea se poate rescrie: v Ax d= +

Se partiţionează A şi x operând eventual o rearanjare a componentelor x:

[ ]A A A xxx

= ′ ′′ =′′′

⎧⎨⎩

⎫⎬⎭

,

astfel încât A' să fie nesingulară şi de dimensiuni m x m. Rezultă:

( ) ( )′ = ′ − ′′ ′′ −−x A v A x d1

Noul vector al variabilelor este:

38

wx′′⎧⎨⎩

⎫⎬⎭

39