КАТЕГОРИЯ:


Астрономия- (809) Биология- (7483) Биотехнологии- (1457) Военное дело- (14632) Высокие технологии- (1363) География- (913) Геология- (1438) Государство- (451) Демография- (1065) Дом- (47672) Журналистика и СМИ- (912) Изобретательство- (14524) Иностранные языки- (4268) Информатика- (17799) Искусство- (1338) История- (13644) Компьютеры- (11121) Косметика- (55) Кулинария- (373) Культура- (8427) Лингвистика- (374) Литература- (1642) Маркетинг- (23702) Математика- (16968) Машиностроение- (1700) Медицина- (12668) Менеджмент- (24684) Механика- (15423) Науковедение- (506) Образование- (11852) Охрана труда- (3308) Педагогика- (5571) Полиграфия- (1312) Политика- (7869) Право- (5454) Приборостроение- (1369) Программирование- (2801) Производство- (97182) Промышленность- (8706) Психология- (18388) Религия- (3217) Связь- (10668) Сельское хозяйство- (299) Социология- (6455) Спорт- (42831) Строительство- (4793) Торговля- (5050) Транспорт- (2929) Туризм- (1568) Физика- (3942) Философия- (17015) Финансы- (26596) Химия- (22929) Экология- (12095) Экономика- (9961) Электроника- (8441) Электротехника- (4623) Энергетика- (12629) Юриспруденция- (1492) Ядерная техника- (1748) Arhitektura- (3434) Astronomiya- (809) Biologiya- (7483) Biotehnologii- (1457) Военни бизнесмен (14632) Висока technologies- (1363) Geografiya- (913) Geologiya- (1438) на държавата (451) Demografiya- ( 1065) Къща- (47672) журналистика и смирен (912) Izobretatelstvo- (14524) външен >(4268) Informatika- (17799) Iskusstvo- (1338) историята е (13644) Компютри- (11,121) Kosmetika- (55) Kulinariya- (373) културата е (8427) Lingvistika- (374) Literatura- (1642) маркетинг-(23702) математиците на (16968) Механична инженерно (1700) медицина-(12668) Management- (24684) Mehanika- (15423) Naukovedenie- (506) образователна (11852) truda- сигурност (3308) Pedagogika- (5571) Poligrafiya- (1312) Politika- (7869) Лево- (5454) Priborostroenie- (1369) Programmirovanie- (2801) производствено (97 182 ) индустрия- (8706) Psihologiya- (18388) Religiya- (3217) Svyaz (10668) Agriculture- (299) Sotsiologiya- (6455) на (42831) спортист строително (4793) Torgovlya- (5050) транспорт ( 2929) Turizm- (1568) физик (3942) Filosofiya- (17015) Finansy- (26596) химия (22929) Ekologiya- (12095) Ekonomika- (9961) Electronics- (8441) Elektrotehnika- (4623) Мощност инженерно ( 12629) Yurisprudentsiya- (1492) ядрена technics- (1748)

изпъкнала програмиране

Математически основи на изпъкнала програмиране.

Посоките производни. При един функция Z = F (х, у), определена в затворено домейн D XY равнина (фиг. 7.1). Известно е, че частни производни функция Z = F (X, Y) може да се тълкува като скоростта на промяна на функцията в точка M 0 (X, Y) в посока на осите Ox и Oy.

Фиг. 71

Понятието производно могат да бъдат обобщени, ако вземем предвид скоростта на изменение на функцията Z = F (х, у) във всяка посока сключваща ъгъл с оста х. нека - Точка на повърхността Z = F (х, у). Ние даваме аргументите х и у увеличените , Тогава функция Z получава увеличение , през обозначи точка на координатите на повърхността ; М 0 (х, у) и М 1 ( ) - Прогнозите на точки и върху хоризонтална равнина на. нека ъгъл, който е директен М 0 М 1 до оста Ox ( ), И по- - Дължината на сегмента М 0 М 1.

Определение 7.1. дериват функция Z = F (X, Y) при 0 M (X, Y) в алфа посоката е единичната съотношението граница Z функцията, възникнали при преместване от положението на точката М 0 М покрай гредата под ъгъл положителната посока на оста х, към стойността на това изместване, когато Това клони към нула, т.е.. Д.

(7.1)

Ние намираме формулата за изчисляване на посоката производно на точка M (X, Y) на функция Z = F (X, Y) е диференцируема в точката. От фиг. .1 7 показва, че ,

Използването на равностойността на общия прираст и общата разлика , От формулата (7.1), получаваме

защото стойностите на производните и ъгъла са независими , По този начин,

(7.2.)

По този начин, производно на а посоката е линейна комбинация от частични производни.

Ако производно е по-голяма от 0, увеличенията функция в посока посочено друго - намаление.

И градиента на неговите свойства. В математически програмиране, най-интересното е въпросът за посоката на най-стръмната увеличение на функцията в дадена точка. Този проблем е решен чрез вектор, наречен градиент функция.

Определение 7.2. Gradient функция Z = F (X, Y) в даден момент M 0 (X, Y) е вектор намира в XY плоскост, която има своите координати частни производни на Z, изчислени в този момент.

Gradient посочи град е (X, Y) ,

По този начин, ,

Теорема 7 0.1. Посоката на градиента е най-стръмната увеличение на функция Z = F (X, Y); градиент модул е ​​най-високият процент на увеличение на функция Z.

Доказателство. Фиг. 7.1 α посока на диференциация се определя от вектора , вектор единица тази тенденция има координати COS α, грях α, като ,

Намираме вътрешното произведение на вектори и :

( , ) = ,

Сравнявайки това с (7.2), се установи, че



( , ) (7,3)

Нека ъгълът между векторите , чрез φ, получаваме

Ако φ = 0, т. Е. Ако посоката на вектора (Посока диференциация) съвпада с посоката на градиента Тогава COS φ достигне максималната си стойност (равна на 1) и

(7.4)

По този начин, производно на функция Z = F (х, у) достига максимална стойност в посока на градиента, което показва, че посоката на функция градиент Z на Той се увеличава с най-голяма скорост. Формулата (7.4) също показва, че най-висок процент на увеличение на функция Z равен на модула на градиента.

QED.

Пример 7.2. Намерете най-стръмната увеличение на функция Z = х 2 + XY + 5 в точка M 0 (1, -1), и да се изчисли стойността на производната в тази посока.

Solution. Ние намерите координатите на градиент дал една функция:

DZ / DX = 2x + Y, DZ / Dy = х.

По този начин, буква м има координатите градиент 0 , Според координатите на наклона може да се види, че желаната посока на диференциация сключва ъгъл от 45 ° с оста х. Производно стойност в тази посока

,

Теорема 7.2. Градиент функция Z = F (х, у) на всяка точка М 0 (х, у) е насочено чрез преминаване през тази точка нормално ниво на повърхността на линия Z = F (х, у).

Доказателство. Нека уравнението на линията на ниво L (фиг. 7.2), минаваща през точка M 0, тя има формата

F (х, у) = С (7,5)

За да намерите наклон к на допирателната в точка М 0 в този ред, ние се диференцират уравнение (7.5) като косвен функция:

,

отгдето

, (7.6)

Ние намираме коефициента Директно, която има наклон. Очевидно е, че

(7.7)

Сравнение на уравнение (7.6) и (7.7), виждаме, че KK 1 = 1, т. Е. градиент на допирателната и перпендикулярни една на друга. С други думи, на градиента в даден момент по нормалната линия на нивото на повърхността.

QED.

Обобщаване на понятието градиент по случая на наш тримерно пространство, ние приема следното определение.

Определение 7.3. Ако функцията диференцируема в , Градиент на е (х) в точката х 0, се нарича н двумерен вектор, чиито координати са равни на частните производни на F на функция (х), изчислена в точката х 0, т. Е.

,

Всички имоти градиент, установен в триизмерното пространство се прехвърлят в наш тримерно пространство.

вектор противоположния градиент, наречен antigradient. Това показва посоката на най-стръмната намаление на F на функция (х).

На забележителна имота да се уточни градиент във всяка точка, в която тя съществува, най-стръмната увеличението на функцията, базирани методи градиентни за решаване на математически програмни проблеми, по-специално изпъкнала програмиране.

Изпъкналите и вдлъбнати функции, техните основни свойства. Важен клас на математически задачи за програмиране представляват предизвикателства, които моделът съдържа изпъкнала (вдлъбната) функции.

дефиниция 7 0.4. F функцията (х), дефинирана върху изпъкнало множество X, наречена изпъкнали, ако за всеки две точки Х "и х" в този набор и всеки 0≤λ≤1 неравенството

, (7.8)

Ако съотношението (7.8) за 0 <1 и всеки X ', X " X (X '≠ х ") е строго неравенство, а след това е (х) се нарича строго изпъкнала.

Определение 7.5. F функцията (х), дефинирана върху изпъкнало множество X, наречена вдлъбната, ако за всички точки Хх" в този набор и всеки 0≤ λ ≤1 неравенството

F (λ х '+ (1- λ) х ") ≥ λf (х') + (1 λ) е (х"). (7.9)

Ако съотношението (7.9) за 0 <λ <1 и всеки X ', X " X (X '≠ х ") е строго неравенство, а след това е (х) се нарича строго вдлъбната.

Геометрична илюстрация на определения за данни за двумерен пространство е видно от фиг. 7.3: изпъкнала (. Фигура 7.3, както и) F функцията (х) на интервала "; х "] не може да вземе по-големи стойности от линейна функция на интерполиране стойности на е (х) и е (х"). На свой ред, вдлъбната функция F на (х) (фиг. 7.3, б) да не предприема по-ниски стойности, отколкото линейна функция, която интерполира на F стойности (х ") и F (х").

Фиг. 7.3

От определенията 7.4 и 7.5 показват, че изпъкналост (вдлъбнатина) функции предполага изпъкналост на устройството върху която се определя функцията.

Ние можем да докажем, че ако функцията F I (х) са изпъкнали на изпъкнало множество X, изпъкналата на X ще бъде неотрицателно линейна комбинация от тези функции, т.е.. д. функция при По-специално е изпъкнала и сумата от изпъкнала функция.

Теорема 7.3. Ако φ (х) - изпъкнала функция за всички х ≥0, той ще бъде изпъкнала и набор от решения на φ (х) ≤b, h≥ 0.

Доказателство. Ние потвърди, че, заедно с решенията х 1 и х 2 система φ (х) ≤b, h≥ 0, набор от решения на тази система принадлежи и всеки вектор където , Ясно е, , Остава да се покаже, че φ 0) ≤b. Чрез собственост на изпъкналост на МФ на функция (х)

(7.10)

но Така че за всички 0≤ ламбда ≤1 неравенства , Добавянето на тези неравенства, ние получаваме , С оглед на (7.10), стигаме до неравенство CP 0) ≤b.

QED.

Подобен теорема се доказва и вдлъбната функция.

Може да бъде показано, че наборът от разтвори изпъкнала, ако неравенството с знак - изпъкнала функция, и неравенства с знак - Вдлъбната функция на х ≥0.

Доказано е, че изпъкнала функция е (х), дефинирана върху изпъкнало множество X, е непрекъснато във всеки интериор точка на този набор.

Теорема 7.4. Ако F изпъкналата функция (х) е диференцируема в интериора точки на набор X, след това за всички вътрешни точки х 1, х 2 и неравенството

(7.11)

Доказателство. Тъй като е (х) - изпъкнала функция,

,

отгдето

(7.12)

Известно е, че ако функцията F на (X) на една променлива х в интервала от 0 до х х 0 + Δ X е непрекъсната и има непрекъсната производно, след това по формулата на Тейлър:

,

В нашия случай това е функция F на (х), която зависи от наш променливи, така че формулата Тейлър във векторен нотация добиват следната форма:

,

Използването му за х 0 = х 1, б х = λ (х 2 - х 1), имаме

(7.13)

Замествайки (7.13) в (7.12), ние откриваме

,

Преминавайки към границата като λ → 0 в това неравенство, ние получаваме отношението (7.11).

QED.

Теорема 7.5. Изпъкнала функция е (х), дефинирана върху изпъкнало множество X, достига своя глобален минимум във всяка точка х, в които наклонът на функцията изчезва.

Доказателство. Да предположим, например, градиент на точка х 0 gradf 0) = 0. Ние показваме, че в тази буква е на функция (х) е глобален минимум, т.е.. Д., че за всяка точка х X на неравенството е (х) ≥f (х 0). Известно е, че за изпъкнала на X функция е (х) неравенството (7.11), където х 1 и х 2 - всички вътрешни точки на X. Ако приемем, че в (7.11) х 1 = х 0 и х 2 = х, ние получаваме е (х) - е 0) ≥ gradf (х 0) - х 0), където е (х)е 0), което доказва теоремата.

QED.

Теорема 7.6. Местната минимум на изпъкнала функция е (х), дефинирана върху изпъкнало множество X, съвпада с глобалната минимум на този набор.

Доказателство. Нека функцията F (х) в точката х 0 е локален минимум, т.е.. Д. За всички точки х в някои квартал на точка х ε 0 неравенството на

(7.14)

Нека докажем, че (7.14) е валидна за всяка точка на възможно област X. Да приемем, напротив, т.е.. Д., че има точка хX, така че

(7.14)

и по този начин, х 0 не е точка на глобалния минимум.

Помислете сегмента, свързващи точките Хх 0. уравнение му е , Тъй като допустима домейн X е изпъкнало, на сегмент х 0 лежи изцяло в него. Вземете го точка х ", се намира в ε-квартала на х 0, но не съвпада с точката х 0. Тъй като точка Х" се намира на сегмента X'X 0, то съответства на някаква определена стойност на X = λ "и състояние х" = λ "X" + (1- λ ") х 0 (0 <λ "<1). По силата на изпъкналост на F на функция (х) за точките х" и х 0 неравенството или

(7.16)

Но от допускане на неравенството (7.15), а следователно и на съотношението (7.16) , Изхвърлянето на този срок, ние може да се увеличи само неравенство (7.16), т. Е. Ние се получи

(7.17)

Въпреки това, неравенството (7.17) е в противоречие (7.14) за точките ε-sorrounding точка х 0. Така че, в зоната за изпълнение X все още няма точки на тип X ", за които условието (7.15). Следователно точка х 0 наистина е точка на глобален минимум.

QED.

За да бъде полезна практическа функция за проверка на издутината на следния собственост на изпъкнала функция: F на функция (х) е изпъкнала, ако си втори частни производни образуват матрица, в която всички основни малолетните са не-отрицателни.

7.2. Проблемът на изпъкнала програмиране.

Математически проблеми програмиране

макс (мин) = Z е ( х); (7.18)

(7.19)

където или целевата функция (7.18), или ограничения (7.19), или и двете нелинейни нарича нелинеен.

Нелинейни проблеми представляват широк клас проблеми е толкова сложна, че тя все още е невъзможно да се разработят общи методи като симплекс метод в линейното програмиране, която ще позволи да се справят с всякакви нелинейни проблеми. Но, въпреки липсата на универсални методи, разработени начини за справяне с някои специални класове на проблеми, и най-вече проблеми с изпъкнала (вдлъбната) функции, е (х) и φ I (х).

В изпъкнал програмиране теория като ядрото обикновено се разглежда проблема за минимизиране изпъкнала функция на N променливи Z = F (X) с ограничения , Когато функцията Приема се, че изпъкнала. Изпъкналост на набора от допустими решения на проблема следва от Теорема 7.3.

Ако е (х) и е вдлъбната функция, тогава имаме проблем на максимизиране на е (х) с ограничения , ,

<== Предишна лекция | На следващата лекция ==>
| изпъкнала програмиране

; Дата: 01.07.2014; ; Прегледи: 290; Нарушаването на авторските права? ;


Ние ценим Вашето мнение! Беше ли полезна публикуван материал? Да | не



ТЪРСЕНЕ:


Вижте също:



ailback.ru - Edu Doc (2013 - 2017) на година. Тя не е автор на материали, и дава на студентите с безплатно образование и използва! Най-новото допълнение , Al IP: 11.45.9.24
Page генерирана за: 0.063 сек.