Глобалды және локалды минимум критерийі

J(u) → inf, u U=

J(u) – E^r – дегі дөңес U жиынында анықталған дөңес функция.

Теорема. Егер J(u) дөңес U жиынында анықталған дөңес функция және

J_* = J(u)>- , U_*={u, }≠  болса, онда U -дағы J(u) функциясының локальдік минимумының кез-келген нүктесі бір мезгілде U–дағы оның глобальдық минимумының нүктесі болып, U_*  жиыны дөңес болады. Егер J(u) U-да әлді дөңес болса, онда U_* жиыны қамтитын нүктелер саны бірден аспайды. Дәлелі. Мәселен, u_* - дағы J(u) функциясының локальді минимум нүктесі десек, яғни барлық u O(u,… U кезінде J(u_*)≤ J(u). Айталық, v  – еркін нүкте болын. Онда U жиынының дөңестігінен шығатыны: w=u_*+ () егер < .

Демек, J  теңсіздігі орындалады. Екінші жағынан U-да J(u) дөңес функция, ендеше:

J(w)=J + ())=J( +(1-  теңсіздігі орындалады, мұндағы өте аз сан, яғни [0,1].

Енді J(u_*) ≤J(w) теңсіздігі J(u_*)≤J(w) ≤ түрінде жазылады. 0≤ [J( u_*)]. Демек, J(u_*) ≤J(w), u_*  U нүктесінде J(u) функциясының U-дағы глобальдық минимумына жететіндікті білдіреді. Сонымен, дөңес программалау есебінде J(u) функциясының U-дағы кез-келген локальдік минимум нүктесі U-дағы глобальдық минимум нүктесі, яғни есептің шешімі болады.

Тиімділік критерийі.

J(u)  C¹(U) жағдайындағы дөңес программалау есебіне келсек:

J(u) → inf, u U=

ТЕОРЕМА. Егер J(u)  C¹(U)-еркін функция, U – дөңес жиын,

U_*≠ , онда кез-келген u_*  U_* нүктесінде

〈 J’(u_*),u- u_* 〉≥0,                   (1) теңсіздігі орындалады. Егер

J(u)  C¹(U) дөңес функция, U – дөңес жиын, U_*≠ , онда кез-келген u_*  U_* нүктесінде (1) шарттың орындалуы қажетті және жеткілікті.

Дәлелі. Қажеттілігі. u_*  U_* дейік. Кез-келген J(u)  C¹(U) функциясы үшін (1) өрнек орындалатынын көрсетейік, мұндағы U-дөңес жиын (дербес жағдайда J(u) (U)-дағы дөңес функция)

Мәселен,  u  U – еркін нүкте және  Онда J()-J(u_*) ≥0

 Мұндағы = +(1-  u_*  U. Осыдан

0≤J(= ) u_*)- J(u_*)= J(u_*+ )-J(u_*)= 〈 J’(u_*),u- u_* 〉+O( ) әрі  кезінде О / →0. Теңдіктің екі жағын да -ға бөліп, кезіндегі шекке көшсек, (1) өрнекті аламыз. Қажеттілік дәлелденді.

Жеткіліктілігі.  J(u)  C¹(U) дөңес функция, U – дөңес жиын, U_*≠  және (1) өрнек орындалсын. u_*  U_* екенін көрсетейік. Мәселен, u  U-еркін нүкте. Салдар. Егер J(u)  C¹(U), U – дөңес жиын, U_*≠  және u_*  U_*, u_*  intU, онда J’(u_*)=0 теңдігінің орындалуы қажет. Шынында да, егер u_*  intU, онда барлық ₀ кезінде u= u_*+ e  U болатын кез-келген e ⁿ үшін ₀>0 саны табылады. Сонда (1)-ден барлық ₀ кезінде де 〈 J’(u_*), e 〉≥0, e ⁿ. Осыдан алатынымыз: J’(u_*)=0.