86223 (612688), страница 2

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

Текст из файла (страница 2)

С учетом (3) уравнение касательной у (х) =f (х₀) +f ’ (х₀) (х-х₀) к графику f (x) для точки x₀ =х* принимает вид у (х) =f (x*). Поэтому из (2) следует, что f (x) f (x*) для всех х [а; b], т.е. х* - точка глобального минимума f (x).

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

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

5. Можно показать, что всякая выпуклая непрерывная на отрезке [а; b] функция является и унимодальной на этом отрезке. Обратное, вообще говоря, неверно (рисунок 4).

Рисунок 4 - график унимодальной, но не выпуклой функции

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

2. Прямые методы безусловной оптимизации

Для решения задачи минимизации функции f (х) на отрезке [а; b] на практике, как правило, применяют приближенные методы. Они позволяют найти решение этой задачи с необходимой точностью в результате определения конечного числа значений функции f (х) и ее производных в некоторых точках отрезка [а; b]. Методы, использующие только значения функции и не требующие вычисления ее производных, называются прямыми методами минимизации.

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

Рассмотрим наиболее распространенные на практике прямые методы поиска точки минимума. Самым слабым требованием на функцию f (х), позволяющим использовать эти методы, является ее унимодальность. Поэтому далее будем считать функцию f (х) унимодальной на отрезке [а; b].

Рассмотрим конкретные вычислительные алгоритмы решения задачи безусловной минимизации f (х) min, x E_n, которые опираются только на вычисление значений функции f (х), т.е. прямые методы минимизации. Важно отметить, что для их применения не требуется дифференцируемость целевой функции и даже ее аналитическое задание. Нужно лишь иметь возможность вычислять или измерять значения f (х) в произвольных точках. Такие ситуации часто встречаются в практически важных задачах оптимизации.

2.1 Прямые методы одномерной безусловной оптимизации

Методы исключения отрезков

Пусть а < x₁<х₂1 и х₂ (пробных точках), можно сократить отрезок поиска точки х *, перейдя к отрезку [а; х₂], если или к отрезку m [x_1; b] если (рисунок 5). Описанную процедуру можно повторить необходимое число раз, последовательно уменьшая отрезок, содержащий точку минимума. Когда длина последнего из найденных отрезков станет достаточно малой, следует положить , где - одна из точек этого отрезка, например, его середина. Методы минимизации, основанные на этом принципе, называются методами исключения отрезков.

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

Рисунок 5 - Уменьшение отрезка поиска точки минимума методами исключения отрезков

2.1.1 Метод деления отрезка пополам (дихотомии)

Суть метода заключается в том, что заданный отрезок [а; b] делится пополам:

.

Затем в каждой из половин отрезка [а; с] и [с; b] выбираются по одной точке x₁ и х_2, в них вычисляются значения функций, производится сравнение полученных значений, и в результате сравнения устанавливается отрезок, в котором минимума быть не может. Откинув его, продолжаем ту же процедуру с полученным отрезком до тех пор, пока вновь полученный отрезок не станет меньше по длине некоторой наперед заданной величины:

.

Скорость достижения очевидно зависит от величины откидываемого отрезка. Поэтому x₁ и х₂ выбираются симметрично на расстоянии :

(4)

где > 0 - малое число.

В конце вычислений по методу дихотомии в качестве приближенного значения х* берут середину последнего из найденных отрезков [а; b], убедившись предварительно, что достигнуто неравенство .

Опишем алгоритм метода деления отрезка пополам.

Шаг 1. Определить середину отрезка и значения x₁ и х₂ по формулам (4). Вычислить f (x₁) и f (x₂).

Шаг 2. Сравнить f (x₁) и f (x₂). Если , то перейти к отрезку [а; x₂], положив b = x_2, иначе - к отрезку [x₁; b], положив а = x_1.

Шаг 3. Найти достигнутую точность . Если то перейти к следующей итерации, вернувшись к шагу 1. Если , то завершить поиск х*, перейдя к шагу 4.

Шаг 4. Положить

.

Замечания:

1. Число из (4) выбирают на интервале (0; 2) с учетом следующих соображений:

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

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

Пусть - погрешность счета. Тогда следует учитывать следующее условие:

.

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

Рассмотрим такое симметричное расположение точек x₁ и х₂ на отрезке [а; b], при котором одна из них становится пробной точкой и на новом отрезке, полученном после исключения части исходного отрезка. Использование таких точек позволяет на каждой итерации метода исключения отрезков, кроме первой, ограничиться определением только одного значения f (x), так как другое значение уже найдено на одной из предыдущих итераций.

Найдем точки x₁ и х_2, обладающие указанным свойством.

Рассмотрим сначала отрезок [0; 1] и для определенности предположим, что при его уменьшении исключается правая часть этого отрезка. Пусть х₂ = , тогда симметрично расположенная точка х₁ = 1- (рисунок 6).

Рисунок 6 - Определение пробных точек в методе золотого сечения

Пробная точка х₁ отрезка [0; 1] перейдет в пробную точку х₂ = 1- нового отрезка [0; ]. Чтобы точки х₂ = , и х₂ = 1- делили отрезки [0; 1] и [0; ] в одном и том же отношении, должно выполняться равенство или , откуда находим положительное значение

…

Таким образом,

х₁ = 1- = , .

Для произвольного отрезка [а; b] выражения для пробных точек примут вид

; . (5)

Замечания:

1. Точки x₁ и х₂ из (5) обладают следующим свойством: каждая из них делит отрезок [а; b] на две неравные части так, что отношение длины всего отрезка к длине его большей части равно отношению длин большей и меньшей частей отрезка. Точки с таким свойством называются точками золотого сечения отрезка [а; b]. Это и объясняет название рассматриваемого метода.

2. На каждой итерации исключения отрезков с пробными точками (5) одна из них переходит на следующий отрезок и значение f (x) в этой точке вычислять не следует. Если новым отрезком становится [а; х₂], то на него переходит пробная точка исходного отрезка, становясь его второй пробной точкой (х₂^’= х₁) (рисунок 6). В случае перехода к отрезку [х₁; b] пробная точка исходного отрезка становится первой пробной точкой отрезка [х₁; b].

3. Легко проверить, что х₁=а+b-х_2, и x₂=а+b-х₁. Поэтому на каждой итерации метода золотого сечения недостающую пробную точку нового отрезка можно найти по перешедшей на него пробной точке с помощью сложения и вычитания, не используя формул (5).

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

.

Опишем алгоритм метода золотого сечения.

Шаг 1. Найти х₁ и х₂ по формулам (5). Вычислить f (x₁) и f (x₂).

Шаг 2. Определить . Проверка на окончание поиска: если _n > , то перейти к шагу 3, иначе - к шагу 4.

Шаг 3. Переход к новому отрезку и новым пробным точкам. Если f (x₁) f (x₂) то положить b=x_2, x₂=x₁, f (x₂) f (x₁), x₁=b- (b-a) и вычислить f (x₁), иначе - положить a=x₁, x₁= x₂, f (x₁) = f (x₂), x₂=b+ (b-a) и вычислить f (x₂). Перейти к шагу 2.

Шаг 4. Окончание поиска: положить

, .

Сравнение методов исключения отрезков. При сравнении прямых методов минимизации обычно учитывают количество N значений f (x), гарантирующее заданную точность определения точки х* тем или иным методом. Чем меньше N, тем эффективнее считается метод. При этом вспомогательные операции такие, как выбор пробных точек, сравнение значений f (x) и т.п., не учитываются. Во многих практических случаях определение значений целевой функции требует больших затрат (например, времени ЭВМ или средств для проведения экспериментов) и вспомогательными вычислениями можно пренебречь. А эффективность метода минимизации особенно важна именно в таких случаях, поскольку позволяет сократить указанные затраты.

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

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

Пусть заданы следующие параметры:

Примем и . Тогда (рисунок 7).

Рисунок 7 - Поведение исходной функции на заданном отрезке

Проведем несколько итерации методом дихотомии:

Поскольку f (x₁) < f (x₂), то b: =x₂, a оставляем прежним. Тогда для следующей итерации:

Так как f (x₁) > f (x₂), то a: =x₁, b оставляем прежним. Тогда на третьем шаге:

Результаты полного решения данной задачи представлены на рисунке 8. Листинг программы представлен в приложении А.

Рисунок 8 - Получение решения методом дихотомии

Для метода золотого сечения:

Так как f (x₁) < f (x₂), то b: =x₂, a оставляем прежним. Тогда для следующей итерации:

Поскольку f (x₁) < f (x₂), то b: =x₂, a оставляем прежним. Тогда на третьем шаге:

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

Рисунок 9 - Получение решения методом золотого сечения

2.2 Методы безусловной минимизации функций многих переменных

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

2.2.1 Метод циклического покоординатного спуска

Этот метод заключается в последовательной минимизации целевой функции f (x) по направлениям x1 и x2.

Рисунок 10 - Циклический покоординатный спуск.

Опишем этот алгоритм.

Шаг 0. Выбрать х E_n, критерий достижения точности и шаг . Найти f (x1 ^(0),x2 ⁽⁰⁾⁾.

Шаг 1. Принять x1 ⁽¹⁾ = x1 ⁽⁰⁾ + . Определить f (x1 ^(1),x2 ⁽⁰⁾⁾. Сравнить полученное значение с значением начальной функции. Если f (x1 ^(1),x2 ⁽⁰⁾⁾ < f (x1 ^(0),x2 ⁽⁰⁾⁾, то перейти к шагу 5, если же f (x1 ^(1),x2 ⁽⁰⁾⁾ > f (x1 ^(0),x2 ⁽⁰⁾⁾, то перейти к шагу 2.

Шаг 2. Принять x1 ⁽¹⁾ = x1 ^{(0) -} . Определить f (x1 ^(1),x2 ⁽⁰⁾⁾. Сравнить полученное значение с значением начальной функции. Если f (x1 ^(1),x2 ⁽⁰⁾⁾ < f (x1 ^(0),x2 ⁽⁰⁾⁾, то перейти к шагу 5, если же f (x1 ^(1),x2 ⁽⁰⁾⁾ > f (x1 ^(0),x2 ⁽⁰⁾⁾, то перейти к шагу 3.

Шаг 3. Принять x2 ⁽¹⁾ = x2 ⁽⁰⁾ + . Определить f (x1 ^(0),x2 ⁽¹⁾⁾. Сравнить полученное значение с значением начальной функции. Если f (x1 ^(0),x2 ⁽¹⁾⁾ < f (x1 ^(0),x2 ⁽⁰⁾⁾, то перейти к шагу 5, если же f (x1 ^(0),x2 ⁽¹⁾⁾ > f (x1 ^(0),x2 ⁽⁰⁾⁾, то перейти к шагу 4.

Шаг 4. Принять x2 ⁽¹⁾ = x2 ^{(0) -} . Определить f (x1 ^(0),x2 ⁽¹⁾⁾. Сравнить полученное значение с значением начальной функции. Если f (x1 ^(0),x2 ⁽¹⁾⁾ < f (x1 ^(0),x2 ⁽⁰⁾⁾, то перейти к шагу 4, если же f (x1 ^(0),x2 ⁽¹⁾⁾ > f (x1 ^(0),x2 ⁽⁰⁾⁾, то принять исходную точку за минимум.

Шаг 5. Проверить условие достижения точности .

Если в процессе решения с шагом не получено решения, то принять

2.2.2 Алгоритм Хука-Дживса

Этот алгоритм содержит две основные процедуры:

а) исследующий покоординатный поиск в окрестности данной точки, предназначенный для определения направления убывания f (х);

б) перемещение в направлении убывания.

Рисунок 11 - Метод Хука-Дживса

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

Опишем один из алгоритмов данного метода.

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

Шаг 2. Обозначим координаты начального вектора: .

Тогда, соответственно, угол направления движения

.

Рассчитываем координаты 4-х точек в окрестности начальной по следующим формулам:

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

Шаг 3. Сравниваем полученные значения с f (x1 ^(0),x2 ⁽⁰⁾⁾. Если какое-нибудь из них оказалось меньше значения функции в 0-й точке точке, то принимаем его за исходное и переходим к шагу 5.

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

Шаг 5. Проверить условие достижения точности

.

Характеристики

Список файлов курсовой работы