CUPRINS

CAP.1.PROBLEMA COMPLEMENTARITATII

1.1.Introducere 4

1.2.Importanta problemei complementaritatii si rolul

calculatorului in rezolvarea ei 7

1.3.Notatii 10

1.4.Conurile complementare 12

1.5.Problema complementaritatii liniare 14

1.6.Aplicatii 15

1.6.1.Programarea liniara 15

1.6.2.Programarea patratica 17

1.6.3.Jocuri de doua persoane 18

1.6.4.Alte aplicatii 19

1.7.Clase de matrici 20

1.8.Algoritmi pentru rezolvarea problemei

complementaritatii liniare 21

1.8.1.Bazele 22

1.8.2.Operatii pivot 24

1.8.3.Baza initiala 26

1.8.4.Proprietatile bazele 27

1.8.5.Bazele complementare admisibile aproape

adiacente 28

1.8.6.Regula pivotului complementar 28

1.8.7.Incheierea 29

1.9.Exemple numerice 30

1.10.Conditii 35

1.11.Alti algoritmi 35

1.12.Rezumat al rezultatelor teoretice 36

1.13.Probleme nerezolvabile 36

1.14.Problema complementaritatii neliniare 37

1.15.Metode de calcul a punctelor fixe 38

CAP.2.PROBLEMA COMPLEMENTARITATII IN

PROGRAMAREA PATRATICA

2.1.Restrictii ecuatii 41

2.2.Metoda multiplicatorilor Lagrange 53

2.3.Metoda multimii active 58

2.4.Proprietati avansate 65

2.5.Probleme speciale de programare patratica 68

2.6.Pivotarea complementara si alte metode 72

2.7.Exercitii 81

BIBLIOGRAFIE   

Capitolul 1

Problema complementaritatii

1.1.Introducere

Fie Rⁿ un spatiu vectorial euclidian de dimensiune n.Fie M o matrice patratica de rang n si q un vector coloana in Rⁿ.Se considera problema:sa se gaseasca w₁,..,w_n,z₁,.,z_n cu proprietatille:

w-Mz=q, w 0, z 0 si w_iz_i=0 pentru toti i

Ca un exemplu concret,fie

2 1 -5

n=2 M= q=

1 2 -6

Pentru acest caz,problema asociata ce trebuie rezolvata este:

w₁ -2z₁-z₂ = -5

w₂-z₁-2z₂= -6 (1.1)

cu variabilele w₁,w₂,z₁,z₂ 0 si w₁z₁=w₂z₂=0

Probleme de acest fel,cunoscute sub denumirea de problemele complementaritatii liniare (P.C.L.) ,se pot intalni in programarea liniara,programarea patratica,in teoria jocurilor si in numeroase alte domenii.Problema (1.1) poate fi scrisa si sub forma de ecuatie vectoriala:

1 0 -2 -1 -5

w₁ +w₂ +z₁ +z₂ = (1.2)

2 1 -1 -2 -6

w₁,w₂,z₁,z₂ 0 si w₁z₁=w₂z₂=0    (1.3)

Pentru orice solutie care satisface (1.3),cel putin una dintre variabilele din perechea (w₁,z₁) trebuie sa fie egala cu zero,deoarece w₁z₁=0.Analog si pentru perechea (w₂,z₂).O metoda de rezolvare pentru aceasta problema este:se alege cate o variabila din fiecare pereche (w₁,z₁),(w₂,z₂) si se egaleaza aceste variabile cu valoarea zero in sistemul de ecuatii (1.2).Variabilele ramase in sistem se numesc variabile active.Dupa eliminarea variabilelor nule din (1.2),daca sistemul obtinut are o solutie in care varibilele active sunt nenegative,aceasta va fi solutie pentru (1.2),(1.3).

Fig.1. Pos ,

-1 -2

Notam cu (q₁,q₂) vectorul constant (-5,-6) din (1.2).Alegem w₁,w₂ ca variabile cu valoare zero.Rezulta ca variabilele active sunt z₁,z_2.Dupa

inlocuirea w₁,w₂=0 in (1.2),sistemul obtinut este:

-2 -1 -5 q₁

z₁ +z₂ = = =q (1.4)

-1 -2 -6 q₂

z₁ 0 , z₂

Sistemul redus (1.4) are o solutie daca si numai daca vectorul q poate fi

-2 -1

exprimat ca o combinatie liniara nenegativa de vectorii si

-1 -2

-2 -1

Multimea tuturor combinatiilor lineare nenegative de vectori si

-1 -2

reprezinta un con in spatiul de coordonate q₁ si q₂ ,ca in Fig1.Daca vectorul

-5

dat q= se afla in acest con. Atunci P.C.L.(1.1) are o solutie in care

variabilele active sunt z₁ , z₂ si w₁=w₂=0.

Verificam daca punctul (-5,-6) se afla in acest con si daca solutia pentru (1.4) este (z₁ , z₂ )=(4/3,7/3) si rezulta ca solutia pentru (1.1) este

(w₁,w₂ , z₁ , z₂ )=( 0,0,4/3,7/3).

Conul din Fig.1 se numeste conul complementar asociat P.C.L (1.1).Conurile complementare sunt generalizari ale claselor de sferturi de cerc sau ale claselor de ortanti.

P.C.L. (1.1) este de ordin 2.Intr-o P.C.L. de ordin n vor fi 2n variabile.Problemele de ordin 2 pot fi rezolvate prin trasarea tuturor conurilor complementare si verificarea daca vectorul q se afla in aceste conuri.Pentru rezolvarea problemelor de ordin mai mare avem nevoie de algoritmi eficienti si calculatoare care pot obtine solutii folosind acesti algoritmi.

1.2.Importanta problemei complementaritatii si

rolul calculatorului in rezolvarea ei

Exemplu:

Fie K suprafata poliedrala convexa hasurata ca in Fig.2.Fie P puctul de coordonate (-2,-1).Se cere sa se gaseasca punctul K cel mai apropiat de P (se considera dinstanta euclidiana ).Probleme de acest fel apar foarte des in inginerie si in aplicatiile cercetarii operationale.

Fiecare punct din K poate fi exprimat co o combinatie convexa de puncte de extrem (sau puncte unghiulare) A,B,C,D, i.e.,coordonatele puctelor generale din K sunt (l l l l l l l l ) unde l_i satisfac l l l l =1 si l_i 0 pentru toti i.Astfel problema gasirii punctului din K cel mai apropiat de P este echivalenta cu rezolvarea problemei:

inf

l poate fi eliminat din aceasta problema prin inlocuirea lui cu expresia l l l l Prin simplificare, se obtine problema patratica:

inf (-66,-54,-20)l l^T l

4 16 8

pentru -l l l -1 si l

unde l

.Se va arata in sectiunea 1.61. Programarea patratica ca rezolvarea acestui program este echivalenta cu rezolvarea unei P.C.L..

u₁ 34 16 4 1 l

u_{2 -} 16 34 16 1 l = -54

u₃ 4 16 8 1

v₁ -1 -1 -1 0 Y₁ 1

toate variabilele

u₁,u₂,u₃,v₁,l l l ,y₁

si

u₁l =u₂l =u₃l =v₁y₁=0

Daca ( u_1, u₂, u₃, v_1, l l l y₁) este o solutie a acestei P.C.L.,fie l l l l si x=( l l l l l l l ) este punctul din K cel mai apropiat de P.

In sectiunea 1.6. Aplicatii se arata ca toate problemele de programare liniara si problemele de programare patratica convexa pot fi transformate in P.C.L. .Astfel de P.C.L. pot fi rezolvate prin algoritmul pivot complementar tratat in sectiunea 1.8 .Algoritmi pentru rezolvare P.C.L.

Fif.2. Problema distantei minime.

Totusi , majoritatea aplicatiilor practice ale P.C.L. conduc la probleme de ordin mare . Este practic imposibil de rezolvat manual asemenea probleme de ordin mare si devine esentiala folosirea calculatorului . De asemenea, este importanta dezvoltarea algoritmilor pentru rezolvarea P.C.L.,ceea ce conduce la programe mai eficiente pentru calculator.

Programarea liniara detine un vast numar de aplicatii .In prezent, variante ale metodei simplex sunt folosite frecvent pentru solutionarea programelor liniare intalnite in aplicatiile vietii reale .Un studiu experimental a aratat ca algoritmul pivot complementar pentru rezolvarea P.C.L. (vezi sectiunea 1.8.Algoritmi pentru rezolvarea P.C.L.) este net superior metodei simplex pentru rezolvarea programelor liniare .Este posibil ca in viitorul apropiat , programele pentru calculator ce rezolva P.C.L. sa fie deseori folosite pentru rezolvarea problemelor programarii liniare .

In sectiunile 1.6.Aplicatii, 1.8.Algoritmi pentru rezolvarea P.C.L. si 1.10.Conditii se arata ca algoritmul pivot complementar pentru rezolvarea P.C.L. poate fi folosit pentru rezolvarea problemelor liniare ,problemelor patratice convexe si problemelor de jocuri bimatriciale .Astfel P.C.L. asigura o teorie generala pentru studierea tuturor acastor tipuri diferite de probleme .

De asemenea, s-a aratat ca argumentele folosite in algoritmul pivot complementar pentru rezolvarea P.C.L. pot fi generalizate si aceste generalizari au condus la algoritmi care pot calcula aproximativ punctele fixe Brower si Kakutani .Pana acum ,singura si cea mai mare contributie a problemei complementaritatii este probabil intelegerea si dezvoltarea algoritmilor de calcul a punctelor fixe (vezi sectiunea 1.15.Metode de calcul a punctelor fixe).

In matematica ,teoria punctului fix este foarte mult dezvoltata , dar absenta unor algoritmi eficienti pentru calculator ale acestor puncte fixe au impiedicat pana acum toate incercarile de aplicare ale acestei importante teorii in problemele vietii reale .Impreuna cu dezvoltarea acestor noi algoritmi ,teoria punctului fix si-a gasit numeroase aplicatii in programarea matematica ,in economia matematica si in numeroase alte domenii.

1.3.Notatii

Fie D o matrice .Vectorul coloana j al matricei D se noteaza cu D.j.

D^T reprezinta transpusa matricei D. I repezinta matricea identica .

Exemplu1:

Fie n=3 ,atunci I= 0 1 0 si I.₃ = 0

0 0 1 1

Daca este o multime de vectori coloana din Rⁿ Pos reprezinta multimea tuturor vectorilor din Rⁿ care pot fi exprimati ca o combinatie liniara nenegativa de E.₁,.,E._k , i.e. ,

Pos=.

0

Exemplu 2: Pos , este ortant nenegativ din R² (vezi Fig.3).

2 -2

Exemlu 3:Pos , este conul hasurat din Fig.4.

1 -2

Pentru orice r,e_r este vectorul coloana din R^r ale carui elemente sunt egale cu 1.

Exemplu 4: e₃ =( 1,1,1)^T

1 0

Fig. 3.Pos ,

0 1

-2 2

Fig.4.Pos. ,

-2 1

1.4.Conul complementar

Se da M o matrice patratica de ordin n.Pentru a obtine C(M), clasa conurilor complementare corespunzatoare lui M, perechea de vectori coloana (I._j,-M._j) se numeste perechea complementara de vectori j,1≤j≤n.

Se alege un vector din perechea (I._j,-M._j) si se noteaza cu A._j. Multimea ordonata de vectori (A.₁,.,A._n) se numeste multimea complementara de vectori.Conul Pos( A.₁,.,A._n) se numeste conul complementar din clasa C(M).In total sunt 2ⁿ conuri complementare.

Exemplu 5:Fie n=2 si M=I.In acest caz clasa C(I) este chiar clasa ortantilor

din R² (vezi Fig.5).

In general pentru orice n,C(I) este clasa ortantilor din Rⁿ.Astfel clasa

conurilor complementare este o generalizare a clasei ortantilor.

Exemplul 6: n=2 si M= . Vezi Fig.6.

Exemplu 7: n=2 si M= .Vezi Fig.7.

1 0

Fig.5. Conurile complementare cand M=

0 1

Fig.6. Conurile complementare cand M=

Fig.7. Conurile complementare cand M=

1 -2

1.5.Problema complementaritatii liniare

Fiind date M o matrice patratica de ordin n si vectorul coloana qIRⁿ,P.C.L (q,M) este sa se gaseasca conul complementar in C(M) care sa contina punctul q, adica sa se gaseasca multimea complementara de vectori (A.₁,.,A._n) astfel incat :

(i)        A._j I , pentru 1≤j≤ n si

(ii)     q poate fi exprimat ca o combinatie liniara de vectorii (A.₁,.,A._n).

Aceasta este echivalenta cu gasirea lui wI Rⁿ,zIRⁿ satisfacand

_{n n}

∑ I._jw_j -∑ M._jz_j=q

^{j=1 j=1}

w_j≥0, z_j≥0 ( pentru toti 1≤j≤ n)

si w_j=0 sau z_j=0 (pentu toti 1≤j≤n)

Cu ajutorul matricelor se mai poate scrie astfel:

w-Mz=q (5.5)

w≥0 z≥0 (5.6)

w_jz_j=0 (pentru toti j) (5.7)

_n

Datorita relatiei (5.6), conditia (5.7) este echivalenta cu w_jz_j=w^Tz=0

^j=1

si aceasta conditie este cunoscuta sub denumirea de restrictia complementaritatii .Deci P.C.L.(q,M) consta in gasirea lui w IRⁿ,z I Rⁿ ce satisfac (5.5),(5.6),(5.7).

Pentru orice solutie a P.C.L.(q,M) ,daca una dintre variabilele din perechea (w_j,z_j) este pozitiva , cealalta trebuie sa fie zero.De aceea perechea (w_j,z_j) se numeste pereche complementara de variabile si fiecare variabila

din aceasta pereche este complementara celeilalte.

Aplicatii

1.6.1. Programarea liniara

Se stie ca orice problema de progamare liniara poate fi scrisa sub forma canonica ( simetrica ).

inf C^Tx

pentru Ax≥ b (6.8)

x≥0

Presupunem ca A este o matrice de rang m N.Daca x este o solutie optima pentru problema (6.8), atunci exista vectorul dual y I R^m si vectorii liberi

u x

vIR^m, uI R^N astfel incat . si . sa satisfaca:

v y

u 0 -A^T x c^T

v A 0 y -b (6.9)

u x u ^T x

. ≥0, . ≥0, si . . =0

v y v y

u x

Si reciproc daca . si .

v y

satisfac toate conditiile din (6.9),atunci x este solutie optima pentru problema (6.8).

Observatie:In (6.9) toti vectorii si matricile sunt scrise sub forma

u    extinsa (separata). De exemplu .

v

este vectorul (u₁,.,u_n,v₁,.,v_m)^T.Daca n= m+N,

u x 0 -A^T c^T

w = . , z = . , M = ..... , q= .

v y A 0 -b

Problema (6.9) este vazuta ca o P.C.L. .Solutia problemei liniare (6.8) poate fi obtinuta si prin rezolvarea P.C.L. (6.9) .

1.6.2.Programarea patratica

Se considera problema de programare patratica

Inf

pentru Ax≥b (6.10)

x≥0

unde A este o matrice de rang mN si D este o matrice simetrica patratica . x I Rⁿ reprezinta punctul Karush-Kuhn-Tucker pentru problema (6.10),daca exista vectorul yIR^msi vectorii liberi uIR^N, v I R^m astfel incat ( x, y, u, v) sa satisfaca:

u D -A^T x c^T

v A 0 y -b (6.11)

u x u ^T x

. ≥0, . ≥0, si . . =0

v y v y

atunci (6.11) este o P.C.L. .Din Teorema Karush-Kuhn-Tucker partea de necesitate daca x reprezinta punctul de minim local pentru (6.10) ,atunci x este punct Karush-Kuhn-Tucker .Daca D este o matrice pozitiv semidefinita, atunci (6.10) se numeste problema de programare patratica convexa,si, in acest caz din Teorema de suficienta Krush-Kuhn-Tucker se deduce ca fiecare punct Krush-Kuhn-Tucker este solutie optima pentru (6.10).Rezolvand P.C.L. (6.11) se obtine punctul Krush-Kuhn-Tucker pentru(6.10) si daca D este matrice pozitiv semidefinita, aceasta reprezinta solutia optima pentru (6.10).

1.6.3.Jocuri de doua persoane

La fiecare joc, jucatorul I alege una dintre cele m optiuni ale sale din multimea posibila si independent,jucatorul II alege una dintre cele N optiuni ale sale din multimea posibila.Intr-un joc, daca se intampla ca jucatorul I sa aleaga optiunea i ,si jucatorul II sa aleaga optiunea j, atunci jucatorul I pierde

suma a'_ij$ si jucatorul II pierde suma b'_ij$,unde A'=(a'_ij) si B=(b'_ij) sunt matricile de pierdere date .

Daca a'_ij+b'_ij=0 pentru toti i si j , jocul se numeste jocul cu suma nula, si in acest caz este posibila dezvoltarea conceptului de strategie optima,

pentru joc folosind Teorema Von Neumann minimax.Jocurile care nu sunt jocuri cu suma nula sunt numite jocuri cu suma nenula sau jocuri bimatriciale.In jocurile bimatriceale este dificil de definit o strategie optima.Totusi,in acest caz strategia perechiide ehilibru se poate defini si problema de calculare a strategiei perechii de echilibru poate fi transformata intr-o P.C.L.

Presupunem ca jucatorul I isi alege optiunea i cu probabilitatea x_i.Vectorul coloana x=(x_i)I R^m defineste complet strategia jucatorului I .Analog , fie vectorul y=(y_i)I R^N probabilitatea de strategie a jucatorului II.Daca jucatorul I adopta strategia x , si jucatorul II adopta strategia y , pierderile jucatorului I sunt x^T A' y si pierderile jucatorului II sunt x^TB'y.

Perechea de strategie ( x, y) reprezinta perechea de echilibru daca un jucator nu beneficiaza de dreptul sau de a-si schimba strategia , in timp ce celalalt jucator isi pastreaza strategia din perechea ( x, y) neschimbata , i.e., daca

xA' y≤xA' y (pentru toti vectorii probabili xIR^m)

xB' y≤ xB' y (pentru toti vectorii probabili yIR^N)

Fie α, β numere pozitive arbitrare astfel incat a_{i j} =a^'_{i j} +α>0 si b_{i j} =b^'_{i j}+β>0 pentru toti i,j: Fie A=(a_{i j}), B=(b_{i j}).Se considera P.C.L.

u 0 A ξ -e_m

v B^T 0 -e_N (6.12)

u u ^T

. ≥0, . ≥0, si . . =0

v η v η

vezi partea 1.3.Notatii pentru definirea lui e_m,e_N.S-a aratat ca daca ( u, v, η) este solutie pentru P.C.L.(12), atunci x = ξ_i) si

y = η_i) reprezinta strategiile perechii de echilibru pentru jocul initial.

1.6.4.Alte aplicatii

P.C.L este folosita pentru studiul problemelor din analiza plastica de structura, din comportarea rezistentei neelastice la incovoiere a grinzilor din beton armat, din suprafata de separatie pentru lagarela de sustinere, pentru studiul modelelelor financiare si numeroase alte domenii.

1.7.Clase de matrici

Vom defini cateva clase de matrici pe care le vom folosi in studiul P.C.L Fie M o matrice patratica de rang n.

M este o matrice pozitiv definita daca:

_{n n}

y^TMy =Σ Σ y_i m_{i j} y_j>0 pentru toti 0≠y Rⁿ

^{i=1 j=1}

2.M este o matrice pozitiv semi-definita daca:

y^TMy ≥0 pentru toti y IRⁿ

3. M este o matrice copozitiva daca:

y^TMy ≥0 pentru toti y≥0

4.M este o matrice plus copozitiva daca este o matrice copozitiva si daca

y^T(M+M^T)=0 pentru toti y≥0 cu proprietatea y^TMy =0

5. M este o P_ matrice daca toti determinantii principali ai matricei M sunt pozitivi.

6.M este o Q_matrice daca P.C.L. (q,M) are solutie pentru toti q I Rⁿ

1.8.Algoritmi de rezolvare a P.C.L.

P.C.L de ordin 2 pot fi rezolvate prin trasarea (desenarea) tuturor conurilor complementare in planul determinat de q₁,q₂ asa cum s-a discutat in 1.1.Introducere.

Exemplu 8

Fie q= si M=

1 -2

si se considera P.C.L.(q,M).

Clasa conurilor complementare corespunzatoare acestei probleme este in Fig.7

Tabelul 8.13.

w₁,w₂,z₁,z₂≥0, w₁z₁=w₂z₂=0

q se afla situat in doua conuri complementare Pos(- M._1,I.₂) si Pos(-M₁,-M.₂). Aceasta implica ca multimile variabile active (z₁,w₂) si (z₁,z₂) conduc la solutia P.C.L.

Inlocuind w₁=z₂=0 in (8.13) si rezolvand sistemul ramas pentru valorile variabilelor active (z₁,w₂) se obtine solutia (z₁,w₂)=(2,1). Astfel (w₁,w₂,z₁,z₂)=(0,1,2,0) este solutia P.C.L considerate. Analog , inlocuid w₁=w₂=0 in (8.13) si rezolvand sistemul pentru valorile variabilelor active (z₁,z₂) se obtine o a doua solutie (w₁,w₂,z₁,z₂)=(0,0, 7/3,2/3 ) pentru P.C.L. considerata.

Exemplu 9 :

Fie q= si M=

1 -2

si se considera P.C.L.(q,M).Clasa conurilor complementare corespunzatoare acestei probleme este trasata in Fig.7.Se verifica ca q nu se afla in nici un con complementar.Rezulta ca aceasta P.C.L. nu are solutie.

S-a discutat in 1.1.Introducere ca metoda de mai sus poate fi aplicata doar pentru P.C.L. de rang 2.Pentru rezolvarea P.C.L. de ordin mai mare,vom descrie algoritmul pivot complementar care foloseste operatii liniare pentru sistemul de ecuatii (5.5).

Pentru P.C.L. (5.5),(5.6),(5.7) daca q≥0,atunci w=q,z=0 este o solutie si problema este rezolvata.Deci presupunem ca q<0.

1.8.1.Bazele

Variabila artificiala z₀,asociata vectorului coloana -e_n (vezi sectiunea 1.3.Notatii),este introdusa in sistemul (5.5) pentru a obtine o baza admisibila.Folosind forma tabelara,sistemul (5.5) devine:

Tabelul 8.14.

w≥0 z≥0 z₀≥0

In fiecare etapa a algoritmului folosim o baza care oste o submatrice patratica nesingulara de ordin n a matricei coeficient din (8.14).Vectorii coloana din baza sunt numiti vectori coloana de baza si variabilele din (8.14) asociate vectorilor sunt numite variabile de baza.Vectorii coloana ramasi in tabel se numesc vectori coloana secundari(nebazici) si variabiabilele asociate lor sunt variabile secundare.

Solutia pentru (8.14) corespunzatoare unei baze date se obtine prin egalarea tuturor variabilelor secundare cu zero si rezolvarea sistemului de ecuatii liniare ramas din (8.14) cu valorile variabilelor de baza.Baza este o baza admisibila daca valorile tuturor variabilelor de baza din solutie sunt nenegative.Algoritmul foloseste doar baze admisibile.

Cand baza este transformata in matricea identica (prin aplicarea operatiilor necesare sau prin inmultirea la dreapta a intregului tabel din (8.14) cu inversa bazei), (8.14) este transformat in tabelul canonic asociat bazei.Variabilele de baza asociate lui I._r din tabelul canonic sunt numite r_variabile de baza, sau variabile de baza din linia r a tabelului canonic.

Toti vectorii coloana din tabelul canonic sunt numiti vectori coloana actuali.Fie q vectorul actual constant din dreapta.Atunci q este vectorul valorilor variabilelor de baza pentru solutia corespunzatoare acestei baze, q≥0 daca baza reprezinta o baza admisibila.

1.8.2.Operatii pivot

Prima etapa folosita in algoritm este etapa pivot care reprezinta si etapa principala a algoritmului simplex folosit pentru rezolvarea problemelor liniare.

La fiecare etapa a algoritmului ,baza se schimba prin introducerea in baza a unui vector coloana secundar.Variabilele din (8.14) asociate acestui vector se numesc variabile de intrare.Vectorul lor coloana actual se numeste coloana pivot pentru aceasta schimbare a bazei.

In solutia pentru (8.14),asociata la noua baza,toate variabilele secundare,diferite de variabilele de intrare,vor fi egalate cu zero.

Deoarece baza pentru (8.14) este formata din n vectori coloana,atunci cand o noua coloana este introdusa in baza,unul dintre vectorii coloana prezent in baza va trebui eliminat.Eliminarea vectorului trebuie facuta dupa o anumita regula numita:testul raportului minim(criteriul de iesire din baza) in terminologia programarii liniare.Acest criteriu garanteaza ca noua baza obtinuta dupa etapa pivotului este admisibila.

Vom analiza pe scurt acest criteriu de iesire din baza. Singurele variabile ale caror valori din solutie se schimba la aceasta etapa sunt variabilele de intrare si variabilele de baza actuale.Presupunem ca valoarea variabilei de intrare este schimbata de la valoarea actuala 0 la o valoare oarecare nenegativa, .Valorile variabilelor de baza se determina in functie de astfel incat noua solutie sa satisfaca conditiile egalitatii din (8.14).

Spre exemplu sa presupunem ca variabilele de baza actuale sunt

y_1,y₂ ,.,y_n cu y_r variabilele de baza ale liniei r si fie x_s variabilele de intrare.[Variabilele din (14) sunt w₁,w₂,.,w_n;z₁,z₂,.,z_n;z₀.Exact n dintre aceste variabile sunt variabile de baza actuale.Pentru usurinta, presupunem ca aceste variabile de baza sunt notate cu y_1,y₂ ,.,y_n ].Dupa rearanjarea variabilelor din (8.14),daca este necesar,forma canonica (8.14) a bazei prezente este de forma:

Deoarece toate variabilele secundare ,altele decat x_s,vor fi egalate cu zero,noua solutie este:

x_s=λ

y₁ = q₁ - a_1sλ (8.15)

y_i = q_i - a_isλ

y_n = q_n - a_nsλ

toate celelalte variabile=0

Exista doua posibilitati:

1.Coloana pivot poate fi nepozitiva,i.e., a _is≤0 pentru toti 1≤i≤ n .In acest caz solutia pentru (8.15) ramane nenegativa pentru toti λ≥0.Cum λ ia valori de la 0 la ∞ ,aceasta solutie traseaza o semidreapta nemerginita(sau o frontiera nelimitata) a multimii bazelor admisibile pentru (8.14).Daca se intampla acest lucru,algoritmul se incheie.

2.Exista cel putin o intrare pozitiva in coloana pivot.In acest caz,daca solutia (8.15) ramane nenegativa,valoarea maxima pe care o poate lua λ este θ=min( q_i / a_is : I astfel incat a_is >0).

Acest θ este numit raportul minim in aceasta etapa pivot.Daca θ= q_r / a_rs atunci y_r devine egal cu zero in solutia pentru (8.15) cand x_s=θ.Astfel y_r este eliminat din vectorul de baza si x_s devine variabila de baza r in locul lui.Linia r este numita linia pivot pentru aceasta etapa pivot.

Pivotarea consta in transformarea coloanei pivot in I._r prin operatii liniare.Aceasta conduce la tabelul canonic asociat noii baze si la terminarea etapei.

Deoarece ia valori de la 0 la in (8.15),schimbam solutia de la aceasta etapa la solutia din (8.14) asociata noii baze.Aceste doua solutii sunt puncte extreme adiacente ale multimii de solutii admisibile pentru (8.14) si segmentul de linie care le uneste este o margine.

1.8.3.Baza initiala

Variabila artificiala z₀ a fost introdusa in (8.14) pentru a obtine o baza admisibila pentru inceperea algoritmului.

Identificam linia t astfel incat q_t=min(q_i : 1≤i≤n).Deoarece am presupus q<0,atunci q_t<0.Atunci cand un pivot este format in (8.14) cu vectorul coloana z₀ ca si coloana pivot si linia r ca linia pivot,vectorul constant din dreapta devine un vector nenegativ.Tabelul rezultat este tabelul canonic asociat bazei in care variabilele de baza sunt w₁,.,w_t-1,z₀,w_t+1,.,w_n.Aceasta este baza initiala pentru inceperea algoritmului.

1.8.3. Proprietatile bazelor

Baza initiala satisface urmatoarele proprietati:

1.Exista cel putin o variabila de baza din fiecare pereche complementara de variabile (w_j,z_j ).

2.z₀ este variabila de baza in ea.Contine exact o variabila de baza din fiecare (n-1) perechi complementare de variabile si ambele variabile din perechea complementara ramasa sunt secundare.

O baza admisibila pentru (8.14) care contine exact o variabila de baza din fiecare pereche complementara(w_j,z_j) se numeste baza complementara admisibila.Solutia admisibila pentru (8.14) corespunzatoare bazei admisibile complementare este o solutie pentru P.C.L.

O baza admisibila pentru (8.14) care satisface cele doua proprietati de mai sus se numeste baza complementara admisibila apropiata.Toate bazele obtinute in algoritm ,cu posibila exceptie a bazei finale,sunt baze complementare admisibile apropiate.Daca la o anumita etapa a algoritmului se obtine o baza complementara admisibila, atunci ea reprezinta baza finala si algoritmul se incheie.

1.8.5.Bazele complementare admisibile aproape adiacente

Fie (y₁,.,y_j-1,z₀,y_j+1,.,y_n) un vector de variabile de baza complementara admisibila apropiata pentru (8.14),unde y_iI pentru fiecare i≠j.In aceasta baza ambele variabile din perechea complementara sunt variabile secundare. Bazele complementare admisibile apropiate adiacente pot fi obtinute doar prin alegerea ,ca variabile de intrare, ori alui w_j,ori a lui z_j .Astfel ,pentru fiecare baza complementara admisibila apropiata sunt exact doua posibilitati pentru obtinerea bazelor complementare admisibile apropiate adiacente.

Initial,in baza complementara admisibila apropiata,atat w_t cat si z_t sunt variabile secundare.In tabelul canonic asociat bazei initiale ,vectorul coloana actual w_t poate fi verificat ca fiind -e_n ,care este <0.Deci baza complementara admisibila apropiata initiala este in final o semidreapta complementara apropiata.

Deci ,este o unica metoda de obtinere a unei baze complementara admisibila apropiata adiacenta:prin alegerea lui z_t ca variabila de intrare.

1.8.6.Regula pivotului complementar

Pentru toate etapele ulterioare este un singur mod de a continua algoritmul si anume:se alege ca variabila de intrare, complementara variabilei care tocmai a iesit din baza.Aceasta se numeste regula pivotului complementar.

Principala proprietate a drumului generat de algoritm este urmatoarea:fiecare solutie de baza admisibila obtinuta in algoritm contine doua margini complementare apropiate.Am ajuns la aceasta solutie urmand o astfel de margine si plecam prin cealalta margine.Astfel, algoritmul continua intr-o maniera unica.

1.8.7.Incheierea

Sunt exact doua moduri de terminare a algoritmului:

1.La o anumita etapa a algoritmului,z₀ poate parasi vectorul de baza si astfel se obtine o baza admisibila complementara.Solutia pentru (8.14) corespunzatoare acestei baze finale este o solutie pentru P.C.L. (5.5),(5.6),(5.7).

2.La o anumita etapa a algoritmului ,coloana pivot poate fi nepozitiva (problema discutata la partea 1.8.2.Operatiile pivot) si in acest caz algoritmul se termina cu o raza(semidreapta).

Aceasta se numeste terminatie raza.Cand acest lucru se intampla,algoritmul nu poate rezolva P.C.L.

Exemple numerice

Exemplu 10:

Se considera urmatoarea P.C.L.:

w_i≥0 , z_i≥ 0 , w_i z_i =0 pentru toti I

Introducem variabila artificiala z₀ si tabelul devine:

Deoarece cel mai mare numar negativ q_i este q₃=-9,atunci pivotul se afla in coloana vectorului z₀ si cea de-a treia linie este linia pivotului.Elementul pivot este incercuit in tabel.Operatiile pivotului conduc la tabelul canonic asociat bazei initiale.Variabilele de baza sunt scrise in ordine in coloana din partea stanga.

La fel ca in sectiunea 1.8.5.Baze complementare admisibile apropiate adiacente,alegem pe z₃ ca variabila de intrare.Vectorul coloana z₃ devine coloana pivot.Raporturile discutate in sectiunea 1.8.2.Operatiile pivot sunt introduse in coloana din dreapta.Cel mai mic raport este pe linia a patra.Astfel linia pivot este a patra linie.Elementul pivot este incercuit.w₄ iese din vectorul de baza si este inlocuit cu z₃.

Deoarece w₄ nu a iesit din vectorul de baza ,complementul sau,z₄ este variabila de intrare pentru urmatorul pas.Coloana lui z₄ este coloana pivot.Elementul pivot este incercuit .w₁ iese din vectorul de baza.

Deoarece w₁ a iesit din baza,complementul sau,z₁ este noua variabila de intrare.Acum w₂ iese din vectorul de baza.

Deoarece w₂ a iesit din vectorul de baza ,complementara sa,z₂ este variabila de intrare.Acum z₀ iese din vectorul de baza.

Deoarece baza actuala este o baza complementara admisibila,algoritmul se termina.Solutia corespunzatoare este:

variabilele secundare w₁,w₂,w₃,w₄=0

vectorul de baza z₄=1,z₁=2,z₂=1,z₃=3

si reprezinta solutia pentru P.C.L.

Exemplu 11:

Se considera urmatoarea P.C.L.:

w_i≥0 , z_i≥ 0 , w_i z_i =0 pentru toti i

Tabelul cu variabila artificiala z₀ este:

Tabelul canonic initial este:

Variabila de intrare este z₃.Coloana pivot este nepozitiva.Deci algoritmul se opreste aici printr-o terminatie raza.Algoritmul nu poate rezolva P.C.L.

1.10. Conditii

S-a aratat ca algoritmul pivot complementar pentru rezolvarea P.C.L. ofera o solutie pentru problema,daca aceasta solutie exista,chiar daca M este o matrice nenegativa cu admiteri diagonal pozitive,sau o P-matrice,sau o matrice pozitiv semidefinita,sau o matrice plus copozitiva,sau daca M apartine altor clase speciale de matrici nediscutate aici.

Programarea liniara si programarea patratica convexa pot fi rezolvate cu acest algoritm folosind forma P.C.L. discutata in sectiunea 1.6.Aplicatii.Algoritmul pivot complementar poate oferi o solutie pentru P.C.L. (5.5),(5.6),(5.7), chiar daca M nu se afla in nici una din aceste clase de matrici,dar in acest caz este posibil ca algoritmul sa se opreasca cu o terminatie raza ,chiar daca exista o solutie pentru P.C.L.

1.11.Alti algoritmi

S-a dezvoltat un nou algoritm special care,atunci cand a fost combinat cu algoritmul pivot complementar din sectiunea 1.8.Algoritmi pentru rezolvarea P.C.L.,a oferit o solutie pentru P.C.L.asociata unui joc bimatricial.Algoritmii bazati pe pivotarea principala sunt disponobili si sunt folositi atunci cand M este pozitiv semidefinita.Algoritmii care folosesc metode sistematice au fost de asemenea dezvoltati.

Singurele metode prin care se dezvolta P.C.L. cand M este o matrice oarecare sunt algoritmii enumerativi.Chiar atunci cand M apartine unei clase speciale de matrici,singurii algoritmi care pot genera multimea tuturor solutiilor unei P.C.L. sunt tot algoritmii enumerativi_tip.

1.12. Rezumat al rezultatelor teoretice

In problema complementaritatii liniare (q,M),daca M este fixata,problema are o solutie unica pentru fiecare qIRⁿ daca M este o P_matrice,i.e.,clasa conurilor complementare C(M) partitioneaza Rⁿ (precum clasa ortantilor), daca M este o P_matrice.Pentru anumite conditii puse lui M s-a aratat ca problema poate avea un numar par de solutii pentru toti qIRⁿ sau un numar impar de solutii pentru toti qIRⁿ.Se cunosc mai multe astfel de rezultate.Proprietatile problemei complementaritatii liniare pentru M, apartinand unei clase speciale de matrici sunt studiate foarte mult.

1.13.Probleme nerezolvabile

Un algoritm pentru o problema este un bun algoritm daca numarul calculelor necesare este limitat superior de un polinom de grad n,ordinul (sau marimea ) problemei.

Se cunosc algoritmi eficienti pentru testarea unei matrici daca este pozitiv definita sau pozitiv semidefinita.Acesti algoritmi se bazeaza pe operatii liniare pentru matrici si sunt trecuti in cartile despre algebra liniara.

Pana acum nu se cunosc algoritmi buni pentru testarea unei matrici patratice oarecare daca este copozitiva ,plus copozitiva,o P_matrice sau o Q_matrice.De asemenea ,pentru o matrice oarecare , nu sunt cunoscute conditii simple necesare si suficiente pentru a fi o Q_matrice.

Obtinand o solutie pentru o P.C.L.,vrem sa aflam daca aceasta solutie este unica sau daca mai exista alte solutii alternative.Daca aceste solutii alternative exista,vrem sa le calculam.Algoritmii enumerativi disponibili in prezent ,care pot raspunde la aceste intrebari si care pot rezolva P.C.L. cand M este o matrice oarecare,nu sunt foarte eficienti cand n este mare.

In plus ,exista un mare numar de probleme teoretice nerezolvate cu privire la proprietatile conurilor complementare si la proprietatile teoretice ale matricei asociate la P.C.L.

1.14.Problema complementaritatii neliniare

Fie f(z)=(f₁(z),.,f_n(z))^T Rⁿ un vector de functii , zRⁿ.Problema ce trebuie rezolvata

z≥0

f(z)≥0

_n

f(z)^Tz=∑z_If_I(z)=0

ⁱ⁼¹

se numeste problema complementaritatii neliniara.Daca f(z)=Mz+q aceasta devine o P.C.L.Numeroase rezultate ale conditiilor necesare si suficiente pentru existenta unei solutii a problemei complementaritatii neliniare se poate transforma intr-o problema de calcul a punctelor fixe Kakutani (vezi sectiunea urmatoare) a unui punct din harta multimilor(vezi urmatoarea sectiune) definite pe Rⁿ .Algoritmi pentru calcularea acestor puncte fixe,folosind idei asemanatoare cu cele discutate in algoritmul pivot complementar pentru rezolvarea P.C.L.,au fost dezvoltati si sunt discutati foarte pe scurt in sectiunea urmatoare.

Metode de calcul a punctelor fixe

Se considera o harta careia i se asociaza o submultime F(x)IRⁿ pentru fiecare punct xIRⁿ.O astfel de harta se numeste harta multimii de puncte.Un punct fix Kakutani din aceasta harta este punctul yIRⁿ care satisface yIf(y).

Recent s-au dezvoltat algoritmi pentru calaculul eficient al acestor puncte fixe.Acesti algoritmi folosesc triangularile din Rⁿ.O triangulare este o partitie a lui Rⁿ in simplexuri.Fiecare simplex din Rⁿ este acoperirea convexa a n+1 puncte numite vertexuri.Fiecare vertex are asociata o eticheta din multimea .Etichetarea se face astfel incat daca se gaseste un simplex,dintre cele care au vertexuri cu etichete distincte,fiecare punct din acel simplex este o aproximare a punctului fix.Problema se reduce la gasirea acelui simplex din triangulare care are vertexuri cu etichete diferite.Deoarece fiecare simplex are exact n+1 vertexuri,multimea etichetelor asociate vertexurilor unui simplex etichetat diferit trebuie sa fie .Astfel de simplexuri se numesc simplexuri etichetate complet.

Algoritmul incepe cu construirea unui simplex special care este etichetat aproape complet,i.e.,vertexurile acestui simplex au etichete diferite intre ele,cu exceptia unei singure perechi de vertexuri care au aceeasi eticheta.Spre exemplu,multimea de etichete asociate vertexurilor din simplexul de inceput poate fi .Etichetele asociate vertexurilor unui simplex etichetat aproape complet satisfac urmatoarele proprietati:

1.O singura eticheta apare exact de doua ori.

2.O singura eticheta din multimea lipseste.

Proprietatile triangularii folosite asigura faptul ca fiecare simplex atichetat aproape complet are cel putin doua simplexuri adiacente care sunt etichetate complet sau aproape complet.Simplexul de inceput are un singur simplex adiacent etichetat aproape complet si algoritmul poate fi folosit.Toate simplexurile obtinute de-a lungul algoritmului vor fi etichetate aproape complet cu exceptia ultimului care va fi etichetat complet.Am ajuns la un simplex pornind de la un simplex adiacent etichetat aproape complet.Simplexul mai are un singur simplex adiacent care este etichetat aproape complet sau este etichetat complet si algoritmul continua.Astfel metoda urmeaza o cale unica si clara care se termina cu un simplex etichetat complet.

Este evidenta asemanarea dintre algoritmul de obtinere a simplexurilor etichetate aproape complet si dintre algoritmul pivot complementar de obtinere a bazelor aproape complementare pentru rezolvarea P.C.L.

S-a aratat ca problemele programarii neliniare (restictionate sau nu) pot fi transformate in probleme de calcul a punctelor fixe.Algoritmii pentru calculul punctelor fixe au o larga aplicabilitate in programarea matematica si aplicatiile ei.

Capitolul 2

Problema complementaritatii

in programarea patratica

2.1.Restrictii ecuatii

Asemeni problemei de programare liniara,o alta problema de optimizare care poate fi rezolvata printr-un numar finit de pasi este problema de programare patratica (P.P.).Pentru aceasta problema functia obiectiv f(x) este patratica si functiile de restrictie c_i(x) sunt liniare.Astfel problema consta in gasirea unei solutii x* pentru:

Inf    (1.1)

Sau in forma canonica:

Inf

Unde q(x)=(1/2)x^TGx+g^Tx , gIRⁿ,G matrice simetrica.

Ca si in programarea liniara,problema poate fi fara solutie admisibila sau poate avea solutie infinita;totusi aceste posibilitati sunt detectate promt in algoritmi,astfel in general se presupune ca solutia x* exista.Daca matricea hessiana G este pozitiv semi-definita atunci x* este solutie globala;in plus , daca G este pozitiv definita atunci x* este unic.Aceste proprietati rezulta din convexitatea (stricta) a lui q(x) si deci (1.1) este o problema de programare convexa.Cand hessiana G este nedefinita ,atunci pot apare solutii locale care nu sunt globale si calcularea unei astfel de solutii nu este importanta (vezi Sectiunea 2.4).Un algoritm eficient pentru P.P. trebuie sa fie destul de complex,astfel se realizeaza mai intai un calcul simplificat al structurii de baza si apoi se amplifica acest calcul.In primul caz se arata in Sectiunea2.1 si 2.2 cum se rezolva problemele cu restrictii ecuatii.Generalizarea acestor idei ,in cazul restrictiilor inecuatii ,se face prin intremediul unor strategii de multimi active si sunt descrise in Sectiunea 2.3.Proprietati mai avansate ale algoritmului P.P.,in care se foloseste matricea hessiana nedefinita si care permite rezolvarea eficienta a unui set de probleme, sunt date in Sectiunea 2.4.Probleme de P.P. cu o structura speciala ,cum ar fi cele care au doar restrictii marginite sau cele care apar din problemele patratelor minime, sunt tratate in Sectiunea 2.5.Pentru rezolvarea unei probleme de P.P. se foloseste ades forma tabelara modificata a metodei simplex din programarea liniara.Aceasta rezolvare este descrisa in Sectiunea 2.6 si a ajuns sa fie exprimata in termeni de problema complementaritatii liniare.Este descrisa echivalenta dintre aceste metode si metodele multimii active,precum si motivele pentru care este preferata ultima deducere.

Programarea patratica difera de programarea liniara prin faptul ca este posibil sa avem anumite probleme (altele decat un sistem de nn ecuatii) in care nu sunt restrictii inecuatii.De aceea aceasta sectiune studiaza cum sa afli o solutie x* a problemei cu restrictii ecuatii

Inf (1.2)

unde q(x)=(1/2)x^TGx+g^Tx

Presupunem ca sunt m≤n restrictii astfel incat bIR^m si A este o matrice nm si contine vectorii coloana a_i ,iIE.Presupunem ca A are rangul m;daca restrictiile sunt cosistente aceasta se poate obtine prin inlaturarea restrictiilor dependente, desi pot fi dificultati numerice in recunoasterea acestei situatii.Aceasta presupunere afecteaza existenta si unicitatea multiplicatorilor Lagrange * si calcularea acestora.

O metoda directa de rezolvare a problemei (1.1) este aceea de a folosi restrictiile pentru a elimina variabilele.Daca matricile

x₁ A₁ g₁ G₁₁ G₁₂

x= A= g= G=

x₂ A₂ g₂ G₂₁ G₂₂

Sunt definite ,unde x₁ IR^m si x₂ I R^n-m atunci ecuatiile (1.1) devin

A^T₁x₁+A^T₂x₂=b si sunt gata rezolvate (prin eliminarea gaussiana) inlocuind x₁ cu x₂; aceasta se scrie convenabil astfel:

x₁=A^-T₁(b-A^T₂x₂) (1.3)

Inlocuind in q(x) problema devine :inf (x₂), x₂ I R^n-m, unde (x₂) este functia patratica:

Ψ(x₂)=(1/2)x^T₂(G₂₂-G₂₁A^-T₁A^T₂-A₂A^-1₁G₁₂+A₂A^-1₁G₁₁A^-T₁A^T₂)x₂

. +x^T₂(G₂₁-A₂A^-1₁G₁₁)A^-T₁b+(1/2)b^TA₁^-1 G₁₁ ^T₁b

+x^T₂(g₂-A₂A^-1₁g₁)+g^T₁A^-T₁b (1.4)

Exista si este unic un x₂^* minim daca hessiana Ψ este pozitiv definita caz in care x₂^* se obtine prin rezolvarea sistemului liniar Ψ (x₂) =0.Apoi x₁* se obtine prin substitutie in (1.3).Vectorul multiplicatorului lagrange λ* este definit prin g*=Aλ*, unde g*= q(x*), si poate fi calculat prin rezolvarea primei divizari g*₁=A₁λ*.Din definitia lui q(x) din (1.2),g*=g+Gx* deci o expresie explicita pentru λ* este:

λ*=A₁^-1(g₁+G₁₁x₁*+G₁₂x₂*) (1.5)

Exemplu de rezolvare a unei probleme prin aceasta metoda:

Inf (1.6)

Pentru eliminarea lui x₃,ecuatiile se scriu sub forma:

x₁+2x₂= 4+x₃

x₁-x₂= -2-x₃

si sunt gata rezolvate prin eliminarea Gaussiana ,obtinand:

x₁=0-(1/3)x₃, x₂=2+(2/3)x₃ (1.7)

x₁

Se verifica usor ca aceasta solutie corespunde cu (1.3) cu X₁=

1 1 x₂

X₂=(x₃), A₁= si A₂=[-1 1].

2 -1

Inlocuind (1.7) in q(x) din (1.6) se obtine

(x₃)=(14/9)x₃²+(8/3)x₃+4 (1.8)

2 0

Care corespunde cu (1.4) cu G₁₁ =

0 2

G₁₂=G^T₂₁=0,G₂₂=[2] si g=0.Matricea hessiana din (1.8) este [28/9] care este pozitiv definita, deci minimul este obtinut prin =0 si x₃*=-6/7. Inlocuind inapoi in (1.6) se obtine x₁*=2/7 si x₂=10/7.Sistemul g*=A * devine :

2 1 1

si rezolvand primele 2 linii avem *₁=8/7 si *₂=-4/7,si aceasta este valabila cu a treia linie.

Eliminarea directa a variabilelor nu este singura metoda de rezolvare a (1.2) si nici cea mai buna.O metoda de eliminare generalizata este posibila in care se face initial o transformare liniara a variabilelor.

Fie Ysi Z matrici de nm, respectiv de n(n-m) astfel incat [Y:Z] este nesingulara si in plus fie A^TY=I si A^TZ=0, Y^T fiind privita ca inversa generalizata la dreapta a matricei A astfel incat o solutie a A^Tx=b sa fie data de x=Yb.Totusi ,aceasta solutie nu este unica in general si alte puncte admisibile sunt date de x=Yb+ , unde este spatiu coloana nul din A.

Acesta este spatiu liniar

(1.9)

care are dimensiunea n-m.Matricea Z are coloane z₁,z₂ ,.,z_n-m liniar independente in acest spatiu nul si de aceea pot fi vectori de baza pentru spatiu nul.Adica ,pentru orice punct admisibil x orice corectie admisibila poate fi scrisa astfel:

_n-m

=Zy= ∑z_iy_i (1.10)

ⁱ⁼¹

unde y_1,y₂,.,y_n-m sunt componente (sau variabile reduse)ale fiecarei directii a coordonatei reduse(vezi Fig. 1).Astfel fiecare punct admisibil x poate fi scris sub forma:

x=Yb+Zy (1.11)

Fig.1:Coordonatele reduse pentru regiunea admisibila

Aceasta poate fi interpretat (Fig.2) ca un pas de la origine la punctul admisibil Yb,urmat de o corectie admisibila Zy pentru a ajunge la punctul x.Astfel (1.11) ofera o metoda de eliminare a restictiilor A^Tx=b in termeni ai vectorului variabilelor reduse y care are n-m elemente,fiind astfel o generalizare a (1.3).Inlocuind in q(x) obtinem functia patratica redusa

(y)=(1/2)y^TZ^TGZ y+(g+GYb)^TZy+(1/2) (g+GYb)^TYb (1.12)

Daca Z^TGZ este pozitiv definita ,atunci exista un punct de minim unic y* care (din (y)=0) rezolva sistemul liniar

(Z^TGZ)y=-Z^T(g+GYb) (1.13)

x* se obtine prin inlocuire in (1.11).Matricea Z^TGZ din (1.12) se numeste matricea hessiana redusa si vectorul Z^T(g+GYb) se numeste vectorul gradient redus.Se observa ca g+Gyb= q(Yb) este vectorul gradient al lui q(x) pentru x=Yb (la fel cum g este q(0)), deci derivatele reduse se obtin print-o operatie matriciala cu Z^T.In plus , inmultind cu Y^T la g*=A * se obtine ecuatia

*=Y^Tg*=Y^T(Gx*+g) (1.14)

care poate fi folosita pentru a calcula multiplicatorii lagrange.Expresiile explicite pentru x* si * in termenii datelor originale sunt:

x*=Yb-Z(Z^TGZ)^-1Z^T(g+Gyb) (1.15)

si

*=Y^T(g+Gx*)

=(Y^T-Y^TGZ(Z^TGZ)^-1Z^T)g

+Y^T(G-GZ(Z^TGZ)^-1Z^TG)Yb (1.16)

Aceste formule nu vor fi folosite direct dar sunt folositoare pentru a arata relatia cu metoda alternativa a multiplicatorilor Lagrange pentru rezolvarea problemelor P.P. cu restrictii ecuatii, considerate in Sectiunea 2.2.

Anumite metode depind de alegera lui Y si alui Z si pentru construirea acestor matrici Y si Z cu proprietatile corecte este descrisa in continuare o procedura generala.Totusi , o alegere particulara este factorizarea matricei A.Aceasta se poate scrie astfel:

R R

A=Q =[Q₁ Q₂ ] =Q₁R (1.17)

0 0

Unde Q este de dimensiune nn si este ortogonala, R este de dimensiune mm si superior triunghiulara si Q₁ si Q₂ sunt de dimensiune nm,respectiv

n(n-m).Alegerile

Y=A^+T=Q₁R^-T, Z=Q₂ (1.18)

se observa ca au proprietatile corecte.In plus vectorul Yb din (1.11) si Fig.2 se observa ca este ortogonal pe multimea restrictiilor si directiile coordonatelor reduse z_i sunt reciproc ortogonale.Solutia x* se obtine ca mai sus prin punere in ecuatie si rezolvand (1.13) pentru y* si apoi inlocuind in (1.11).Yb este calculat din substitutia dinainte in R^Tu=b urmata de Yb=Q₁u.

Fig.2:Eliminarea generalizata intr-un caz special

Multiplicatorii * din (1.14) sunt calculati prin substitutia

R *=Q^T₁g* (1.19)

Planul se datoreaza lui Gill si Murray (1974) si se va face referire la el sub denumirea de metoda factorizarii ortogonale.

Exemplu de aplicare a metodei pentru problema (1.16) .Matricile respective sunt:

5 8 1

Y=(1/14) 4 -2 Z= -2

-1 4 -3

1/√6 4/√21 1/√14 √6 -√6/3

A= 2/√6 -1/√21 -2/√14 0 √21/3

Vectorul Yb=(1/7)(2,10,-6)^T, g=0 si GYb=2Yb,Z^T(g+Gyb)=0.Rezulta ca y*=0 si x*=Yb=(1/7)(2,10,-6)^T . De asemenea g*=g+Gyb=(2/7) (2,10,-6)^T si *=(8/7,-4/7)^T si aceste rezultate sunt egale cu cele obtinute prin eliminarea directa.

Un algoritm general pentru calcularea matricelor Y si Z este urmatoarea: se alege o matrice oarecare V de dimensiune n(n-m) astfel incat [A:V] este nesingulara.Fie matricea inversa exprimata astfel:

Y^T

[A:V]^-1= (1.20)

Z^T

unde Y si Z sunt de dimensiune nm,respectiv n(n-m).Apoi urmeaza Y^TA=I si Z^TA=0 astfel incat aceste matrici sa fie potrivite pentru folosirea lor in metoda eliminarii generalizate.Metoda rezultata poate fi interpretata ca o metoda care foloseste o transformare liniara cu matricea [A:V].Metodele descrise la inceput pot fi cazuri particulare ale acestui algoritm.Daca se alege

0

V= (1.21)

I

atunci egalitatea

A₁ 0 ^-1 A₁^-1 0 Y^T

A₂ I -A₂A₁^-1 I Z^T

ofera expresiile pentru Y si Z.Se verifica usor ca in acest caz metoda se reduce la metoda eliminarii directe.Alternativ, daca se alege

V=Q₂ (1.23)

unde Q₂ este definita de (1.17),atunci se obtine metoda factorizarii ortogonale de mai sus.Egalitatea

R^-1Q₁^T

[A:V]^-1=[Q₁R:Q₂]^-1= (1.24)

Q₂^T

poate fi exprimata sub forma

A⁺

[A:V]^-1= (1.25)

V⁺

unde A⁺=(A^TA)^-1A^T si ,in acest caz,(1.14) poate fi scris astfel:

*=A⁺g* (1.26)

De fapt pentru orice Y si Z,exista un unic V datorita relatiei (1.20).Totusi,daca Z este dat si Y este arbitrar,atunci V poate fi ales mai usor; acest lucru este discutat in Sectiunea 2.6.Generalizarea din (1.20) nu este tocmai cea mai potrivita ; este preferabil sa nu construim pe Y si Z ,ci sa generam indirect aceste matrici prin factorizarea [A:V] ; in particular , forma simpla (1.21) si (1.22) poate fi avantajoasa pentru probleme mai mari.

O alta metoda care poate fi descrisa in aceasta Sectiune este metoda gradientului redus a lui Wolfe(1963).Folosind termenii din metoda multimii active (Sectiunea 2.3),matricea V este formata din vectorii normali ai restrictiilor inactive care anterior au fost active.Asfel , cand o restrictie devine inactiva ,coloana a_i din A este transferata in V asfel incat [A:V]^-1 trebuie sa fie recalculata si numai linia de divizare trebuie repozitionata.Cand o restrictie inactiva devine activa,vectorul de intrare a_i inlocuieste o coloana din V.Alegera coloanei este arbitrara si poate fi facuta astfel incat [A:V] sa fie bine determinata.Acest schimb de coloane este analog cu cel din programarea liniara.

Alte metode pentru P.P pot de asemenea folosi acesti termeni.Murray (1971) ofera o metoda in care matricea Z este construita si pentru care

Z^TGZ=D (1.27)

unde D este matrice diagonala.In aceasta metoda coloanele din Z pot fi

interpretate ca directii conjugate si sunt legate de matricea (Z^) din metoda de factorizare ortogonala prin Z=Z^L^-1.Din aceasta cauza metoda prezinta in primul rand informatii despre matricea inversa dar poate fi nesigura pe motive de stabilitate.Totusi , are avantajul ca solutia pentru (1.13) devine triviala si nu este necesara o retinere a elementelor matricei Z^TGZ.Se poate considera metoda Beale (1959) (vezi Sectiunea 2.6) prin care se pot selecta directiile de cautare cunjugate din liniile matricei [A:V]^-1.In acest caz matricea V se formeaza din diferenta gradientilor ^(j) din iteratiile anterioare.Totusi si aceasta metoda are unele dezavantaje.

Nu este usor sa faci alegera cea mai buna dintre aceste metode,deoarece aceasta depinde de tipul problemei si de faptul ca metoda poate fi considerata o parte a metodei multimii active pentru restrictii inecuatii (Sectiunea 2.3).In plus, in Sectiunea 2.2 sunt descrise alte metode importante.Totusi,metoda factorizarii ortogonale este avantajoasa deoarece calcularea lui Z implica operatii cu matrici ortogonale elementare care sunt foarte stabile numeric.De asemenea ,aceasta alegere (Z=Q₂) ofera cea mai buna posibila marginire

k(Z^TGZ)≤k(G) (1.28)

a numarului conditie k(Z^TGZ).Nu se poate spune ca ofera cel mai bun k(Z^TGZ), asa cum sustineau in mod eronat Gill si Murray (1974).Intr-adevar o modificare triviala a metodei Murrey(1971) cu D=I permite sa fie calculata matricea Z pentru care k(Z^TGZ)=1.De fapt semnificatia acestui numar conditie este nesigura deoarece poate fi schimbat prin scalarea liniilor si coloanelor simetrice din Z^TGZ ,fara modificarea propagarii erorii.Relatia (1.28) indica faptul ca k(Z^TGZ) nu poate fi arbitrar mare.Totusi aceasta concluzie poate fi obtinuta si cu alte metode care folosesc pivotarea.Pe de alta parte , o alegere arbitrara a lui V care face coloanele lui Z aproape dependente,poate induce cresteri neplacute a erorilor de rotunjire.

2.2.Metoda multiplicatorilor Lagrange

O cale alternativa de obtinere a solutiei x* pentru problema (1.2) si a multiplicatorilor * asociati este prin metoda multiplicatorilor Lagrange.Functia lagrangeian devine:

L(x, )=(1/2)x^TGx + g^Tx - ^T(A^Tx - b) (2.1)

si conditiile pentru punct stationar devin:

_x L=0: Gx + g - A

_x L=0: A^Tx - b =0

care pot fi rearanjate sub forma de sistem liniar

G -A x g

= - (2.2)

-A^T 0 b

Matricea coeficient este denumita matricea lagrangeian si este simetrica,dar nu este pozitiv definita.Daca inversa exista si se scrie sub forma

G -A ^-1 H -T

-A^T 0 -T^T U

atunci solutia pentru (2.2) este

x*= -Hg+Tb (2.4)

*=T^Tg-Ub    (2.5)

Aceste relatii sunt folosite de Fletcher(1971) pentru rezolvarea problemei cu restrictii ecuatii (3.1) care provin din metoda multimii active.Deoarece b=0 in acest caz doar matricile H si T trebuie retinute.Expresiile explicite pentru H,T si U ,cand G^-1 exista, sunt :

H=G^-1-G^-1A(A^TG^-1A)^-1A^TG^-1

T= G^-1A(A^TG^-1A)^-1 (2.6)

U= -(A^TG^-1A)^-1

si sunt gata verificate prin inmultiri ale matricei lagrangeian si a inversei sale.Murtagh si Sargent (1969) sugereaza metode pentru restrictii liniare care folosesc aceasta reprezentare prin retinerea matricelor (A^TG^-1A)^-1 si

G^-1.Totusi nu este necesar pentru ca G^-1 sa existe si pentru ca matricea lagrangeian sa fie nesingulara.Nici una dintre aceste de mai inainte nu este recomandata in practica deoarece pot fi potentiale probleme de stabilitate.De fapt, daca Y si Z sunt definite de (1.20), atunci o expresie alternativa pentru inversa matricei lagrangeian este:

H=Z(Z^TGZ)^-1Z^T

T=Y- Z(Z^TGZ)^-1Z^TGY (2.7)

U=Y^TGZ(Z^TGZ)^-1Z^TGY-Y^TGY

Acestea pot fi verificate folosind relatiile obtinute din (1.20).Astfel se considera ca pentru calcularea lui Y si Z in orice metoda de eliminare este esentiala o cale subtila de factorizare a matricei lagrangeian din metoda Lagrange.Ecuatiile (2.7) demonstreaza ca matricea lagrangeian este nesingulara daca si numai daca exista Z astfel incat matricea Z^TGZ

este nesingulara.In plus, x* este minim local unic daca si numai daca Z^TGZ este pozitiv definita datorita conditiilor de ordin 2 aplicate functiei patratice (1.12).

Aceste reprezentari diferite ale inversei matricei lagrangeian se folosesc in doua tipuri diferite de metode care au fost propuse pentru rezolvarea problemelor (2.4) si (2.5).In general este metoda spatiului nul in care Y , Z si Z^TGZ = LL^T se presupune ca exista.Metoda spatiului nul este asociata cu reprezentarea (2,7) care este folosita pentru a modul de rezolvare a (2.4) si (2.5).Expresiile intermediare sunt simplificate acolo unde este posibil si operatiile de inversare cu matrici triunghiulare sunt indeplinite de substitutii.De fapt, aceasta ofera metoda eliminarii generalizata din Sectiunea 1.1.Exista numeroase metode diferite de spatii nule legate de diferite moduri de alegere a lui Y si Z si sunt discutate in Sectiunea 1.1.O abordare alternativa este metoda spatiului imagine care necesita ca matricea hessiana sa fie pozitiv definita si foloseste factorii Choleski G=LL^T.Metoda spatiului imagine este asociata cu reprezentarea (2.6).Folosind factorii Choleski putem sa rearanjam relatia (2.6) si se observa ca produsul L^-1A apare frecvent.Recent, metodele spatiului imagine se bazeaza pe folosirea L^-1A astfel incat:

R

L^-1A=[Q₁:Q₂] =Q₁R

0

si matricile din (2.6) au forma determinata

H=L^-T(I-Q₁Q₁^T)L^-1

T=L^-TQ₁R^-T

U= -R^-1R^-T

Gill (1984) ofera o astfel de metoda in care Q₁(dar nu Q₂) si R sunt explicit actualizate.Goldfarb si Idnani (1983) au o metoda inrudita in care introduc matricea S=L^-TQ si in care retin si actualizeaza pe S si R .Evident formulele de mai sus permit inlocuirea lui L^-TQ₁ cu S₁: se poate ca metoda sa fie imbunatatita doar prin retinera si actualizarea lui S₁ si a lui R.Algoritmul se poate numi metoda retinerii minime deoarece actualizeaza doar matricea R, inlocuind Q cu produsul L^-1AR^-1 in formulele de mai sus.Trnsformarea ridica la patrat numarul conditie al problemei si acest lucru nu se doreste.Metoda spatiului imagine este des folosita cand factorul Choleski al matricei G este dat apriori si nu trebuie sa fie calculat.Operatiile folosite pentru aceste metode sunt favorabile cand sunt doar cateva restrictii pentru problema.

Urmeaza operatii cu privire la structura inversei din (2.3).In primul rand T^TA=I astfel incat T^T este inversa la stanga generalizata a matricei

A.Daca Z^TGZ este pozitiv definita ,atunci H este pozitiv semi-definita cu rangul n-m.Se verifica ca HA=0 astfel ca proiecteaza orice vector v in multimea restrictiilor (din A^THv=0).Daca x^(k) este este un punct oarecare admisibil atunci A^Tx^(k)=b si g^(k)=g+Gx^(k) este vectorul gradient al lui q(x) in x^(k).Folosind apoi (2.6) putem rearanja (2.4) si (2.5) astfel incat

x*=x^(k) - Hg^(k) (2.8)

*=T^Tg^(k) (2.9)

Ecuatia (2.8) are o relatie apropiata cu metoda Newton si arata ca H contine curbura corecta pentru regiunea admisibila si poate fi privita ca o matrice hessiana inversa redusa.De aceea aceste formule pot defini o metoda de proiectie relativa la matricea G (pozitv definita); daca G este inlocuita cu I atunci H=AA⁺=P care este o matrice de proiectie ortogonala.De fapt se poate stabili ca H=(PGP)⁺, inversa generalizata a matricei hessiane de proiectie.

Se pot folosi metode (atribuite initial lui Bunch si Parlett (1971)) pentru factorizarea unei matrici generale simetrice nesingulare.Aceasta include si calcularea factorilor LDL^T ai matricei lagrangeian, unde D este matrice diagonala.De aceea,aceasta ofera un mijloc stabil de rezolvare a (2.2), in special pentru probleme in care G este nedefinita.Totusi, metoda ignora matricea nula care exista in (2.2) si astfel nu profita destul de structura.De asemenea , deoarece este inclusa pivotarea,factorii nu sunt foarte potriviti pentru a fi actualizati in metoda multimii active.Pe de alta parte,matricea lagrangeian este nesingulara daca si numai daca A are rangul intreg,deci metodele de eliminare generalizata, care formeaza matricele Y si Z in mod rezonabil atunci cand A are rangul intreg , nu pot fi instabile datorita factorizarii matricei lagrangeian atat timp cat Z^TGZ este pozitiv definita.Astfel ,metodele stabile de eliminare generalizata sunt cele preferate.

Un alt mijloc de rezolvare a sistemului Lagrange (2.2) este acela de a factoriza dinainte matricea lagrangeian.Mai intai se calculeaza factorii LDL^T ai matricei G care este stabila atat timp cat G este pozitiv definita.Apoi acesti factori sunt folositi pentru a elimina divizarile diagonale (-A si -A^T) in matricea lagrangeian.Divizarea 0 se schimba in -A^TG^-1A care este negativ definita si astfel poate fi factorizata ca -^L^D^L^T cu ^D>0.De aceea factorii rezultati L D L^T ai matricei lagrangeian sunt dati de

L D

L= D= (2.10)

B^T ^L -D^

unde B este definita de LDB= -A si este deja calculata de substitutia dinainte.Pentru a evita pierderea preciziei in formarea A^TG^-1A,^L si ^D sunt calculate cel mai bine prin formarea matricei D^-1/2L^-1 si factorizarea ei in Q^D^1/2 .Metoda este foarte avantajoasa in cazul in care G are o anumita structura care poate fi exploatata si cand numarul de restrictii m este mic .Nu este absolut sigur ca metoda este stabila cu privire la erorile de rotunjire, in special cand G este aproape singulara , dar metoda este folosita cu succes.Cerinta ca G sa fie pozitiv definita este importanta,totusi,o alta calculare a factorilor LDL^T poate sa nu fie posibila sau poate fi instabila.Metoda este echivalenta cu metoda spatiului imagine descrisa mai sus.

2.3.Metoda multimii active

Majoritatea problemelor de P.P. include restrictii inegalitati si astfel pot fi exprimate sub forma data de relatia (1.1).Aceasta sectiune descrie modul in care metodele pentru rezolvarea problemelor cu restrictii ecuatii pot fi generalizate sa rezolve probleme cu inegalitati cu ajutorul metodei multimii active .Cea mai folosita este metoda multimii active primale si cea mai mare parte a sectiunii este dedicata acesteia.Este descrisa in cazul in care matricea hessiana G este pozitiv definita ceea ce asigura ca solutia sa fie punct de minim global unic si astfel unele potentiale dificultati sa fie evitate.

Pe parcursul acestei sectiuni este posibil sa consideram metoda multimii active duale ,desi aceasta se aplica doar in cazul in care G este pozitiv definita.

In metoda multimii active primale anumite restrictii ,indexate de multimea activa A , sunt privite ca egalitati pe cand celelalte sunt temporar neluate in seama si metoda aranjeaza aceasta multime pentru a identifica corect restrictiile active ale solutiei preoblemei (1.1).Deoarece functia obiectiva este patratica este posibil sa fie m (0≤m≤n) restrictii active,spre deosebire de programarea liniara unde m=n.La iteratia k se cunoaste punctul admisibil x^(k) care satisface restrictiile active ca egalitati,adica a_i^Tx^(k)=b_i,iIA.Pentru a_i^Tx^(k)>b_i,i A.Fiecare iteratie incearca sa localizeze solutia problemei egalitatii (P.E.) in care apar doar restrictii active.Cel mai convenabil este sa schimbam originea in x^(k) si sa cautam o corectie δ^(k) care rezolva

inf (1/2)δ^TGδ+δ^Tg^(k)

^δ (3.1)

pentru a_i^Tδ=0 , iIA

unde g^(k) este definita prin g^(k)=g+Gx^(k) si este q(x^(k)) pentru functia q(x) definita in (1.1).Aceasta reprezinta de fapt problema scrisa sub forma (1.2),deci poate fi rezolvata prin orice metoda descrisa in Sectiunea 2.1 si Sesctiunea 2.2.Daca δ^(k) este admisibila cu privire la restrictiile ce nu se afla in A , atunci urmatoarele iteratii sunt x^(k+1)=x^(k)+δ^(k) .Daca nu , atunci o linie de cautare este facuta in directia lui δ^(k) pentru a gasi cele mai bune puncte admisibile.Acest lucru poate fi exprimat prin definirea solutiei problemei (3.1) si cautarea directiei s^(k) si alegerea pasului α^(k) pentru a rezolva

b_i- a_i^Tx^(k)

^(k) =min 1, min ----- (3.2)

^{I:i IA} a_i^Ts^(k)

a_i^Ts^(k)<0

astfel incat x^(k+1)=x^(k)+ ^(k)s^(k).Daca ^(k)<1 in (3.2) atunci o noua restrictie devine activa , definita de indicele ( sa spunem p) care atinge minimul din (3.2) si acest indice este adaugat la multimea activa A.

Daca x^(k) (adica =0) rezolva P.E. curenta atunci este posibila calcularea multiplicatorilor ( sa spunem ^(k)) pentru restrictiile active asa cum este descris in Sectiunea 2.1 si 2.2.Vectorii x^(k) si ^(k) satisfac apoi toate conditiile de ordin intai pentru probleme cu restrictii inecuatii,exceptand conditiile dual admisibile ,adica _i≥0 ,iI I.Astfel se testeaza daca _i^(k) iIA^(k)∩I; daca da , atunci conditiile de ordin intai sunt suficiente pentru a asigura solutia globala de vreme ce q(x) este convexa.Astfel, exista un indice ,q,qIA^(k)∩I astfel incat _q^(k)<0.In acest caz , putem reduce q(x) prin devenirea lui q restrictie inactiva.Astfel q este eliminat din A si algoritmul continua ca mai inainte cu rezolvarea P.E. rezultata (3.1).Daca exista mai multi indici pentru care _q^(k)<0 atunci se alege q rezolvand

min _i^(k) (3.3)

^{i IA∩I}

Aceasta alegere este destul de buna si convenabila si este folosita foarte des.

Pentru a rezuma algoritmul , daca x⁽¹⁾ este un punct admisibil dat si A=A⁽¹⁾ este multimea activa corespunzatoare, atunci metoda multimii active primale este definita astfel:

(a) Pentru k=1 : se da x⁽¹⁾ si A.

(b) Daca =0 nu rezolva (3.1) se trece la pasul (d).

(c) Se calculeaza multiplicatorii Lagrange ^(k) si se rezolva (3.3);

daca _q^(k)≥0 algoritmul se termina cu solutia x*=x^(k),altfel se

elimina q din A.

(d) Se rezolva (3.1) pentru s^(k). (3.4)

(e) Se gaseste ^(k) pentru rezolvarea (3.2) si x^(k+1)=x^(k)+ ^(k)s^(k).

(f) Daca ^(k) <1, se adauga p la A.

(g) k=k+1 si se trece la pasul (b).

In Fig.3.1 este ilustrata metoda pentru o problema de P.P. simpla .Pentru aceasta problema de P.P. restrictiile sunt marginile x≥0 si restrictia generala a^Tx≥b.

Fig 3:Metoda multimii active primale pentru o problema patratica simpla

La x⁽¹⁾ marginile x₁≥0 si x₂≥0 sunt active si astfel x⁽¹⁾ ( =0) rezolva P.E. curenta (3.2) .Calcularea arata ca restrictiile x₂≥0 au multiplicator negativ si astfel devin inactive si doar x₁≥0 este activa.P.E. corespunzatoare este acum rezolvata de x⁽²⁾ (sau = x⁽²⁾-x⁽¹⁾) care este admisibil si astfel devine urmatoarea iteratie.Calcularea lui indica faptul ca restrictia x₁≥0 are multiplicatorul negativ si devine astfel inactiva, lasand multimea A vida.P.E. corespunzatoare este acum rezolvata de x′ care este admisibil si directia de cautare s⁽²⁾= x′- x⁽²⁾ este calculata din (3.1) si o cautare liniara

de-a lungul lui s⁽²⁾ prin rezolvarea (3.2) il da pe x⁽³⁾ ca cel mai bun punct admisibil.Restrictia generala a^Tx≥b devine activa pentru x⁽³⁾ si astfel este adaugat in A.Deoarece x⁽³⁾ nu rezolva P.E. curenta , multiplicatorii nu sunt calculati, dar in schimb este rezolvata P.E. si x⁽⁴⁾ este urmatoarea iteratie.Calcularea multiplicatorilor lui x⁽⁴⁾ indica faptul ca x⁽⁴⁾ este solutia problemei de P.P. cu inegalitati si algoritmul se termina.

In general,algoritmul se poate termina la fiecare pas ^(k)≠0 , caz in care q(x) se reduce la fiecare iteratie.Este o consecinta a (3.2) faptul ca vectorii a_i,iIA , sunt independenti ;deci P.E. in (3.1) este tot timpul bine definita.Demonstrarea terminarii se bazeaza pe faptul ca este un sir de iteratii care rezolva P.E. curenta .(Doar cand ^(k)<1 in (3.2) , x^(k+1) nu este solutie pentru P.E.In acest caz un indice p este adaugat la A .Aceasta se poate intampla de cel mult n ori, caz in care x^(k) este vertex si astfel rezolva P.E. corespunzatoare).Deoarece numarul de P.E. este finit si deoarece fiecare x^(k) din sir este solutia globala unica pentru o P.E. si pentru ca q(x^(k)) este monoton descrescatoare , inseamna ca algoritmul trebuie sa se incheie.Aceasta demonstratie este gresita atunci cand se iau pasi de marime zero si q(x^(k)) nu este descrescatoare; in acest caz algoritmul poate fi ciclic prin intoarcerea la o multime activa anterioara din sir.Aceasta este cauza de degenerare in multimea restrictiilor.Pentru valoarea ^(k)=1(pentru care s^(k) rezolva (3.1)) restrictiile inactive devin active.Teoretic, este posibil ca ciclarea sa fie evitata,dar in practica sunt unele dificultati si majoritatea algoritmilor ignora faptul ca poate apare degenerarea.

Metoda multimii active primala necesita un punct admisibil initial x⁽¹⁾; acesta poate fi aflat ; se calculeaza un vertex admisibil(poate include unele pseudo-restrictii) care devine punctul admisibil x⁽¹⁾ cerut.Elementele matricii A pentru multimea activa pot fi folosite in algoritmul principal.O posibilitate alternativa care evita folosirea punctului admisibil este aceea de a influenta faza 1 a functiei cost prin adaugarea unui multiplu vq(x) a functiei patratice .Pentru un v suficient de mic, problema poate fi rezolvata

intr-o singura faza.Aceasta duce la studiul unor metode asemanatoare P.P. pentru problema

min (x) =q(x)+║l(x)^-║₁ (3.5)

(pentru restrictii inecuatii l(x)≥0),unde l(x)=A^Tx-b si a‾=max(-a,0).Este posibila aici utilizarea unei metode ale multimii active care difera de (3.4) in mai multe privinte.Una ar fi aceea ca, cautarea liniara (3.2) este shimbata la cautarea unui minim pentru (3.5).O alta diferenta este aceea ca pentru conditiile de ordin intai pentru (3.5) multiplicatorii care exista satisfac 0≤ _i≤1.Astfel testul (3.3) este schimbat astfel incat sa aleaga _q ca multiplicator care incalca cel mai mult aceste conditii.De asemenea, restrictiile inactive au multiplicatorii corespunzatori ori 0 ori 1 dupa cum l_i(x)>0 sau <0.P.E. care este rezolvata este:

min q(x) - ∑ _il_i(x)

^{x i A} (3.6)

pentru l_i(x)=0, i IA

si tehnicile din Sectiunea 2.1 si 2.2 sunt din nou relevante,impreuna cu metodele de actualizare potrivite.

In Sectiunea 2.6 sunt descrise relatiile dintre metoda multimii active (3.4) si unele metode derivate ca extensii ale programarii liniare.Variantele posibile ale (3.4) care au fost sugerate includ inlaturarea mai multor restrictii ( cu _i^(k)<0) din A la pasul (c ) sau modificarea pasului (b) astfel incat sa fie acceptata o solutie aproximativa a P.E.Ambele posibilitati induc multimi active mai mici.Goldfarb (1972) dovedeste ca astfel este avantajos.Modificarea , in care se inlatura mai mult de o restrictie , creeaza unele dificultati pentru P.P. nedefinita asociata cu cerinta de a mentine stabili factorii matricei de curbura Z^TGZ.

O metoda mai recenta pentru P.P. convexa este sugerata de Goldfarb si Idnani (1983) si poate fi interpretata ca metoda multimii active duale .Prin aceasta metoda este calculata o secventa de vectori x, care satisface conditiile Kuhn-Tucker ,cu exceptia admisibilitatii primale.Initial x= -G^-1g este minimul fara restrictii a functiei patratice,A= si =0 este un vertex in spatiul dual.O iteratie majora a metodei consta in urmatorii pasi:

(i)        Se alege q astfel incat restrictia q este neadmisibila in (1.1) si se adauga q la A.

(ii)     Daca a_q I atunci se elimina din A indicele restrictiei inegalitatii care va deveni pozitiva la pasul (iii).

(iii) Mergi la solutia P.E.

(iii)           Daca orice _i↓0, iIA∩I atunci se inlatura I din A si se va merg la (iii).

Iteratia majora este completa cand solutia P.E. este gasita la pasul (iii).Iteratiile majore se continua pana cand se recunoaste admisibilitatea majora la pasul (i) (x este solutia optima) sau pana cand nici un indice potrivit din A ce trebuie eliminat,nu este gasit la pasul (ii) (P.P.este neadmisibila).O problema de P.P. nemarginita nu poate sa apara deoarece G este pozitiv definita.Daca problema de P.P., care este duala problemei (1.1) este setata (organizata), atunci metoda lui Goldfarb si Idnani este echivalenta cu metoda multimii active primale,fiind aplicata acestei probleme duale si este instructiv sa comparam proprietatile acestor metode ale multimii active primale si duale .Desi metoda lui Goldfarb si Idnani cauta si inlatura irealizarile primale,nu este necesar cazul in care o restrictie primala ramane realizabila odata ce devine realizabila.Proprietatea de terminare a metodei este asigurata de faptul ca fiecare iteratie mareste atat functia obiectiv primala, cat si functia obiectiv duala.Admisibilitatea dualei este mentinuta.

Avantajul metodei este acela ca se poate deja folosi de disponibilitatea factorilor Cholescki ai matricei G.Metoda este mai eficienta cand sunt doar cateva restrictii active ca solutie si ai avantajului unei bune estimari a lui A.Nu este posibila degenerarea restrictiilor _i≥0,iII.Singura dificultate cauzata de degenerare in restrictiile primale apare aproape de solutie.Proprietatile nefavorabile ale metodei includ si lipsa de generalizare, in faptul ca matricea G trebuie sa fie pozitiv definita.La fel si in cazul in care vor apare dificultati atunci cand G este rau conditionata de exemplu ,pot apare elemente si erori de rotunjire mari in vectorul x=-G^-1g.Totusi, Powell(1985) sustine ca aceste dificultati pot fi depasite.Metoda este mai mult asociata cu folosirea metodei spatiului imagine pentru rezolvarea P.E..Este posibil sa fie dezvoltate alte metode numite metode dual-primale

pentru P.P. convexa care permit ambele irealizari primale si duale si care au pasi similari cu cei din metodele de mai sus.Transformarea unei probleme de P.P. intr-o problema de complementaritate liniara, cum este descrisa in Sectiunea 2.6, poate fi privita ca o marire a numarului de metode dual-primale.

O proprietate importanta a oricarei metode de multimi active priveste eficienta solutiei P.E. (3.1) atunci cand sunt efectuate schimbari asupra multimii A .Ca si in programarea liniara este posibil sa evitam refactorizarea matricei Lagrange la fiecare iteratie si in schimb sa actualizam factorii oricand se face o schimbare in A.

2.4.Proprietati avansate

Un algoritm modern pentru P.P. ar trebui stabilit pentru o aplicatie mai larga decat cele considerate pana acum; ar trebui sa rezolve problema de P.P. nedefinita si ar trebui sa nu permita utilizatorului sa poarte dinainte informatia eficienta de la o calculare anterioara a P.P., atunci cand o secventa de probleme trebuie rezolvata.Aceste extinderi sunt luate in considerare in aceasta sectiune.P.P. nedefinita se refera la cazul in care nu se cere ca hessiana G sa fie pozitiv definita, deci adesea va fi nedefinita, desi sunt incluse si cazurile negativ si pozitiv semi-definita.Pentru P.P. cu restrictii ecuatii nu apar dificultati si exista o solutie unica globala daca si numai daca matricea hessiana redusa Z^TGZ este pozitiv definita.Totusi, cand sunt prezente inegalitati si se exclude cazul pozitiv semi-definit, este posibil sa existe solutii locale care nu sunt globale.Problema de optimizare globala este foarte dificila astfel ca algoritmii sunt folositi pentru gasirea unei solutii locale.De fapt, o modificare a metodei multimii active este folosita doar daca garanteaza gasirea unui punct Kuhn-Tucker pentru care hessiana redusa Z^TGZ este pozitiv definita.Daca _i*>0, i II*, atunci aceste conditii sunt suficiente pentro o solutie locala.Totusi , daca exista _i*=0, iI I*, atunci este posibil ca metoda sa gaseasca un punct Kuhn-Tucker care nu este o solutie locala.In acest caz, de obicei exista mici perturbari arbitrare ale preoblemei (a) care fac punctul Kuhn-Tucker o solutie locala sau (b) care fac punctul sa nu mai fie un punct Kuhn-Tucker astfel ca metoda multimii active sa continuie sa gaseasca o solutie locala mai buna.Totusi, desi este teoretic posibil ca aceste situatii sa apara , in practica este imposibil si ,de obicei, algoritmul gaseste o solutie locala (adesea globala).

Dificultatea principala din rezolvarea problemei nedefinite de P.P. apare in mod diferit.Posibilitatea exista pentru o alegere arbitrara a lui A astfel ca matricea hessiana redusa care rezulta Z^TGZ poate fi nedefinita astfel incat factorii sai LDL^T pot sa nu existe sau pot fi instabili cu privire la propagarea de rotunjire.(De sigur , daca G este pozitiv definita , atunci nu apar probleme pentru Z^TGZ).Intr-o oarecare masura, metoda spatiului nul evita aceasta dificultate.Initial x⁽¹⁾ este un vertex astfel ca spatiul nul (1.9) are dimensiunea zero si dificultatea nu apare.De asemenea daca Z^TGZ este pozitiv definita pentru multimea A data si o restrictie este adaugata la A,atunci noul spatiu nul este o submultime a celei dinainte, astfel ca noua matrice Z^TGZ are cu o dimensiune mai putin si este si pozitiv definita.

Deci dificultatea apare la pasul (c) din (3.4).In acest caz x^(k) rezolva P.E. actuale si Z^TGZ este pozitiv definita.Totusi, cand un indice de restrictie q este inlaturat din A , dimensiunea spatiului nul creste si se adauga in plus la Z o coloana.Aceasta cauzeaza in plus o linie si o coloana ce trebuie adaugate la Z^TGZ si este posibil ca matricea ce rezulta sa nu fie pozitiv definita.Calcularea noilor factori LDL^T este doar pasul obisnuit pentru extinderea factorizarii Choleski, dar cand Z^TGZ nu este pozitiv definita noul element din D este ori negativ ori zero.Aceasta impica faptul ca , corectia ^(k) care este un punct stationar al (3.1) nu mai este minima, astfel ca trebuie aleasa directia de cautare s^(k) la pasul (d) pentru (3.4).Deoarece x^(k) nu este

punct Kuhn-Tucker , directiile de cautare admisibile exista si orice astfel de directie poate fi aleasa pentru s^(k) .O posibilitate este sa se considere linia cauzata de cresterea slabirii restrictiei q la x^(k) .Asfel b_q este schimbat in b_q+ si din (2.4) directia de cautare ce rezulta este s^(k)=Te_q , coloana din T corespunzatoare restrictiei q.De fapt atunci cand D are un element negativ aceasta este echivalenta cu alegerea s^(k)= - ^(k) unde ^(k) este punctul stationar din (3.1) pentru problema actualizata.In acest caz , unitatea pasului ^(k)=1 in (3.2) nu mai are semnificatie.Astfel , modificarea ceruta in (3.4) cand D are un element negativ este sa alegem s^(k)= - ^(k) la pasul (d) si sa rezolvam (3.2) pentru a obtine ^(k) la pasul (e).Daca D are un element zero poate fi inlocuit de - ,unde >0 este neglijabil.Aceasta cauzeaza ca s^(k) sa fie foarte mare , dar dimensiunea lui s^(k) nu are importanta pentru rezolvarea (3.2).Este posibil ca (3.2) sa nu aiba solutie;acesta este modul in care o solutie nemarginita a P.P. nedefinita este indicata.Se poate vedea ,prin calcul ,ca nu exista nici o dificultate reala,daca se fac schimbarile de mai sus.Situatia in care D are un singur element negativ este doar temporara ,de vreme ce algoritmul continua prin adaugarea restrictiilor,reducand dimensiunea spatiului nul, pana cand solutia unei P.E. este gasita, caz in care matricile Z^TGZ si D sunt pozitiv definite.Singura posibilitate nefavorabila este aceea ca nu este marginit elementul negativ din D.Astfel, cand acest element este calculat , eroarea de rotunjire care rezulta poate fi semnificativa.De aceea Gill si Murray (1978) sugereaza ca aceasta posibilitate este monitorizata si daca se observa un element negativ mare ,atunci factorii sunt recalculati in alta etapa.

O posibilitate alternativa care evita aceasta problema de rotunjire este urmatoarea: cand se determina o restrictie q ca la pasul (c ), atunci poate fi lasata in A ca o pseudo-restrictie.Vectorului din dreapta b_q I se permite sa creasca la b_q+α si urmeaza directia de cautare s^(k)=Te_q descrisa mai sus.Daca o noua restrictie p devine activa in linia de cautare, atunci p este adaugat la A si procesul continua.Doar cand solutia unei P.E. se gaseste intr-o secventa a liniei de cautare, atunci indicele q este inlaturat din A.Aceasta abordare are avantajul ca toate matricile hessiene reduse Z^TGZ care sunt calculate sunt pozitiv definite.Dezavantajul este ca apar situatii degenerate aditionale cand vectorul de intrare a_pde la pasul (f) din (3.4) este dependent de vectorii a_i,i A q.Aceasta apare cel mai evident cand se face schimbarea de la un vertex la altul, ca in programarea liniara.Un posibil remediu este sa avem formule pentru a actualiza factorii matricei Lagrange cand se face un schimb de indici ai restrictiilor din A (ca in metoda simplex din programarea liniara).O idee de acest fel este folosita de Fletcher (1971) si ar trebui practicata cu metode mai stabile ,dar inca nu a fost investigata.

O alta trasatura importanta a algoritmului P.P. este aceea ca ar trebui sa permita informatiei sa fie trecuta dinainte de la o calculare anterioara a P.P. atunci cand problema a fost perturbata doar de o mica cantitate .Aceasta este un exemplu de programare parametrica.In acest caz ,poate fi avatajos sa se rezolve o P.E. initiala cu multimea activa A dintr-o calculare anteriora a P.P.Punctul ce rezulta x⁽¹⁾va rezolva noua problema de P.P.Daca A este neschimbata atunci Z trebuie recalculata in majoritatea metodelor si daca si G este neschimbata, atunci Z^TGZ nu se schimba ,astfel ca factorii sai trebuie recalculati.Sunt totusi unele potentiale dificultati.Daca A se schimba , atunci ar putea sa-si piarda rangul si astfel pot apare dificultati de rotunjire.In problemele de P.P. nedefinite , daca se schimba A sau G atunci s-ar putea ca

Z^TGZ sa nu mai fie pozitiv definita.Totusi, sunt solutii posibile pentru aceste dificultati, fara sa abandonam incercarea de a folosi o multime activa anterioara.O alta posibilitate este aceea ca solutia intiala x ⁽¹⁾ a P.E. este neadmisibila in raport cu anumite restrictii i A .In acest caz este preferabil sa nu incercam sa gasim un vertex admisibil.O idee mai buna este sa inlocuim vectorii din dreapta b_i ai restrictiilor incalcate cu b_i +θ si sa gasim solutia problemei de P.P. cu θ↓0 .O abordare alternativa se bazeaza pe folosirea unei functii de penalitate exacta cum este descrisa in (3.5).

Un alt aspect al programarii parametrice este in gasirea sensibilitatii solutiei asociata schimbarilor lui g si b.Rata rezultata prin schimbarea lui x* si λ* se obtine prin inlocuire in (2.4) si (2.5) si efectul asupra lui q(x*) prin folosirea definitiei lui q(x) din (1.1).Se observa ca dq/db_i este apropiat de λ_i*.Aceste estimari pot fi invalide daca exista multiplicatori pentru care

_i*=0,i II*.

2.5.Probleme speciale de programare patratica

In unele cazuri problemele de P.P. au o structura speciala care este utilizata cu scopul de a obtine o mai buna eficienta sau stabilitate.Anumite posibilitati sunt descrise in aceasta sectiune.Un caz important apare atunci cand singurele restrictii din problema sunt marginile

l_i≤x_i≤u_i , i=1,2,.,n (5.1)

unde orice u_i sau -l_i poate fi ∞ si l_i≤u_i.Astfel vectorii a_i sunt e_i si este posibil ca P.E. sa fie exprimata (dupa ce se permuta variabilele astfel incat marginile active sa fie primele m variabile) sub forma:

I ^m 0 ^m

A=Y= Z=V= (5.2)

0 ^n-m I ^n-m

si Z^TGZ=G₂₂ (vezi definitia dinainte (1.3)).Astfel nu este nevoie ca Z sa fie calculata si acest lucru poate fi folosit in metode speciale cu un anumit scop.Singura actualizare necesara este pentru factorii LDL^T ai matricei Z^TGZ.De asemenea , din (1.14) multiplicatorii ^(k) la solutia unei P.E. sunt chiar elementele corespunzatoare lui g^(k) in raport cu Y de mai sus.O alta proprietate a acestei probleme este ca nu poate apare degenerarea in restrictii.De asemenea nu sunt dificultati pentru P.P. nedefinita in folosirea metodei a doua (bazata pe pseudo-restrictii) descrisa in Sectiunea 2.4.Singura formula de schimbare care se foloseste este aceea pentru inlocuirea unei margini inferioare pentru x_i cu marginea superioara si vice versa ,ceea ce este trivial. Pseudo-restrictiile sunt importante pentru calcularea unui vertex initial pentru problema, in special daca u_i si -l_i sunt mari.Metode pentru aceasta problema sunt date de Fletcher si Jackson (1974) si de Gill si Murray (1976).Metoda de mai tarziu actualizeaza o

G₂₂ G₁₂

factorizare partiala a matricei

G₂₁ G₁₁

Acum este de preferat sa actualizam factorii LDL^T ai matricei G₂₂ cum s-a aratat mai sus.

Un alt caz special al P.P. apare atunci cand G este o matrice diagonala pozitiv definita.Prin scalarea variabilelor,functia obiectiv poate fi scrisa cu G=I astfel

q(x)=(1/2)x^Tx+g^Tx (5.3)

Problema ce rezulta se numeste problema distantei minime deoarece solutia x* pentru (1.1) poate fi interpretata ca punctul admisibil cel mai apropiat de punctul x= -g (dupa ce se scrie (5.3) ca (1/2)║x+g║₂² si se ignora termenii constanti ).Din nou este potrivita metoda cu un scop special , deoarece alegerea Z=Q₂ este avantajoasa pentru Z^TGZ=Z^TZ=I.Astfel nu trebuie facuta nici o pregatire speciala pentru actualizarea factorilor Z^TGZ si sunt necesare doar operatiile de actualizare pentru Z, pentru care pot fi folosite formulele lui Gill si Murray(1978).Deoarece G este pozitiv definita , nu apare nici o dificultate speciala.

Mai apare un alt caz special al P.P. atunci cand problema este sa se gaseasca solutia celor mai mici patrate pentru ecuatiile liniare

Bx=c (5.4)

Unde B est de pn si cI R^p,asociat la restrictiile din (1.1).In acest caz functia obiectiv este suma patratelor definite atfel:

q(x)=(Bx-c)^T(Bx-c) (5.5)

Este posibil sa continuam ca la metoda standard cu G=B^TB si g= -B^TC, dupa ce impartim prin doi si omitem termenii constanti.Totusi, se stie ca forma explicita B^TB dintr-o calculare patratica liniara minima cauzeaza aparitia 'efectului patratic' prin care se pot pierde doua sau mai multe figuri semnificative ,atat cat este necesar.De aceea este din nou avantajos sa avem o rutina scop speciala care evita dificultatea.Aceasta se poate realiza prin actualizarea factorilor matricei BZ.Astfel:

U

BZ=P =P₁U (5.6)

este definita, unde P este pp ortogonala, U este (n-m)(n-m) superior triunghiulara, P₁ este formata din primele n-m coloane ale lui P.Urmeaza ca U^T U sa fie factorizarea Choleski a Z^TGZ (=Z^TB^TBZ) si astfel poate fi folosita pentru rezolvarea (1.3) sau (3.1).

In sfarsit, un caz special al P.P. pentru cele mai mici patrate foloseste doar marginile variabilelor considerate.Este posibil sa se introduca o metoda suplimentara cu scop special, asemanatoare cu cele descrise mai sus , in care, folosind (5.2) si (5,6) B este scris [B₁:B₂] si factorii P₁U ai lui B₂ sunt folositi pentru rezolvarea P.E.O posibilitate alternativa este sa se transforme problema intr-o problema de distanta minima folosind duala Wolfe.De exemplu , problema de P.P.:

Inf.(1/2)x^TB^TBx+g^T

^x (5.7)

pentru x≥0

devine:

sup (1/2) x^TB^TBx+g^Tx - ^Tx (5.8)

^x,

pentru B^TBx+g-

(5.10)

Eliminand din (5.8) , folosind (5.9) si scriind Bx=u se obtine problema distantei minime:

Inf (1/2)u^Tu

^u (5.11)

pentru B^Tu≥-g

Sistemul poate fi rezolvat prin metoda descrisa mai sus,obtinand solutia u*.Solutia x* pentru (5.7) poate fi aflata si prin alta metoda.Se aplica pentru (5.11) transformarea duala si se observa usor ca duala pentru (5.11) este (5.7) si astfel vectorul x este vectorul multiplicativ pentru restrictiile din (5.11).Astfel x_i*=0 daca i corespunde unei restrictii inactive la solutia pentru (5.11).Mai mult,este disponibila o factorizare a coloanelor lui B corespunzatoare restrictiilor active astfel incat elementele ramase ale lui x* pot fi determinate din Bx*=u*.Astfel, problemele celor mai mici patrate marginite pot fi reduse la probleme de distanta minima si vice versa.

2.6.Pivotarea complementara si alte metode

Un numar de metode pentru P.P. au fost sugerate ca extensii ale metodei simplex pentru programarea liniara.Cea mai noua metoda este algoritmul Dantzig-Wolfe (Danzig 1963) care rezolva conditiile Kuhn-Tucker pentru P.P.

Inf.(1/2)x^TGx+g^Tx

^x (6.1)

pentru A^Tx≥b , x≥0

Itroducand multiplicatorii pentru restrictiile A^Tx≥b si pentru marginile x≥0 se obtine functia Lagrange:

L(x, )=(1/2) x^TGx+g^Tx- ^T(A^Tx-b)- ^Tx    (6.2)

Definim variabilele ecart r =A^Tx-b si conditiile Kuhn-Tucker devin:

-Gx+A =g

r-A^Tx= -b (6.3)

,r,x, ^Tx=0 , r^T

Metoda presupune ca G sa fie pozitiv definita, care este conditia suficienta pentru ca orice solutie pentru (6.3) sa rezolve (6.1).Sistemul (6.3) poate fi exprimat si sub forma :

w-Mz=q (6.4)

w≥0, z≥0, w^Tz=0

p x G -A g

w= , z= , M= ,q= (6.5)

r l A^T 0 -b

Astfel se obtine problema complementaritatii liniare (P.C.L.) si se mai pot exprima in acest fel probleme din teoria jocurilor sau din problemele de calculare a valorilor marginite.Metoda Dantzig-Wolfe pentru rezolvarea (6.3) ofera metoda pivotarii principale pentru rezolvarea problemei (6.5) si este prezentata in continuare.Totusi, toate metodele pentru rezolvarea (6.4) au unele proprietati comune.Acestea efectueaza operatii liniare asupra ecuatiilor de la (6.4) intr-o maniera apropiata cu problema liniara.Astfel ambele variabile w si z sunt rearanjate ca variabile bazice (B) si nebazice (N): x_B si x_N.La o etapa generala, se poate folosi reprezentarea tabelara

x_B

[I:A^] =b^ (6.6)

x_N

a ecuatiilor din (6.4) si variabelele au valorile x_B=b^ si x_N=0.Se alege pentru a fi marita o variabila x_q, q N si efectul asupra lui x_B din (6.6) este dat de

x_B = b^ -a^_qx_q (6.7)

unde a^_q este coloana din A^ corespunzatoare variabilei x_q .Un element x_i, iIB devine zero cand x_q=b_i^/a_iq^.Aceasta determina ca unele variabile x_p sa devina zero si astfel p si q sunt interschimbate intre B si N ca in programarea liniara.Tabelul este apoi rearanjat prin efectuarea operatiilor liniare care reduc coloana veche x_q a tabelului la un vector unitate.Algoritmul se termina cand b^≥0 si cand solutia este complementara,adica z_i IB <=> w_i IN si z_i IN<=> w_i IB, pentru toti i.

Metoda de pivotare principala este initializata de x_B=w,x_N=z,A^= -M si b^=q.Aceasta este complementara si deci algoritmul se termina daca b^≥0.Daca nu,exista un element x_t IB pentru care b_t^<0 (daca exista mai multi se alege elementul cel mai negativ).

Tabelul 6.1: Tabelul pentru metoda de pivotare principala

x₁ p

x₂ r₁

l p

Se alege apoi variabila complementara x_q IN pentru a fi marita (x_t si x_q sunt complementare daca (x_t si x_q ) pot fi identificate ca (w_i,z_i) sau (z_i,w_i) pentru un anumit i).Efectul asupra variabilelor de baza se observa cu ajutorul relatiei (6.7).Atat timp cat toate variabilele nenegative din B raman nenegative,atunci x_q se mareste pana cand x_t↑0.Apoi x_q si x_t sunt interschimbate in B si N si tabelul este actualizat; tabelul rezultat este tot complementar ,astfel ca iteratia poate fi repetata . Se poate intampla ca atunci cand x_q este marit , variabila de baza x_p↓0.In acest caz se realizeaza o interschimbare pivot pentru a obtine un tabel necomplementar.La urmatoarea iteratie , complementara lui x_p se alege pentru a fi marita .Daca aceasta cauzeaza ca x_t↑0 , atunci este restabilita complementaritatea si algoritmul poate continua ca mai sus.Totusi, un x_p diferit poate deveni zero, caz in care se repeta aceeasi operatie de crestera a complementarei.Excluzand degenerarea , fiecare iteratie mareste x_t astfel ca o eventuala complementaritate este restabilita.Un exemplu de aplicare a metodei pentru problema de la Sectiunea 2.7. este dat in Tabelul 6.1.Metoda Dantzing -Wolfe difera printr-un singur aspect de metoda de pivotare principala si anume prin faptul ca permite variabilelor de baza corespunzatoare variabilelor λ si π din (6.3) sa ramana negative in timpul cautarii. Metoda Dantzing -Wolfe este ilustrata in Tabelul 6.2 si se pot observa diferentele dintre Tabelul 6.1.Nu este dificil de aratat ca metoda Dantzing -Wolfe este echivalenta cu metoda multimii active primala (3.4).O solutie complementara este echivalenta cu solutia unei P.E. si alegerea celui mai negativ x_t este analog cu (3.3).Cazul cand x_t↑0 este acelasi cu alegerea α^(k)=1 in (3.2) si cazul x_p↓0 este echivalent cu α^(k)<1 cand o restrictie inactiva devine activa in linia de cautare.Aceste proprietati se pot observa in Tabelul 6.2.Rezolvarea problemei prin forma tabelara are avantajul simplitatii pentru o problema mica si poate oferi un algoritm compact pentru aplicatiile pe calculator.Totusi,forma tabelara este dezavantajoasa: nu exploateaza eficient factorizarea matricei Lagrange si in shimb este esentiala actualizarea matricei inverse care poate fi instabila numeric.Variabilele ecart pentru toate inegalitatile sunt necesare , astfel ca tabelul poate fi largit.Se rezolva doar o forma restrictionata (6.1) a problemei P.P. si metoda poate esua pentru P.P. nedefinita.Astfel,in general, se prefera un algoritm modern pentru metoda multimii active.

Tabelul 6.2: Tabelul pentru metoda Dantzig -Wolfe

x₁ p

x₂ r₁

l p

Un algoritm diferit pentru rezolvarea problemei complementaritatii liniare (6.4) ete atribuit lui Lemke (1965).In aceata metoda tabelul este extins prin adaugarea in plus a unei variabile z₀ si a coloanei corespunzatoare -e= -(1,1,.,1)^T la A^.Problema (6.4) este initializata de x_B=w, x_N=( z₀ ,z), A^=(-e,-M), b^=q si valorile variabilelor sunt x_N=0 si

x_B=b^.Daca b^≥0 atunci aceasta este solutia; altfel se mareste z₀ in (6.6) pana cand toate variabilele w sunt nenegative.Algoritmul incearca acum sa reduca z₀ la zero.Efectul pasului initial este sa conduca o variabila (x_p) la zero (corespunzatoare celui mai negativ q_i).Apoi x_p si z₀ se interschimba in pasul pivot si complementul lui x_p este marit la inceputul celei de-a doua iteratii.In general, se interschimba la pasul pivotului variabila ce trebuie marita si variabila care se reduce la zero.Apoi urmatoarea variabila ce trebuie marita este complementara celei ce trebuie redusa la zero.Algoritmul se termina cand z₀ devine zero, ceea ce da o solutie pentru (6.4).Un exemplu de metoda aplicata problemei de la Sectiunea 2.7. este dat in Tabelul 6.3.O observatie despre metoda este ca includerea termenului z₀ face ca fiecare tabel din metoda sa fie o solutie a problemei in forma modificata (6.1) in care g este inlocuit de g+z₀e si b de b- z₀e.Astfel metoda Lemke poate fi privita ca o solutie a programarii parametrice pentru (6.1) in care solutia este gasita ca parametrul z₀ ↓0.Pasul la care π_i↓0 sau λ_i↓0 corespunde unor margini sau restrictii active ce devin inactive cand z₀ este micsorat.Pasul la care x_i↓0 si r_i↓0 corespunde unor margini sau restrictii inactive ce devin active.Un avantaj al algoritmului Lemke este ca nu necesita tehnici speciale pentru rezolvarea degenerarii.O forma a algoritmului Lemke fara variabila

z₀ apare daca este o anumita coloana m_q≥0 in M asfel incat m_jq>0 cand q_j<0.Apoi este posibil un pas initial pentru a-l mari pe z_q , care face din (6.6) pe w≥0.Apoi algoritmul continua ca mai sus si se termina cand se obtine complementaritatea (vezi Sectiunea 2.7.).

Exista o forma generala mai interesanta a problemei P.C.L.Problema L₁ a P.P. la care se face referire in (3.5) poate fi de asemenea exprimata folosind un tabel de P.C.L., dar cu margini inferioare si superioare pentru ambele variabile primale si duale.

Tabelul 6.3:Tabelul pentru metoda Lemke

z₀ p

x₁ p

x₂ r₁

l z₀

O tehnica mai noua pentru P.P. este metoda Beale care a fost dezvoltata tot ca o extindere a programarii liniare.Totusi, metoda poate fi descrisa pe scurt ca o metoda a multimii active in felul urmator.Se considera metoda multimii active pentru programarea liniara aplicata pentru a minimiza o functie patratica.Daca linia de cautare k se termina prin gasirea unei restrictii minime, atunci diferenta dintre gradienti γ^(k)=g^(k+1)-g^(k) este schimbata cu restrictiile normale in matricea A.Dupa o secventa de pasi in care restrictiile sunt inlaturate din A efectul este ca directia de cautare s^(k+1) este ortogonala cu vectorii γ⁽¹⁾,., si deci si conjugata cu s⁽¹⁾,.,s^(k).Asfel se introduce posibilitatea de terminare patratica.Din pacate, daca o restrictie inactiva anterioara devine apoi activa, secventa de directii conjugate este rupta.Pentru a se restabili aceasta, metoda Beale necesita anumite iteratii neproductive in care vectorii irelevanti γ^(j) sunt inlaturati din matricea A.Posibilitatea de rearanjare a tabelului pentru a evita aceste iteratii a fost studiata de Benveniste (1979).Metoda devine apoi apropiata de metoda Murray (1971)care de asemenea recurge la directii conjugate.Cu cat este actualizata inversa matricei , cu atat mai mult se prefera factorizarea stabila descrisa in Sectiunea 2.1.Relatiile dintre metoda multimii active,metoda Dantzig -Wolfe,metoda Bale si altele sunt discutate mai pe larg de Goldfarb(1972).

2.7.Exercitii

7.1Pornind de la x⁽¹⁾ =0, sa se ilustreze pasii din metoda multimii active primale pentru rezolvarea urmatoarei probleme de P.P.

inf x₁²-x₁x₂+x₂²-3x₁

^x

pentru x₁≥0

x₂≥0

-x₁-x₂≥-2

Verificati echivalenta metodei cu metoda Dantzig-Wolfe. (Tabelul 6.1,Tabelul 6.2 ).

7.2.Stabiliti problema complementaritatii liniare aparuta la problema 7.1 si aratati ca satisface conditiile de aplicabilitate pentru forma modificata a metodei Lemke.( Tabelul 6.3).

Bibliografie

1.C.Zidaroiu si S.Stefanescu,'Cercetari operationale'.

2.Albert G. Holzman,'Operations Research Methodology'.

3.R.Fletcher, 'Practical methods of optimization'.