Основы теории оптимизации (стр. 1 )

Парадигма развития науки

Методологическое обеспечение

А.Е. Кононюк

ОСНОВЫ ТЕОРИИ ОПТИМИЗАЦИИ

Книга 2

Безусловная оптимизации

Часть 1

Киев

Освiта України

2011

УДК 51 (075.8)

ББК В161.я7

К 213

Рецензент: - д-р техн. наук, проф. (Национальный авиационный университет).

К65 Основы теории оптимизации. Безусловная оптимизация К.2.ч.1. Киев:"Освіта України", 2011. - 544 с.

ISBN 978-966-7599-50-8

Настоящая работа является систематическим изложением базовой теории оптимизации для конечномерных задач. Основное внимание уделя­ется идейным основам методов, их сравнительному анализу и примерам использования. Охвачен широкий круг задач — от безусловной минимизации до условной минимизации. Об­суждается методика постановки и решения прикладных проблем оптимиза­ции. Приводятся условия экстремума, теоремы существования, единственности и устойчивости решения для основных классов задач. Исследуется влияние помех, негладкости функций, вырожденности минимума. Работа предназначена для магистров, аспирантов, докторантов, инженеров, экономистов, статистиков, вычислителей и всех тех, кто сталкивается с задачами оптимизации.

ББК В161.я7

ISBN 978-966-7599-50-8 ©А. Е. Кононюк, 2011

Часть І

Методы безусловной оптимизации

Оглавление

1. Введение в теорию безусловной оптимизации ………………….6 . 1.1. Задачи оптимизации ……………………………………………10

1.2. Краткий обзор методов оптимизации ………………………...17

1.3. Задача безусловной оптимизации ……………………………..26

2. Методы одномерной оптимизация ………………………………..42

2.1. Введение в одномерную оптимизацию ………………………42

2.2. Одномерная оптимизация …………………………………..56

3. Методы одномерной минимизации нулевого порядка

(прямые методы) ……………………………………………………..63

3.1. Общая характеристика методов нулевого порядка………… 70

3.2. Нелокальная линейная аппроксимация……………………71

3.3. Квадратичная аппроксимация…………………………………74

3.4. Метод перебора ………………………………………………..76

3.5. Метод поразрядного поиска …………………………………..78

3.6. Методы исключения отрезков…………………………………80 . 3.7. Метод Фибоначчи …………………………………………….117

3.8. Метод конфигураций. ………………………………………..146 . 3.9. Mетод деформируемого многогранника ……………………154 . 3.10. Метод прямого поиска (метод Хука-Дживса) …………….170

3.11. Метод вращающихся координат (метод Розенброка)…….172 . 3.12. Метод параллельных касательных (метод Пауэлла) ……..175

3.13. Краткий обзор других методов ……………………………177

4. Методы одномерной минимизации первого порядка ………….178

4.1. Минимизация функций. Основные положения …………….178 . 4.2. Метод парабол ……………………………………………….183

4.3. Градиентный метод как классический метод оптимизации.187 . 4.4. Метод наискорейшего спуска ………………………………..195 . 4.5. Метод градиентного спуска…………………………………. 198 . 4.6. Градиентный метод с дроблением шага……………………..209

4.7. Метод сопряженных градиентов …………………………….212

4.8. Методы оврагов ……………………………………………….225 . 4.9. Метод Флетчера-Ривса………………………………………..228 . 4.10. Минимизация неквадратичной целевой функции………… 235 . 4.11. Метод Дэвидона — Флетчера — Пауэлла (ДФП)………….236

4.12. Некоторые методы первого порядка в иной

интерпретации ……………………………………………………….237 5. Методы минимизации второго порядка ………………………248 . 5.1. Особенности методов второго порядка …………………….248

5.2. Методы линейной аппроксимации………………………...250

5.3. Интерполяция кубическими сплайнами ……………………260 . 5.4. Метод Ньютона ………………………………………………269 . 5.5. Метод касательных (Ньютона)………………………………274 . 5.6. Метод Коши…………………………………………………. 290

5.7. Метод Марквардта …………………………………………..292

5.8. Связь методов Ньютона и сопряженных градиентов…….. 294

5.9. Сравнение методов одномерного поиска …………………..305

5.10. Многошаговые методы …………………………………….310

5.11. Краткий анализ методов одномерной минимизации……. 319

6. Методы многомерной безусловной оптимизации ………………327

6.1. Введение в  методы многомерной оптимизации …………..327

  6.2. Постановка задачи многомерной оптимизации. ……………330

6.3. Критерий оптимальности для функции многих переменных 335

6.4. Квадратичная функция аргумента …………………………341

6.5. Рельеф поверхности целевой функции f(х). …………………..342

6.6. Введение в методы безусловной минимизации функций

многих переменных ……………………………………………………344

6.7. Многомерный поиск без использования производных……….364

6.8. Методы минимизации первого порядка. ……………………... 381

6.9. Методы второго порядка ……………………………………….409 7. Методы анализа многомерной безусловной оптимизации ……….415

7.1. Анализ методов прямого поиска ………………………………416

7.2. Анализ методов первого и второго порядков……………….. 430

7.3. Обобщённый алгоритм………………………………………… 441 8. Методы оптимизации овражных функций………………………… 442

9. Влияние помех на поведение методов безусловной минимизации 452

9.1. Источники и типы помех ……………………………………….453

9.2. Градиентный метод при наличии помех……………………… 455

9.3. Другие методы минимизации при наличии помех…………… 459

9.4. Прямые методы ………………………………………………….462

9.5. Оптимальные методы при наличии помех …………………….466

9.6. Псевдоградиентный метод с возмущением на входе для нестационарной задачи безусловной оптимизации …………………..472

10. Стратегия оптимизационного исследования ……………………482 . 10.1. Построение модели ………………………………………….482 . 10.2. Реализация модели ………………………………………….484 . 10.3. Преодоление вычислительных трудностей………………..486 . 10.4. Анализ модели ………………………………………………487 . 10.5. Методы поиска и оценки решений………………………… 489 Приложения…………………………………………………………….495Список обозначений…………………………………………………. .545 Литература. …………………………………………………………….547

1. Введение в теорию безусловной оптимизации

Оптимизация как раздел математики существует достаточно давно. Оптимизация - это выбор, т. е. то, чем постоянно приходится заниматься в повседневной жизни. Термином "оптимизация" в литературе обозначают процесс или последовательность операций, позволяющих получить уточненное решение. Хотя конечной целью оптимизации является отыскание наилучшего или "оптимального" решения, обычно приходится довольствоваться улучшением известных решений, а не доведением их до совершенства. Поэтому под оптимизацией понимают скорее стремление к совершенству, которое, возможно, и не будет достигнуто.

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

Возьмем пример: человек вышел утром из дому, чтобы ехать на работу. По ходу дела ему приходится принять целый ряд решений: брать ли с собой зонтик? В каком месте перейти улицу? Каким видом транспорта воспользоваться? И так далее. Разумеется, все эти решения человек принимает без специальных расчетов, просто опираясь на имеющийся у него опыт и на здравый смысл. Для обоснования таких решений никакая наука не нужна, да вряд ли понадобится и в дальнейшем.

Однако возьмем другой пример. Допустим, организуется работа городского транспорта. В нашем распоряжении имеется какое-то количество транспортных средств. Необходимо принять ряд решений, например: какое количество и каких транспортных средств направить по тому или другому маршруту? Как изменять частоту следования машин в зависимости от времени суток? Где разместить остановки? И так далее.

Эти решения являются гораздо более ответственными, чем решения предыдущего примера. В силу сложности явления последствия каждого из них не столь ясны; для того, чтобы представить себе эти последствия, нужно провести расчеты. А главное, от этих решений гораздо больше зависит. В первом примере неправильный выбор решения затронет интересы одного человека; во втором - может отразиться на деловой жизни целого города. Конечно, и во втором примере при выборе решения можно действовать интуитивно, опираясь на опыт и здравый смысл. Но решения окажутся гораздо более разумными, если они будут подкреплены количественными, математическими расчетами. Эти предварительные расчеты помогут избежать длительного и дорогостоящего поиска правильного решения "на ощупь".

Наиболее сложно обстоит дело с принятием решений, когда речь идет о мероприятиях, опыта в проведении которых еще не существует и, следовательно, здравому смыслу не на что опереться, а интуиция может обмануть. Пусть, например, составляется перспективный план развития вооружения на несколько лет вперед. Образцы вооружения, о которых может идти речь, еще не существуют, никакого опыта их применения нет. При планировании приходится опираться на большое количество данных, относящихся не столько к прошлому опыту, сколько к предвидимому будущему. Выбранное решение должно по возможности гарантировать нас от ошибок, связанных с неточным прогнозированием, и быть достаточно эффективным для широкого круга условий. Для обоснования такого решения приводится в действие сложная система математических расчетов.

Вообще, чем сложнее организуемое мероприятие, чем больше вкладывается в него материальных средств, чем шире спектр его возможных последствий, тем менее допустимы так называемые "волевые" решения, не опирающиеся на научный расчет, и тем большее значение получает совокупность научных методов, позволяющих заранее оценить последствия каждого решения, заранее отбросить недопустимые варианты и рекомендовать те, которые представляются наиболее удачными.

Практика порождает все новые и новые задачи оптимизации причем их сложность растет. Требуются новые математические модели и методы, которые учитывают наличие многих критериев, проводят глобальный поиск оптимума. Другими словами, жизнь заставляет развивать математический аппарат оптимизации.