Разработка и исследование нелокальных алгоритмов параметрической идентификации динамических систем тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Сороковиков Павел Сергеевич

• Сороковиков Павел Сергеевич
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Сороковиков Павел Сергеевич

Введение

Глава 1. Анализ предметной области

1.1. Классификация конечномерных задач оптимизации и методов их решения

1.2. Численные методы локального поиска

1.3. Обзор существующих подходов к решению задач глобальной оптимизации

1.3.1. Алгоритмы одномерной глобальной оптимизации

1.3.2. Безградиентные методы многомерного нелокального поиска

1.4. Задача параметрической идентификации нелинейных динамических моделей

1.5. Обзор вычислительных технологий для решения задач оптимального управления

1.6. Методология обучения с подкреплением

1.7. Методики тестирования алгоритмов и коллекция тестовых задач

Глава 2. Методы одномерного глобального поиска, основанные на условии Гёльдера

2.1. Общая схема реализации алгоритмов одномерного глобального поиска

2.2. Алгоритмы, основанные на эвристической идеологии

2.2.1. Модификация метода парабол

2.2.2. Метод «сжимающего перебора»

2.3. Алгоритмы, основанные на условии Липшица (Гёльдера) функции

2.3.1. Модификация алгоритма Евтушенко с автоматической оценкой константы Липшица (Гёльдера)

2.3.2. Модификация метода Пиявского

2.3.3. Модификация метода Стронгина

2.3.4. Комбинированный алгоритм на основе методов Стронгина и парабол

2.4. Алгоритмы, основанные на условии Липшица (Гёльдера) производной функции

2.5. Семейство вероятностных Р-алгоритмов

2.6. Численное исследование свойств предложенных модификаций алгоритмов нелокального одномерного поиска

2.6.1. Тестирование модификации алгоритма Евтушенко с автоматической оценкой константы Гёльдера

2.6.2. Тестирование модификации метода Пиявского

2.6.3. Тестирование модификации метода Стронгина

2.6.4. Тестирование комбинированного алгоритма на основе методов Стронгина и парабол

2.6.5. Сравнение алгоритмов

Глава 3. Алгоритмы решения многомерных задач невыпуклой оптимизации

на основе поисковых методов

3.1. Модификации алгоритмов, основанных на методах одномерного глобального поиска

3.1.1. Модификация метода парабол

3.1.2. Модификация туннельного метода

3.1.3. Модификации метода Пауэлла и партан-метода

3.1.4. Модификация метода Розенброка

3.1.5. Модификация метода криволинейного поиска

3.1.6. Обсуждение результатов вычислительных экспериментов

3.2. Алгоритмы, не использующие методы одномерного глобального поиска

3.2.1. Модификация метода Растригина

3.2.2. Модификация метода Лууса-Яаколы

3.2.3. Модификация метода поиска с запретами

3.2.4. Модификация метода случайных покрытий

3.2.5. Экспертный метод

3.2.6. Тестирование алгоритмов

3.3. Модификации биоинспирированных алгоритмов

3.3.1. Многоагентные алгоритмы, вдохновленные живой природой

3.3.2. Эволюционные алгоритмы

3.3.3. Многоагентные алгоритмы, инспирированные неживой природой или человеческим обществом

3.3.4. Численное исследование свойств предложенных модификаций биоинспирированных алгоритмов

Глава 4. Специализированное программное обеспечение

4.1. Специализированное программное обеспечение МЕОРТ для численного решения задач многоэкстремальной оптимизации

4.1.1. Постановка задачи

4.1.2. Архитектура и реализация специализированного программного обеспечения

4.2. Вероятностный динамический планировщик расчетов для задачи глобального поиска

4.2.1. Описание планировщика

4.2.2. Тестирование планировщика

Глава 5. Прикладные задачи и задачи с содержательным смыслом

5.1. Задачи оптимального управления в робототехнических системах

5.1.1. Постановка задачи оптимального управления

5.1.2. Учет фазовых ограничений

5.1.3. Задача оптимальной ориентации летательного аппарата в пространстве

5.1.4. Задача оптимального управления мобильным роботом

5.1.5. Задача оптимального управления манипулятором промышленного робота

5.2. Прогнозирование экономического развития Баргузинского района Республики Бурятия

5.2.1. Формулировка проблемы

5.2.2. Задача параметрической идентификации модели

5.3. Задачи из области атомно-молекулярного моделирования

5.3.1. Трехэтапная вычислительная технология оптимизации потенциалов атомно-молекулярных кластеров

5.3.2. Потенциал Морса

5.3.3. Потенциал Саттона-Чена

5.3.4. Потенциал Гупты

5.4. Задачи нахождения равновесия анти-Бержа

Заключение

Список литературы

Приложения

Приложение А. Коллекция тестовых задач

А1. Тестовые функции одной переменной

А2. Многомерные тестовые функции

Приложение Б. Вычислительные эксперименты

Б1. Тестирование модификации метода Стронгина

Б2. Тестирование модификации метода парабол

Б3. Тестирование модификации туннельного метода

Б4. Тестирование модификации метода Пауэлла

Б5. Тестирование модификации метода Розенброка

Б6. Тестирование модификации метода криволинейного поиска

Введение диссертации (часть автореферата) на тему «Разработка и исследование нелокальных алгоритмов параметрической идентификации динамических систем»

ВВЕДЕНИЕ

Актуальность темы исследования. При решении задач системного анализа, управления и обработки информации важную роль играют методы и программные средства решения задач параметрической идентификации динамических систем. Известные методы и программные средства решения задач параметрической идентификации нелинейных динамических моделей во многих ситуациях не позволяют проводить эффективные исследования сложных прикладных задач из различных научно-технических областей. Это связано, в первую очередь, с невыпуклостью формулируемых в таких задачах функционалов, их овражностью и/или плохой обусловленностью, проявлением «нефизичных» эффектов и т.п. Проблема построения эффективных и надежных алгоритмов и методик исследования прикладных задач параметрической идентификации продолжает оставаться актуальной.

Анализ конструкций и свойств известных алгоритмов оптимизации позволяет сделать заключение о том, что степень обучаемости алгоритмов зачастую не слишком велика. Для задач локальной оптимизации это обстоятельство, как правило, не является критичным - алгоритм может работать долго, но, в конце концов, достигает экстремума. Совершенно другая ситуация в невыпуклой (глобальной) оптимизации. Задача достаточно полного сканирования вариабельного множества может оказаться весьма сложной даже для задач небольших размерностей - до десятков переменных. В многомерных задачах математического программирования и задачах оптимизации динамических систем, формально бесконечномерных, малообучаемые алгоритмы могут оказаться совершенно неэффективными, что влечет выдачу неверных результатов - решений, не являющихся оптимальными. Можно утверждать, что в основе любой успешной поисковой стратегии лежит баланс между глобальным сканированием допустимого множества («разведкой») и локальным уточнением полученных приближений («эксплуатацией»).

Работа посвящена построению и численному исследованию свойств

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

Цель работы заключается в повышении эффективности и расширении области применения алгоритмов и вычислительных технологий1 решения невыпуклых задач параметрической идентификации динамических систем и траекторной оптимизации.

Поставленная цель достигается путем решения следующих задач:

1. Провести анализ современных методов и алгоритмов решения задач параметрической идентификации динамических моделей и оптимального управления.

2. Разработать модификации алгоритмов решения вспомогательных задач нелокального одномерного поиска, основанные на использовании условия Гёльдера и эвристических подходов.

3. Реализовать модификации поисковых алгоритмов решения многомерных задач невыпуклой оптимизации.

4. Разработать вычислительные технологии и специализированное программное обеспечение для решения невыпуклых задач параметрической идентификации динамических систем и оптимального управления.

1Множество алгоритмов, методов, программных реализаций математической модели, структур компьютерной обработки данных и методик расчетов понимается под вычислительной технологией (Ильин В.П. Вычислительно-информационные технологии математического моделирования // Автометрия. 2000. Т. 1. С. 3-16).

5. Оценить эффективность разработанных алгоритмов и вычислительных технологий на модельных, содержательных и прикладных задачах оптимизации.

Объект исследования. Оптимизационные проблемы, включающие задачи параметрической идентификации нелинейных динамических моделей и оптимального управления. Задачи параметрической идентификации заключаются в поиске значений параметров модели, позволяющих обеспечить ее близость к экспериментальным данным. Для этого используется вариационный подход -минимизируется некоторый показатель точности приближения, т.е. функция параметров динамической системы. Указанная задача вкладывается в задачу оптимального управления, если она решается путем сужения на класс кусочно-постоянных управлений (параметров), а терминальные и фазовые ограничения «снимаются» методами штрафов или модифицированных лагранжианов. Эта связь позволяет объединить в одном исследовании методы параметрической идентификации динамических систем с рядом методов решения задач оптимального управления.

Предмет исследования. Новые нелокальные алгоритмы параметрической идентификации динамических систем и траекторной оптимизации.

Научная новизна выполненного исследования заключается в следующем:

1. Разработаны модификации алгоритмов параметрической идентификации и динамической оптимизации, опирающиеся на использование предложенных методов одномерного глобального поиска, основанных на условии Гёльдера.

2. Разработаны двухметодные вычислительные схемы решения невыпуклых задач параметрической идентификации динамических систем и траекторной оптимизации на основе комбинации биоинспирированных алгоритмов и методов локального спуска.

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

4. Получены решения ряда прикладных оптимизационных задач из научно -

технических областей управления роботами, атомно-молекулярного

7

моделирования и экономики.

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

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

Практическая реализация результатов. С применением разработанных вычислительных технологий и программных средств проведено исследование ряда моделей атомно-молекулярных кластеров, в том числе потенциалов Морса, Гупты, Саттона-Чена сверхбольших размерностей. Найдены решения задач оптимального управления в робототехнических системах, нахождения равновесия анти-Бержа в биматричных играх.

Создано алгоритмическое и программное обеспечение для исследования проблемы параметрической идентификации модели динамики финансового развития Баргузинского района Республики Бурятия. Полученные методы решения указанной задачи были использованы в Институте экономики и организации промышленного производства СО РАН при разработке системы поддержки принятия решений в рамках Интеграционного проекта СО РАН № 66 «Подходы к разработке стратегий и программ социально-экономического развития сибирских регионов ресурсного типа с экстремальными природно-климатическими

условиями» Комплексной Программы фундаментальных исследований СО РАН «Междисциплинарные интеграционные исследования» на 2018-2020 гг.

Результаты, полученные в ходе выполнения работы, были использованы в трех проектах, поддержанных РФФИ: № 19-37-90065 «Алгоритмы идентификации нелинейных динамических моделей на основе методик обучения с подкреплением», № 18-07-00587 «Вычислительные технологии оптимизации для задач атомно-молекулярного моделирования и молекулярной динамики», №2 17-0700627 «Разработка алгоритмов поиска глобального экстремума функционалов на основе технологии машинного обучения с подкреплением».

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

Основные положения, выносимые на защиту:

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

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

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

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

5. Новые решения ряда задач оптимизации атомно-молекулярных кластеров

9

рекордных размерностей.

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

Апробация результатов работы. Основные положения и результаты работы докладывались и обсуждались на следующих научных конференциях:

• 8th, 9th, 10th International Workshop on Mathematical Models and their Applications (IWMMA) (Красноярск, Россия, 2019-2021 гг.);

• 9th, 11th, 12th International Conference on Optimization Methods and Applications (OPTIMA) (Петровац, Черногория, 2018, 2020, 2021 гг.);

• 14th International Conference on Evolutionary and Deterministic Methods for Design, Optimization and Control (EUROGEN-2021) (Афины, Греция, 2021 г.);

• International Conference «Geometric and Quantum Control» (Сочи, Россия, 2021 г.);

• International Conference on Mathematics and its Applications in New Computer Systems (MANCS) (Ставрополь, Россия, 2021 г.);

• 17th Baikal International School-Seminar «Methods of Optimization and Their Applications» (Максимиха, Бурятия, Россия, 2017 г.);

• 6th, 7th, 8th International Workshop «Critical Infrastructures in the Digital World» (IWCI) (Байкальск, Россия, 2019-2021 гг.);

• LXIII, LXIV Всероссийской научной конференции МФТИ (Москва, Россия, 2020, 2021 г.);

• VIII, X, XII Всероссийской научно-образовательной школе-конференции «Управление. Информация. Оптимизация» (Санкт-Петербург, Москва, Сочи, Россия, 2016, 2018, 2020 гг.);

• XX Всероссийской конференции с международным участием «Математические методы распознавания образов» (ММРО-2021) (Москва, Россия, 2021 г.);

• XIII Международной конференции «Интеллектуализация обработки информации» (ИОИ-2020) (Москва, Россия, 2020 г.);

• LI Всероссийской молодежной школе-конференции «Современные проблемы математики и ее приложений» (Екатеринбург, Россия, 2020 г.);

• XXII Международном молодежном научном форуме «Ломоносов-2015» (Москва, Россия, 2015 г.);

• VIII Международной конференции «Системный анализ и информационные технологии» (САИТ-2019) (Иркутск, Россия, 2019 г.);

• VI Международной школе-семинаре «Нелинейный анализ и экстремальные задачи» (NLA-2018) (Иркутск, Россия, 2018 г.);

• X, XII Международной молодежной конференции «Прикладная математика и фундаментальная информатика» (Омск, Россия, 2020, 2022 гг.);

• XXV Байкальской Всероссийской конференции с международным участием «Информационные и математические технологии в науке и управлении» (Иркутск, Россия, 2020 г.);

• XIII Всероссийской конференции молодых ученых «Моделирование, оптимизация и информационные технологии» (Иркутск, Россия, 2017 г.);

• XXXШ-XXXVП Всероссийской конференции «Ляпуновские чтения» (Иркутск, Россия, 2017-2021 гг.) и др.

Результаты работы также обсуждались на семинаре в ФИЦ «Информатика и управление» РАН (Москва, рук. М.А. Посыпкин), семинаре лаборатории «Математические модели в геоэкологии» Сибирского федерального университета (Красноярск, рук. К.В. Симонов), семинарах ИДСТУ СО РАН.

Публикации. По материалам диссертационной работы опубликовано более 50 работ. Список основных публикаций приведен в конце автореферата. В число указанных работ входят 3 статьи, опубликованные в российских рецензируемых

периодических изданиях, рекомендуемых ВАК РФ для опубликования основных научных результатов диссертационных исследований, 9 статей в зарубежных изданиях, включенных в международную базу цитирования Scopus, 5 статей в зарубежных изданиях, включенных в международную базу цитирования Web of Science.

Соответствие диссертации паспорту специальности. В соответствии с областью исследований и паспортом специальности 2.3.1 в диссертационной работе предложены численные методы решения многоэкстремальных задач оптимизации (п. 4), на основе которых разработаны вычислительные технологии исследования задач параметрической идентификации нелинейных динамических моделей (п. 7). Создано специализированное алгоритмическое и программное обеспечение для решения исследуемых оптимизационных задач (п. 5).

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

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, приложений и списка литературы из 199 источников. Объем работы без учета приложений составляет 176 страниц, общий объем работы - 262 страницы. В тексте содержится 63 таблицы и 133 рисунка.

ГЛАВА 1. АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ

1.1. Классификация конечномерных задач оптимизации

и методов их решения

Под задачей оптимизации в физико-математических и технических науках понимается проблема поиска оптимума целевой функции в определенной области векторного пространства конечной размерности. Оптимизационные задачи возникают и решаются повсеместно, везде, где необходимо найти наилучшее решение в допустимой области, определяемой набором ограничений в виде равенств или неравенств.

В настоящее время специалистами предложено значительное количество различных оптимизационных методов. Ниже представлена классификация методов оптимизации в соответствии с исследуемой задачей.

• По характеру искомого решения: методы локальной / глобальной оптимизации (сходятся к локальному / глобальному оптимуму целевой функции соответственно).

• По наличию ограничений на оптимизируемые переменные: методы безусловной / условной оптимизации (ограничения отсутствуют / присутствуют).

• По характеру поиска: детерминированные / стохастические методы. В первых экстремум ищется с помощью процедуры, в которой заранее определены конкретные шаги и отсутствует элемент случайности. В отличие от детерминированных методов, в стохастические (методы случайного поиска) намеренно вводится элемент случайности в оптимизационные шаги. Присущие случайному поиску такие качества, как простота реализации, наглядность описания, повышенное быстродействие (особенно при большой размерности решаемой задачи), нечувствительность к «ловушкам» оптимизируемой функции и т.п., делают его наиболее предпочтительным для решения задач большой размерности [199].

• По критерию размерности допустимого множества: методы одномерной / многомерной оптимизации.

• По виду целевой функции: методы линейного / нелинейного программирования. Методы нелинейного программирования в свою очередь делятся на методы выпуклой, невыпуклой и целочисленной (дискретной) оптимизации.

• По способу оптимизации: аналитические / численные / графические методы.

• По классу алгоритма: пассивные / последовательные методы.

• По числу предыдущих учитываемых шагов: одношаговые / многошаговые методы.

• По количеству поисковых агентов: одноточечные (одноагентные) / многоточечные (многоагентные) методы.

• По степени математической обоснованности: рациональные / эвристические методы.

• По числу оптимизируемых целевых функций: методы однокритериальной /многокритериальной оптимизации.

• По типу поиска: траекторные / популяционные методы.

• По порядку используемых производных: методы нулевого / к -го порядка (к > 0).

В работе рассматривается наиболее общая задача непрерывной невыпуклой оптимизации с прямыми (параллелепипедными) ограничениями:

f (xmin, x е B, B = jx | x = (x1,x2,...,xn), x - X - X, i = 1,nj.

1.2. Численные методы локального поиска

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

Пусть целевая функция / (х) дифференцируема на всем пространстве

поиска. Тогда можно вычислить градиент функции V/(х) в любой точке х. В

методе градиентного спуска, начиная с некоторого начального приближения х0, строится итерационная последовательность вида

*+1 = хк -укV/(хк), (1.3)

где параметр ук> 0 - длина шага. Таким образом, минимизация функции осуществляется в направлении наискорейшего спуска, которое задается антиградиентом -V/ (х).

Критерии останова итерационного процесса данного алгоритма и других методов выбираются на основе различных соображений. Например, критерии могут быть следующими: хк+1 -хк <е или /(хк+1) - /(хк) <£, где £> 0 -

некоторое заданное число.

К достоинствам метода градиентного спуска можно отнести простоту вычислений, слабые требования к целевой функции /(х) и гарантированную локальную сходимость (при оптимальном выборе длины шага ук). К сожалению, данный метод имеет несколько существенных недостатков: низкая скорость сходимости и необходимость выбора длины шага ук.

Легко видеть, что основной идеей метода градиентного спуска является построение линейной аппроксимации целевой функции /(х). Пусть функция дважды дифференцируема. Тогда в любой точке х можно вычислить не только градиент функции V/(х), но и матрицу вторых производных V2/(х) (матрицу Гессе). Значит, возможно построить квадратичную аппроксимацию /(х). На указанной идее основан простейший градиентный метод второго порядка - метод Ньютона. В этом методе строится следующая итерационная последовательность:

-1

хк+1 = хк - [V2/(хк)]- V/(xk). (1.4)

Достоинствами данного алгоритма являются быстрая сходимость (по сравнению с методом градиентного спуска), сохранение работоспособности при овражном характере / (х) и отсутствие настраиваемых параметров. Однако метод Ньютона имеет следующие недостатки: требовательность к хорошему начальному приближению, жесткие требования к целевой функции, большой объем вычислений [45].

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

При реализации метода градиентного спуска (1.3) возникает важный вопрос выбора длины шага ук. Очевидной идеей является прохождение до минимума по направлению антиградиента. На этой идее основана известная модификация метода градиентного спуска - метод наискорейшего спуска:

П = агвтт^ ^,

/>0

(1.5)

срк (Г) = /(хк (/)).

Таким образом, в данном алгоритме на каждой итерации решается вспомогательная задача одномерной минимизации.

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

Еще один способ выбора длины шага у основан на его дроблении, то есть в процессе градиентного спуска длина шага делится на некоторое число. В этом алгоритме сначала выбирается некоторый начальный шаг у и задаются следующие параметры: 0<£< 1, 0<а< 1. На каждой итерации алгоритма происходит

Если оно выполняется, то осуществляется градиентный спуск (1.3). В противном случае происходит дробление шага, то есть у заменяется на ау и снова повторяется проверка неравенства (1.6). Разумеется, метод градиентного спуска с дроблением шага представляет собой лишь еще один способ выбора длины шага ук и не в состоянии добиться более быстрой сходимости, чем базовый метод.

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

Рассмотрим теперь способы улучшения метода Ньютона. Одним из недостатков данного алгоритма является его требовательность к хорошему начальному приближению. Справиться с этой проблемой может регулировка длины шага. Таким образом, мы получаем так называемый демпфированный метод Ньютона:

Разумеется, длину шага можно выбирать теми же способами, что и описанными выше. Например, наискорейшим спуском:

вычисление /(хк - у//(хк)) и проверка условия выполнения следующего неравенства:

(1.6)

(1.7)

Ук = а^тт^ (у),

(1.8)

Рк (у) = /(хк -у\у2/(хк)]-1 V/(хк))

Длина шага также может дробиться подобно методу градиентного спуска с дроблением шага до выполнения одного из неравенств (на выбор):

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

Существует также другая, более удачная, модификация метода Ньютона -метод Левенберга-Марквардта. В этом алгоритме в сравнении с методом Ньютона направление движения несколько иное. Его идея заключается в добавлении квадратичного штрафа за отклонение от точки хк к аппроксимирующей функции. В результате получаем итерационный процесс вида:

где ак> 0 - параметр, I - единичная матрица.

Ясно, что при ак= 0 алгоритм становится методом Ньютона, а при ак^ю направление движения стремится к антиградиенту. Метод Левенберга-Марквардта является компромиссным вариантом между этими двумя крайностями. При оптимальном выборе ак метод глобально сходится для квадратичной функции.

Метод (1.11) хорош тем, что он пригоден не только для выпуклых функций, в отличие от демпфированного метода Ньютона (1.7).

Таким образом, вышеописанные модификации метода Ньютона улучшают базовый метод, но требуют достаточно большого объема вычислений.

/(хк+1) < /(хк) - уд ([V2/(хк)]-1 V/(хк), V/(хк)), (1.9)

хк+1)2 < (1 -уд) V/( хк )2, 0 < д < 1. (1.10)

хк+1 = хк -(V2/(хк) + ак1 )-1 V/(хк),

(111)

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

В методе градиентного спуска и его простых модификациях на каждом шаге мы никак не используем ту информацию, которую получили на предыдущих итерациях. Значит, можно попытаться ускорить сходимость алгоритмов, учитывая «предысторию» итерационного процесса. Подобные алгоритмы, в которых каждое новое приближение зависит от к предыдущих, называются к -шаговыми. Легко видеть, что метод градиентного спуска, метод Ньютона и их модификации являются одношаговыми (к = 1). В этом пункте будем рассматривать многошаговые методы (к > 1).

Самым простым многошаговым алгоритмом является двухшаговый метод тяжелого шарика:

X+1 = X - аУ/ (X) + Д( X - X-1), (1.12)

где а > 0, Д > 0 - параметры алгоритма. Очевидно, что при Д = 0 мы получаем метод градиентного спуска.

Название данного алгоритма объясняется определенной физической аналогией. При наличии силы трения траектория движения физического тела (тяжелого шарика) в потенциальном поле определяется дифференциальным уравнением второго порядка:

п

М^ = -У(х(0)-р^. (1.13)

ж &

Очевидно, что в итоге тело сдвинется в точку минимума потенциала / (х) в связи с потерей энергии на трении. Следовательно, тяжелый шарик решает оптимизационную задачу. Рассматривая разностный аналог уравнения (1.13), получаем итерационный процесс (1.12).

Список литературы диссертационного исследования кандидат наук Сороковиков Павел Сергеевич, 2022 год

СПИСОК ЛИТЕРАТУРЫ

1. Аникин, А.С. Архитектура и функциональное наполнение программного комплекса ОРТСО^М для задач оптимизации потенциалов атомно-молекулярных кластеров / А.С. Аникин, А.Ю. Горнов, А.Н. Андрианов // Труды XVIII Байкальской всероссийской конференции «Информационные и математические технологии в науке и управлении». Ч. III. - Иркутск: ИСЭМ СО РАН, 2013. -С. 213-219.

2. Беллман, Р. Динамические программирование / Р. Беллман. - М.: Наука, 1976. - 352 с.

3. Беллман, Р. Динамические программирование и современная теория управления / Р. Беллман, Р. Калаба. - М.: Наука, 1969. - 118 с.

4. Бертсекас, Д. Условная оптимизация и методы множителей Лагранжа / Д. Бертсекас. - М.: Радио и связь, 1987. - 400 с.

5. Брестер, К.Ю. О применении эволюционных алгоритмов при анализе больших данных / К.Ю. Брестер, В.В. Становов, О.Э. Семенкина, Е.С. Семенкин // Искусственный интеллект и принятие решений. - 2017. - №. 3. - С. 82-93.

6. Булатов, В.П. Метод отсечения в ЕАп+1 для решения задач глобальной оптимизации на одном классе функций / В.П. Булатов, О.В. Хамисов // Журнал вычислительной математики и математической физики. - 2007. - Т. 47, № 11. -С. 1830-1842.

7. Васильев, Ф.П. Методы оптимизации: учебник для вузов: в 2-х кн. / Ф.П. Васильев. - М.: МЦНМО, 2011. - Кн. 1: Конечномерные задачи оптимизации. Принцип максимума. Динамическое программирование. - 620 с.

8. Габасов, Р. Пакет прикладных программ «Математическое программирование многомерных задач» / Р. Габасов, А.И. Тятюшкин, А.И. Жолудев, Н.М. Эринчек // Алгоритмы и программы: Инф. Бюлл. -М.: ВНТИЦ. - 1986. - № 2 (71). - 33 с.

9. Гергель, В.П. Многомерная многоэкстремальная оптимизация на основе адаптивной многошаговой редукции размерности / В.П. Гергель, В.А. Гришагин,

A.В. Гергель // Вестник Нижегородского университета им. Н.И. Лобачевского. -2010. - № 1. - С. 163-170.

10. Горнов, А.Ю. Вычислительные технологии решения задач оптимального управления / А.Ю. Горнов. - Новосибирск: Наука, 2009. - 278 с.

11. Горнов, А.Ю. Комплекс программ OPTCON для решения задач оптимального управления / А.Ю. Горнов, А.О. Диваков // Руководство пользователя. - Иркутск: ИрВЦ СО РАН, 1990. - 36 с.

12. Горнов, А.Ю. Применение сплайн-аппроксимации для конструирования алгоритмов оптимизации с новыми вычислительными свойствами / А.Ю. Горнов // Труды всеросс. конф. «Дискретная оптимизация и исследование операций». -Владивосток, 2007. - С. 99.

13. Горнов, А.Ю. Рейдер-метод для квазисепарабельных задач безусловной оптимизации / А.Ю. Горнов // Материалы конференции «Ляпуновские чтения» (Иркутск, 3-5 декабря 2018 г.). - Иркутск: ИДСТУ СО РАН, 2018. - С. 28.

14. Горнов, А.Ю. Метод криволинейного поиска глобального экстремума в задаче оптимального управления / А.Ю. Горнов, Т.С. Зароднюк // Современные технологии. Системный анализ. Моделирование. - 2009. - №. 3. - С. 19-27.

15. Горнов, А.Ю. Метод случайных покрытий для задачи оптимального управления / А.Ю. Горнов, Т.С. Зароднюк // Вычислительные технологии. - 2012. - Т. 17. - №. 2. - С. 31-42.

16. Горнов, А.Ю. Численное решение задач оптимального управления в пакетном режиме / А.Ю. Горнов, А.И. Жолудев, А.И. Тятюшкин, Н.М. Эринчек // Пакеты прикладных программ. Опыт разработки. - Новосибирск: Наука, 1983. -С. 3-17.

17. Грачев, Н.И. Решение задач оптимального управления в системе ДИСО / Н.И. Грачев, А.Н. Фильков. - М.: ВЦ АН СССР, 1986. - 67 с.

18. Гурман, В.И. Приближенные методы оптимального управления /

B.И. Гурман, В.А. Батурин, И.В. Расина. - Иркутск: Изд-во Иркутского гос. ун-та, 1983. - 178 с.

19. Демьянов, В.Ф. Введение в минимакс / В.Ф. Демьянов, В.Н. Малоземов. - М.: Наука, 1972. - 368 с.

20. Демьянов, В.Ф. Приближенные методы решения экстремальных задач /

B.Ф. Демьянов, А.М. Рубинов. - Ленинград: Изд-во ЛГУ, 1968. - 180 с.

21. Дивеев, А.И. Исследование эволюционных алгоритмов для решения задачи оптимального управления / А.И. Дивеев, С.В. Константинов // Труды Московского физико-технического института. - 2017. - Т. 9, № 3. - С. 76-85.

22. Дыхта, В.А. Некоторые приложения неравенств Гамильтона-Якоби в оптимальном управлении / В.А. Дыхта // Известия Иркутского государственного университета. Серия: Математика. - 2009. - №. 1. - С. 183-196.

23. Евтушенко, Ю.Г. Диалоговый комплекс ДИСО / Ю.Г. Евтушенко, О.П. Бурдаков, А.И. Голиков, В.Г. Жадан, М.А. Потапов // Раздел нелинейного программирования (версия 2). - М.: ВЦ АН СССР, 1982. - 88 с.

24. Евтушенко, Ю.Г. Методы поиска глобального экстремума / Ю.Г. Евтушенко // Исследование операций, вып.4. - М.: ВЦ АН СССР, 1974. -

C. 39-68.

25. Евтушенко, Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации / Ю.Г. Евтушенко. - М.: Наука, 1982. - 432 с.

26. Жиглявский, А.А. Математическая теория случайного глобального поиска / А.А. Жиглявский. - Ленинград: Издательство Ленинградского университета, 1985. - 296 с.

27. Жиглявский, А.А. Методы поиска глобального экстремума / А.А. Жиглявский, А.Г. Жилинскас. - М.: Наука, 1991. - 248 с.

28. Жолудев, А.И. Численные методы оптимизации управляемых систем / А.И. Жолудев, А.И. Тятюшкин, Н.М. Эринчек // Известия АН СССР. Техническая кибернетика. - 1989. - № 4. - С. 14-31.

29. Зароднюк, Т.С. Технология поиска глобального экстремума в задаче оптимального управления / Т.С. Зароднюк, А.Ю. Горнов // Современные технологии. Системный анализ. Моделирование. - 2008. - № 3. - С. 70-76.

30. Карпенко, А.П. Основные сущности популяционных алгоритмов глобальной оптимизации. Опыт систематизации / А.П. Карпенко // Вестник евразийской науки. - 2017. - Т. 9. - №. 6 (43).

31. Карпенко, А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой / А.П. Карпенко. - М.: Изд-во МГГУ им. Н.Э. Баумана, 2014. - 446 с.

32. Карпенко, А.П. Эволюционные операторы популяционных алгоритмов глобальной оптимизации. Опыт систематизации / А.П. Карпенко // Математика и математическое моделирование. - 2018. - №. 1. - С. 59-89.

33. Ковалев, И.В. Использование метода роя частиц для формирования состава мультиверсионного программного обеспечения / И.В. Ковалев, Е.В. Соловьев, Д.И. Ковалев, К.К. Бахмарева, А.В. Демиш // Приборы и системы. Управление, контроль, диагностика. - 2013. - №. 3. - С. 1-6.

34. Кротов, В.Ф. Вычислительные алгоритмы решения и оптимизации управляемых систем уравнений. Ч. 1, 2 / В.Ф. Кротов // Известия АН СССР. Техническая кибернетика. - 1975. - № 5. - С. 3-15; № 6. - С. 3-13.

35. Левин, А.Ю. Об алгоритме минимизации выпуклых функций / А.Ю. Левин // ДАН СССР. - 1965. - Т. 160. - № 6. - С. 1244-1247.

36. Левитин, Е.С. Методы минимизации при наличии ограничений / Е.С. Левитин, Б.Т. Поляк // Журнал вычислительной математики и математической физики. - 1966. - Т. 6. - №. 5. - С. 787-823.

37. Лопатин, А.С. Метод отжига / А.С. Лопатин // Стохастическая оптимизация в информатике. - 2005. - Т. 1. - №. 1. - С. 133-139.

38. Немировский, А.С. Сложность задач и эффективность методов оптимизации / А.С. Немировский, Д.Б. Юдин. - М.: Наука, 1979. - 384 с.

39. Нестеров, Ю.Е. Введение в выпуклую оптимизацию / Ю.Е. Нестеров. -М.: МЦНМО, 2010. - 280 с.

40. Нестеров, Ю.Е. Эффективные методы в нелинейном программировании / Ю.Е. Нестеров. - М.: Радио и связь, 1989. - 301 с.

41. Норкин, В.И. О методе Пиявского для решения общей задачи глобальной оптимизации / В.И. Норкин // Журнал вычислительной математики и математической физики. - 1992. - Т. 32, № 7. - С. 992-1006.

42. Пантелеев, А.В. Метаэвристические алгоритмы глобальной оптимизации / А.В. Пантелеев, Д.В. Скавинская. - М.: Вузовская книга, 2019. - 332 с.

43. Пестерев, А.В. Синтез линеаризующего управления в задаче стабилизации движения автомобилеподобного робота вдоль криволинейного пути / А.В Пестерев // Известия РАН. Теория и системы управления. - 2013. - № 5. -С. 153-165.

44. Пиявский, С.А. Один алгоритм отыскания абсолютного экстремума функций / С.А. Пиявский // Журнал вычислительной математики и математической физики. - 1972. - Т.12. - С. 885-896.

45. Поляк, Б.Т. Введение в оптимизацию. 2-е изд. / Б.Т. Поляк. - М.: Ленанд, 2014. - 392 с.

46. Понтрягин, Л.С. Математическая теория оптимальных процессов / Л.С. Понтрягин, В.Г. Болтянский, Р.В. Гамкрелидзе, Е.В. Мищенко. - М.: Наука, 1961. - 384 с.

47. Попов, В.С. Комплекс программ для приближенного решения задач оптимального управления (описание применения) / В.С. Попов, Р.П. Федоренко. -М.: ИПМ АН СССР, 1984. - 56 с.

48. Рапопорт, Л.Б. Оценка области притяжения в задаче управления колесным роботом / Л.Б Рапопорт // Автоматика и телемеханика. - 2006. - №9. -С. 69-89.

49. Растригин, Л.А. Адаптация сложных систем / Л.А. Растригин. - Рига: Зинатне, 1981. - 386 с.

50. Растригин, Л.А. Системы экстремального управления / Л.А. Растригин. -М.: Наука, 1974. - 632 с.

51. Семенкин, Е.С. Самоконфигурируемые эволюционные алгоритмы моделирования и оптимизации: монография / Е.С. Семенкин, М.Е. Семенкина. -Магнитогорск: [б. и.], 2014. - 309 с.

52. Семенкин, Е.С. Эволюционные методы моделирования и оптимизации сложных систем / Е.С. Семенкин, М.Н. Жукова, В.Г. Жуков, И.А. Панфилов, В.В. Тынченко. - Красноярск: Сибирский федеральный университет, 2007. - 310 с.

53. Сергеев, Я.Д. Диагональные методы глобальной оптимизации / Я.Д. Сергеев, Д.Е. Квасов. - М.: Физматлит, 2008. - 352 с.

54. Стрекаловский, А.С. Элементы невыпуклой оптимизации /

A.С. Стрекаловский. - Новосибирск: Наука, 2003. - 356 с.

55. Стронгин, Р.Г. Параллельные вычисления в задачах глобальной оптимизации / Р.Г. Стронгин, В.П. Гергель, В.А. Гришагин, К.А. Баркалов. -М.: Издательство Московского университета, 2013. - 280 а

56. Стронгин, Р.Г. Численные методы в многоэкстремальных задачах (информационно-статистические алгоритмы) / Р.Г. Стронгин. - М.: Наука, 1978. -240 с.

57. Сухарев, А.Г. Курс методов оптимизации / А.Г. Сухарев, А.В. Тимохов,

B.В. Федоров. - М.: Физматлит, 2005. - 368 а

58. Толстоногов, А.А. Дифференциальные включения в банаховом пространстве / А.А. Толстоногов. - Новосибирск: Наука, 1986. - 295 с.

59. Тятюшкин, А.И. ППП КОНУС для оптимизации непрерывных управляемых систем / А.И. Тятюшкин // Пакеты прикладных программ: Опыт использования. - М.: Наука, 1989. - С. 63-83.

60. Тятюшкин, А.И. Численные методы и программные средства оптимизации управляемых систем / А.И. Тятюшкин. - Новосибирск: Наука, 1992. - 193 с.

61. Федоренко, Р.П. Приближенное решение задач оптимального управления / Р.П. Федоренко. - М.: Наука, 1978. - 488 с.

62. Фихтенгольц, Г.М. Курс дифференциального и интегрального исчисления. Т. 1 / Г.М. Фихтенгольц. - М.: Физматлит, 2001. - 616 с.

63. Форсайт, Д. Машинные методы математических вычислений / Д. Форсайт, М. Малькольм, К. Моулер. - М.: Мир, 1980. - 279 с.

64. Хачиян, Л.Г. Полиномиальный алгоритм в линейном программировании / Л.Г. Хачиян // ДАН СССР. - 1979. - Т. 244. - № 5. - С. 1093-1096.

65. Химмельблау, Д. Прикладное нелинейное программирование / Д. Химмельблау. - М.: Мир, 1975. - 534 с.

66. Черноруцкий, И.Г. Методы оптимизации. Компьютерные технологии / И.Г. Черноруцкий. - СПб.: БХВ-Петербург, 2011. - 384 с.

67. Черноусько, Ф.Л. Вариационные задачи механики и управления / Ф.Л. Черноусько, В.П. Баничук. - М.: Наука, 1973. - 236 с.

68. Шарый, С.П. Конечномерный интервальный анализ / С.П. Шарый -Новосибирск: ИВТ СО РАН, 2010. - 700 с.

69. Шор, Н.З. Методы отсечения с растяжением пространства для решения задач выпуклого программирования / Н.З. Шор // Кибернетика. -1977. - № 1. -

C. 42-50.

70. Юдин, Д.Б. Информационная сложность и эффективные методы решения выпуклых экстремальных задач / Д.Б. Юдин, А.С. Немировский // Экономика и мат. методы. - 1976. - Т. 12. - № 2. - С. 357-369.

71. Adorio, E.P. MVF-multivariate test functions library in C for unconstrained global optimization / E.P. Adorio. - Quezon City: U.P. Diliman, 2005. - 56 p.

72. Ali, M.M. A numerical evaluation of several stochastic algorithms on selected continuous global optimization test problems / M.M. Ali, C. Khompatraporn, Z.B. Zabinsky // Journal of global optimization. - 2005. - Vol. 31. - N 4. - P. 635-672.

73. Andersson, J.A.E. CasADi: a software framework for nonlinear optimization and optimal control / J.A.E. Andersson //Mathematical Programming Computation. -2019. - Т. 11. - №. 1. - P. 1-36.

74. Ashlock, D. Evolutionary computation for modeling and optimization /

D. Ashlock. - New York: Springer-Verlag, 2006. - 571 p.

75. Back, T. Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms / T. Back. - Oxford university press, 1996.

76. Becerra, V.M. Solving complex optimal control problems at no cost with PSOPT / V.M. Becerra // 2010 IEEE International Symposium on Computer-Aided Control System Design. - IEEE, 2010. - P. 1391-1396.

77. Beiranvand, V. Best practices for comparing optimization algorithms / V. Beiranvand, W. Hare, Y. Lucet // Optimization and Engineering. - 2017. - Vol. 18, No. 4. - P. 815-848.

78. Bertsekas, D.P. Convex optimization algorithms / D.P. Bertsekas. - Belmont: Athena Scientific, 2015. - 576 p.

79. Bertsekas, D.P. Reinforcement learning and optimal control / D.P. Bertsekas.

- Belmont: Athena Scientific, 2019. - 388 p.

80. Betts, J.T. Practical methods for optimal control and estimation using nonlinear programming / J.T. Betts. - Philadelphia: Society for Industrial and Applied Mathematics, 2010. - 434 p.

81. Betts, J.T. Sparse optimal control software SOCS / J.T. Betts, W.P. Huffman // Mathematics and Engineering Analysis Technical Document MEA-LR-085, Boeing Information and Support Services, The Boeing Company, PO Box. - 1997. - Vol. 3707.

- P. 98124-2207.

82. Birbil, §.L An electromagnetism-like mechanism for global optimization / §.I. Birbil, S.C. Fang // Journal of global optimization. 2003. Vol. 25. No. 3. P. 263-282.

83. Blatt, M. PDECON: A FORTRAN code for solving control problems based on ordinary, algebraic and partial differential equations / M. Blatt, K. Schittkowski // Technical report Dep. of Mathematics, University of Bayreuth. - 1997.

84. Boyd, S.P. Convex optimization / S.P. Boyd, L. Vandenberghe. - Cambridge: Cambridge University Press, 2010. - 716 p.

85. Bradtke, S.J. Learning to predict by the method of temporal differences / S.J. Bradtke, A.G. Barto // Machine Learning. - 1996. - Vol. 22. - P. 33-57.

86. Brauer, G.L., Cornick D.E., Stevenson R. Capabilities and applications of the Program to Optimize Simulated Trajectories (POST). Program summary document / G.L. Brauer, D.E. Cornick, R. Stevenson. - 1977.

87. Brent, R.P. Algorithms for minimization without derivatives / R.P. Brent. -New Jersey: Prentice Hall, 1973. - 195 p.

88. Brooks, R.L. The Fundamentals of Atomic and Molecular Physics / R.L. Brooks. - New York: Springer, 2013. - 179 p.

89. Bubeck, S. Convex optimization: Algorithms and complexity / S. Bubeck // Foundations and Trends® in Machine Learning. - 2015. - Vol. 8. - N 3-4. - P. 231-357.

90. Calvin, J.M. On convergence of the P-algorithm for one-dimensional global optimization of smooth functions / J.M. Calvin, A. Zilinskas // Journal of Optimization Theory and Applications. - 1999. - Vol. 102, N 3. - P. 479-495.

91. Chu, S.C. Cat swarm optimization / S.C. Chu, P.W. Tsai, J.S. Pan // Pacific Rim International Conference on Artificial Intelligence. Springer Berlin Heidelberg. 2006. P. 854-858

92. Clerc, M. The particle swarm-explosion, stability, and convergence in a multidimensional complex space / M. Clerc, J. Kennedy // IEEE transactions on Evolutionary Computation. - 2002. - Vol. 6. - N 1. - P. 58-73.

93. Coello, C.A.C. Evolutionary multiobjective optimization using a cultural algorithm / C.A.C. Coello, R.L. Becerra // Swarm Intelligence Symposium, 2003. SIS'03. Proceedings of the 2003 IEEE. - IEEE, 2003. - P. 6-13.

94. Cormen, T.H. et al. Introduction to algorithms / T.H. Cormen. 3rd ed. Cambridge, Mass: MIT Press, 2009. 1292 p.

95. Cruz, I.L.L. Efficient evolutionary algorithms for optimal control / I.L.L. Cruz. Wageningen Univ., Netherlands, 2002. - 122 p.

96. Dai, Y.H. A nonlinear conjugate gradient method with a strong global convergence property / Y.H. Dai, Y. Yuan // SIAM Journal on optimization. - 1999. -Vol. 10. - N 1. - P. 177-182.

97. Deisenroth, M.P. A survey on policy search for robotics / M.P. Deisenroth // Foundations and Trends® in Robotics. - 2013. - Vol. 2. - N 1. - P. 1-142.

98. Dieterich, J.M. Empirical review of standard benchmark functions using evolutionary global optimization / J.M. Dieterich, B. Hartke // Applied Mathematics. -2012. - Vol. 3, N 10A. - P. 1552-1564.

99. Ding, K. A CUDA-Based Real Parameter Optimization Benchmark / K. Ding, Y. Tan // Advances in Swarm Intelligence: 5th International Conference. Part II. - 2014.

- P. 66-78.

100. Dorigo, M. Ant colony optimization / M. Dorigo, M. Birattari. Springer US. 2010. P. 36-39

101. Doye, J.P.K. Global minima for transition metal clusters described by Sutton-Chen potentials / J.P.K. Doye, D.J. Wales // New journal of chemistry. - 1998. - Vol. 22, No. 7. - P. 733-744.

102. Doye, J.P.K. Structural consequences of the range of the interatomic potential a menagerie of clusters / J.P.K. Doye, D.J. Wales // Journal of the Chemical Society, Faraday Transactions. - 1997. - Vol. 93, N 24. - P. 4233-4243.

103. Falugi, P. Imperial college London optimal control software user guide (ICLOCS) / P. Falugi, E. Kerrigan, E. Van Wyk // Department of Electrical and Electronic Engineering, Imperial College London, London, England, UK. - 2010. -Vol. 28.

104. Fletcher, R. Function minimization by conjugate gradients / R. Fletcher, C.M. Reeves // The computer journal. - 1964. - Vol. 7. - N 2. - P. 149-154.

105. Floudas, C.A. A review of recent advances in global optimization / C.A. Floudas, C.E. Gounaris // Journal of Global Optimization. - 2009. - Vol. 45. - N 1.

- P. 3.

106. Floudas, C.A. Encyclopedia of optimization / C.A. Floudas, P.M. Pardalos. -Springer Science & Business Media, 2008.

107. Floudas, C.A. Handbook of test problems in local and global optimization / C.A. Floudas et al. - Springer Science & Business Media, 2013. - 441 p.

108. Galperin, E.A. The cubic algorithm / E.A. Galperin // Journal of Mathematical Analysis and Applications. - 1985. - Vol. 112, N 2. - P. 635-640.

109. Gavana, A. Global optimization benchmarks and AMPGO [Electronic resourse] / A. Gavana. - Режим доступа : http://infinity77.net/global optimization/, свободный.

110. Geem, Z.W. A new heuristic optimization algorithm: harmony search / Z.W. Geem, J.H. Kim, G.V. Loganathan // Simulation. - 2001. - Vol. 76, N 2. - P. 6068.

111. Gerdts, M. User's guide OC-ODE (version 1.4) / M. Gerdts. - Technical report, Universität Würzburg, 2009.

112. Gergel, V.P. A global optimization algorithm for multivariate functions with Lipschitzian first derivatives / V.P. Gergel // Journal of Global Optimization. - 1997. -Vol. 10, No. 3. - P. 257-281.

113. Glover, F. Tabu search: A tutorial / F. Glover // Interfaces. - 1990. - Vol. 20, N 4. - P. 74-94.

114. Gornov, A.Y. Optimal control problem: Heuristic algorithm for global minimum / A.Y. Gornov, T.S. Zarodnuk // Proc. of the Second Intern. Conf. on Optimization and Control. Ulanbaatar, Mongolia. - 2007. - P. 27-28.

115. Goryachih, A. A Class of Smooth Modification of Space-Filling Curves for Global Optimization Problems / A. Goryachih // Models, Algorithms, and Technologies for Network Analysis. - 2016. - P. 57-65.

116. Gosavi, A. Simulation-based optimization / A. Gosavi et al. - Berlin: Springer, 2015.

117. Gupta, R.P. Lattice relaxation at a metal surface / R.P. Gupta // Physical Review B. - 1981. - Vol. 23, N 12. - P. 6265-6270.

118. Hansen, N. The CMA evolution strategy: A tutorial / N. Hansen // arXiv preprint arXiv: 1604.00772. - 2016.

119. Hansen, P. Global optimization of univariate Lipschitz functions: I. Survey and properties / P. Hansen, B. Jaumard, S.H. Lu // Mathematical programming. - 1992. - Vol. 55, N 1. - P. 251-272.

120. Hedar, A.R. Global optimization test problems [Electronic resourse] / A.R. Hedar. - Режим доступа : http://www-optima.amp.i.kyoto-u.ac.jp/member/student/hedar/Hedar files/TestGO.htm, свободный.

121. Hestenes, M.R. Methods of conjugate gradients for solving linear systems /

M.R. Hestenes, E. Stiefel. - NBS, 1952. - Vol. 49. - P. 1.

169

122. Hirmajer T., Balsa-Canto E., Banga J.R. DOTcvpSB, a software toolbox for dynamic optimization in systems biology / T. Hirmajer, E. Balsa-Canto, J.R. Banga // BMC bioinformatics. - 2009. - T. 10. - №. 1. - C. 1-14.

123. Horst, R. Handbook of global optimization / R. Horst, P.M. Pardalos. -New York: Springer, 2013. - 880 p.

124. Hughes, S. GMAT-Generalized Mission Analysis Tool / S. Hughes // NASA Goddard Space Flight Center, Greenbelt, MD. - 2008.

125. Jaksch, T. Near-optimal regret bounds for reinforcement learning / T. Jaksch, R. Ortner, P. Auer // Journal of Machine Learning Research. - 2010. - Vol. 11. - N Apr.

- P. 1563-1600.

126. Jamil, M. A literature survey of benchmark functions for global optimisation problems / M. Jamil, X.S. Yang // International Journal of Mathematical Modelling and Numerical Optimisation. - 2013. - Vol. 4, N 2. - P. 150-194.

127. Jie, J. An extended mind evolutionary computation model for optimizations / J. Jie, J. Zeng, C. Han // Applied Mathematics and Computation. 2007. Vol. 185. No. 2. P. 1038-1049.

128. Kaelbling, L.P. Reinforcement learning: A survey / L.P. Kaelbling, M.L. Littman, A.W. Moore // Journal of artificial intelligence research. - 1996. - Vol. 4.

- P. 237-285.

129. Karmarkar, N. A new polynomial-time algorithm for linear programming / N. Karmarkar // Combinatorica. - 1984. - № 4. - P. 373-395.

130. Kennedy, J. Particle swarm optimization / J. Kennedy // Encyclopedia of machine learning. - 2011. - P. 760-766.

131. Khamisov, O.V. Univariate global optimization with point-dependent Lipschitz constants / O.V. Khamisov, M. Posypkin // AIP Conference Proceedings. - AIP Publishing LLC, 2019. - Vol. 2070. - No. 1. - P. 020051.

132. Kirkpatrick, S. Optimization by simulated annealing / S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi // Science. - 1983. - Vol. 220. - N 4598. - P. 671-680.

133. Krotov, V. Global methods in optimal control theory / V. Krotov. - CRC Press, 1995. - Vol. 195.

134. Kühl, P. Muscod-ii users manual / P. Kühl // University of Heidelberg. - 2007.

135. Kushner, H.J. A new method of locating the maximum point of an arbitrary multipeak curve in the presence of noise / H.J. Kushner // Journal of Basic Engineering. - 1964. - Vol. 86. - N 1. - P. 97-106.

136. Lera, D. Acceleration of univariate global optimization algorithms working with Lipschitz functions and Lipschitz first derivatives / D. Lera, Y.D. Sergeyev // SIAM Journal on Optimization. 2013. Vol. 23, No. 1. P. 508-529.

137. Levy, A.V. Topics in Global Optimization / A.V. Levy, A. Montalvo, S. Gomez, A. Calderon // Lecture Notes on Mathematics. - 1982. - N 909. - P. 18-33.

138. Liu, D.C. On the limited memory BFGS method for large scale optimization / D.C. Liu, J. Nocedal // Mathematical programming. 1989. Vol. 45, No. 1-3. P. 503-528.

139. Liu, J. Tuning BARON using derivative-free optimization algorithms / J. Liu, N. Ploskas, N.V. Sahinidis // Journal of Global Optimization. - 2019. - Vol. 74. - N 4. -P. 611-637.

140. Luus, R. Optimization by direct search and systematic reduction of the size of search region / R. Luus, T.H.I. Jaakola // AIChE Journal. - 1973. - Vol. 19. - N 4. - P. 760-766.

141. Mahdavi, M. An improved harmony search algorithm for solving optimization problems / M. Mahdavi, M. Fesanghary, E. Damangir // Applied mathematics and computation. - 2007. - Vol. 188. - N 2. - P. 1567-1579.

142. Mezura-Montes, E. A simple multimembered evolution strategy to solve constrained optimization problems / E. Mezura-Montes, C.A.C. Coello // IEEE Transactions on Evolutionary computation. 2005. Vol. 9, No. 1. P. 1-17.

143. Milam, M.B. Real-time optimal trajectory generation for constrained dynamical systems / M.B. Milam. - California Institute of Technology, 2003.

144. Mirjalili, S. Grey wolf optimizer / S. Mirjalili, S.M. Mirjalili, A. Lewis // Advances in Engineering Software. 2014. Vol. 69. P. 46-61.

145. Mitchell, M. An Introduction to Genetic Algorithms / M. Mitchell. Cambridge: MIT Press, 1999. - 158 p.

146. Mokhtari, A. Global convergence of online limited memory BFGS / A. Mokhtari, A. Ribeiro // The Journal of Machine Learning Research. - 2015. - Vol. 16.

- N 1. - P. 3151-3181.

147. Molga, M. Test functions for optimization needs / M. Molga, C. Smutnicki // Test functions for optimization needs. - 2005. - Vol. 101.

148. Nasuto, S. Convergence analysis of stochastic diffusion search / S. Nasuto, M. Bishop // Parallel algorithms and application. - 1999. - Vol. 14, No. 2. - P. 89-107.

149. Nesterov, Yu.E. Interior-Point Polynomial Algorithms in Convex Programming / Yu.E. Nesterov, A.S. Nemirovskii. - Philadelphia: SIAM, 1994. - 405 p.

150. Newman, D.J. Location of the maximum on unimodal surfaces / D.J. Newman // Journal of the ACM (JACM). - 1965. - Vol. 12. - № 3. - P. 395-398.

151. Nocedal, J. Numerical optimization / J. Nocedal, S.J. Wright. - New York: Springer, 2006. - 664 p.

152. Ocampo, C. An architecture for a generalized spacecraft trajectory design and optimization system / C. Ocampo // Libration Point Orbits and Applications. - 2003. -P. 529-571.

153. Pardalos, P.M. Handbook of global optimization: Volume 2 / P.M. Pardalos.

- New York: Springer, 2002. - 580 p.

154. Passino, K.M. Bacterial foraging optimization / K.M. Passino // Innovations and Developments of Swarm Intelligence Applications. 2012. P. 219-233.

155. Paulavicius, R. Simplicial global optimization / R. Paulavicius, J. Zilinskas. -New York: Springer, 2014. - 137 p.

156. Pintér, J.D. Convergence properties of stochastic optimization procedures / J.D. Pintér // Optimization. - 1984. - Vol. 15, N 3. - P. 405-427.

157. Pintér, J.D. Global optimization in action: continuous and Lipschitz optimization: algorithms, implementations and applications / J.D. Pintér. - New York: Springer, 2013. - 478 p.

158. Polak, E. Note sur la convergence de méthodes de directions conjuguées /

E. Polak, G. Ribiere // Revue française d'informatique et de recherche opérationnelle,

série rouge. - 1969. - Vol. 3. - N 1. - P. 35-43.

172

159. Posypkin, M. Implementation and verification of global optimization benchmark problems / M. Posypkin, A. Usov // Open Engineering. - 2017. - Vol. 7. - N 1. - p. 470-478.

160. Powell, W.B. Approximate Dynamic Programming: Solving the curses of dimensionality / W.B. Powell. - John Wiley & Sons, 2007. - Vol. 703.

161. Rao, R. An elitist teaching-learning-based optimization algorithm for solving complex constrained optimization problems / R. Rao, V. Patel // International Journal of Industrial Engineering Computations. - 2012. - Vol. 3. - N 4. - P. 535-560.

162. Rao, R.V. Teaching-learning-based optimization: a novel method for constrained mechanical design optimization problems / R.V. Rao, V.J. Savsani, D.P. Vakharia // Computer-Aided Design. - 2011. - Vol. 43, N 3. - P. 303-315.

163. Rao, A.V. Trajectory optimization: a survey / A.V. Rao // Optimization and optimal control in automotive systems. - Springer, Cham, 2014. - P. 3-21.

164. Rashedi, E. GSA: a gravitational search algorithm / E. Rashedi, H. Nezamabadi-Pour, S. Saryazdi // Information sciences. 2009. Vol. 179. No. 13. P. 2232-2248.

165. Reynolds, R.G. An introduction to cultural algorithms / R.G. Reynolds // Proceedings of the third annual conference on evolutionary programming. - 1994. - P. 131-139.

166. Rios, L.M. Derivative-free optimization: a review of algorithms and comparison of software implementations / L.M. Rios, N.V. Sahinidis // Journal of Global Optimization. - 2013. - Vol. 56, No. 3. - P. 1247-1293.

167. Rutquist, P.E. Propt-matlab optimal control software / P.E. Rutquist, M.M. Edvall // Tomlab Optimization Inc. - 2010. - T. 260. - №. 1. - P. 12.

168. Saramud, M.V. On the application of a modified ant algorithm to optimize the structure of a multiversion software package / M.V. Saramud, I.V. Kovalev, V.V. Losev, M.V. Karaseva, D.I. Kovalev // International Conference on Swarm Intelligence. -Springer, Cham, 2018. - P. 91-100.

169. Sauer, Jr.C.G. MIDAS-Mission design and analysis software for the optimization of ballistic interplanetary trajectories / Jr.C.G. Sauer // Journal of the Astronautical Sciences. - 1989. - T. 37. - P. 251-259.

170. Schoen, F. On a sequential search strategy in global optimization problems / F. Schoen // Calcolo. - 1982. - Vol. 19, N 3. - P. 321-334.

171. Schwartz, A. Consistent approximations for optimal control problems based on Runge-Kutta integration / A. Schwartz, E. Polak // SIAM Journal on Control and Optimization. - 1996. - Vol. 34. - N 4. - P. 1235-1269.

172. Schweiger, C.S. MINOPT: A software package for mixed-integer nonlinear optimization / C.S. Schweiger, C.A. Floudas. - Princeton: Princeton University, 1996.

173. Semenkin, E. Self-configuring genetic algorithm with modified uniform crossover operator / E. Semenkin, M. Semenkina // Advances in Swarm Intelligence. Lecture Notes in Computer Science. - 2012. - Vol. 7331. - P. 414-421.

174. Shewchuk, J.R. An Introduction to the Conjugate Gradient Method Without the Agonizing Pain / J.R. Shewchuk. - 1994.

175. Simon, D. Biogeography-based optimization / D. Simon // IEEE transactions on evolutionary computation. - 2008. - Vol. 12, N 6. - P. 702-713.

176. Sopov, E. A self-configuring multi-strategy multimodal genetic algorithm / E. Sopov // Advances in Nature and Biologically Inspired Computing. - 2016. - Vol. 419.

- P. 15-26.

177. Sopov, E. Multi-strategy genetic algorithm for multimodal optimization / E. Sopov // 2015 7th International Joint Conference on Computational Intelligence (IJCCI). - 2015. - Vol. 1. - P. 55-63.

178. Storn, R. Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces / R. Storn, K. Price // Journal of global optimization.

- 1997. - Vol. 11, N 4. - P. 341-359.

179. Strongin, R.G. Global optimization with non-convex constraints: Sequential and parallel algorithms / R.G. Strongin, Ya.D. Sergeyev. - Dordrecht: Kluwer Academic Publishers, 2000. - 728 p.

180. Surjanovic, S. Virtual Library of Simulation Experiments: Test Functions and Datasets [Electronic resourse] / S. Surjanovic. - Режим доступа: http://www.sfu.ca/~ssurjano, свободный.

181. Sutton, R.S. Learning to predict by the methods of temporal differences / R.S. Sutton // Machine learning. - 1988. - Vol. 3, N 1. - P. 9-44.

182. Sutton, R.S. Reinforcement learning: An introduction / R.S. Sutton, A.G. Barto. USA: MIT press, 2018.

183. Teo, K.L. A unified computational approach to optimal control problems / K.L. Teo, C. Goh, K. Wong. - 1991.

184. The Cambridge Energy Landscape Database, D.J. Wales, J.P.K. Doye, A. Dullweber, M.P. Hodges, F.Y. Naumkin, F. Calvo, J. Hernández-Rojas and T.F. Middleton, URL http://www-wales.ch.cam.ac.uk/CCD.html.

185. Timonov, L.N. An Algorithm for Search of a Global Extremum / L.N. Timonov // Engineering Cybernetics. - 1977. - Vol. 15, N 3. - P. 38-44.

186. Von Stryk, O. User's guide for DIRCOL: A direct collocation method for the numerical solution of optimal control problems / O. Von Stryk // Lehrstuhl für Höhere Mathematik und Numerische Mathematik, Technische Universität, München. - 1999. -Vol. 2.

187. Vlases, W.G. Optimal trajectories by implicit simulation / W.G. Vlases // Boeing Aerospace and Electronics, Technical Report WRDC-TR-90-3056, Wright-Patterson Air Force Base. - 1990.

188. Wales, D.J. Global optimization by basin-hopping and the lowest energy structures of Lennard-Jones clusters containing up to 110 atoms / D.J. Wales, J.P.K. Doye // The Journal of Physical Chemistry A. - 1997. - Vol. 101. - N 28. - P. 5111-5116.

189. Walster, G. Test results for a global optimization algorithm / G. Walster, E. Hansen, S. Sengupta // SIAM Numerical Optimization 1984. - 1985. - P. 272-287.

190. Whitley, D. A genetic algorithm tutorial / D. Whitley // Statistics and computing. - 1994. - Vol. 4, N 2. - P. 65-85.

191. Williams, R.J. A class of gradient-estimating algorithms for reinforcement learning in neural networks / R.J. Williams // Proceedings of the IEEE First International Conference on Neural Networks, 1987.

192. Wingo, D.R. Globally minimizing polynomials without evaluating derivatives / D.R. Wingo // International Journal of Computer Mathematics. - 1985. - T. 17. - №. 34. - P. 287-294.

193. Xing, B. Innovative computational intelligence: a rough guide to 134 clever algorithms / B. Xing, W.J. Gao. - Cham: Springer, 2014. - 451 p.

194. Yang, X.S. Engineering optimization by cuckoo search / X.S. Yang, S. Deb // International Journal of Mathematical Modelling and Numerical Optimization. 2010. Vol. 1. No. 4. P. 330-343.

195. Yang, X.S. Firefly algorithm, stochastic test functions and design optimization / X.S. Yang // International Journal of Bio-Inspired Computation. - 2010. -Vol. 2, N 2. - P. 78-84.

196. Yang, X.S. Flower pollination algorithm for global optimization / X.S. Yang // International conference on unconventional computing and natural computation. -Springer, Berlin, Heidelberg, 2012. - P. 240-249.

197. Yang, X.S. Nature-inspired metaheuristic algorithms / X.S. Yang. - Frome: Luniver Press, 2010. - 148 p.

198. Zhigljavsky, A. Stochastic global optimization / A. Zhigljavsky, A. Zilinskas. - New York: Springer, 2008. - 262 p.

199. Zhu, C. Algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound-constrained optimization / C. Zhu et al. // ACM Transactions on Mathematical Software. - 1997. - Vol. 23, N 4. - P. 550-560.

Утверждаю:

Замест^щгьдиректора по научной работе •Гсгшлта экономики и организации шшлепного производства СО РАН. доктор экономических наук, профессор

■01

чояв^

Н.И. Суслов 20 г.

Акт

об использовании результатов диссертационной работы П.С. Сороковикова «Разработка и исследование нелокальных алгоритмов параметрической идентификации динамических систем»

Настоящим подтверждается, что результаты исследования, полученные в диссертационной работе Сороковикова Павла Сергеевича «Разработка и исследование нелокальных алгоритмов параметрической идентификации динамических систем», были использованы в Институте экономики и организации промышленного производства СО РАН при реализации Интеграционного проекта № 66 «Подходы к разработке стратегий и программ социально-экономического развития сибирских регионов ресурсного типа с экстремальными природно-климатическими условиями» Комплексной Программы фундаментальных исследований СО РАН «Междисциплинарные интеграционные исследования» на 2018-2020 гг.

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

Заведующий лабораторией моделирования и анализа экономических процессов ИЭОПГ1 СО РАН. о д.э.н., профессор, чл.-к. РАН ' ^

В.И. Суслов

ПРИЛОЖЕНИЯ Приложение А. Коллекция тестовых задач А1. Тестовые функции одной переменной

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

1. Функция /(х) = Бт(лх- 0,5 л) + 0,1х2

Функция является многоэкстремальной, имеет несколько равномерно распространенных локальных минимумов. Задача рассмотрена в работе [Горнов А.Ю., 2007].

Точка глобального минимума: х* = 0

Значение глобального минимума: / * = -1

Отрезок: [-4; 5]

Рисунок А1.1 - График функции /(х) = 8т(лх - 0,5 л) + 0,1х2 2. Функция Растригина

Функция Растригина - одна из классических тестовых задач невыпуклой оптимизации. Является многоэкстремальной, имеет несколько равномерно распространенных локальных минимумов. /(х) = 10 + х2 -10 • соб(2лх)

Точка глобального минимума: х* = 0 Значение глобального минимума: f * = 0 Отрезок: [-5; 10]

Источники: [Растригин Л.А., 1974; Dieterich Johannes M., Bernd Hartke, 2012, с. 7-9; Ding Ke, Ying Tan, 2014]

Рисунок А1.2 - График функции Растригина 3. Функция Schwefel

Функция является многоэкстремальной, имеет несколько локальных минимумов, которые, в отличие от функции Растригина, распространены по отрезку поиска неравномерно.

f (х) = 418,9829 - х • sin(^/|Xf)

Точка глобального минимума: х* = 420,9687 Значение глобального минимума: f * = 0 Отрезок: [-100; 500]

Источники: [Adorio Ernesto P., 2005, с. 13-14; Dieterich Johannes M., Bernd Hartke, 2012, с. 9-10; Surjanovic S., Bingham D., 2013]

100 200 300 400 500

Рисунок А1.3 - График функции Schwefel 4. Функция Griewank

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

f ( x) = 1 + —Х--cos ( x )

4000 v ;

Точка глобального минимума: x* = 0 Значение глобального минимума: f * = 0 Отрезок: [-100; 500]

Источники: [Gavana A., 2007; Jamil Momin, Xin-She Yang, 2013, с. 17; Surjanovic S., Bingham D., 2013]

100 200 300 400

Рисунок А1.4 - График функции Griewank 180

5. Функция Ackley

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

f (х) = 20 + e - 20 • e~°'2х - ecos(2™) Точка глобального минимума: х* = 0 Значение глобального минимума: f * = 0 Отрезок: [-10; 30]

Источники: [Dieterich Johannes M., Bernd Hartke, 2012, с. 5-7; Ding Ke, Ying Tan, 2014]

20 AAAA/VV V V V V V V V V V V V V V l

I\A A/ii V »

/ulA Л/и V1

мА Am

lA 15 /v

lA 10 Л/

-10 10 20 30

Рисунок А1.5 - График функции Ackley 6. Функция Alpine 1

Функция является многоэкстремальной, имеет несколько равномерно распространенных локальных экстремумов. Основной особенностью данной функции является малое отличие значений целевой функции в глобальном и локальных минимумах.

f (x) = \x - sin(x) + 0,1 - x\

Точка глобального минимума: x* = 0 Значение глобального минимума: f * = 0 Отрезок: [-5; 10]

Источники: [Gavana A., 2007; Jamil Momin, Xin-She Yang, 2013, с. 6]

Рисунок А1.6 - График функции Alpine 1 7. Функция Trigonometric 2

Функция Trigonometric 2 является многоэкстремальной, имеет множество локальных минимумов, составляющих сложную систему экстремумов.

f (x) = 1 + 8 sin2 [7( x - 0,9)2 ] + 6 sin2 [14( x - 0,9)2 ] + (x - 0,9)2

Точка глобального минимума: x* = 0,9 Значение глобального минимума: f * = 1 Отрезок: [-2; 4]

Источники: [Jamil Momin, Xin-She Yang, 2013, с. 36]

Рисунок А1.7 - График функции Trigonometric 2

8. Функция Multiextremal 2

Функция Multiextremal 2 является, как следует из названия, многоэкстремальной, имеет множество локальных минимумов. Глобальный минимум расположен около границы отрезка поиска. Наблюдается небольшое отличие значений целевой функции в глобальном и локальных минимумах. Функция сильно осциллирует на всем отрезке поиска.

f (x) = 1 - 0,5 cos(l, 5(10x - 0,3)) cos(31,4x) + 0,5 cos(V5 • 10x) cos(35x) Точка глобального минимума: x* « -0,81 Значение глобального минимума: f * « 0,15 Отрезок: [-1; 2]

Источники: [Е.С. Семенкин, М.Н. Жукова, В.Г. Жуков и др., 2007, с. 27]

Рисунок А1.8 - График функции Multiextremal 2 9. Функция Levy

Функция является многоэкстремальной, имеет несколько локальных минимумов. Наблюдается небольшое отличие значений целевой функции в

глобальном и локальных экстремумах.

f (х) = sin2

' (х-1 1 ж--Ь 1

V V

4

JJ

+ -1 (х -1)2 16v J

Г Г sin

2ж

х-1

V V V

4

+1

Л Л +1

JJ J

Точка глобального минимума: х* = 1

183

Значение глобального минимума: f * = 0 Отрезок: [-5; 10]

Источники: [Adorio Ernesto P., 2005, с. 9; Gavana A., 2007; Hedar A.R., 2007]

Рисунок А1.9 - График функции Levy 10. Функция HappyCat

Функция является многоэкстремальной, имеет два экстремума. Задача выделяется тем, что минимумы функции расположены в двух искривленных узких «ямках».

f (x) =

2 1 x -1

0,25

+ 0,5x2 + x + 0,5

Точка глобального минимума: x* = -1 Значение глобального минимума: f * = 0 Отрезок: [-4; 4]

Источники: [Ding Ke, Ying Tan, 2014]

Рисунок А1.10 - График функции HappyCat

11. Функция Тимонова

( 2 х ^

f (х) = - sin(х) - sin —

V 3 J

Точка глобального минимума: х* = 1,8104 Значение глобального минимума: f * = -1,906 Отрезок: [-15; 20,4] Источники: [Timonov L.N., 1977]

Рисунок А1.11 - График функции Тимонова 12. Функция Levy-Montalvo

f (х) = - х + sin(3x) -1

Точка глобального минимума: х* «14,25047 Значение глобального минимума: f « -16,19325

Источники: [Levy A.V., Montalvo A., Gomez S., Calderon A., 1982]

15

10

5

-15 -10 -5 -5 -10 -15 5 10 15

Рисунок А1.12 - График функции Levy-Montalvo 13. Функция Walster

5

f (x) = X k cos [(к +1) x + к ]

к=i

Точка глобального минимума: x* «-1,42513 Значение глобального минимума: f «-12,8709 Отрезок: [-2ж\ п\

Источники: [Walster G., Hansen E., Sengupta S., 1985]

Рисунок А1.13 - График функции Walster

14. Функция

/(х) = х6 - 2,08х5 + 0,4875х4 + 7,1х3 - 3,95х2 - х + 0,1 Точка глобального минимума: х*« -1,1913

Значение глобального минимума: / « -7,4873

186

Источники: [Wingo D., 1985; Floudas C.A et al., 2013]

Рисунок А1.14 - График функции Wingo 15. Функция Фихтенгольца

ч -x2 + 5x - 6 f(x) =-—-

x +1

Точка глобального минимума: x = 1 -42 «-0,4142

7 5

Значение глобального минимума: f = -— - —j^ « -7,0355 Отрезок: [-12; 12]

Источники: [Фихтенгольц Г.М., 2001; Horst R., Pardalos P.M., 2013]

Рисунок А1.15 - График функции Фихтенгольца 16. Функция Wilkinson

f (х) = 0,2х5 -1,6995х4 + 0,998266х3 - 0,0218343х2 + 0,000089248х Точка глобального минимума: х* = 6,325 Значение глобального минимума: f = -443,67

187

Источники: [Floudas C.A et al., 2013]

Рисунок А1.16 - График функции Wilkinson

17. Функция Salomon

f (x) -1 - cos (2л|x) + 0,1 x|

Точка глобального минимума: x* - 0 Значение глобального минимума: f * - 0 Отрезок: [-19,5; 20]

Источники: [Gavana A., 2007; Jamil Momin, Xin-She Yang, 2013, с. 27]

Рисунок А1.17 - График функции Salomon

18. Функция Xin-She Yang 4

f (x) = (sin2 (x) - e~x ) e~™

№ )

Точка глобального минимума: x* - 0 Значение глобального минимума: f * - -1

Источники: [Jamil Momin, Xin-She Yang, 2013, с. 40]

Рисунок А1.18 - График функции Xin-She Yang 4 19. Авторская функция 1

Функция предложена автором.

f - Л

3

- cos

f (x) =

п ~2

x + 3

sin(0,2 x)

X2 + 5

Точка глобального минимума: х* « 2,09067 Значение глобального минимума: / «-0,04333 Отрезок: [-10; 10]

Рисунок А1.19 - График авторской функции 1 20. Авторская функция 2

Функция предложена автором.

0,1x

Формула: f (x) = - sinh( x)cos(^x) - e

Точка глобального минимума: x* « 4,09863

189

Значение глобального минимума: f * « -30,1927 Отрезок: [-4,2; 4,2]

30

20 10 - _

I -4 \ / ~2--- " \ 4 V/ -10 \ I -20 \ -30 V

Рисунок А1.20 - График авторской функции 2

А2. Многомерные тестовые функции А2.1. Маломерные немасштабируемые модельные задачи 1. Функция Mladineo 1

f (х) = -4xjx2 sin (4 nx2)

Точка глобального минимума: х* =(1,00000000, 0,63492204) Значение глобального минимума: f * = -2,51997258 Ограничения: [0,1]2

Источники: [Paulavicius R., Zilinskas J., 2014, с. 107]

2. Функция Mladineo 2

f (x) = 1 (x2 + x22)-cos (l0ln (2 x)) cos (l0ln (3x2)) +1

Точка глобального минимума: x* = (0,01152703, 0,01440453) Значение глобального минимума: f * = -0,0001 Ограничения: [0,01,1]2

Источники: [Horst R., Pardalos P.M., 2013, с. 468]

Рисунок А2.1.2 - График функции Mladineo 2

3. Функция Wood

2

x2

f (x) = -e X1 sin Xj +

Точка глобального минимума: x* = (0,65327118, 0,00000000) Значение глобального минимума: f =-0,39665295 Ограничения: [0,10]2

Источники: [Paulavicius R., Zilinskas J., 2014, с. 108-109]