Funkcja wypukła - Convex function

Funkcja wypukła na przedziale.
Funkcja (na czarno) jest wypukła wtedy i tylko wtedy, gdy obszar nad jej wykresem (na zielono) jest zbiorem wypukłym .
Wykres dwuwymiarowej funkcji wypukłej x 2 + xy + y 2 .

W matematyce , o funkcja o wartościach rzeczywistych nazywamy wypukłym , jeśli odcinek między dwoma dowolnymi punktami na wykresie funkcji nie leży poniżej wykresu między dwoma punktami. Równoważnie funkcja jest wypukła, jeśli jej epigraf (zbiór punktów na lub nad wykresem funkcji) jest zbiorem wypukłym . Podwójnie różniczkowalna funkcja jednej zmiennej jest wypukła wtedy i tylko wtedy, gdy jej druga pochodna jest nieujemna na całej swojej dziedzinie. Dobrze znane przykłady funkcji wypukłych pojedynczej zmiennej to funkcja kwadratowa i funkcja wykładnicza . Mówiąc prościej, funkcja wypukła odnosi się do funkcji, która ma kształt kubka , a funkcja wklęsła ma kształt nasadki .

Funkcje wypukłe odgrywają ważną rolę w wielu dziedzinach matematyki. Są one szczególnie ważne w badaniu problemów optymalizacyjnych , gdzie wyróżnia je szereg dogodnych właściwości. Na przykład funkcja ściśle wypukła na zbiorze otwartym ma nie więcej niż jedno minimum. Nawet w przestrzeniach nieskończenie wymiarowych, przy odpowiednich dodatkowych hipotezach, funkcje wypukłe nadal spełniają takie własności iw rezultacie są najlepiej poznanymi funkcjonałami w rachunku wariacyjnym . W teorii prawdopodobieństwa , funkcja wypukła stosowane do wartości oczekiwanej o zmiennej losowej jest zawsze ograniczony powyżej wartości oczekiwanej wypukłej funkcji zmiennej losowej. Wynik ten, znany jako nierówność Jensena , może być wykorzystany do wydedukowania nierówności, takich jak nierówność średniej arytmetyczno-geometrycznej i nierówność Höldera .

Definicja

Wizualizacja funkcji wypukłej i nierówności Jensena

Niech będzie wypukłym podzbiorem rzeczywistej przestrzeni wektorowej i niech będzie funkcją.

Wtedy nazywa się wypukłą wtedy i tylko wtedy, gdy spełniony jest którykolwiek z następujących równoważnych warunków:

  1. Dla wszystkich i wszystkich :
    Prawa strona przedstawia linię prostą pomiędzy i na wykresie jako funkcję wzrostu od do lub spadku od do przecina tę linię. Podobnie argument funkcji po lewej stronie reprezentuje linię prostą między i na lub oś wykresu więc warunek ten wymaga, aby linia prosta między dowolną parą punktów na krzywej znajdowała się powyżej lub po prostu spełnia wykres.
  2. Za wszystkich i wszystkich takich, którzy :
    Różnica tego drugiego warunku w stosunku do pierwszego warunku powyżej polega na tym, że warunek ten nie obejmuje punktów przecięcia (np. i ) między linią prostą przechodzącą przez parę punktów na krzywej (linia prosta jest reprezentowana przez prawej stronie tego warunku), a krzywa pierwszego warunku zawiera punkty przecięcia w takiej postaci, w jakiej się staje lub w lub lub W rzeczywistości punkty przecięcia nie muszą być rozpatrywane w stanie wypukłym przy użyciu
    ponieważ i są zawsze prawdziwe (więc nieprzydatne jako część warunku).

Druga instrukcja charakteryzująca funkcje wypukłe, które są wartościowane w linii rzeczywistej, to również instrukcja używana do definiowania funkcji wypukłych, które są wartościowane w rozszerzonej linii liczb rzeczywistych, gdzie taka funkcja może (ale nie musi) przyjąć jako wartość. Pierwsza instrukcja nie jest używana, ponieważ pozwala na przyjęcie lub jako wartość, w którym to przypadku, jeśli lub odpowiednio, wtedy byłoby niezdefiniowane (ponieważ mnożenia i są niezdefiniowane). Suma jest również niezdefiniowana, więc wypukła rozszerzona funkcja o wartościach rzeczywistych może zwykle przyjmować tylko jedną z wartości i jako wartość.

Drugie zestawienie może być również zmodyfikowany, aby uzyskać definicję ścisłej wypukłości , gdzie ten ostatni otrzymuje się przez zastąpienie w ścisłym nierówności wyraźnie, mapa nazywa się ściśle wypukła wtedy i tylko wtedy, gdy dla wszystkich rzeczywistych i wszystko takie, że :

Funkcja ściśle wypukła to funkcja polegająca na tym, że linia prosta między dowolną parą punktów na krzywej znajduje się powyżej krzywej, z wyjątkiem punktów przecięcia między linią prostą a krzywą.

Mówi się, że funkcja jest wklęsła (odp. ściśle wklęsła ), jeśli ( pomnożona przez -1) jest wypukła (odp. ściśle wypukła ).

Alternatywne nazewnictwo

Termin wypukły jest często określany jako wypukły w dół lub wklęsły w górę , a termin wklęsły jest często określany jako wklęsły w dół lub wypukły w górę . Jeśli termin „wypukły” zostanie użyty bez słowa kluczowego „w górę” lub „w dół”, oznacza to, że odnosi się on wyłącznie do wykresu w kształcie miseczki . Na przykład nierówność Jensena odnosi się do nierówności obejmującej funkcję wypukłą lub wypukłą (górną).

Nieruchomości

Wiele własności funkcji wypukłych ma takie samo proste sformułowanie dla funkcji wielu zmiennych, jak dla funkcji jednej zmiennej. Zobacz poniżej właściwości dla przypadku wielu zmiennych, ponieważ niektóre z nich nie są wymienione dla funkcji jednej zmiennej.

Funkcje jednej zmiennej

  • Załóżmy, że jest funkcją jednej zmiennej rzeczywistej określonej na przedziale i niech
    (Należy zauważyć, że to nachylenie purpurowej linii powyższego rysunku, funkcja
    R jest symetryczny w oznacza, że R nie ulega zmianie przez wymianę i ). wypukła tylko wtedy, gdy jest monotonicznie nie zmniejsza się o co stałe (lub na odwrót). Ta charakterystyka wypukłości jest całkiem przydatna do udowodnienia następujących wyników.
  • Funkcja wypukła jednej zmiennej rzeczywistej określona na pewnym otwartym przedziale C jest ciągła na dopuszcza pochodne lewą i prawą , a te są monotonicznie niemalejące . W konsekwencji jest w ogóle różniczkowalny, ale co najwyżej przeliczalnie wiele punktów, przy czym zbiór, na którym nie jest różniczkowalny, może jednak nadal być gęsty. Jeśli jest zamknięty, może nie być ciągły w punktach końcowych (przykład pokazano w sekcji przykładów ).
  • Różniczkowa funkcja jednej zmiennej jest wypukła na przedziale wtedy i tylko wtedy, gdy jej pochodna jest monotonicznie niemalejąca na tym przedziale. Jeżeli funkcja jest różniczkowalna i wypukła, to jest również różniczkowalna w sposób ciągły .
  • Różniczkowalna funkcja jednej zmiennej jest wypukła na przedziale wtedy i tylko wtedy, gdy jego wykresu leży powyżej wszystkich swoich stycznych :
    dla wszystkich x i y w przedziale.
  • Podwójnie różniczkowalna funkcja jednej zmiennej jest wypukła na przedziale wtedy i tylko wtedy, gdy jej druga pochodna jest tam nieujemna; daje to praktyczny test na wypukłość. Wizualnie podwójnie różniczkowalna funkcja wypukła "wygina się", bez żadnych zagięć w drugą stronę ( punkty przegięcia ). Jeśli jej druga pochodna jest dodatnia we wszystkich punktach, to funkcja jest ściśle wypukła, ale odwrotność nie zachodzi. Na przykład druga pochodna is , która wynosi zero, ale jest ściśle wypukła.
    • Ta własność i powyższa własność w kategoriach "...jej pochodna jest monotonicznie niemalejąca..." nie są równe, ponieważ jeśli jest nieujemna na przedziale, to jest monotonicznie niemalejąca dalej, podczas gdy jej odwrotność nie jest prawdziwa, na przykład jest monotonicznie nie malejący na , podczas gdy jego pochodna nie jest zdefiniowana w niektórych punktach na .
  • Jeśli jest funkcją wypukłą jednej zmiennej rzeczywistej, i , to jest superaddytywną do dodatnich liczb rzeczywistych , czyli dla dodatnich liczb rzeczywistych i .
Dowód

Ponieważ jest wypukła, używając jednej z powyższych definicji funkcji wypukłej i pozwalając, aby wynikało z tego, że dla wszystkich rzeczywistych

Z tego wynika, że
  • Funkcja jest wypukła w punkcie środkowym na przedziale jeśli dla wszystkich
    Ten stan jest tylko nieznacznie słabszy niż wypukłość. Na przykład wymierna funkcja Lebesgue'a o wartościach rzeczywistych, która jest wypukła w punkcie środkowym, jest wypukła: jest to twierdzenie Sierpińskiego . W szczególności funkcja ciągła, która jest wypukła w punkcie środkowym, będzie wypukła.

Funkcje kilku zmiennych

  • Funkcja wartościowana w rozszerzonych liczbach rzeczywistych jest wypukła wtedy i tylko wtedy, gdy jej epigraf
    to zestaw wypukły.
  • Funkcja różniczkowalna zdefiniowana w dziedzinie wypukłej jest wypukła wtedy i tylko wtedy, gdy obowiązuje dla wszystkich w dziedzinie.
  • Podwójnie różniczkowalna funkcja wielu zmiennych jest wypukła na zbiorze wypukłym wtedy i tylko wtedy, gdy jej macierz Hessowska drugich pochodnych cząstkowych jest dodatnio półokreślona na wnętrzu zbioru wypukłego.
  • Dla funkcją wypukłą te zestawy Sublevel i ze są zbiorów wypukłych. Funkcja spełniająca tę właściwość nazywa się funkcją quasi -wypukłą i może nie być funkcją wypukłą.
  • W konsekwencji zbiór globalnych minimizerów funkcji wypukłej jest zbiorem wypukłym: - wypukłym.
  • Każde lokalne minimum funkcji wypukłej jest również minimum globalnym . Funkcja ściśle wypukła będzie miała co najwyżej jedno globalne minimum.
  • Nierówność Jensena dotyczy każdej funkcji wypukłej . Jeżeli jest zmienną losową przyjmującą wartości w domenie to gdzie E oznacza oczekiwanie matematyczne . Rzeczywiście, funkcje wypukłe są dokładnie tymi, które spełniają hipotezę nierówności Jensena .
  • Jednorodna funkcja pierwszego rzędu dwóch zmiennych dodatnich i (tj. funkcja spełniająca wszystkie dodatnie realne ), która jest wypukła w jednej zmiennej, musi być wypukła w drugiej zmiennej.

Operacje zachowujące wypukłość

  • jest wklęsły wtedy i tylko wtedy, gdy jest wypukły.
  • Nieujemne sumy ważone:
    • jeśli i wszystkie są wypukłe, to tak jest . W szczególności wypukła jest suma dwóch funkcji wypukłych.
    • ta własność rozciąga się również na sumy nieskończone, całki i wartości oczekiwane (pod warunkiem, że istnieją).
  • Maksimum elementarne: niech będzie zbiorem funkcji wypukłych. Wtedy jest wypukły. Domeną jest zbiór punktów, w których wyrażenie jest skończone. Ważne przypadki specjalne:
    • Jeśli są funkcjami wypukłymi, to tak jest
    • Twierdzenie Danskina : Jeśli jest wypukłe w to jest wypukłe w nawet jeśli C nie jest zbiorem wypukłym .
  • Kompozycja:
    • Jeśli f i g są funkcjami wypukłymi, a g nie maleje w dziedzinie jednowymiarowej, to jest wypukłe. Na przykład, jeśli jest wypukła, to tak jest . ponieważ jest wypukły i monotonicznie narastający.
    • Jeśli f jest wklęsłe, a g jest wypukłe i nie rosnące w dziedzinie jednowymiarowej, to jest wypukłe.
    • Wypukłość jest niezmienna pod mapami afinicznymi: to znaczy, jeśli f jest wypukłe z dziedziną , to tak jest , gdzie z dziedziną .
  • Minimalizacja: Jeśli jest wypukła w to jest wypukła w x , pod warunkiem, że C jest zbiorem wypukłym i że
  • Jeśli jest wypukła, to jej perspektywa z domeną jest wypukła.

Funkcje silnie wypukłe

Pojęcie silnej wypukłości rozszerza i parametryzuje pojęcie wypukłości ścisłej. Funkcja silnie wypukła jest również ściśle wypukła, ale nie odwrotnie.

Funkcję różniczkowalną nazywamy silnie wypukłą z parametrem m > 0, jeśli dla wszystkich punktów x , y w jej dziedzinie zachodzi następująca nierówność :

lub, bardziej ogólnie,
gdzie jest jakakolwiek norma . Niektórzy autorzy, na przykład, określają funkcje spełniające tę nierówność jako funkcje eliptyczne .

Równoważny warunek jest następujący:

Nie jest konieczne, aby funkcja była różniczkowalna, aby była silnie wypukła. Trzecią definicją silnie wypukłej funkcji, z parametrem m , jest to, że dla wszystkich x , y w dziedzinie i

Zauważ, że ta definicja zbliża się do definicji ścisłej wypukłości jako m → 0 i jest identyczna z definicją funkcji wypukłej, gdy m = 0. Mimo to istnieją funkcje, które są ściśle wypukłe, ale nie są silnie wypukłe dla żadnego m > 0 ( patrz przykład poniżej).

Jeżeli funkcja jest dwukrotnie nieprzerwanie różniczkowalna, to jest silnie wypukła z parametrem

m wtedy i tylko wtedy, gdy dla wszystkich x w dziedzinie, gdzie I jest tożsamością i jest macierzą Hessów , a nierówność oznacza, że jest dodatnia półokreślona . Jest to równoważne z konieczności, że minimalna wartość własna z wynosić przynajmniej m dla wszystkich x . Jeśli dziedzina jest tylko rzeczywistą prostą, to jest tylko drugą pochodną, więc warunek staje się . Jeśli m = 0, oznacza to, że Hessian jest dodatnio półokreślony (lub jeśli dziedziną jest linia rzeczywista, oznacza to, że ), co implikuje, że funkcja jest wypukła i być może ściśle wypukła, ale nie silnie wypukła.

Zakładając jednak, że funkcja jest dwukrotnie nieprzerwanie różniczkowalna, można wykazać, że dolna granica z implikuje, że jest ona silnie wypukła. Korzystając

z twierdzenia Taylora istnieje
takie, że
Następnie
przez założenie o wartościach własnych, a zatem odzyskujemy drugie powyższe równanie silnej wypukłości.

Funkcja jest silnie wypukła z parametrem

m wtedy i tylko wtedy, gdy funkcja
jest wypukła.

Rozróżnienie między wypukłym, ściśle wypukłym i mocno wypukłym może być na pierwszy rzut oka subtelne. Jeżeli jest dwukrotnie w sposób ciągły różniczkowalny, a dziedziną jest linia rzeczywista, to możemy ją scharakteryzować w następujący sposób:

  • wypukły wtedy i tylko wtedy, gdy dla wszystkich
x .
  • ściśle wypukły, jeśli dla wszystkich
  • x (uwaga: to wystarczy, ale nie jest konieczne).
  • silnie wypukły wtedy i tylko wtedy, gdy dla wszystkich
  • x .

    Na przykład niech będzie ściśle wypukły i załóżmy, że istnieje ciąg punktów taki, że . Mimo że funkcja nie jest mocno wypukła, ponieważ stanie się dowolnie mała.

    Funkcja podwójnie nieprzerwanie różniczkowalna na zwartej dziedzinie, która spełnia wszystkie wymagania, jest silnie wypukła. Dowód tego twierdzenia wynika z

    twierdzenia o wartościach ekstremalnych , które mówi, że funkcja ciągła na zbiorze zwartym ma maksimum i minimum.

    Funkcje silnie wypukłe są ogólnie łatwiejsze w obsłudze niż funkcje wypukłe lub ściśle wypukłe, ponieważ są one mniejszą klasą. Podobnie jak funkcje ściśle wypukłe, funkcje silnie wypukłe mają unikalne minima na zbiorach kompaktowych.

    Funkcje jednostajnie wypukłe

    Jednostajnie wypukła funkcja, z modułem , jest funkcją, która dla wszystkich

    x , y w dziedzinie oraz t ∈ [0, 1] , spełnia
    gdzie jest funkcją nieujemną i zanika dopiero w punkcie 0. Jest to uogólnienie pojęcia funkcji silnie wypukłej; biorąc , odzyskujemy definicję silnej wypukłości.

    Przykłady

    Funkcje jednej zmiennej

    • Funkcja ma , więc
    f jest funkcją wypukłą. Jest również silnie wypukły (a więc również ściśle wypukły), o silnej stałej wypukłości 2.
  • Funkcja ma , więc
  • f jest funkcją wypukłą. Jest ściśle wypukła, chociaż druga pochodna nie jest we wszystkich punktach ściśle dodatnia. Nie jest mocno wypukła.
  • Wartość bezwzględna funkcja jest wypukła (jak pokazano na
  • nierówności trójkąt ), mimo że nie posiada pochodną w punkcie  x  = 0, nie jest ściśle wypukła.
  • Funkcja for jest wypukła.
  • Funkcja wykładnicza jest wypukła. Jest również ściśle wypukła, ponieważ , ale nie jest silnie wypukła, ponieważ druga pochodna może być dowolnie bliska zeru. Mówiąc bardziej ogólnie, funkcja jest
  • logarytmicznie wypukła, jeśli f jest funkcją wypukłą. Czasami zamiast tego używa się terminu „superwypukły”.
  • Funkcja z dziedziną [0,1] zdefiniowaną przez for jest wypukła; jest ciągła w otwartym przedziale (0, 1), ale nie ciągła w 0 i 1.
  • Funkcja x 3 ma drugą pochodną 6 x ; jest więc wypukła na zbiorze, gdzie x ≥ 0 i wklęsła na zbiorze, gdzie  x  ≤ 0.
  • Przykłady funkcji, które rosną monotonicznie, ale nie są wypukłe, obejmują i .
  • Przykłady funkcji, które są wypukłe, ale nie rosną monotonicznie, obejmują i .
  • Funkcja ma which jest większa od 0, jeśli
  • x > 0, więc jest wypukła na przedziale . Jest wklęsły na interwale .
  • Funkcja z , jest wypukła na przedziale i wypukła na przedziale , ale nie wypukła na przedziale , ze względu na osobliwość w 
  • x  = 0.

    Funkcje n zmiennych

    • Funkcja
    LogSumExp , zwana również funkcją softmax, jest funkcją wypukłą.
  • Funkcja w dziedzinie
  • macierzy dodatnio określonych jest wypukła.
  • Każda transformacja liniowa o wartościach rzeczywistych jest wypukła, ale nie ściśle wypukła, ponieważ jeśli f jest liniowe, to . Stwierdzenie to obowiązuje również wtedy, gdy „wypukły” zastąpimy „wklęsłym”.
  • Każda funkcja afiniczna o wartościach rzeczywistych , tj. każda funkcja formy , jest jednocześnie wypukła i wklęsła.
  • Każda norma jest funkcją wypukłą, przez nierówność trójkąta i dodatnią jednorodność .
  • Promień spektralny z nieujemnej matrycy jest wypukła funkcją przekątnej elementów.
  • Zobacz też

    Uwagi

    Bibliografia

    • Bertsekas, Dimitri (2003). Analiza wypukła i optymalizacja . Atena naukowa.
    • Borwein, Jonathan i Lewis, Adrian. (2000). Analiza wypukła i optymalizacja nieliniowa. Skoczek.
    • Donoghue, William F. (1969). Rozkłady i transformaty Fouriera . Prasa akademicka.
    • Hiriart-Urruty, Jean-Baptiste i Lemaréchal, Claude . (2004). Podstawy analizy wypukłej. Berlin: Springer.
    • mgr Krasnoselskii , Rutickii Ya.B. (1961). Funkcje wypukłe i przestrzenie Orlicza . Groningen: P.Noordhoff Ltd.
    • Lauritzen, Niels (2013). Wypukłość licencjacka . Światowe Wydawnictwo Naukowe.
    • Luenberger, David (1984). Programowanie liniowe i nieliniowe . Addisona-Wesleya.
    • Luenberger, David (1969). Optymalizacja metodami przestrzeni wektorowej . Wiley i Synowie.
    • Rockafellar, RT (1970). Analiza wypukła . Princeton: Wydawnictwo Uniwersytetu Princeton.
    • Thomson, Brian (1994). Symetryczne własności funkcji rzeczywistych . CRC Prasa.
    • Zălinescu, C. (2002). Analiza wypukła w ogólnych przestrzeniach wektorowych . River Edge, NJ: World Scientific Publishing Co., Inc. s. xx+367. Numer ISBN 981-238-067-1. MR  1921556 .

    Zewnętrzne linki