Nužni i dovoljni uvjeti optimalnosti

diplomski rad

• Autor: Lucija Cestarić
• Mentor: Marko Vrdoljak (mentor)
• Član povjerenstva: Marko Vrdoljak (predsjednik povjerenstva)
• Član povjerenstva: Josip Tambača (član povjerenstva)
• Član povjerenstva: Nenad Antonić (član povjerenstva)
• Član povjerenstva: Nela Bosner (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2019-09-26, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U ovom radu smo se bavili razvojem nužnih i dovoljnih uvjeta optimalnosti. Na samom početku smo obradili pitanje egzistencije rješenja zadaće nelinearnog programiranja i u tu svrhu smo dokazali poopćenu verziju Weierstrassovog teorema. Prokomentirali smo osnovne rezultate za jednostavniji slučaj uvjetne optimizacije u kojem je dopustivi skup zatvoren i konveksan. U ostatku rada analiziramo općenitiju zadaću nelinearnog programiranja u kojoj je dopustivi skup zatvoren i funkcija cilja diferencijabilna. Iskazali smo geometrijske uvjete optimalnosti koji zahtijevaju da je u točki lokalnog minimuma presjek tangencijalnog konusa i konusa svih smjerova silaska prazan skup. Budući da je tangencijalni konus općenito teško izračunati, uveli smo dodatne uvjete tipa nejednakosti na dopustivi skup koji olakšavaju računanje konusa koji dobro aproksimiraju tangencijalni konus. Novouvedeni konusi nas vode do Fritz Johnovih uvjeta optimalnosti koji su ipak dosta slabi i mogu ih zadovoljavati mnoge točke koje nisu lokalno optimalne. Stoga smo uveli dodatni zahtjev Abadijevog uvjeta regularnosti i time smo došli do specijalnog slučaja Fritz Johnovih uvjeta koji je poznat kao Karush-Kuhn-Tuckerovi uvjeti. Kako Abadijev uvjet nije uvijek lako provjeriti definirali smo i ostale najčešće korištene uvjete regularnosti koji impliciraju Abadijev. Pokazali smo da su Karush-Kuhn-Tuckerovi uvjeti optimalnosti općenito nužni, a u zadaćama konveksnog programiranja dovoljni za lokalnu optimalnost točke.

Sažetak (engleski)

In this thesis we studied development of necessary and sufficient optimality conditions. At the beginning we introduced an important result about existence of solutions to a nonlinear programming problem, known as generalized Weierstrass’ theorem. We introduced some basic results for the case of constrained optimization over closed and convex sets. The rest of the thesis deals with a quite general nonlinear programming problem, where feasible set is closed and the objective function is differentiable. We established geometric optimality conditions which say that at every point of local minimum, the intersection of tangent cone and cone of descent directions must be an empty set. Tangent cone is nearly impossible to compute for general feasible sets so we gave a specific description of a feasible set in terms of inequalities, which helps us to compute other cones that approximate tangent cone in many practical situations. In this way we obtain the Fritz John conditions that, however, are somewhat too weak to be practical and they can be satisfied by many points that have nothing in common with locally optimal points. We assume an additional regularity on feasible set, Abadie’s constraint qualification, and we get special case of Fritz John conditions, known as Karush-Kuhn-Tucker optimality conditions. Abadie’s constraint qualification is difficult to check when it comes to practical problems so we defined some computationally verifiable assumptions that all imply Abadie’s constraint qualification. We showed that Karush-Kuhn-Tucker optimality conditions are necessary, and for convex problems the Karush-Kuhn-Tucker optimality conditions are sufficient for local optimality.

• Ključne riječi: uvjeti optimalnosti; nelinearno programiranje; Weierstrassov teorem; Fritz Johnovi uvjeti optimalnosti; Abadijev uvjet regularnosti; Karush-Kuhn-Tuckerovi uvjeti optimalnosti
• Ključne riječi (engleski): optimality conditions; nonlinear programming; Weierstrass’ theorem; Fritz John conditions; Abadie’s constraint qualification; Karush-Kuhn-Tucker optimality conditions
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:203652
• Studijski program: Naziv: Financijska i poslovna matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra matematike (mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2020-01-22 13:11:13