6.3. ПРЯМЫЕ МЕТОДЫ ПОИСКА
Прямые методы одномерного поиска
К прямым методам поиска относят методы, в которых для отыскания экстремума не используются производные первого и высших порядков. В этих методах направления поиска определяются на основе последовательных вычислений значений функции 
.
Как правило, при решении задач НП при отсутствии ограничений градиентные методы и методы, использующие вторые производные, сходятся быстрее, чем прямые методы. Тем не менее, применяя на практике методы, использующие производные, мы сталкиваемся со следующими трудностями. Во-первых, в задачах с большим числом переменных трудно или совсем невозможно получить производные в виде аналитических функций, необходимых для методов первого и второго порядков. Конечно, аналитические выражения для производных можно заменить вычислением их по разностным схемам, однако возникающие при этом погрешности (в особенности в окрестности экстремума), ограничивают возможности такой аппроксимации. Прямые методы не требуют выполнения условий регулярности и непрерывности и существования производных.
Во-вторых, градиентные методы оптимизации требуют довольно большого времени на подготовку задачи к решению по сравнению с прямыми методами.
Рассмотрим сначала задачу минимизаци функции одной переменной 
при условии 
. Так как точное место нахождения локального минимума на интервале 
неизвестно, то целесообразно назвать этот интервал интервалом неопределенности.
Вообще называется интервалом неопределенности, если точка минимума 
, хотя ее точное значение неизвестно.
 |
Рис. 6.7.
Покажем, что если функция выпукла или строго квазивыпукла, то интервал неопределенности можно сократить с помощью вычисления значений в двух точках, принадлежащих интервалу.
Теорема 6.1. Пусть выпукла или строго квазивыпукла в интервале . Пусть 
такие, что 
. Если 
, то 
для всех 
. Если же 
, то 
для всех 
.
Доказательство. Пусть и 
. Предположим, что утверждение теоремы неверно, т.е. пусть 
. Так как точка 
может быть представлена в виде выпуклой комбинации точек 
, а - строго квазивыпуклая функция, то
но это противоречит утверждению, что . Следовательно, .
Аналогично доказывается и вторая часть теоремы. Из этой теоремы следует, что при условии строгой квазивыпуклости , если , то новым интервалом неопределенности является 
. Если же , то новым интервалом неопределенности будет 
. Оба эти случая проиллюстрированы на рис.6.8.
Рассмотрим несколько процедур минимизации строго квазивыпуклой функции на замкнутом ограниченном интервале, последовательно сокращая начальный интервал неопределенности.
Дихотомический поиск
Итак, пусть задана строго квазивыпуклая функция , которую требуется минимизировать на интервале 
. Очевидно, наименьшее число вычислений значений функции, которые необходимы для сокращения интервала неопределенности, равно двум. На рис.6.8, а имеем 
и, следовательно, согласно теореме 6.1 новым интервалом неопределенности является 
, а для случая 
(рис.6.8, б) новым интервалом неопределенности является 
. Таким образом, в зависимости от вида функции длина нового интервала неопределенности равна 
или 
. Априори не известно, будет ли или . Поэтому оптимальная стратегия выбора точек 
состоит в минимизации максимума величины 
и .
Это может быть достигнуто выбором в качестве 
и 
середины интервала . Однако в этом случае будем иметь только одну точку и не сможем далее сократить интервал неопределенности. Поэтому выбираем 
и 
 |
Рис. 6.8.
симметрично расположенными относительно середины интервала на расстоянии 
от него. Здесь число 
должно быть выбрано настолько малым, чтобы, с одной стороны, длина нового интервала неопределенности 
являлась достаточно близкой к теоретически оптимальному значению 
и в то же время значения функций 
и 
были различимы.
Таким образом, в методе дихотомического поиска место нахождения каждого из двух первых наблюдений (вычислений) функции и выбирается симметрично на расстоянии от середины интервала 
. В зависимости от значений функции в точках , определяется новый интервал неопределенности.
Дадим описание алгоритма дихотомического поиска.
Предварительный этап. Выбрать константу различимости и допустимую конечную длину интервала неопределенности 
. Пусть - начальный интервал неопределенности. Положить 
и перейти к основному этапу.
Основной этап. Он состоит из конечного числа однотипных итераций.
-я итерация. Первый шаг. Если 
, то конец алгоритма, точка минимума принадлежит интервалу 
. В противном случае вычислить
(6.3.1)
и перейти ко второму шагу.
Второй шаг. Если 
, то положить 
. В противном случае, положить 
. Заменить 
на 
и перейти к первому шагу. Заметим, что длина интервала неопределенности в начале (
)-й итерации равна
(6.3.2)
Данное соотношение можно использовать для определения числа итераций, необходимых для достижения желаемой точности.
Сравнение различных процедур одномерного поиска естественно производить в соответствии со следующим коэффициентом сжатия:
где 
- длина интервала неопределенности 
до начала наблюдения; 
- длина интервала неопределенности спустя 
наблюдений. Очевидно, чем меньше величина 
, тем более эффективна соответствующая процедура алгоритма поиска.
При дихотомическом поиске значение этого коэффициента приблизительно равно 0,5.
Метод золотого сечения
Рассмотрим более эффективный метод для минимизации выпуклых и строго квазивыпуклых функций - метод золотого сечения.
Пусть на -й итерации метода золотого сечения интервал неопределенности равен . Согласно теореме 6.1 новый интервал неопределенности 
будет равен 
, если 
и 
- в противном случае.
Точки 
и 
выбираются исходя из следующих условий.
Длина нового интервала неопределенности 
не зависит от результата на -й итерации, т.е. от того, выполняется ли неравенство или 
. Кроме того, должно выполняться равенство 
. Таким образом, если
(6.3.3)
где 
, то для должно выполняться условие
(6.3.4)
так что
(6.3.5)
Для новой итерации 
и 
выбираются так, что либо совпадает с , либо совпадает с . Тогда на 
-й итерации потребуется только одно новое вычисление функции. Чтобы показать это, рассмотрим следующие два возможных случая (рис.6.9).
Случай 1. . В этом случае . Воспользуемся соотношением (6.3.3), заменив на . При 
имеем
(6.3.6)
Подставляя выражение для , из (6.3.3), (6.3.4) в (6.3.6), получим 
.
Случай 2. . В этом случае . Воспользуемся (6.3.4), заменив на . При 
имеем
.
Подставив (6.3.3), (6.3.4) в это уравнение, получим
.
Корнями этого уравнения являются 
и 
. Но так как
должно быть взято из интервала (0, 1), то 
. Таким образом, если на -й итерации и выбраны в соответствии с (6.3.3), (6.3.4), где , то длина интервала неопределенности сжимается с коэффициентом . При этом на первой итерации необходимы два вычисления функции в точках 
, 
, а на всех последующих - только одно вычисление, так как либо , либо .
Алгоритм золотого сечения. Предварительный этап. Выбрать допустимую конечную длину интервала неопределенности . Пусть - начальный интервал неопределенности. Положить 
, где . Вычислить 
, положить и перейти к основному этапу.
Основной этап. Первый шаг. Если 
, то остановиться, оптимальная точка принадлежит интервалу . В противном случае, если , то перейти ко второму шагу, а если , то к третьему шагу.
Второй шаг. Положить , , 
. Вычислить 
и перейти к четвертому шагу.
Третий шаг. Положить , , 
. Вычислить 
и перейти к четвертому шагу.
Четвертый шаг. Заменить на и перейти к первому шагу.
Пример 6.1. Пусть требуется найти 
при условии 
.
Очевидно, функция 
строго квазивыпукла и начальная длина интервала неопределенности равна 8. Сократим этот интервал неопределенности до интервала, длина которого не больше чем 0,2.
Определим первые две точки:
. Вычислив 
и 
, получим 
. Следовательно, новый интервал неопределенности равен (-3; 1.941). находим 
. На этом первая итерация заканчивается. Далее процесс поиска продолжается аналогично. Результаты вычислений приведены в табл.6.2.
После восьми итераций, содержащих девять вычислений функции, интервал неопределенности оказывается равным (-1.112; -0.936), так что в качестве точки минимума может быть взята, например, середина этого интервала -1.024. Заметим, что точкой точного минимума является точка -1.0.
Таблица 6.2
|
|
|
|
|
|
|
|
|
1 |
-3.000 |
5.000 |
0.056 |
1.944 |
0.115 |
7.667 |
|
2 |
-3.000 |
1.944 |
-1.112 |
0.056 |
-0.987 |
0.115 |
|
3 |
-3.000 |
0.056 |
-1.832 |
-1.112 |
-0.308 |
-0.987 |
|
4 |
-1.832 |
0.056 |
-1.112 |
-0.664 |
-0.987 |
-0.887 |
|
5 |
-1.832 |
-0.664 |
-1.384 |
-1.112 |
-0.853 |
-0.987 |
|
6 |
-1.384 |
-0.664 |
-1.112 |
-0.936 |
-0.987 |
-0.996 |
|
7 |
-1.384 |
-0.936 |
-1.208 |
-1.112 |
-0.457 |
-0.987 |
|
8 |
-1.208 |
-0.936 |
-1.112 |
-1.032 |
-0.987 |
-0.999 |
|
% |
-1.112 |
-0.936 |
Метод Фибоначчи
Метод Фибоначчи является одним из наиболее эффективных методов одномерной оптимизации выпуклых или квазивыпуклых функций. Подобно методу золотого сечения, он требует двух вычислений функции на первой итерации, а на каждой последующей только по одному. Однако этот метод отличается от метода золотого сечения тем, что коэффициент сокращения интервала неопределенности меняется от итерации к итерации.
Метод основан на последовательности чисел Фибоначчи 
, которая определяется следующим образом [2, 18]:
(6.3.7)
Таким образом, последовательность Фибоначчи имеет вид 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, .
Предположим, что на -й итерации интервал неопределенности равен . Рассмотрим две точки и определяемые следующим образом:
(6.3.8)
(6.3.9)
где n - заданное общее число вычислений функции.
Согласно теореме 6.1, новый интервал неопределенности будет равен , если и , если . В первом случае, учитывая (6.3.8) и полагая 
в (6.3.7), получим
(6.3.10)
Во втором случае, учитывая (6.3.9), получаем
Таким образом, в обоих случаях длина интервала неопределенности сжимается с коэффициентом 
. Покажем, что на -й итерации либо , либо , так что требуется только одно новое вычисление функции. Предположим, что . Тогда по теореме 6.1 
, 
. Таким образом, используя (6.3.7) и заменивна,получаем 
Подставив выражение для из (6.3.8) и заменив на , получим
(6.3.11)
Подставляя это значение в (6.3.11), получим
. (6.3.12)
Если , то выполнив аналогичные преобразования, получим . Таким образом, в обоих случаях на -й итерации требуется только одно вычисление функции.
В отличие от методов дихотомического поиска и золотого сечения в методе Фибоначчи требуется, чтобы общее число вычислений 
(или коэффициент сокращения исходного интервала) было задано заранее. Это объясняется тем, что точки, в которых производятся вычисления, определяются по формулам (6.3.8), (6.3.9) и, следовательно, зависят от . Из формулы (6.3.10) следует, что длина интервала неопределенности на -й итерации сжимается с коэффициентом 
. Следовательно, после 
итерации, где - заданное общее число вычислений функции , длина интервала неопределенности сократится от 
до 
.
Алгоритм метода Фибоначчи. Предварительный этап. Выбрать допустимую конечную длину интервала неопределенности и константу различимости . Пусть задан начальный интервал неопределенности . Выбрать общее число вычислений функции так, чтобы 
. Положить 
. Вычислить 
, положить и перейти к основному этапу.
Основной этап. Первый шаг. Если , то перейти ко второму шагу, в противном случае - к третьему шагу.
Второй шаг. Положить , . Затем положить , 
. Если 
, то перейти к пятому шагу, в противном случае вычислить и перейти к четвертому шагу.
Третий шаг. Положить 
, 
, , 
. Если , то перейти к пятому шагу, в противном случае 
и перейти к четвертому шагу.
Четвертый шаг. Заменить на и перейти к первому шагу.
Пятый шаг. Положить 
. Если 
, то положить 
, 
. В противном случае (если 
), положить 
, 
. Конец: оптимальное решение содержится в интервале 
.
Пример 6.2. Рассмотрим ту же задачу;
при условии
.
Потребуем, чтобы длина конечного интервалаа неопределенности не превосходила 0,2. Следовательно, 
, так что 
. Выберем в качестве константы различимости значение 
. Два первых вычисления значений функции проводятся в точках 
.
Так как, то новый интервал неопределенности будет равен [-3.000; 1.945]. Далее процедура повторяется аналогично. Результаты итераций приведены в табл.6.3.
Так как 
, то конечный интервал неопределенности 
равен [-1.109; -0.964], а его длина 
.
За приближение положения точки минимума выберем середину интервала -1.0364.
Таблица 6.3
|
|
|
|
|
|
|
|
|
1 |
-3.000 |
5.000 |
0.0545 |
1.9454 |
0.112 |
7.676 |
|
2 |
-3.000 |
1.9454 |
-1.109 |
0.0545 |
-0.988 |
0.112 |
|
3 |
-3.000 |
0.0545 |
-1.836 |
-1.109 |
-0.300 |
-0.988 |
|
4 |
-1.836 |
0.0545 |
-1.109 |
-0.673 |
-0.988 |
-0.893 |
|
5 |
-1.836 |
-0.673 |
-1.399 |
-1.109 |
-0.840 |
-0.988 |
|
6 |
-1.399 |
-0.673 |
-1.109 |
-0.964 |
-0.988 |
-0.999 |
|
7 |
-1.109 |
-0.673 |
-0.964 |
-0818 |
-0.999 |
-0.967 |
|
8 |
-1.109 |
-0.818 |
-0.998 |
-0.964 |
-1.000 |
-0.999 |
|
9 |
-1.109 |
-0.964 |
-1.054 |
-0.998 |
-0.999 |
-1.000 |
Сравнение методов линейного поиска
Сравним выше рассмотренные методы одномерного поиска по скорости сокращения интервала неопределенности.
Пусть длина исходного интервала равна 
, а 
- длина конечного интервала неопределенности.
При заданной величине конечного интервала , которая удовлетворяет требуемой степени точности, необходимое число вычислений функции может быть определено как наименьшее положительное целое, удовлетворяющее следующим соотношениям:
метод дихотомического поиска: 
метод золотого сечения: 
метод Фибоначчи: 
Для фиксированного значения 
наименьшее число требуемых вычислений функции 
отвечает более эффективному алгоритму.
С этой точки зрения наиболее эффективным является метод Фибоначчи, далее - метод золотого сечения, затем метод дихотомического поиска.
Заметим, что при достаточно больших значение 
стремится к 0.618, так что методы Фибоначчи и золотого сечения становятся асимптотически эквивалентными.
Характеристика методов поиска экстремума
нелинейных функций при ограничениях
Решение задач нелинейной оптимизации при ограничениях (т.е. задач НП) вызывает значительно большие трудности, чем без ограничений (т.е. задач безусловной оптимизации) в силу наличия ограничивающих условий. Известные различные вычислительные процедуры для задач НП с ограничениями опираются на один из следующих подходов.
Распространение аппарата линейного программирования на нелинейные условия путем многократной используемой процедуры линейной аппроксимации (методы аппроксимирующего программирования).
Преобразование задачи НП с ограничениями в эквивалентную ей последовательность задач безусловной оптимизации путем введения в рассмотрение штрафных функций (методы штрафных функций).
Использование скользящих допусков, позволяющих оперировать в процессе решения задачи как с допустимыми, так и с недопустимыми векторами в пространстве решений. Основные характеристики и потенциальные возможности ряда методов решения задач НП приведены в табл.6.4.
Таблица 6.4
|
№ Структур-ные Характеристики |
Методы линейной апроксимации |
Методы штрафных функций |
|||||||
|
Метод апроксимирующего программи-рования |
Метод Розена |
Обобщенный градиентный метод |
Проектированный вариант метода Д-Ф-П |
Метод допустимых направлений |
Метод приведенного градиента |
Метод |
Метод барьерных поверхностей |
Метод Фиакко-Мак-Кормика |
|
|
1. Целевая функция |
Л и НЛ |
Л и НЛ |
Л и НЛ |
Л и НЛ |
Л и НЛ |
Л и НЛ |
Ли НЛ |
Л и НЛ |
Л и НЛ |
|
2.Позволяет манипули-ровать с ограничени-ями типа = |
Нет |
Л2 |
Л и НЛ |
Л |
Нет |
Л и НЛ |
Нет |
Нет |
Л |
|
3. Позволяет манипули-ровать с ограничени-ями типа ³ |
НЛ1 |
Л и НЛ1 |
Л и НЛ |
Л и НЛ |
Л и НЛ |
Л и НЛ |
Л и НЛ |
Л и НЛ |
Л и НЛ |
|
4.Начальная точка |
Д |
Д |
Д и НД |
Д |
Д |
Д и НД |
Внутренняя |
Внутренняя |
Внутренняя |
|
5. Позволяет решать невыпуклыезадачи |
Да |
Да |
Да |
Да |
Да |
Да |
Да |
Да |
Да |
|
6. Скорость сходимости |
Низкая |
Высо-кая |
Низкая |
Средняя |
Высо-кая |
Средняя |
Средняя |
Средняя |
Высо-кая |
|
7. Промежу-точные точки |
Д |
Д |
Д и НД |
Д |
Д |
Д |
Д |
Д |
Д |
Условные обозначения: 1 - метод не эффективен при решении задач с нелинейными ограничениями;
2 - применяется только для задач с линейными ограничениями;
Л - линейные методы;
НЛ - нелинейные методы;
Д - допустимые;
НД - недопустимые.
