Методы нулевого порядка одномерной минимизации




Глава II. Численные методы нелинейного программирования

Общие положения

 

Постановка проблемы

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

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

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

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

Общие принципы.

Подавляющее большинство численных методов оптимизации относится к итерационным. Суть итерационных методов заключается в том, что задаётся некоторая начальная точка X 0 в R n и строится последовательность { Xk } точек в R n, причём очередная Xk +1 строится по предыдущим, как правило, по Xk.

Для определённости рассмотрим задачу безусловного локального минимума:

f (X *)= . (1.2.1)

Численное решение задачи (1.2.1) заключается в построении последовательности { Xk }, обладающей свойством

f (Xk +1)< f (Xk), k =0, 1, …, (1.2.2)

В общем виде итерационная последовательность по формулам

Xk +1= Xk + hkDk, (1.2.3)

где Dk - направление перехода из точки Xk в точку Xk +1, обеспечивающее выполнение условия (1.2.2). Оно называется направлением спуска, hk - величина шага.

Начальная точка X 0 задаётся, исходя из некоторых соображений применительно к конкретному методу.

Направление спуска Dk должно удовлетворять условию

f (Xk), Dk)<0, k =0, 1, …, (1.2.4)

которое обеспечивает убывание функции. Например, в качестве Dk можно взять антиградиент -Ñ f (Xk).

Величина шага hk >0 выбирается либо из условия (1.2.2), либо из условия

f (Xk + hkDk. (1.2.5)

обеспечивающего наискорейший спуск в направлении Dk.

Последовательность { Xk } называется минимизирующей, если = . Сходимость последовательности { Xk } при выборе приемлемого направления Dk и величины шага hk из условия (1.2.2) или (1.2.5) зависит от характера функции f (X) и от выбора начальной точки X 0.

В зависимости от наивысшего порядка (частных) производных функции f (X), используемых для формирования Dk и hk, численные методы задачи безусловной оптимизации делятся на три группы:

1. Методы нулевого порядка, использующие только информацию о значении функции f (X).

2. Методы первого порядка, использующие информацию о первых производных функции f (X).

3. Методы второго порядка, использующие информацию о вторых производных функции f (X).

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

 

Методы нулевого порядка одномерной минимизации

Общие положения

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

Функция f (x) называется унимодулярной на интервале [ a, b ], если она достигает глобального минимума на [ a, b ] в единственной точке x *, причём слева от x * функция строго убывает, а справа - строго возрастает.

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

Для любого метода одномерной оптимизации необходимо задание начального интервала L 0=[ a 0, b 0], в котором лежит точка минимума. Интервал L 0 называется начальным интервалом неопределённости.

Для выбора начального интервала неопределённости можно применить, например, алгоритм Свенна, идея которого заключается в следующем:

Берутся равноотстоящие друг от друга на некоторый шаг h три точки x 0- h, x 0, x 0+ h и сравниваются значения f в этих точках. Если f (x 0- hf (x 0f (x 0+ h), то в качестве начального интервала неопределённости берётся отрезок [ x 0- h, x 0+ h ]. Если f (x 0- hf (x 0)≥ f (x 0+ h), то функция на этом отрезке противоречит определению унимодулярности, и таковой не является. Тогда берутся другие три точки и процедура повторяется. Если же на отрезке [ x 0- h, x 0+ h ] функция монотонна, то наращиваем отрезок в сторону убывания с определённым шагом D до тех пор, пока значение функции в очередном конце отрезка не превысит значения на предыдущем. Это будет означать, что локальный минимум функции достигается на полученном отрезке. Более подробно:

1. Задать произвольно следующие параметры: x 0 - некоторую точку, h >0 - величину шага. Положить k =0.

2. Вычислить значение функции в точках x 0- h, x 0, x 0+ h.

3. Проверить условие окончания:

а) если f (x 0- hf (x 0f (x 0+ h), то начальный интервал неопределённости определён: [ a 0, b 0]=[ x 0- h, x 0+ h ];

б) если f (x 0- hf (x 0f (x 0+ h), то функция не является унимодулярной, и требуемый интервал не может быть найден. Требуется задать другую x 0.

в) если условие окончания не выполняется, то перейти к шагу 4.

4. Определить величину D:

а) если f (x 0- hf (x 0f (x 0+ h), то D= h, a 0= x 0, x 1= x 0+ h;

б) если f (x 0- hf (x 0f (x 0+ h), то D=- h, b 0= x 0, x 1= x 0- h, k =1

5. Найти следующую точку xk +1= xk +2 k D;

6. Проверить условие убывания функции:

а) если f (xk +1)< f (xk) и D= h, то a 0= xk;

если f (xk +1)< f (xk) и D=- h, то b 0= xk;

в обоих случаях положить k = k +1 и перейти к шагу 5);

б) если f (xk +1f (xk), то процедура завершается. При D= h положить b 0= xk +1, а при D=- h положить a 0= xk +1. В результате имеем [ a 0, b 0] - искомый интервал неопределённости.

Пример I. Найти методом Свенна начальный интервал неопределённости для решения задачи f (x)= x 2-6 x +14®min при x 0=0, h =1.

Решение. 1. Положим k =0.

2.0. Вычислить значение функции в точках x 0- h =-1, x 0=0, x 0+ h =1:

f (-1)=21, f (0)=14, f (1)=9.

3.0. Так как f (-1)> f (0)> f (1)=9, то условие окончания не выполняется.

4.0. Полагаем D= h =1, a 0= x 0=0, x 1= x 0+ h =1, k =1.

5.1. Найдём следующую точку x 2= x 1+2D=3.

6.1. Проверим условие убывания функции. Так как f (x 2)=5< f (x 1)=9 и D= h, то a 0= x 1=1. Положим k =2.

5.2. Найдём следующую точку x 3= x 2+22D=7;

6.2. Проверим условие убывания функции. Так как f (x 3)=21>5= f (x 2) то поиск завершён: правая граница b 0=7.

Ответ: [1; 7] - начальный интервал неопределённости.

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

1. Выбор начального интервала неопределённости.

2. Уменьшение интервала неопределённости.

3. Проверка условия окончания. Поиск заканчивается, когда длина текущего интервала неопределённости [ ak, bk ] оказывается меньше заданной величины e.

Ниже мы рассматриваем два метода нулевого порядка. Один относится к параллельным, другой - к последовательным стратегиям.



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-02 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: