Optimizarea, ca disciplinã bine conturatã în cadrul ºtiinþelor computaþionale, constã în determinarea valorilor unor variabile care realizeazã valoarea minimã (sau maximã) posibilã a unei funcþii în situaþia în care acestea trebuie sã satisfacã anumite restricþii. Astfel formulatã, problema are un caracter foarte general, fiind prezentã ca atare în foarte multe domenii de activitate sau ca subproblemã în cadrul unor probleme mai generale. Când numãrul de variabile ºi de restricþii este mare (câteva zeci de mii), atunci optimizarea devine o activitate foarte complexã.

    Beneficiind de o serie de dezvoltãri de substanþã din domeniile algebrei liniare computaþionale, precum ºi al limbajelor de programare, optimizarea este un domeniu matur cu realizãri ºi aplicaþii remarcabile, dispunând de numeroase clase de metode care stau la baza unui numãr impresionant de algoritmi de optimizare. Toþi algoritmii de optimizare sunt iterativi. Una dintre cele mai importante caracteristici ale acestora este convergenþa lor.

    Scopul monografiei. Întregul efort în scrierea acestei lucrãri se concentreazã asupra prezentãrii rezultatelor de convergenþã a câtorva algoritmi fundamentali de optimizare. Se prezintã în detaliu ºi riguros matematic convergenþa metodei Newton pentru optimizare fãrã restricþii, convergenþa metodelor simplex, a elipsoidului ºi a celor de punct interior pentru programarea liniarã, precum ºi a metodelor barierã ºi a planelor de secþiune pentru optimizarea cu restricþii.

    Structura monografiei. Monografia este structuratã în opt capitole. Primul are un caracter introductiv insistând asupra unei formalizãri posibile a conceptului de problemã, precum ºi a unor detalii privind problemele standard de optimizare ºi de algebrã liniarã computaþionalã. Totodatã aici se prezintã conceptul de ordin de mãrime ºi acela de creºtere a funcþiilor foarte mult utilizate în analiza algoritmilor din punctul de vedere al convergenþei ºi al complexitãþii. Urmãtoarele trei capitole prezintã la un nivel foarte general conceptele de convergenþã globalã ºi asimptoticã în condiþiile în care un algoritm este privit ca o aplicaþie multivocã. Se definesc tipurile de convergenþã liniarã ºi superliniarã de ordin m împreunã cu o caracterizare a acestora din punctul de vedere al numãrului de cifre semnificative câºtigate la fiecare iteraþie ºi al numãrului de iteraþii corespunzãtor acestor tipuri de convergenþã. Capitolele cinci, ºase ºi ºapte constituie esenþa acestei lucrãri. În capitolul cinci se trateazã analiza convergenþei algoritmilor de optimizare fãrã restricþii. Dupã o prezentare foarte sumarã a condiþiilor de optimalitate asociate acestei probleme împreunã cu rezultatele fundamentale asupra convergenþei algoritmilor de optimizare fãrã restricþii se prezintã în detaliu analiza convergenþei metodei gradientului descendent ºi a metodei Newton. Ultima secþiune a acestui capitol este dedicatã analizei convergenþei metodei Newton pentru funcþii autoconcordante. Capitolul ºase trateazã analiza convergenþei algoritmilor de programare liniarã. Se prezintã câteva aspecte asupra convergenþei metodei simplex pentru programarea liniarã, a metodei elipsoidului, precum ºi a metodelor de punct interior. Capitolul ºapte este dedicat analizei convergenþei algoritmilor de optimizare cu restricþii. Pentru început se prezintã condiþiile de optimalitate pentru cinci clase de probleme de optimizare cu restricþii împreunã cu teoremele de alternativã care stau la baza existenþei soluþiilor acestora. Dupã o prezentare generalã a convergenþei principalelor metode de optimizare cu restricþii se trateazã riguros analiza convergenþei metodei barierã ºi a metodei planelor de secþiune. În cazul metodei barierã fundamentalã este metoda Newton. Rezultatele de convergenþã ale acesteia se aplicã în cadrul metodei barierã în presupunerea autoconcordanþei funcþiei barierã.
    În ipoteze destul de tari asupra funcþiilor problemei se prezintã formule închise care exprimã numãrul de iteraþii efectuat de algoritm în funcþie de dimensiunea problemei, precum ºi de un numãr de parametri, care pentru majoritatea problemelor sunt necunoscuþi. Ca atare, aceste formule nu au vre-o valoare practicã deosebitã, ci ne furnizeazã o idee asupra convergenþei. Ultimul capitol prezintã câteva opinii referitoare la analiza empiricã a algoritmilor de optimizare fiind o criticã a limitelor dezvoltãrilor teoretice.
    Lucrarea este un discurs teoretic asupra algoritmilor de optimizare, concentrându-se asupra convergenþei acestora. Câteva dintre aceste probleme sunt, de asemenea, considerate în [Boyd ºi Vandenberghe, 2001], unde se prezintã numeroase aspecte ale optimizãrii convexe bazate pe metoda Newton ºi barierã.

    Adresabilitate. Monografia se adreseazã tuturor specialiºtilor interesaþi de posibilitãþile de rezolvare a problemelor de optimizare ºi în performanþele algoritmilor asociaþi acestor probleme din punctul de vedere al convergenþei acestora. Parcurgerea acestui material necesitã o serie de cunoºtinþe din domeniul algebrei liniare, calculului diferenþial ºi integral, precum ºi analizã convexã.

    Mulþumiri. Autorul mulþumeºte Fundaþiei Alexander von Humboldt pentru generozitatea ºi solicitudinea cu care a ºtiut sã-l sprijine de-a lungul timpului atât în perioada stagiului de peste doi ani petrecuþi în câteva universitãþi din Germania, cât ºi dupã aceea. De asemenea, autorul mulþumeºte celor câþiva colegi ºi prieteni cu care a discutat conþinutul acestei monografii. În acelaºi timp, autorul este recunoscãtor soþiei sale Mihaela ºi copiilor Denisa ºi Cosmin pentru afecþiunea ºi înþelegerea cu care l-au înconjurat ºi sprijinit în efortul de a concretiza o muncã depusã pe parcursul mai multor ani.

Bucuresti,
Februarie 10, 2003

                                                                                                                                   Neculai Andrei