292 293

292 293



Programowanie wypukłe i kwadratowe



292

Scharakteryzujemy wykorzystywane dalej funkcje wypukłe i wklęsłe. Funk-



cja liniowa ma postać:

n

a(x) = pTx = z PjXj. j= I

Twierdzenie 6.1

Funkcja liniowa jest jednocześnie funkcją wypukłą i funkcją wklęsłą. Formą kwadratową nazywamy funkcję:

n n

(3(x) = xTCx= X X CijXiXj.

•= t j-1

Zakładamy przy tym, że C=[c,v] jest macierzą symetryczną, czyli zachodzi ■ związek cij = cJi. Jeżeli tak nie jest, można łatwo do tego doprowadzić, definiując nowe współczynniki:

Wówczas Cij = Cji.

Chcąc zbadać, czy forma kwadratowa jest funkcją wypukłą lub wklęsłą, należy sprawdzić, czy macierz C tej formy jest nieujemnie lub niedodatnio określona.

Macierz C formy kwadratowej jest nieujemnie określona, jeżeli dla dowolnego wektora x:

xTCx > 0,

a niedodatnio określona, jeżeli dla dowolnego wektora x: xTCx ^ 0.

Związek między określonością formy kwadratowej oraz wypukłością (wklęsłością) tej formy jest następujący:

Twierdzenie 6.2

Forma kwadratowa jest funkcją wypukłą (wklęsłą) wtedy i tylko wtedy, gdy macierz formy C jest nieujemnie (niedodatnio) określona.

Funkcją kwadratową nazywamy funkcję będącą różnicą funkcji liniowej i formy kwadratowej:

Y(x) = pTx-xTCx.

Jeżeli macierz formy kwadratowej C jest nieujemnie określona, wtedy macierz . -C jest niedodatnio określona i funkcja y(x) jest funkcją wklęsłą.

$

Zadanie programowania wypukłego

293


6.2.2. Sformułowanie zadania

programowania wypukłego

Zadanie programowania nieliniowego można w sposób ogólny zapisać następująco:

/(x) -> max, 5i(x)3sO,

(6.2)


gm(x) > 0.

Przyjmując:

S.(x)

2(x) = mamy:

/(x) —> max,

g(x) > 0.    (6.3)

Zadanie (6.3) jest zadaniem programowania wypukłego, jeżeli funkcja celu / oraz wszystkie funkcje gh opisujące warunki ograniczające, są funkcjami wklęsłymi.

Przedstawimy dwa przykładowe problemy programowania wypukłego.

Przykład 6.1

Rozpatrujemy zadanie:

/(x) = X|+x2 —» max, g,(x) = 8SsO, g2(x)=X| JłO, g,(x)=x2>0.

Funkcje/, g2, g3 są wklęsłe jako funkcje liniowe. Na podstawie definicji można sprawdzić, że funkcja g, jest wklęsła. Tak więc rozpatrywany problem jest zadaniem programowania wypukłego. Zbiór rozwiązań dopuszczalnych tego zadania wyznaczamy jako część wspólną okręgu o środku w początku układu współrzędnych i promieniu 2 oraz pierwszej ćwiartki układu współrzędnych. Jest on przedstawiony na rys. 6.5. Punkty A i B, będące punktami przecięcia osi układu współrzędnych z rozpatrywanym okręgiem, mają współrzędne: .4(0, 2a/2), B(2yl2, 0). Zadanie to można rozwiązać geometrycznie. Po dołączeniu warstwicy funkcji celu, przechodzącej przez początek układu współrzędnych, i znalezieniu


Wyszukiwarka

Podobne podstrony:
290 291 290 Programowanie wypukłe i kwadratowe Rysunek 6.3 290 Programowanie wypukłe i kwadratowe W
294 295 294 Programowanie wypukłe i kwadratowe Rysunek 6.5 kierunku wzrostu funkcji celu określamy p
296 297 296 Programowanie wypukłe i kwadratowe Ponadto mówimy, że spełniony jest warunek Slatera, je
298 299 Programowanie wypukłe i kwadratowe298 Podzbiór 2 Pierwszy warunek jest spełniony jako równoś
300 301 300 Programowanie wypukłe i kwadratowe Rysunek 6.12 A W t Podzbiór 1 Jeżeli gi>0, g2>
302 303 302 Programowanie wypukłe i kwadratowe Sprowadzimy zadanie do ogólnej postaci programowania
304 305 304 Programowanie wypukłe i kwadratowe Warunek 3 Warunek ten stanowi powtórzenie warunków
306 307 306 Programowanie wypukłe i kwadratowe • i 306 Programowanie wypukłe i kwadratowe 
308 309 308 Programowanie wypukłe i kwadratowe tarnej x?2 i niemożność jej wymiany ze zmienną y2 (wa
310 311 310 Programowanie wypukłe i kwadratowe Tablica 6.6 cx
312 313 312 Programowanie wypukłe i kwadratowe 8 n
314 315 314 Programowanie wypukłe i kwadratowi Oznaczmy symbolem /?,(/■) cenę / -tej akcji osiągnięt
316 317 316 Programowanie wypukłe i kwadratowe Tablica 6.9 Notowania spółka 1 spółka 2 spółka
318 319 318 Programowanie wypukłe i kwadratoweFunkcja celu min, f(xj, Aj, Aj, A.j, A5) = [A
320 321 320 Programowanie wypukłe i kwadratowe Funkcje celu: • minimalizacja ryzyka
322 323 322 Programowanie wypukłe i kwadratowe Rozpatrywane zadanie nie jest zadaniem wektorowej mak
img211 Planowanie programu produkcji Planowanie przybliżone wykorzystuje zarówno dane z poprzednich

więcej podobnych podstron