519.85

 

А.И. Косолап, д-р физ.-мат. наук

УГХТУ, г. Днепропетровск, Украина

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ И ГЛОБАЛЬНАЯ ОПТИМИЗАЦИЯ

А.І. Косолап, д-р фіз.-мат. наук

УДХТУ, м. Дніпропетровськ, Україна

МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ГЛОБАЛЬНА ОПТИМІЗАЦІЯ

А.I. Kosolap, Doctor of Physical and Mathematical Sciences

USCTU, Dnipropetrovsk, Ukraine

MATHEMATICAL MODELING AND GLOBAL OPTIMIZATION

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

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

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

Ключові слова: складна система, глобальна оптимізація, точна квадратична регуляризація, двоїста задача, опуклі множини і функції.

We offer a new scheme for the simulation of complex systems. It includes a periodic global optimization system at predetermined time intervals from the mathematical model by modifying the interval boundaries. We propose a new method of exact quadratic regularization for the global optimization of complex systems. This method allows to transform the problem of global optimization in to maximum the of norm of the vector on the convex set. The resulting convex set is approximated by the intersection of the ball, and the maximum of the norm of the vector at the intersection of the balls is the solution corresponding dual problem. Numerous experiments confirm the effectiveness of the new method.

Key words: complex system, global optimization, exact quadratic regularization, dual problem, convex sets and function.

Постановка проблемы. Системы, которые нас окружают, можно разбить на два класса: естественные и искусственные. Существует гипотеза, что естественные системы (например, вселенная или человек) функционируют в соответствии с некоторым вариационным принципом (критерием). В каждый момент времени система минимизирует или максимизирует заданный критерий. Естественно, что сам критерий естественной системы не всегда можно определить однозначно. Однако природа в естественных системах не может прогнозировать их будущее состояние. Поэтому естественные системы в своем развитии находят только локальные решения. Часто эти решения обеспечивают устойчивость системы, но возможны исключения. Этим можно объяснить природные катаклизмы. В тоже время искусственные системы должны создаваться и функционировать в соответствии с заданным критерием качества, который должен быть максимальным (минимальным) на заданном интервале времени. Выбор локальных решений при построении сложных систем приводит к невосполнимым ресурсным потерям. Учитывая то, что критерием оптимизации функционирования сложной системы является функционал, интервал времени на котором ищется его оптимальное значение, не может быть большим. Это связано с тем, что с течением времени меняется структура сложной системы. В конце заданного интервала необходимо модифицировать математическую модель системы и ее критерий качества. Модификация включает уточнение параметров системы, часть из которых может быть включена в переменные модели следующего интервала времени ее функционирования. Таким образом, сложная система оптимально функционирует и модернизируется в фиксированные моменты времени. Схема функционирования сложной системы представлена на рис. 1.

Рис.1. Схема математического моделирования сложных динамических систем

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

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

, (1)

где все  дважды дифференцируемые функции, а  евклидово пространство. Функция определяет критерий функционирования системы, а функции  ограничения. Даже в том случае, когда поведение системы описывается системой дифференциальных уравнений, то при численной реализации математические модели таких систем преобразуются к виду (1). Задача (1) является достаточно сложной, поэтому для ее решения предлагаются различные методы случайного поиска [1-2]. Эти методы позволяют найти решение задачи (1) только с некоторой вероятностью. Поэтому поиск более эффективных методов глобальной оптимизации продолжается [3].

Метод точной квадратичной регуляризации. Рассмотрим метод точной квадратичной регуляризации [3], который позволяет преобразовать задачу (1) к максимизации нормы вектора на выпуклом множестве. Это преобразование содержит две новых переменных и два параметра s, r. Используем переменную x_n+1 для преобразования задачи (1) к виду

(2)

где значение параметра s выбираем таким, чтобы x^*  решение задачи (1) (значение параметра s можно уточнить после решения задачи (1)). Далее, с помощью нелинейного преобразования x = Az, где матрица А порядка имеет вид

,

задачу (2) преобразуем к виду

(3)

где , . Существует такое значение r > 0, что все функции

будут выпуклыми для допустимых значений z.

Таким образом, задача (3) сведена к следующей

(4)

где все g_i(z) – выпуклые функции, а d – новая переменная. В задаче (4) необходимо найти минимальное допустимое значение d, тогда соответствующая ему точка z^* будет принадлежать границе шара . Точка глобального минимума z^* задачи (4) будет точкой касания двух выпуклых множеств и при минимальном значении d, которое находим, решая выпуклую задачу

. (5)

Если решение задачи (5) принадлежит границе множества , то задача (1) решена. В этом случае В противном случае, необходимо решать задачу

(6)

и искать минимальное значение d, при котором граница множества коснется поверхности шара . Задача (6) является многоэкстремальной, но эффективно разрешимой. Если выпуклое множество совпадает с прямоугольным параллелепипедом с центром в точке c, то решение задачи (6) находим, решая выпуклую задачу

и находим минимальное значение d, для которого выполняется условие Это условие будет справедливым и для любого центрально симметричного множества . Таким образом, центр выпуклого множества позволяет определить решение задачи (6). Это означает, что для решения задачи (6) могут быть использованы прямо-двойственные методы внутренней точки [4], которые используют аналитический центр выпуклого множества . В общем случае, в задаче (6) переменную d будем фиксировать и решать последовательность задач

, (7)

где d₀ – решение задачи (5), а h – интервал изменения переменной d. Значение переменной d, удовлетворяющее условию , находим методом дихотомии (при увеличении переменной d значение целевой функции возрастает).

Заметим, что решение задачи (7) не меняется при увеличении параметров s и r, но при увеличении значения r допустимое множество этой задачи стремится к пересечению шаров (квадратичное слагаемое будет доминировать в функциях ). Для этого необходимо определить центры выпуклых множеств и их радиусы. Таким образом, задача (7), при фиксированном значении d, аппроксимируется следующей задачей

, (8)

которая эффективно решается двойственным методом. Двойственная задача для (8) будет иметь вид

(9)

Задача (9) будет выпуклой, если выполняется условие

(10)

Если условие (10) не выполняется, то ограничения задачи (8) необходимо дополнить ограничением ||z – a||² ≤ R², где значение a выбираем из условия z^*  a < 0, а R  достаточно большое число (z^*  решение задачи (8)). Задачу (9) решаем прямо-двойственным методом внутренней точки [4] и подставляем найденное решение в формулу

,

найденную методом множителей Лагранжа, и находим решение прямой задачи (8). Это решение будет совпадать с решением задачи (6) с заданной точностью.

Решение прикладных задач. Задача 1. Необходимо минимизировать вес пружины с параметрами, представленными на рис. 2 [5].

 

Рис.2. Параметры пружины

Найти

_{при ограничениях}

Задача 2. Минимизация веса преобразователя скорости [6]

Задача 3. Оптимальный проект рефрижераторной системы [6]. Найти

при ограничениях

Задача 4. Минимизация стоимости проекта трансформатора [7]. Найти

при ограничениях

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

С помощью метода точной квадратичной регуляризации было решено много известных тестовых задач, в которых найдены точки глобальных минимумов [9]. Приведем решения рассмотренных выше задач. В задаче 1 найдено f(x^*) = 0.012665 в точке x^* = (0.051688332, 0.35670021, 11.28999353), что совпало с лучшим значением глобального минимума, найденного другими методами f(x^*) = 0.012665. В задаче 2 найдено f(x^*) = 2996.347 в точке x^* = (3.5, 0.7, 17, 7.3, 7.8, 3.3502147, 5.28668164), что также совпало с глобальным минимумом, найденным другими методами. В задаче 3 найдено f(x^*) = 0.0311596 в точке x^* = (0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 1.524, 1.524, 5, 2, 0.001, 0.001, 0.007294, 0.087531), что лучше значения, найденного другими методами f(x^*) = 0.057406. Наконец, в задаче 4 найдено f(x^*) = 135.075963 в точке x^* = (5.332809, 4.656604, 10.43367, 12.08154, 0.752611, 0.878648), что практически совпадает со значением глобального минимума, найденного другими методами f(x^*) = 135.075961.

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

Список использованных источников

1. Kenneth V. P. Differential Evolution. A Practical Approach to Global Optimization / V. P. Kenneth, R. M. Storn, J. A. Lampinen. – Berlin Heidelberg : Springer-Verlag, 2005. – 542 p.

2. Rothlauf F. Representation for Genetic and Evolutionary Algorithms / F. Rothlauf. – Berlin Heidelberg : Springer-Verlag, 2006. – 339 p.

3. Косолап А. И. Методы глобальной оптимизации / А. И. Косолап. – Днепропетровск : Наука и образование, 2013. – 318 с.

4. Nocedal J. Numerical optimization / J. Nocedal, S. J. Wright. – Springer, 2006. – 685 p.

5. Coello Coello C. A. Use of a self-adaptive penalty approach for engineering optimization problems // Computers in Industry. – 2000. – 41(2). – Р. 113-127.

6. Pant М. Optimization of Mechanical Design Problems Using Improved Differential Evolution Algorithm / М. Pant, R. Thangaraj, V. P. Singh // Int. journal of recent trends in Engineering. – 2009. – Vol. 1, No 5. – Р. 21-25.

7. B-Biggs M. C. A Numerical Comparison between Two Approaches to the Nonlinear Programming Problem / In: L. C. W. Dixon and G. P. Szego, eds., Towards Global Optimization 2. – Amsterdam, Holland : North Holland Publishing Company, 1978. – Р. 293-312.

8. Arora J. S. Introduction to Optimum Design. – New York : Elsevier Academic Press, 2004. – 751 p.

9. Floudas C. A. A collection of Test Problems for Constrained Global Optimization Algorithms / C. A. Floudas, P. M. Pardalos.  Berlin Helldelberg : Springer-Verlag, 1990. – 193 p.

10. Nie J. Regularization Methods for Sum of Squares Relaxations in Large Scale Polynomial Optimization / J. Nie. – California : University of California, 2009. – 31 p.

11. Сокуренко В. М. Числове дослідження стохастичних методів безперервної глобальної оптимізації / В. М. Сокуренко, В. С. Неділюк // Наукові вісті НТУУ «КПІ». – 2012. – № 1. – С. 81-87.