5.Методы одномерной и многомерной оптимизации

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

5.Методы одномерной и многомерной оптимизации

Я долго готовился и собирал материал, надеюсь в этот раз получилось лучше.

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

P. S. Статья содержит математические формулы, добавленные макросами хабраредактора. Говорят, что они иногда не отображаются. Также есть много анимаций в формате gif.

Преамбула

Задача математической оптимизации — это задача вида «Найти в множестве элемент такой, что для всех из выполняется », что в научной литературе скорее будет записано как-то так

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

Задачи минимизации над пространством вида таким образом стали условно называть «задачами без ограничений» (unconstrained problem), а задачи над множествами, заданными наборами равенств и неравенств — «задачами с ограничениями» (constrained problem).

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

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

где — выпуклые (но не обязательно дифференцируемые) функции, — матрица. Для демонстрации работы методов я буду использовать два примера:

  1. Задача линейного программирования

    $$display$$\begin{array}{rl} \mbox{минимизировать } & -2&x~~~- &y \\ \mbox{при условии } &-1.0 & ~x -0.1 & ~y \leq -1.0 \\ & -1.0 & ~x + ~0.6 &~ y \leq -1.0 \\ & -0.2 & ~x + ~1.5 & ~y \leq -0.2\\ & ~0.7 &~x + ~0.7 & ~y \leq 0.7\\ &~2.0 & ~x -0.2 & ~y \leq 2.0\\ &~0.5 & ~x -1.0 & ~y \leq 0.5\\ &-1.0 & ~x -1.5& ~ y \leq -1.0\\ \end{array} $$display$$

    По сути эта задача состоит в том, чтобы найти самую дальнюю точку многоугольника в направлении (2, 1), решение задачи — точка (4.7, 3.5) — самая «правая» в многоугольнике). А вот собственно и сам многоугольник

  2. Минимизация квадратичной функции с одним квадратичным ограничением

Симплекс-метод

Из всех методов, которые я покрываю этим обзором, симплекс-метод наверно является самым известным.

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

Идея симплекс-метода состоит из двух частей:

  1. Системы линейных неравенств и равенств задают многомерные выпуклые многогранники (политопы). В одномерном случае это точка, луч или отрезок, в двумерном — выпуклый многоугольник, в трехмерном — выпуклый многогранник.

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

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

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

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

Симплекс-метод является итеративным, то есть он последовательно по чуть-чуть улучшает решение. Для таких методов нужно с чего-то начинать, в общем случае это делается с помощью решения вспомогательной задачи
Если для решения этой задачи такое, что , то выполняется , иначе исходная задача вообще задана на пустом множестве. Чтобы решить вспомогательную задачу, можно также использовать симплекс-метод, начальной же точкой можно взять с произвольным . Нахождение начальной точки можно условно назвать первой фазой метода, нахождение решение исходной задачи можно условно назвать второй фазой метода. Траектория двухфазового симплекс-методаТраектория была сгенерирована с помощью scipy.optimize.linprog.

Проективный градиентный спуск

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

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

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

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

Самый распространенный случай, для которого удобно применять проективный градиентный спуск — это «коробочные ограничения», которые имеют вид В этом случае проекция вычисляется очень просто, по каждой координате получается Применение проективного градиентного спуска для задач линейного программирования совершенно бессмысленно, тем не менее если это все-таки сделать, то выглядеть будет как-то так Траектория проективного градиентного спуска для задачи линейного программирования
А вот как выглядит траектория проективного градиентного спуска для второй задачи, если выбирать большой размер шага
и если выбирать небольшой размер шага

Метод эллипсоидов

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

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

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

Метод внутренней точки

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

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

Базовая идея метода — замена ограничений на штраф в виде так называемой барьерной функции.

Функция называется барьерной функцией для множества , если

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

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

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

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

  1. Выбрать начальное приближение ,
  2. Выбрать новое приближение методом Ньютона
  3. Увеличить

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

Задача квадратичного программирования

  • Математика
  • линейные системы и оптимизация

Источник: https://habr.com/post/428794/

Методы одномерной оптимизации

5.Методы одномерной и многомерной оптимизации

Эти методы строятся в предположении унимодальности функции F(x) на заданном интервале [a, b]. К функции не предъявляются требования непрерывности или дифференцируемости, предполагается лишь, что для любого x Î [a, b] значение F(x) может быть вычислено.

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

ü Методы последовательного поиска (методы сокращения интервалов, методы исключения интервалов)

Методы этой группы нацелены на построение такой стратегии поиска x*, при которой любая пара вычислений F(x) позволяет сузить область поиска (или интервал неопределенности). Вычисляя F(x) в точках x1 и x2 таких, что a < x1 < x2 < b, можно локализовать интервал неопределенности путем анализа полученных значений функции:

если F(x1) < F(x2), то x* Î [a, x2];

если F(x1) = F(x2), то x* Î [x1, x2];

если F(x1) > F(x2), то x* Î [x1, b];

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

· Метод дихотомии (половинного деления) – один из самых простых методов последовательного поиска.

Метод половинного деления (метод дихотомии) проиллюстрирован ниже.

· Метод золотого сечения предполагает такое сокращение интервала на каждом шаге, что отношение целого к большей части было равно отношению большей части к меньшей. Это отношение, равное 1.618, и называют «золотым сечением». (1 : 0,618 = 1,618; 0.618 : 0,382 = 1,618)

Координаты точек x1,k и x2,k определяются следующим образом:

x1,k = ak + 0.382×(bk – ak) ; x2,k = bk – 0.382×(bk – ak).

Значение коэффициента К (0,382) подобрано так, что в полученном отрезке меньшей длины одна из промежуточных точек совпадет с промежуточной точкой от предыдущего шага. Это позволяет сократить число вычислений целевой функции на всех шагах (кроме первого) в 2 раза.

Таким образом, требуется не более N шагов и N+1 вычисление целевой функции, где N можно рассчитать, используя соотношение (b–a)/ε = (1–a)N при заданной погрешности ε определения экстремума.

САПР-1986, кн. 9: САПР-1986, кн. 8:

· Метод чисел Фибоначчи

Стратегия поиска связана с использованием чисел Фибоначчи, которые можно получить из рекуррентного соотношения Rk = Rk-1 + Rk-2 , k = 2, 3, …, R0 = R1 = 1. В отличие от метода золотого сечения, здесь коэффициент сокращения интервала изменяется от итерации к итерации, хотя он также близок к значению 0.382.

Норенков-2000: Согласно методу чисел Фибоначчи, используют числа Фибоначчи Ri, последовательность которых образуется по правилу Ri+2 = Ri+1 + Ri при R0 = R1 = 1, т.е. ряд чисел Фибоначчи имеет вид 1, 1, 2, 3, 5, 8, 13, 21, 34, ….

Метод аналогичен методу золотого сечения с тем отличием, что коэффициент K равен отношению Ri-2 /Ri, начальное значение i определяется из условия, что Ri должно быть наименьшим числом Фибоначчи, превышающим величину (b–a)/ε, где ε — заданная допустимая погрешность определения экстремума.

Так, если (b–a)/ε = 100, то начальное значение i = 12, поскольку R12 = 144, и K = 55/144 = 0,3819, на следующем шаге будет K = 34/89 = 0,3820 и т.д.

Основной недостаток метода – необходимость задания числа шагов.

Основное преимущество – быстрое сужение интервала неопределенности: при числе шагов n = 14 интервал неопределенности примерно в 5 раз меньше, чем получаемый по методу половинного деления.

В то же время по сравнению с методом золотого сечения метод Фибоначчи позволяет получить интервал только на 17% меньше, и при большом числе шагов оба эти метода практически идентичны.

ü Методы полиномиальной аппроксимации

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

· Метод квадратичной интерполяции – один из популярных методов этой группы.

Метод заключается в замене нелинейной функции F(x) квадратичной параболой F2(x), построенной по трем точкам, принадлежащим F(x), так, чтобы значения аппроксимирующей функции F2(x) совпали со значениями F(x) в этих трех точках. Минимум квадратичной функции находится с использованием аналитического условия оптимальности: df/dx = 0.

На первом этапе в качестве исходных трех точек используются

x1 = a, x2 = (a + b)/2, x3 = b.

В этих точках вычисляется f(x) и по полученным точкам f(x1), f(x2), f(x3) строится парабола

f2 = C2 x2 + C1 x + C0 ,

коэффициенты которой находятся из решения соответствующей системы уравнений:

f2(x1) = f(x1), f2(x2) = f(x2), f2(x3) = f(x3)

Значения коэффициентов:

C0 = f(x1),

C1 = [f(x2) – f(x1)] / (x2 – x1),

C2 = 1 / (x3 – x2)× {[ f(x3) – f(x1)] / (x3 – x1) – [f(x2) – f(x1)] / (x2 – x1)}

Условие оптимальности приводит к уравнению x4 = – C1 / 2C2 , где х4 – точка минимума параболы f2(x).

Далее выбирается новый отрезок, внутри которого находится точка х4, и c использованием х3, х4 строится новая парабола, по которой уточняется положение минимума f(x), и т. д. до тех пор, пока величина отрезка, внутри которого находится оптимум, не станет меньше заданной погрешности e. Таким образом, метод имеет итерационный характер.

К достоинствам метода относится высокая скорость сходимости, хотя метод может не всегда сходиться.

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

Пример. Найти максимум функции f(x) = sin (x + 1)на интервале [-1; 2], точность e = 0,01.

Решение. Для построения аппроксимирующей параболы находим точки

x1 = a, x2 = (a + b)/2, x3 = b.

Система уравнений для нахождения коэффициентов параболы примет вид:

Решение системы можно найти любым из известных способов, например, по формулам Крамера. На первом шаге получаем = 0,5571, f( ) = 0.9999. По этой точке, а также по второй и третьей исходным точкам, лежащим по обе стороны от точки максимума параболы, аналогично строится вторая парабола.

п x1 x2 x3 f(х1) f(x2) f(x3) C2 C1 C0
1-10.5200.99750.1411-0.4120.4590.8710.55710.9999
20.50.557120.99750.99990.1411-0.42490.49140.8580.57821
30.55710.578220.999910,1411-0,42080.48090.86260.57141
40,55710,57140,57820,999911-0,50,57080,83710,57081

Уже на третьем шаге разница между двумя точками максимума менее заданной погрешности, поэтому поиск можно заканчивать (четвертый шаг приведен для наглядности вычислений). Поэтому х* » 0,5708, и f* » f (0,5708) = 1.

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

Заметим, что универсального метода, наилучшего для любых задач, пока не создано. Поэтому в современных математических пакетах возможна автоматическая смена метода в процессе решения задачи, как например в Matlab – переход от метода золотого сечения (golden) к методу квадратичной аппроксимации (parabolic):

Источник: https://studopedia.su/13_148328_metodi-odnomernoy-optimizatsii.html

VIII. Методы многомерной оптимизации

5.Методы одномерной и многомерной оптимизации

1. Основные определения.Задачей многомерной оптимизации является минимизация функции U=f(x1,x2,…,xm) от m переменных (параметров) x1,x2,…,xm. Если нет ограничений на параметры x1,…,xm, то говорят о глобальной безусловной минимизации, если есть ограничения на параметры x1,…,xm, то говорят об условной минимизации.

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

В соответствии с этим величину можно рассматривать как точку (элемент) m-мерного линейного пространства независимых переменных x1,…,xm. Если в этом пространстве ввести единичные векторы , поставленные в соответствие переменным x1,…

,xm, то величину можно рассматривать как вектор: , а операции сложения и вычитания производить по правилу векторов.

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

б) градиент. Вектор называется градиентом функции и обозначается:

(8.1)

Вектор указывает направление наискорейшего возрастания функции, а вектор называется антиградиентом и указывает направление наискорейшего убывания функции. Градиент всегда перпендикулярен поверхности (линии) уровня.

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

а) необходимое условие. Необходимым условием минимума функции многих переменных является условие равенства нулю ее градиента:

(8.2)

или

б) достаточное условие. Достаточным условием является условие положительной определенности матриц Гессе:

(8.3)

Для положительной определенности матрица Гесса необходимо, чтобы ее собственные числа l1,…,lm были положительны. Собственные числа l1,…,lm являются корнями характеристического уравнения:

(8.4)

где det -определитель квадратной матрицы ранга m, Е — единичная матрица.

Матрица C=G-lE называется характеристической матрицей для матрицы G.

3. Основные методы безусловной многомерной минимизации:

а) покоординатный спуск. В методе покоординатного спуска

выбирается начальная точка x0 с координатами .

Фиксируются все координаты кроме первой, и решается одномерная задача минимизации относительно переменной x1 (Рис.5). Затем фиксируются все координаты кроме второй, и опять решается задача одномерной минимизации относительно переменной x2 и т.д., т.е.

поочередно производится спускание по всем координатам xi, до тех пор, пока не выполнятся все условия:

, (8.5)

Если линия уровня имеет изломы, что соответствует “оврагам” на поверхности , то данный метод становится непригодным;

б) простой градиентный метод. В методе простого градиентного спуска выбирается начальная точка и начальное значение шага h. В точке вычисляется градиент и делается шаг в направлении антиградиента (Рис.6):

. (8.6)

В результате вычисляется точка . Если выполняется условие , то в точке вычисляется градиент и делается шаг в направление антиградиента. Если условие не выполняется, то шаг h уменьшают до тех пор, пока это условие не будет выполнено. Процесс продолжается до выполнения третьего условия (8.5).

Недостатком метода является необходимость на каждом шаге вычислять значение градиента, что требует достаточно много времени;

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

, (8.7)

где a выступает в качестве параметра.

В результате находится значение , соответствующее минимальному значению функции на выбранной прямой (Рис.7). Затем вычислительный процесс повторяется для точки и т.д. Критерием окончания является третье условие (8.5);

г) метод деформирован-ного многогранника. Когда не является гладкой, и имеются множества точек, где она не дифференцируема, используются прямые методы. Наиболее известным из них является метод деформированного многогранника или метод Нелдера-Мида. Задается m+1 точка . При этом все разности должны быть линейно независимыми.

Обычно это делается следующим образом. Задаются координаты точки , а координаты остальных точек определяются с помощью соотношения:

(8.8)

где h-параметр, который определяет стороны многогранника.

Точки являются сторонами равнобедренного многогранника (на плоскости это треугольник).

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

(8.9)

Далее вычисляется пробная точка:

(8.10)

которая является симметричным отражением исключенной точки относительно точки (Рис.8).

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

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

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

(8.11)

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

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

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

(8.12)

и тоже рассматривается новый многогранник с точками , где , а . Многогранник при этом также деформируется.

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

Процесс заканчивается, когда длины всех сторон многогранника, выходящих из точки с минимальным значением, станут меньше некоторого выбранного e или после очередного восстановления параметр h/2 станет меньше e.

Варианты задания №11

Найти точку минимума функции U(x,y) с точностью 0,1 указанным методом: а-покоординатный спуск, б-простой градиентный метод, в-метод наискорейшего спуска, г-метод деформированного многогранника.

1. 2.

3. 4.

5. 6.

7. 8.

9. 10.

11. 12.

13. 14.

15. 16.

17. 18.

19. 20.

21. 22.

23. 24.

25. 26.

27. 28.

29. 30.

31. 32.

33. 34.

35. 36.

37. 38.

39. 40.

Не нашли то, что искали? Воспользуйтесь поиском:

Источник: https://studopedia.ru/6_124471_VIII-metodi-mnogomernoy-optimizatsii.html

Методы многомерной оптимизации

5.Методы одномерной и многомерной оптимизации

Рисунок 5.11 — Поиск оптимума целевой функции методом покоординатного спуска

18

После вычисления N значений целевой функции коэффициент дробления

интервала неопределенности составляет f = 0,618N −1

Используя эту формулу нетрудно показать, что для достижения той же величины коэффициента дробления f = 0.01 по методу золотого сечения достаточно сделать лишь только 11 вычислений целевой функции.

5.6.1Общие соображения

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

ятность унимодальности целевой функции. Кроме того, множество элементов,

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

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

1 методом общего поиска требуется вычислить 19 значений целевой функции, то в случае двумерного пространства это число составляет 361, трехмерного — 6859, четырехмерного — 130321, а пятимерного — 2476099! Поскольку при выборе оптимальном проектировании нередко приходится иметь дело с пятью и более переменными, серьезность трудностей, обусловленных многомерностью, становится бесспорной.

5.6.2 Метод покоординатного спуска (подъема)

Наиболее простым прямым методом поиска оптимума считается метод Га-

усса-Зейделя, называемый также методом покоординатного спуска (подъема).

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

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

поиска

зафиксирована, а вдоль коор-

динаты

ищется минимум или макси-

мум (точка M1) одним из методов одно-

мерной оптимизации. Затем, сохраняя новое значение постоянным, ищут оптимум по (точка M2) и т.д. В общем случае, по завершении этой процедуры для всех переменных можно вернуться к

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

ствляется по достижению заданной точности.

19

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

Если же эти оси наклонены к осям координат (как на рис. 5.

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

Метод покоординатного подъема совершенно неприменим, если линии уровня имеют точки излома (рис. 5.13). Поскольку линии уровня такого типа очень часто встречаются в инженерной

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

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

Рисунок 5.12 — Линии уровня целевой функции близки по форме к окружностям или эллипсам, оси которых параллельны осям координат

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

5.6.3 Метод случайного поиска

Рисунок 5.13 — Целевая функция имеет линию излома

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

вычислить, чтобы, пользуясь методом общего поиска, получить f = 0.1, и было показано, что это число растет как степенная функция, показатель степени которой

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

трудность, основан на случайном поиске (метод Монте-Карло).

Сущность метода Монте-Карло заключается в том, что на каждом k-цикле с

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

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

ции . Перебирая точки (рис. 5.14), компьютер отбрасывает те из них, кото-

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

20

Результат, полученный с помощью метода Монте-Карло характеризуется вероятностью P того, что при данном числе случайных проб K, расположение точки оптимума будет определено с точностью f, где f — объем N-мерного куба, выраженный в долях от общего объема поиска.

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

Рисунок 5.14 — Метод случайного поиска

где

– вероятность попадания в

(метод Монте-Карло).

заданную область f для одной пробы;

– вероятность того же для K проб.

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

В табл. 5.1 указано, сколько надо сделать случайных проб K для соответствующих величин P и f. Из таблицы видно, что при 44 случайных пробах вероятность достижения f = 0.1 составит 99%. Вспомним, что для 100%-ного обеспечения целевую функцию в случае пяти переменных пришлось бы вычислить 2 476 099 раз!

Таблица 5.1 – Необходимое число случайных проб K для обеспечения вероятности P получения заданного точности f

f

Значения K для различных P

0.80

0.90

0.95

0.99

0.100

16

22

29

44

0.050

32

25

59

90

0.010

161

230

299

459

0.005

322

460

598

919

Метод случайного поиска имеет два преимущества. Во-первых, он пригоден

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

сматриваемого пространства. Хотя этот метод не позволяет непосредственно

найти оптимальное решение, он создает подходящие предпосылки для примене-

ния в дальнейшем других методов поиска. Поэтому его часто применяют в соче-

тании с одним или несколькими методами других типов.

5.6.4 Градиентные методы

Во многих алгоритмах многомерной оптимизации используется информация

о градиентах. Как известно, градиент ортогонален к гиперповерхности отклика

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

21

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

Даже ничего не видя, он может это сделать, если все время будет двигаться вверх.

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

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

функции F(х1, х2, х3, …, xN) имеет вид

где частные производные вычисляются в рассматриваемой точке. Этот вектор направлен вверх, в направлении подъема; обратный ему вектор указывает направление спуска. Единичный вектор градиента часто представляют в виде

где

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

Здесь ∆ — небольшое смещение в направлении xi. Эту формулу часто называют «приближением секущей».

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

Пошаговые градиентные методы при отсутствии ограничений сводятся к следующему.

Этап 1. Пусть нам известны начальные значения проектных параметров

.

Этап 2. Определяется направление наискорейшего изменения целевой

функции F(х1, х2, х3, …, xN), т.е. ее градиента

в исходной

точке.

6Математическим эквивалентом обрыва на поверхности, образуемой целе-

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

7В этом случае говорят о квазиградиентных методах

22

Этап 3. Осуществляется перемещение из точки

в точку

по направлению, противоположному направлению

градиента

Этап 4. В точке

определяется новое направление

градиента целевой функции

и осуществляется переме-

щение в точку

и т.д. до тех пор, пока не будет выполнено

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

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

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

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

Особенностью метода наискорейшего спуска (рис. 5.15) является движе-

ние с оптимальным шагом h, рассчитанным с помощью одномерной минимизации

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

новой точки

на заданной прямой. Поэтому алгоритм метода наискорейшего

спуска содержит следующие этапы.

Этап 1.

Определяется направление градиента целевой функции

в исходной точке.

Этап 2. Нахождение одним из методов одномерного поиска оптимального шага вдоль антиградиентного направления. Величина шага h определяется из ус-

ловия минимума функции

.

Этап 3. Осуществляется движение с этим шагом по лучу, направленному

по

антиградиенту целевой

функции

точке

до тех пор, пока функция F не достигнет минимума на

этой прямой (точка

).

Этап 4. В точке

определяется новое направление

градиента

целевой

функции

и осуществля-

ется

перемещение

в

точку

и т.д. до тех

пор, пока не будет выполнено условие

прекращения поиска.

Траектория поиска этим методом

показана на рис. 5.15. Из рисунка видно,

что движение вдоль одного направле-

ния прекращается, когда линия направ-

ления поиска становится касательной к

какой-либо линии равного уровня. Каж-

дое новое направление движения к экс-

тремуму

ортогонально

предшествую-

щему.

Рисунок 5.15 – Траектория поиска

методом наискорейшего подъема

(спуска)

Источник: https://studfile.net/preview/3653207/page:5/

Uchebnik-free
Добавить комментарий