292 293

Programowanie wypukłe i kwadratowe

292

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

cja liniowa ma postać:

a(x) = p^Tx = 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) = x^TCx= X X CijXiXj.

•= t j-1

Zakładamy przy tym, że C=[c,_v] jest macierzą symetryczną, czyli zachodzi ■ związek c_ij = c_Ji. 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:

x^TCx > 0,

a niedodatnio określona, jeżeli dla dowolnego wektora x: x^TCx ^ 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) = p^Tx-x^TCx.

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)

g_m(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 g_h 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|+x₂ —» max, g,(x) = 8SsO, g₂(x)=X| JłO, g,(x)=x₂>0.

Funkcje/, g₂, g₃ 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