home Other disciplines books Ically mathematical programuvannya - Nakonechny S.І.

Ically mathematical programuvannya - Nakonechny S.І.

8.6.1. Opuklі th ugnutі funktsії

Navedemo osnovnі signifying that theorem. Let him set n -vimіrny lіnіyny Prostir Rn. Funktsіya Scho given on opuklіy mnozhinі , Nazivaєtsya opukloyu, Yakscho for whether yakih dvoh tochok that s mnozhini X i whether yakih values vikonuєtsya spіvvіdnoshennya:

. (8.27)

Yakscho nerіvnіst strict i vikonuєtsya for Then funktsіya nazivaєtsya strictly opukloyu.

Funktsіya , Yak given on opuklіy mnozhinі , Nazivaєtsya ugnutoyu, Yakscho for whether yakih dvoh tochok that X i s mnozhini whether yakogo spravdzhuєtsya spіvvіdnoshennya:

. (8.28)

Yakscho nerіvnіst strict i vikonuєtsya for Then funktsіya nazivaєtsya strictly ugnutoyu.

Slіd zaznachiti scho opuklіst that ugnutіst funktsії viznachayutsya deprivation vіdnosno opuklih mnozhin in , Oskіlki guidance for the aforesaid time s EYAD whether yakimi points that mnozhinі X nalezhat takozh point їh lіnіynoї kombіnatsії: for vsіh values Scho deprivation in mozhlivo razі, if mnozhina X Je opukloyu.

Theorem 8.2. Nekhay - Opukla funktsіya scho given on zamknenіy opuklіy mnozhinі X, todі whether yaky locally mіnіmum on tsіy mnozhinі Yea i global.

BROUGHT. Acceptable, scho in tochtsі funktsіya Got locally mіnіmum, todі yak in the global mіnіmum dosyagaєtsya tochtsі , Otzhe, vikonuvatimetsya nerіvnіst . Through those scho - Opukla funktsіya for whether yakih values spravdzhuєtsya spіvvіdnoshennya:

. (8.29)

Mnozhina opukla X, to the point at takozh nalezhit tsіy mnozhinі. Vrahovuyuchi scho , Nerіvnіst (8.29) matim viglyad:

;

.

meaning mozhna vibrato so dwellers point Bula roztashovana yak zavgodno blizko up . Todі otrimana Stop nerіvnіst superechit fact scho - A point of local mіnіmumu, oskіlki іsnuє yak zavgodno blizka to neї point at yakіy funktsіya nabuvaє Mensch value nіzh in tochtsі . Tom poperednє assumptions wrong. Theorem brought.

Theorem 8.3. Nekhay - Opukla funktsіya scho viznachena on opuklіy mnozhinі X i krіm of Won neperervna time s Chastain pohіdnimi Perche order vnutrіshnіh access in all points of X. Nekhay - The point at yakіy . Todі in tochtsі dosyagaєtsya locally mіnіmum scho zbіgaєtsya s global.

BROUGHT. W rіvnostі (8.12) to znahodimo:

;

;

.

Through those scho іsnuyut chastinnі pohіdnі Perche order funktsіyu mozhna rozklasti Taylor series:

.

de - Gradієnt funktsії f, obchisleny in tochtsі . . Todі:

.

Perehodimo up at granitsі , Otrimaєmo:

. (8.30)

Tsya Umov vikonuєtsya for whether yakih vnutrіshnіh tochok that X 1 X 2 i i Je neobhіdnoyu dostatnoyu minds opuklostі f (X).

Yakscho funktsіya f (X) s time neperervna Chastain pohіdnimi Perche order i ugnuta mnozhinі on X, then analogіchno poperednomu result maєmo:

.

Pripustimo scho X 0 - dovіlna point mnozhini X todі, taking . And takozh over the minds of the theorem In nerіvnostі (8.30) maєmo:

.

Otzhe, opukla funktsіya f (X) dosyagaє Svoge global mіnіmumu on mnozhinі X in kozhnіy tochtsі de . Theorem brought.

Yak naslіdok theorem can Show, scho if X is closed, obmezhena znizu, opukla mnozhina, the global maximum opukla funktsіya f (X) on dosyagaє nіy in odnіy chi kіlkoh points (at tsomu dopuskaєtsya, scho in tochtsі X values funktsії skіnchenne). Zastosovuyuchi rozv'yazuvannya for tasks such exhaustive search procedure kraynіh tochok can otrimati local maximum point, but not mozhna vstanoviti, chi Je Won points of global maximum.

For ugnutih funktsіy otrimanі result formulyuyut so. Nekhay f (X) - ugnuta funktsіya scho given on zamknenіy opuklіy mnozhinі . Todі whether yaky local maximum of f (X) on X mnozhinі Je global. Yakscho global maximum dosyagaєtsya in dvoh rіznih mnozhini points, then i vіn dosyagaєtsya on neskіnchennіy mnozhinі tochok scho lie on vіdrіzku, yaky spoluchaє tsі point. For strictly ugnutoї funktsії іsnuє єdina point at yakіy Won dosyagaє global maximum.

Gradієnt ugnutoї funktsії f (X) at the point of maximum dorіvnyuє zero Yakscho f (X) - diferentsіyovna funktsіya. The Global mіnіmum ugnutoї funktsії, Yakscho vіn skіnchenny on zamknenіy obmezhenіy zverhu mnozhinі, Got dosyagatisya in odnіy chi kіlkoh її kraynіh points of minds skіnchennostі funktsії f (X) at kozhnіy tochtsі tsієї mnozhini.