Глава 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- h)³ f (x 0)£ f (x 0+ h), то в качестве начального интервала неопределённости берётся отрезок [ x 0- h, x 0+ h ]. Если f (x 0- h)£ f (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- h)³ f (x 0)£ f (x 0+ h), то начальный интервал неопределённости определён: [ a 0, b 0]=[ x 0- h, x 0+ h ];
б) если f (x 0- h)£ f (x 0)³ f (x 0+ h), то функция не является унимодулярной, и требуемый интервал не может быть найден. Требуется задать другую x 0.
в) если условие окончания не выполняется, то перейти к шагу 4.
4. Определить величину D:
а) если f (x 0- h)³ f (x 0)³ f (x 0+ h), то D= h, a 0= x 0, x 1= x 0+ h;
б) если f (x 0- h)£ f (x 0)£ f (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 +1)³ f (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.
Ниже мы рассматриваем два метода нулевого порядка. Один относится к параллельным, другой - к последовательным стратегиям.