И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 3
Текст из файла (страница 3)
....., ...... ...... 392 !. Непрерывный заразит(392). 2. Дискретнмй аариаит (393). 5.25. Методы фейеровскнх приближений решения задач выпуклого програм. мирования с негладкими ограничениями .. .. .. . .. .. .. 395 14 Обп(ий случай (395). 2. СлучаА кусочно линейных ограиичеииВ (396). 5.26. Двойственные методы 398 1.. Приближенный днойстаеннмй метод решения задач выпуклого программироеення (398). 2.
днойстаенный алгоритм переменной метрики (401). 5.27. Глобально сходящийся метод ...,,,.....,.... 403 5.28. Стохвстические кввзиградиеитные методы .. .... .. . . , . 405 1. Метод проектнровэнвя стохастнческнх квазнгрзднентоа (407). 2. Стокествческнй метод сокрэщевнн мевязок в детермнннроввннмх задачах (410).
3. Метод сокращения невязок в задачах стокастнческого прогрзммнроеаннв (4!2). 4. (нбрндный стохзстнческай метод (414) 5.29. Комбинированный метод стохастическнх градиентов и штрафных функций 416 5.30. Методы усреднения направлений спуска . ..... , .. .. , . 4!7 1. Детермнннроввннея задача (417]. 2. Стохэствческая задаче (420). 5.31. Прямой метод решения задач стохастического программирования , . 42! 5.32. Метод случайного поиска в выпуклых задачах минимизации . .. . . 423 5.33. Методы решения задач оптимизации с бесконечным числом ограничений 424 1. Общий алгоритм (425). 2.
Ослабленный алгоритм (426). 5.34. Методы решения задач квадратичного программйрования 1. Метод сопряженных грзднентов для мнннмнзвцнн квадратичной функннн не подпрострзнстзе (427). 2. Метод сопряженных граднентов для об. щей эздзчя кввдретнчвого программирования (423). 3. Метод сопряженных грзднентов для звдечн квздратнчного прогрвммнровзнвя с простымн огрвннченвямн (431).
4. Моднфнкецня метода сопряженных нвпрэвне. ннй дзя задач квадратичного прогрзммнровеннн большой размерностн (432). 5. Устойчивый епгорнтм решения задач нведрзтвчного прогреммнроввння (435) Глава б. Специальные методы решения минимаксных задач и методм отмсканяв седловых точек 438 6.1. Методы последовательных приближений решения дискретных мини. максных задач 438 1. Мнннмакснзн задаче с огрвннченнямн простой структуры (433).
2. Первый метод последовательных приближений решения мнннмвксной эвдэчн с ограннченнямн тнпз веревепств (440). 3. Второй метод последовательных приближений решення мнвнмаксной ведачн с ограняченнямн типа неравенств (442). 4. 'Мьднфнкэпяя второго методе последоеатезш ных прнблнжевнй 843). 6.2. Обобщенный беспараметрический метод внешней точки решения дискретных минимаксных задач 444 1. Основной елгорнтм (414). 2.
Ускоренный вврнзнт евгорнтме (445). 6.3. Метод второго порядка решения задач дискретного миннмэкса . . . 446 6.4. Сеточимй метод последовательных приближений решения непрерывных минимаксных задач 449 6.5. Метод штрафа в задаче поиска макснмина ............. 450 6.6.
Методы стохвстического квдэигрвдпента в задаче поиска максимина 452 1. Осяоеной елгорнтм (453). 2 Следящий алгоритм .(455) 3. Выпуклый случай (457), 6.7. Метод невязок в задаче поиска мвксимина......,...... 458 6.8. Квазигрвдиентные методы решения непрерывных миннмвксных задач стохастического программирования 461 *1. Стохастнческнй квезнградвентный метод (46Ц. 2.
Моднфкпнрованнмй стохзстнчеокнй кввзнгрвднентный метод (462) 6.9. Градиентяые методы отыскания седловых точек , .. .. .. . .. 464 1. Основной ангорнтм (465) 2, Грвднентный метод отнскеяк» седловмх точек а постоянным шаговым множителем (465). 3 Обобщенный грвдненгный метод (467). 6.10.
Метод экспоненциальных штрафов отыскания седловых точек.... 463 6.11. Задачи оптимального управления и оценивання. Методы развязывающих операторов 471 Список литературы Предметный указатель 482 508 ОБОЗНАЧЕНИЯ И СИМВОЛЫ И вЂ” множество действительных чисел и, (), у, б, е, д, р, т, р, о, г — действительные числа С ), й,!, т, и, з — целые числа Ич — и-мерное евклидова пространство, т. е, множество векторов х (хы х, ..., х ) гасе компоненты которых хг, х„..., х„являются действительными числами а, Ь, с, д, е, ), д, Ь, х, у, з, ... и а~, Ь~, аз, х~, ... — векторы, т. е. а б Иа, л'" б Л А, В, С, Н вЂ” матрицы агр Ьу, сп и Ьу — элементы Ьй строки н )-го столбца соответственно матриц А,В,СнНО .У, эь,  — множество индексов (целых чисел) (х, у) — скалярное произведение векторов х и у, т.
е. (х, у) = ~ х,уг ц х) — евклидова нарын вектора х, т. е. Ц х з = (х, х)Ч' 1г — скалярная функция тг. Х -ь )' — функция, определенная на множестве Х и принимающая значения нз множества )' ): х -+ Вв — п.мерная вектор-функция)=(гО гз, ...,га); возведении) — скалярная функции А — матрица, транспонированная к матрице А т А ' — матрица, обратная к матрице А чгг(х) — градиент функции гг в точке х, т. е.
Чгг(х) =,' —, ..., — ') ~ дУг(х) д)г(х) ь дхг ' ' '' дхл ) Чт(х) — матрица Якоби для вектор-функции г в точке х, т. е. элемент ми строки н )-го столбца данной матрицы равен частной производной дуг (х)/дх) Ч„„~г(х) — матрица Гессе для функции /г в точке х, т. е. элемент й-й строки г и )-го столбца данной матрицы равен дгтг (х)~дхздх; чгг(х) — обобщенный градиент функции /г в точке х Ч)г(х) — квазиградиент функции тг в точке х 0= 0 — 0 равно О по определению (О эквивалентно О) А 6 ~ 0 — 0 содержит 0 6~ 0 — 0 содержится в О 6 (.) 0 — объединение 6 и О 6 Й О вЂ” пересечение 6 и О 0 Х О вЂ” декартово произведение О и 0 (х | 6) — множество всех х, для которых верно утверждение 0 х чь у — х не равно у х р Π— х принадлежит х ((9 — х не принадлежит 9 К А Π— множество Х не содержит индекс О Я вЂ” пустое множество ! — единичная матрица (а, [)) — открытый интервал (х[а ( х ( ()) [се, р) — замкнутый интервал (х )а ( х ..
О) шах — максимум по всем й принадлежащим множеству У АХ х ( у — х ( у для х б Вх у б В", если х; ( уг для ! = 1, ..., и В+ — множество (х[« > О, х р В") б!аш У вЂ” диаметр множества !п1 Х вЂ” внутренность множества Х 1г А — след матрицы А гапйА — ранг матрицы А Еп1 (!) — целая часть числа В (А) — образ матрицы А [1: и) — множество целых чисел от 1 до л включительно со Х вЂ” выпуклая оболочка множества Х бе1 А — определитель матрицы А 0(а) — величина порядка а о(а) — величина бесконечно малая по сравнению с а (Ь ! А) — матрица, образованная столбцом Ь н столбцами матрицы А Ы вЂ” равно почти наверное Ы+ — [!)+ = гпах (О, Г) ([);,)г ~!""'„", — матрица размера щ Х и, ((, [).м элементом которой является [)г! ([г, ) б У) — вектор, компонентами которого являются числа /Р [ Е,у (х, у, ..., г) — множество, состоящее из элементов х, у, ..., г шах (1;, Гз, ..., Гх) — максимальный элемент из множества (1„(з..., (х) Р (событие Ю) — вероятность события Я чгх Е Х вЂ” для всех элементов х из множества Х Л х Е Х вЂ” существует такой элемент х в множестве Х агй ппп гг (х) — тот элемент х* из множества Х, который доставляет наимень- «РХ шее значение гг (х») функции [г на множестве Х, т.
е. чг х Е Х 6 (агн ппп [г (х)) ( [г(х) «йх Агя ппп гг (х) — множество всех элементов агй ппп гг (х) «ЯХ «ЕХ агя щах Гг (х) — элемент х** из множества Х, который доставляет нанболь- «ЯХ шее значение /г (х'*) функции гг на множестве Х, т. е. 'зг х б Х [г (агй гпах /! (х)) > Уг (х) «ЕХ Х» — множество решений задачи оптимизации В$ — математическое ожидание случайной величины $ В ($/х) — условное математическое ожидание прн данном х Рс — дисперсия случайной величины 3 ь) — пространство элементарных событий ы ПРЕДИСЛОВИЕ 0дним из наиболее интенсивно используемых и наиболее важных инструментариев повышения эффективности управления и оптими. ззции сложных систем являются в настоящее время математические методы оптимизации.
Современные методы оптимизации часто оказываются недоступными для многих потенциальных потребителей из-за высокого математического уровня соответствующих публикаций. Поэтому при написании данного пособия авторы стремились довести до реализуемых алгоритмов многие из современных методов оптимизации и сделать пособие удобным для студентов и широких кругов специалистов, использующих методы оптимизации в различных областях науки и техники. Этими целями обусловлен способ изложения материала: каждый метод и алгоритм читаются независимо от изложения других методов.
Для этого каждый метод вместе с соответствующим алгоритмом описывается в отдельном параграфе, который имеет единую «стандартную» структуру и состоит из: формулировки решаемой задачи, предположений (ограничивающих применяемость предлагаемого алгоритма), краткого описания идеи метода, полного текста детально разработанного алгоритма, теорем сходимости (дающих теоретическое обоснование для построенных алгоритмов), замечаний и практических рекомендаций по использованию данного алгоритма. При написании пособия авторы сочли более целесообразным вместо готовых реализаций алгоритмов в виде конкретных программ привести их описание, так как, во-первых, любая программа — зто всего лишь одна из многих реализаций исходного алгоритма, отражающая в большой степени умение программиста-математика использовать существующие возможности выбранного языка программирования с учетом реальных возможностей вычислительной техники и специфики конкретных задач, во-вторых, цель пособия— оказать помощь студентам при составлении программ н в работе над литературой по методам оптимизации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
