К прямым методам поиска относят методы, в которых для отыскания экстремума не используются производные первого и высших порядков. В этих методах направления поиска определяются на основе последовательных вычислений значений функции .
Как правило, при решении задач НП при отсутствии ограничений градиентные методы и методы, использующие вторые производные, сходятся быстрее, чем прямые методы. Тем не менее, применяя на практике методы, использующие производные, мы сталкиваемся со следующими трудностями. Во-первых, в задачах с большим числом переменных трудно или совсем невозможно получить производные в виде аналитических функций, необходимых для методов первого и второго порядков. Конечно, аналитические выражения для производных можно заменить вычислением их по разностным схемам, однако возникающие при этом погрешности (в особенности в окрестности экстремума), ограничивают возможности такой аппроксимации. Прямые методы не требуют выполнения условий регулярности и непрерывности и существования производных.
Во-вторых, градиентные методы оптимизации требуют довольно большого времени на подготовку задачи к решению по сравнению с прямыми методами.
Рассмотрим сначала задачу минимизаци функции одной переменной при условии
. Так как точное место нахождения локального минимума
на интервале
неизвестно, то целесообразно назвать этот интервал интервалом неопределенности.
Вообще называется интервалом неопределенности, если точка минимума
, хотя ее точное значение неизвестно.
![]() |
Покажем, что если функция выпукла или строго квазивыпукла, то интервал неопределенности можно сократить с помощью вычисления значений
в двух точках, принадлежащих интервалу.
Теорема 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.
|
|
|
|
|
|
|
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.
|
|
|
|
|
|
|
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.
№ Структур-ные Характеристики |
Методы линейной апроксимации |
Методы штрафных функций |
|||||||
Метод апроксимирующего программи-рования |
Метод Розена |
Обобщенный градиентный метод |
Проектированный вариант метода Д-Ф-П |
Метод допустимых направлений |
Метод приведенного градиента |
Метод |
Метод барьерных поверхностей |
Метод Фиакко-Мак-Кормика |
|
1. Целевая функция |
Л и НЛ |
Л и НЛ |
Л и НЛ |
Л и НЛ |
Л и НЛ |
Л и НЛ |
Ли НЛ |
Л и НЛ |
Л и НЛ |
2.Позволяет манипули-ровать с ограничени-ями типа = |
Нет |
Л2 |
Л и НЛ |
Л |
Нет |
Л и НЛ |
Нет |
Нет |
Л |
3. Позволяет манипули-ровать с ограничени-ями типа ³ |
НЛ1 |
Л и НЛ1 |
Л и НЛ |
Л и НЛ |
Л и НЛ |
Л и НЛ |
Л и НЛ |
Л и НЛ |
Л и НЛ |
4.Начальная точка |
Д |
Д |
Д и НД |
Д |
Д |
Д и НД |
Внутренняя |
Внутренняя |
Внутренняя |
5. Позволяет решать невыпуклыезадачи |
Да |
Да |
Да |
Да |
Да |
Да |
Да |
Да |
Да |
6. Скорость сходимости |
Низкая |
Высо-кая |
Низкая |
Средняя |
Высо-кая |
Средняя |
Средняя |
Средняя |
Высо-кая |
7. Промежу-точные точки |
Д |
Д |
Д и НД |
Д |
Д |
Д |
Д |
Д |
Д |
Условные обозначения: 1 – метод не эффективен при решении задач с нелинейными ограничениями;
2 – применяется только для задач с линейными ограничениями;
Л – линейные методы;
НЛ – нелинейные методы;
Д – допустимые;
НД – недопустимые.