Многомерные задачи оптимизации (стр. 2 из 6)

(2.1)

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

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

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

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

Число

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

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

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

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

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

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

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

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

2.3 Метод золотого сечения.

Метод золотого сечения состоит в построении последовательности отрезков [a₀, b₀], [a₁, b₁], …,стягивающихся к точке минимума функции f(x). На каждом шаге, за исключением первого, вычисление значения функции f(x) проводится лишь один раз. Эта точка, называемая золотым сечением, выбирается специальным образом.

На первом шаге процесса оптимизации внутри отрезка [a₀, b₀] выбираем две внутренние точки x₁ и x₂ и вычисляем значения целевой функции f(x₁) и f(x₂). Поскольку в данном случае f(x₁) < f(x₂), очевидно, что минимум расположен на одном из прилегающих к x₁ отрезков [a₀, x₁] или [x₁, x₂]. Поэтому отрезок [x₂, b₀] можно отбросить, сузив тем самым первоначальный интервал неопределенности.

Второй шаг проводим на отрезке [a_1, b₁], где a₁ = a₀, b₁ = x₂. Нужно снова выбрать две внутренние точки, но одна из них (x₁) осталась из предыдущего шага, поэтому достаточно выбрать лишь одну точку x₃, вычислить значение f(x₃) и провести сравнение. Поскольку здесь f(x₃) > f(x₁), ясно, что минимум находится на отрезке [x₃, b₁]. Обозначим этот отрезок [a₂, b₂], снова выберем одну внутреннюю точку и повторим процедуру сужения интервала неопределенности. Процесс оптимизации повторяется до тех пор, пока длина очередного отрезка [a_n, b_n] не станет меньше заданной величины ε.

Теперь рассмотрим способ размещения внутренних точек на каждом от резке [a_k, b_k]. Пусть длина интервала неопределенности равна l, а точка деления делит его на части l₁, l₂: l₁ > l₂, l = l₁ + l₂. Золотое сечение интервала неопределенности выбирается так, чтобы отношение длины большего отрезк к длине всего интервала равнялось отношению длины меньшего отрезка к длине большего отрезка:

(1)

Из этого соотношения можно найти точку деления, определив отношение l₂/l₁. Преобразуем выражение (1), и найдем это значение:

l

=l₂l₁, l =l₂(l₁ + l₂),

l

+l₁l₂ - l =0,

² + - 1 =0,

= .

Поскольку нас интересует только положительное решение, то

.

Отсюда l₁

k₁l, l₂ k₂l.

Поскольку заранее неизвестно, в какой последовательности делить интервал неопределенности, то рассматривают внутренние точки, соответствующие двум этим способам деления. Точки деления x₁ и x₂ выбираются с учетом полученных значений для частей отрезка. В данном случае имеем

x₁ – a₀ = b₀ – x₂ = k₂d₀,

b₀ - x₁ = x₂ – a₀ = k₁d₀,

d₀ = b₀ – a₀.

После первого шага оптимизации получается новый интервал неопределенности – отрезок [a_1, b₁].

Можно показать, что точка x₁ делит этот отрезок в требуемом отношении, при этом

b₁ – x₁ = k₂d₁, d₁ = b₁ – a₁.

Для этого проведем очевидные преобразования:

b₁ – x₁ = x₂ – x₁ = (b₀ – a₀) – (x₁ – a₀) – (b₀ – x₂) = d₀ – k₂d₀ - k₂d₀ = k₃d₀,

d₁ = x₂ – a₀ = k₁d₀,

b₁ – x₁ = k₃(d₁/k₁) = k₂d₁.

Вторая точка деления x₃ выбирается на таком же расстоянии от левой границы отрезка, т.е. x₃ – a₁ = k₂d₁.

И снова интервал неопределенности уменьшается до размера

d₂ = b₂ – a₂ = b₁ – x₃ = k₁d₁ = k

d₀.

Используя полученные соотношения, можно записать координаты точек деления y и z отрезка [a_k, b_k] на k +1 шаге оптимизации (y < z):

y = k₁a_k + k₂b_k,

z = k₂a_k + k₁b_k.

При этом длина интервала неопределенности равна

d_k = b_k – a_k = k

d₀.

Процесс оптимизации заканчивается при выполнении условия d_k < ε. При этом проектный параметр оптимизации составляет a_k < x < b_k. Можно в качестве оптимального значения принять x = a_k (или x = b_k, или x = (a_k + b_k)/2 и т.п.).

2.4 Метод Ньютона.