Использование кусочно-линейных ограничивающих функций в одномерной глобальной оптимизации тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Усов Александр Леонидович

• Усов Александр Леонидович
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Усов Александр Леонидович

Введение

Глава 1. Обзор методов одномерной глобальной оптимизации и

методов оценок функций

1.1 Общая задача одномерной глобальной оптимизации

1.2 Интервальные вычисления

1.3 Липшицева глобальная оптимизация и метод Пиявского

1.4 Арифметика скосов

1.5 Опорные функции на основе градиента и интервального анализа

Глава 2. Кусочно-линейные ограничивающие функции

2.1 Определение и основные свойства кусочно-линейных функций

2.2 Базовые арифметические операции над кусочно-линейными функциями

2.3 Построение кусочно-линейных границ для элементарных функций

2.4 Основные арифметические операции над кусочно-линейными границами

2.4.1 Операции сложения, вычитания, линейной комбинации, взятия максимума и минимума для кусочно-линейных оценок

2.4.2 Операция умножения кусочно-линейных оценок

2.4.3 Операция деления кусочно-линейных оценок

2.5 Конструирование кусочно-линейных границ для композиции

функций

2.5.1 Непрерывность кусочно-линейных границ для

композиции функций

Глава 3. Алгоритмы построения и применения

кусочно-линейных границ

3.1 Алгоритм построения максимума (минимума) из нескольких кусочно-линейных функций

3.2 Алгоритм построения композиции кусочно-линейных функций

3.3 Алгоритм уменьшения области поиска глобального минимума функции в методе ветвей и границ

3.4 Алгоритм построения нижней (верхней) кусочно-линейной границы для композиции функций

Глава 4. Экспериментальные исследования

4.1 Пример построения нижней кусочно-линейной границы для композиции функций

4.2 Вычисление нижней кусочно-линейной границы для произведения функций

4.3 Вычисление нижней кусочно-линейной границы для частного функций

4.4 Пример построения высокоэффективной нижней оценки для композиции функций

4.5 Сравнение эффективности кусочно-линейных оценок с другими подходами в задаче поиска глобального минимума функции

Глава 5. Программный комплекс для описания математических

выражений в задачах глобальной оптимизации

5.1 Общее описание архитектуры программного комплекса

5.2 Модуль описания математических выражений

5.3 Модуль интервальных вычислений

5.4 Модуль вычисления производных

5.5 Модуль вычисления кусочно-линейных границ

5.6 Модуль для описания задач оптимизации (бенчмарки)

Заключение

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

Приложение А. Представление целевой функции в виде

абстрактного синтаксического дерева

Приложение Б. Применение методов интервального анализа в

робототехнике

Приложение В. Применение в программном комплексе для

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

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

Данная работа посвящена конструированию нижних и верхних оценок для функций от одной переменной. Функция ф(х) называется нижней (верхней) оценкой для функции /(х) на интервале [а,Ь] если /(х) > ф(х)(/(х) < ф(х)) для всех значений х е [а,Ь].

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

Проблема (1) имеет множество практических применений [1] и кроме того, решение задачи одномерного поиска является вспомогательным методом в многомерной глобальной оптимизации. Например, метод оптимизации, основанный на заполняющих пространство кривых, позволяет свести многомерную задачу оптимизации к последоватнельности одномерных задач [2]. Одномерная глобальная оптимизация также широко используется в сепарабельном программировании [3], где целевая функция и ограничения являются суммой функций одной переменной. Многие одномерные методы оптимизации могут быть распространены на многомерный случай [4; 5].

Тематика одномерной глобальной оптимизации начала активно развиваться в начале 70-х годов. Существенный вклад в развитие данной области внесли работы Ю.Г. Евтушенко, С.А. Пиявского, Р.Г. Стронгина, Я.Д. Сергеева, В.П. Гергеля, В.А. Гришагина, В.П. Булатова, О.В. Хамисова, С.П. Шарого, B. Shubert, C. Floudas, P. Hansen, J. Pinter, D. Ratz, N. Sahinidis и других исследователей. Часть известных подходов [6; 7] используют условие Липшица:

Метод Пиявского [8], который также называют метод ломаных, позволяет построить набор ограничивающих кусочно-линейных функций для целевой функции. Другие подходы использующие свойство (2) и условие Липшица для первых производных были исследованы в статьях [9—11].

Интервальный анализ [12; 13] является другим подходом, применяемым в глобальной оптимизации. Интервальный анализ позволяет получить гаранти-

f (х) ^ min, х Е [а,Ь].

(1)

\f М - f Ы1 < L\x - у^ х,у Е [а,Ь].

(2)

рованные нижние и верхние оценки функции на заданном интервале. Перспективные подходы сочетающие липшицеву оптимизацию и интервальный анализ предложены в статье [14].

Кроме того, существуют эффективные алгоритмы оптимизации основанные на кусочно-линейной и кусочно-выпуклой аппроксимациях [15; 16], а также на технике скосов [17].

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

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

Для достижения поставленной цели необходимо было решить следующие задачи:

1. Разработать теоретические основы построения кусочно-линейных оценок.

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

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

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

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

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

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

ментарных функций с использованием их свойств выпуклости и вогнутости.

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

3. Разработана теория и алгоритм построения кусочно-линейных оценок для композиции функции. Доказано, что достаточным условием непрерывности кусочно-линейной оценки Н(х) для композиции функции Н(х) = /(д(х)) является однократность смены монотонности миноранты (у) внешней функции.

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

Научная новизна:

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

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

Практическая ценность данной работы состоит в следующем:

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

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

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

3. разработан программный комплекс на языке программирования С++, включающий наборы тестовых задач глобальной оптимизации [18], поддержку автоматического вычисления значений функции, ее производной, а также их интервальных и кусочно-линейных оценок.

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

5. модули поддержки интервальных вычислений, разработанные в диссертации, были использованы в программном комплексе для решения задач глобальной оптимизации, созданном в рамках проекта 075-15-2020-799 Министерства науки и высшего образования Российской Федерации «Методы построения и моделирования сложных систем на основе интеллектуальных и суперкомпьютерных технологий, направленные на преодоление больших вызовов» (Приложение В).

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

Апробация работы. Основные результаты, полученные в диссертации, обсуждались и докладывались на XVII Байкальской международной школы-семинара «Методы оптимизации и их приложения» (с. Максимиха, Бурятия, 31 Июля - 7 Августа, 2017), VIII Международной Конференции «Оптимизация и Приложения (ОПТИМА-2017)» (Петровац, Черногория, Октябрь 2-7, 2017) и IX Международной Конференции «Оптимизация и Приложения (ОП-ТИМА-2018)» (Петровац, Черногория, Октябрь 1-5, 2018).

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

Публикации. Основные результаты по теме диссертации изложены в 9 печатных изданиях, 3 из которых изданы в журналах, рекомендованных ВАК [19; 21; 22], 3 в зарубежных журналах [18; 20; 23] и 3 в сборниках трудов конференций [24—26]. Статьи [18; 20; 23; 26] опубликованы в журналах индексируемых в Web of Science Core Collection и/или Scopus.

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

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

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

Глава 3 описывает алгоритмы построения кусочно-линейных границ на основе теории изложенной в главе 2.

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

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

Полный объём диссертации составляет 117 страниц с 34 рисунками и 3 таблицами. Список литературы содержит 39 наименований.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Усов Александр Леонидович

В настоящей работе был предложен метод для автоматического построения кусочно-линейных границ целевой функции от одной переменной, заданной в виде выражения над элементарными функциями. Были разработаны основные правила для алгебраических операций над кусочно-линейными границами. Предложенный подход был экспериментально сопоставлен с методом оценки функций при помощи интервального анализа [12; 27] и арифметики скосов [17; 31]. Эксперименты показали, что для некоторых функций предложенный подход может значительно превышать известные стандартные подходы.

Кроме того, описанный подход был использован на практике в методах глобальной оптимизации. Для этого был разработан программный комплекс (Глава 5), который позволил выполнить экспериментальную часть данной работы. Использование кусочно-линейных оценок позволило не только эффективно оценивать функции, но и выполнять редукцию области поиска глобального экстремума. Предложенный подход также сравнивался с методом интервального анализа и методом Пиявского в вычислительных экспериментах. В результате для многих одномерных функций время нахождения глобального экстремума было меньше при использовании кусочно-линейного метода.

Одним из возможных направлений для дальнейших исследований является применение этого подхода в сепарабельном программировании [38; 39]. В сепарабельном программировании рассматривается специальный класс многомерных функций, которые представляются в виде суммы функций, каждая из которых зависит только от одной переменной, т.е. Г(х\,х2,... ,хп) = Г(х\)+Г2(ж2) + ,... , +Гп(жп) (сепарабельная функция). Задачи сепарабельного программирования также требуют нахождения глобальных экстремумов функций, которые могут быть получены с использованием предложенных кусочно-линейных границ.

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

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

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

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

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

1. Optimization of one-dimensional multimodal functions / A. Zilinskas [и др.] // Journal of the Royal Statistical Society, Series C (Applied Statistics). — 1978. — Т. 27, № 3.

2. Strongin R. G., Sergeyev Y. D. Global optimization with non-convex constraints: Sequential and parallel algorithms. Т. 45. — Springer Science & Business Media, 2013.

3. Jensen P. A., Bard J. F. Operations research models and methods. — John Wiley & Sons Incorporated, 2003.

4. Pinter J. Extended univariate algorithms for n-dimensional global optimization // Computing. — 1986. — Т. 36, № 1. — С. 91—103.

5. Sergeyev Y. D., Kvasov D. E. Deterministic global optimization: An introduction to the diagonal approach. — Springer, 2017.

6. Evtushenko Y. G. Numerical methods for finding global extrema (case of a non-uniform mesh) // USSR Computational Mathematics and Mathematical Physics. — 1971. — Т. 11, № 6. — С. 38—54.

7. Shubert B. O. A sequential method seeking the global maximum of a function // SIAM Journal on Numerical Analysis. — 1972. — Т. 9, № 3. — С. 379—388.

8. Pijavskij S. An algorithm for finding the global extremum of function // Optimal Decisions. — 1967. — Т. 2. — С. 13—24.

9. Kvasov D. E., Sergeyev Y. D. A univariate global search working with a set of Lipschitz constants for the first derivative // Optimization Letters. — 2009. — Т. 3, № 2. — С. 303—318.

10. Lera D., Sergeyev Y. D. Acceleration of univariate global optimization algorithms working with Lipschitz functions and Lipschitz first derivatives // SIAM Journal on Optimization. — 2013. — Т. 23, № 1. — С. 508—529.

11. Gergel V. P. A global optimization algorithm for multivariate functions with Lipschitzian first derivatives // Journal of Global Optimization. — 1997. — Т. 10, № 3. — С. 257—281.

12. Hansen E, Walster G. W. Global optimization using interval analysis: revised and expanded. — CRC Press, 2003.

13. Moore R. E., Kearfott R. B., Cloud M. J. Introduction to interval analysis. — SIAM, 2009.

14. New interval analysis support functions using gradient information in a global minimization algorithm / L. G. Casado [и др.] // Journal of Global Optimization. — 2003. — Т. 25, № 4. — С. 345—362.

15. Fasano G., Pintér J. D. Efficient Piecewise Linearization for a Class of Non-convex Optimization Problems: Comparative Results // Modeling and Optimization: Theory and Applications: MOPTA, Bethlehem, PA, USA, August 2017, Selected Contributions. — 2019. — Т. 279. — С. 39.

16. Floudas C, Gounaris C. Tight convex underestimators for C2-continuous functions: I. Univariate functions //J. Glob. Optim. — 2008. — Т. 42. — С. 51—67.

17. Ratz D. A nonsmooth global optimization technique using slopes: the one-dimensional case // Journal of Global Optimization. — 1999. — Т. 14, № 4. — С. 365—393.

18. Posypkin M., Usov A. Implementation and verification of global optimization benchmark problems // Open Engineering. — 2017. — Т. 7, № 1. — С. 470— 478.

19. Малышев Д., Посыпкин М., Усов А. Анализ рабочей области робота DexTAR-dexterous twin-arm robot // International Journal of Open Information Technologies. — 2018. — Т. 6, № 7.

20. Malyshev D., Posypkin M., Usov A. Approaches to the Determination of the Working Area of Parallel Robots and the Analysis of Their Geometric Characteristics // Engineering Transactions. — 2019. — Т. 67, № 3. — С. 333— 345.

21. Усов А. Построение кусочно-линейных оценок для функций одной переменной // International Journal of Open Information Technologies. — 2019. — Т. 7, № 5.

22. Усов А. Построение непрерывных кусочно-линейных границ для композиции функций от одной переменной. // International Journal of Open Information Technologies. — 2021. — Т. 9, № 1.

23. Posypkin M, Usov A., Khamisov O. Piecewise linear bounding functions in univariate global optimization // Soft Computing. — 2020. — С. 1—17.

24. Posypkin M., Usov A. An Object Oriented Library for Computing the Range of the Objective Function // XVII Baikal International School-Seminar "Methods of Optimization and Their Applications". Abstracts. July 31-August 6 (Maksimikha, Buryatia). — Melentiev Energy Systems Institute SB RAS Irkutsk, 2017. — Pp. 58-58.

25. Evtushenko Y, Posypkin M., Usov A. The Global Optimization Approach to Robot's Workspace Determination // XVII Baikal International School-Seminar "Methods of Optimization and Their Applications". Abstracts. July 31-August 6 (Maksimikha, Buryatia). — Melentiev Energy Systems Institute SB RAS Irkutsk, 2017. — Pp. 39-39.

26. Khamisov O., Posypkin M., Usov A. Piecewise Linear Bounding Functions for Univariate Global Optimization // Optimization and Applications / под ред. Y. Evtushenko [и др.]. — Cham : Springer International Publishing, 2019. — С. 170—185. — ISBN 978-3-030-10934-9.

27. Shary S. Finite-Dimensional Interval Analysis. Institute of Compunational Technologies, SB RAS, Novosibirsk. — 2016.

28. Kearfott R. B. Interval computations: Introduction, uses, and resources // Euromath Bulletin. — 1996. — Т. 2, № 1. — С. 95—112.

29. Kvasov D. E., Sergeyev Y. D. Univariate geometric Lipschitz global optimization algorithms // Numerical Algebra, Control & Optimization. — 2012. — Т. 2, № 1. — С. 69—90.

30. Квасов Д. Е., Сергеев Я. Д. Методы липшицевой глобальной оптимизации в задачах управления // Автоматика и телемеханика. — 2013. — № 9. — С. 3—19.

31. Ratz D. An optimized interval slope arithmetic and its application. — Inst. fiir Angewandte Mathematik, 1996.

32. Alefeld G, Herzberger J. Introduction to interval computation. — Academic press, 2012.

33. Neumaier A., Neumaier A. Interval methods for systems of equations. Т. 37. — Cambridge university press, 1990.

34. Kearfott R. B. Rigorous Global Search: Continuous Problems Kluwer Academic Publishers // Dordrecht, Netherlands. — 1996.

35. Кудрявцев Л. Курс математического анализа. Том 1: учебник для бакалав-ров-6-е изд., перераб. и доп. — 2017.

36. Moore R. E. Interval analysis. Т. 4. — Prentice-Hall Englewood Cliffs, NJ, 1966.

37. Neidinger R. D. Introduction to automatic differentiation and MATLAB object-oriented programming // SIAM review. — 2010. — Т. 52, № 3. — С. 545— 563.

38. Pardalos p. M, Rosen J. Reduction of nonlinear integer separable programming problems // International journal of computer mathematics. — 1988. — Т. 24, № 1. — С. 55—64.

39. Rosen J. B., Pardalos P. M. Global minimization of large-scale constrained concave quadratic problems by separable programming // Mathematical Programming. — 1986. — Т. 34, № 2. — С. 163—174.