МНОГОМЕРНАЯ ЛОКАЛЬНАЯ УСЛОВНАЯ ОПТИМИЗАЦИЯ

5        МНОГОМЕРНАЯ ЛОКАЛЬНАЯ УСЛОВНАЯ ОПТИМИЗАЦИЯ

6.1 Методы последовательной безусловной оптимизации

Методы последовательной безусловной оптимизации предназначены для решения многомерной задачи локальной условной оптимизации. Основная идея методов состоит в преобразовании задачи условной оптимизации к последовательности задач безусловной оптимизации. Более строго, суть методов состоит в сведении задачи поиска локального минимума функции f(x), определенной на множестве D n-мерного арифметического пространства, к решению последовательности вспомогательных задач поиска локального минимума функции f(x) + P(α,x), определенной на всем n-мерном арифметическом пространстве. Здесь P(α,x) – функции, которые возрастают вблизи границ области допустимых значений D и тем быстрее, чем больше значение скалярного параметра α. В качестве приближенного решения исходной задачи условной оптимизации принимается решение вспомогательной задачи безусловной оптимизации при достаточно большом значении параметра α. Наиболее известными методами последовательной безусловной оптимизации являются метод штрафных функций и метод барьерных функций.

Рассмотрим следующую многомерную задачу локальной условной оптимизации: найти минимум критерия оптимальности f(x), определенного во множестве D евклидова пространстве Rⁿ,

                                               (6.1)

где множество допустимых значений

                    (6.2)

         Основная идея методов последовательной условной оптимизации состоит в преобразовании задачи условной оптимизации (6.1), (6.2) к последовательности задач

                          (6.3)

где  функции, которые возрастают вблизи границ области допустимых значений D и тем быстрее, чем больше значение параметра . В качестве приближенного решения задачи (6.1), (6.2) принимается решение  вспомогательной задачи (6.3) при достаточно большом .

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

Пример. Пусть

                                            (6.4)

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

                                               (6.5)

Рис. 6.1. Точка минимума функции Q^α(х) при α = 0 имеет координаты (3, 2). Решением задач (6.3), (6.4), (6.5), (6.6) является точка х^*                                          с координатами (2.5, 1.5)

Положим

                                                   (6.6)

где  – вещественная константа. На рисунках 6.1, 6.2 и 6.3 приведены линии уровня функции при  соответственно.

Рис. 6.2. Точка минимума функции Q^α(х) при α = 1 имеет координаты (2.666…, 1.666…). Решением задач (6.3), (6.4), (6.5), (6.6) является точка х^*                                 с координатами (2.5, 1.5)

Рис. 6.3. Точка минимума функции Q^α(х) при α = 2 имеет координаты (2.6, 1.6). Решением задач (6.3), (6.4), (6.5), (6.6) является точка х^*                                         с координатами (2.5, 1.5)

            Рисунки показывают, что при увеличении параметра  минимум функции приближается к решению задач (6.3), (6.4), (6.5), (6.6).

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

Метод штрафных функций относится к классу методов последовательной безусловной оптимизации и, как все методы этого класса, предназначен для решения многомерной задачи локальной условной оптимизации. В методе штрафных функций функцию P^α(х), которая в этом случае называется штрафной функцией, подбирают таким образом, чтобы при больших  функция  мало отличалась от функции f(x) при  и быстро возрастала при удалении точки  от границы области допустимых значений D. В данном методе точка х в процессе поиска может выходить за границы области D (рис. 6.4). Т.е. метод штрафных функций относится к классу методов внешней точки, в котором при решении задачи условной оптимизации используемый метод поиска разрешает текущей точке х выходить за границы области ее допустимых значений. Рассмотренный выше пример также иллюстрирует метод штрафных функций.

Рис. 6.4. К методу штрафных функций (n = 1). Интервал [a, b] – область допустимых значений D; γ > β > α

Метод барьерных функций относится к классу методов последовательной безусловной оптимизации и, как все методы этого класса, предназначен для решения многомерной задачи локальной условной оптимизации. В методе барьерных функций функцию P^α(х), которая в этом случае называется барьерной функцией, подбирают таким образом, чтобы при больших функция  мало отличалась от функции f(x) при  и быстро возрастала при приближении точки  к границе области допустимых значений D. В данном методе точка х не может выходить за границы области D (рис. 6.5). Это означает, что метод барьерных функций относится к классу методов внутренней точки, в котором при решении задачи условной оптимизации используемый метод поиска запрещает текущей точке х выходить за границы области ее допустимых значений.

Рис. 6.5. К методу барьерных функций (n = 1). Интервал [a, b] – область допустимых значений D; γ > β > α

         В вычислительной практике преимущественно используется метод штрафных функций. Поэтому в дальнейшем ограничимся только им.

            Штрафная функция в общем случае имеет вид

                                 (6.7)

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

            Функционалы  в формуле (6.7) должны удовлетворять очевидным требованиям:

 при

при

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

            Так, в качестве функционалов  обычно используют функционалы

в качестве функционалов  – функционалы

где

            В качестве критерия окончания итераций можно использовать неравенство

                                                         (6.8)

где r – четное число итераций, – требуемая точность решения по х.

Алгоритм метода штрафных функций

            Шаг 1. Задаем начальную точку х⁰ и полагаем счетчик числа итераций       r = 0.

            Шаг 2. Исходя из точки х^r, одним из методов локальной безусловной оптимизации решаем задачу – находим точку х^r+1.

            Шаг 3. Проверяем условие окончания поиска (6.8). Если условие окончания поиска выполнено, то полагаем и завершаем итерации. Иначе – по некоторому правилу увеличиваем значения параметров  полагаем r = r + 1 и переходим к шагу 3.

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

6.2 Метод скользящего допуска

Рассмотрим следующую многомерную задачу локальной условной оптимизации: найти минимум критерия оптимальности f(x), определенного во множестве D евклидова пространства Rⁿ,

                                               (6.9)

где множество допустимых значений

                                 (6.10)

Основы метода скользящего допуска

Метод скользящего допуска существенно использует множество

                                                    (6.11)

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

При этом функционал Т(х) должен быть сконструирован таким образом, чтобы Т(х) = 0 при  и значение Т(х) возрастало по мере удаления точки х от границы области допустимых значений D. Критерий скользящего допуска  определяет требуемую точность выполнения ограничений, которые формируют область допустимых значений D, и конструируется таким образом, чтобы обеспечить его уменьшение с ростом количества итераций r.

Точка x называется допустимой точкой, если Т(х) = 0, почти допустимой точкой – если 0<Т(х) ≤, недопустимой точкой – если Т(х) >. Поскольку величина  с ростом номера итерации уменьшается, отклонение от границы области D, при котором точка считается допустимой, сужается, так что в пределе рассматриваются только допустимые точки.

Метод скользящего допуска может быть скомбинирован со многими из рассмотренных ранее многомерных методов локальной безусловной оптимизации. Будем называть метод, с которым комбинируется метод скользящего допуска, базовым методом.

Одна итерация метода скользящего допуска состоит из одного или двух этапов:

1 С помощью базового метода, исходя из точки x^r, выполняем итерацию по решению задачи локальной безусловной оптимизации

                                                          (6.12)

– находим точку . Если  (точка  является допустимой точкой или почти допустимой точкой), то полагаем  и заканчиваем данную итерацию.

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

                                                           (6.13)

с условием окончания итераций

                                                                     (6.14)

и заканчиваем данную итерацию.

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

Одна из сложностей применения метода скользящего допуска – возможные осцилляция решения относительно границы области D (см. ниже).

Комбинация метода скользящего допуска с методом Нелдера – Мида

При комбинации метода скользящего допуска с методом Нелдера – Мида можно предложить разные виды критерия скользящего допуска. Чаще всего в качестве этого критерия используют следующую функцию координат вершин деформируемого многогранника :

                                           (6.15)

Здесь  – вектор координат центра тяжести многогранника , так что величина

 есть среднее расстояние вершин многогранника  от его центра тяжести.

Из (6.15) следует, что критерий скользящего допуска  является положительно определенной функцией координат вершин многогранника . С другой стороны, поскольку размер многогранника при приближении к точке минимума x^* уменьшается (в пределе до нуля), то справедливо предельное соотношение

Для задач (6.9), (6.10) в качестве функционала Т(х) обычно используют функционал

                                                          (6.16)

где

Из (6.16) следует, что функционал Т(х) обладает следующим свойством

Из (6.16) вытекает также, что если значение функционала Т(х) мало, то точка х находится недалеко от границы области D.

Примечание. Поскольку метод Нелдера – Мида является детерминированным методом нулевого порядка, комбинация метода скользящего допуска с методом Нелдера – Мида также представляет собой детерминированный метод нулевого порядка.

Упрощенный алгоритм комбинации метода скользящего допуска         и метода Нелдера – Мида

Симплекс с вершинами  обозначим s^r.

Шаг 1. Задаем начальный симплекс s⁰ и полагаем счетчик числа итераций r = 0.

Шаг 2. С помощью метода Нелдера – Мида, исходя из симплекса s^r, выполняем одну итерацию по решению задачи локальной безусловной оптимизации (6.12) – находим симплекс  с вершинами .

Шаг 3. Вычисляем значения функционала Т(х) во всех вершинах симплекса  и значение критерия скользящего допуска . Находим вершину симплекса , в которой значение функционала Т(х) максимально, т.е. вершину, которая расположена дальше всех от границы области D. Обозначим эту вершину .

Шаг 4. Если  (точка  является допустимой точкой или почти допустимой точкой), то проверяем условие окончания поиска (см. алгоритм метода Нелдера – Мида). Если это условие выполнено, то завершаем итерации. Если условие окончания поиска не выполнено, то формируем симплекс s^r+1 с вершинами , полагаем r = r + 1 и переходим к шагу 2.

Шаг 5. Если  (точка  является недопустимой точкой), то с помощью метода Нелдера – Мида, исходя из точки , решаем задачу локальной безусловной оптимизации (6.13) с критерием окончания итераций (6.14) –  находим точку . Формируем новый симплекс s^r+1 с вершинами , полагаем r = r + 1 и переходим к шагу 2.

Ослабление осцилляций решения

Как отмечалось выше, одной из сложностей применения метода скользящего допуска являются возможные осцилляции решения относительно границы области D. Поясним суть этого явления на примере.

Пример. Рассмотрим двумерную задачу условной оптимизации (6.9), когда критерий оптимальности равен

и множество допустимых значений D определяется ограничениями

                                              (6.17)

Положим, что на r-й итерации координаты вершин текущего симплекса  равны . Тогда после одной итерации по решению задачи локальной безусловной оптимизации (6.12) методом Нелдера – Мида получим симплекс  с вершинами  (рис. 6.6).

Рис. 6.6. После успешного отражения вершины выполнено успешное растяжение симплекса

Положим далее, что точка , расположенная далее всех от границы области D, является недопустимой точкой, т.е. . Тогда при решении с помощью метода Нелдера – Мида задачи локальной безусловной оптимизации (6.13) возможна ситуация, приведенная на рис. 6.7.

Рис. 6.7. После успешного отражения вершины выполнено растяжение симплекса и отражение вершины

Из (6.16), (6.17) следует, что если  и точка х лежит в первой четверти системы координат , то . На рис. 6.7 показаны линии уровня функции Т(х) именно для этого случая.

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

Эффект, рассмотренный в примере, и называется осцилляцией решения относительно границы области D.

Для ослабления влияния осцилляций в простейшем случае можно вместо точки  использовать точку  – середину отрезка .

Рис. 6.8. Использование квадратичной интерполяции функции T(x) на отрезке по трем точкам для ослабления осцилляций. Случай, когда точка A^r принадлежит области допустимых значений D

Чаще с этой целью используют квадратичную интерполяцию функции Т(х) на отрезке  по трем точкам , где  – также середина отрезка  – рис. 6.8. Обозначим эту интерполирующую функцию  (см. параграф 3.5). Вместо точки  в этом случае можно использовать один из нулей функции y(x) либо его приближенное значение, найденное, например, методом касательных.

6.3 Модифицированный метод комплексов

Рассмотрим многомерную задачу локальной условной оптимизации

                                                  (6.18)

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

                                                     (6.19)

            Здесь  – нижняя и верхняя границы области допустимых значений D по i-му измерению (рис. 6.9).

Рис. 6.9. Область допустимых значений D в виде гиперпараллелепипеда; n = 2

Метод комплексов в многомерной задаче безусловной оптимизации рассмотрен в параграфе 5.3.2. В данном же параграфе рассматривается модификация этого метода для решения многомерной задачи условной оптимизации – модифицированный метод комплексов. Он предназначен для решения многомерной задачи локальной условной оптимизации, в которой множество допустимых значений D задается с помощью ограничений вида неравенств и представляет собой гиперпараллелепипед. Метод представляет собой, как следует из его названия, модификацию метода комплексов, предназначенного для решения многомерных задач локальной безусловной оптимизации. Как и метод комплексов, модифицированный метод комплексов относится, с одной стороны, к классу стохастических методов оптимизации, а с другой стороны – к классу прямых методов оптимизации. Как и метод комплексов, модифицированный метод комплексов использует следующие три основных операции: операцию генерации случайного комплекса; операцию отражения вершины комплекса с растяжением; операцию сжатия комплекса. Кроме того, рассматриваемый метод использует операцию проектирования вершины комплекса на границу множества допустимых значений D. Если на некоторой итерации модифицированного метода комплексов одна или несколько вершин текущего комплекса вышли за границу множества допустимых значений, то они возвращаются в это множество с помощью операции сжатия комплекса или с помощью операции проектирования вершины комплекса на границу множества допустимых значений.

Основные операции метода комплексов

Напомним, что комплексом называется многогранник с N > n + 1 вершинами (не обязательно выпуклый). Рекомендуется N = 2n. Так же как и при решении задачи безусловной оптимизации, при решении задачи (6.18) методом комплексов используются следующие операции:

- генерация случайного комплекса;

- отражение вершины комплекса с растяжением;

- сжатие комплекса.

Генерация случайного комплекса. Координаты вершин случайного комплекса с N вершинами могут быть найдены по формуле

                                     (6.20)

где x₀ – произвольная начальная точка, i – номер вершины комплекса, l > 0        – скаляр, определяющий размеры комплекса,  – реализация n-мерного случайного вектора,  – некоторая векторная норма. Обычно в качестве координат вектора  используют независимые случайные величины, равномерно распределенные в интервале [–1;1] .

Отражение вершины комплекса с растяжением. Положим, что задан комплекс C^r с N вершинами  и его вершину  необходимо отразить через центр тяжести комплекса с растяжением. В новом комплексе C^r+1 все вершины, кроме k-й, совпадают с соответствующими вершинами исходного комплекса C^r, а k-я вершина находится на прямой, проходящей через центр тяжести этого комплекса и его вершину  (рис. 6.10).

Рис. 6.10. Отражение вершины комплекса C^r через центр его тяжести        с растяжением. Пунктиром показан новый комплекс C^r+1

Обозначим координаты вершин нового комплекса . Тогда имеем

                   (6.21)

где  – коэффициент растяжения комплекса (рекомендуемое значение – 1,3),

       – вектор координат центра тяжести комплекса C^r:

                                                          (6.22)

Сжатие комплекса. Положим, что задан комплекс C^r с N вершинами  и его вершину  необходимо переместить ближе к центру тяжести комплекса C^r – выполнить сжатие комплекса. В новом комплексе C^r+1 все вершины, кроме k-й, совпадают с соответствующими вершинами исходного комплекса C^r, а k-я вершина находится на прямой, проходящей через центр тяжести этого комплекса и его вершину  (рис. 6.11). Обозначим координаты вершин нового комплекса . Тогда имеем

                   (6.23)

где  – коэффициент сжатия комплекса (рекомендуемое значение – 2),  – вектор координат центра тяжести комплекса C^r.

Рис. 6.11. Сжатие комплекса C^r. Пунктиром показан новый комплекс C^r+1

Упрощенный алгоритм модифицированного метода комплексов

Шаг 1. Задаем начальную точку , исходя из которой должен быть построен комплекс C⁰, величину l⁰, а также коэффициенты ; полагаем счетчик числа итераций r = 0.

Шаг 2. Строим начальный комплекс C⁰:

- поочередно для i = 1,2,…,N по формуле (6.20) находим координаты вершин комплекса ; комплекса C^r;

- если вершина  является недопустимой (выходит за границы области D), то по формуле, аналогичной формуле (6.23), выполняем сжатие уже построенного комплекса с p вершинами вдоль направления , где  – центр тяжести уже найденных (p – 1)-й вершин комплекса (рис. 6.12);

- если после сжатия комплекса вершина  по-прежнему является недопустимой, повторяем описанную процедуру сжатия;

- вычисляем значения  функции f(x) во всех вершинах построенного комплекса C^r.

Рис. 6.12. Построение комплекса C⁰

Шаг 3. Находим максимальное из значений функции f(x) в вершинах комплекса C^r

Шаг 4. По формулам (6.21), (6.22) отражаем с растяжением вершину  комплекса C^r – получаем вершину  и новый комплекс C^r+1:

- если точка  является не допустимой (выходит за границы области D) и f() > f(), то по формуле (6.23), выполняем сжатие комплекса C^r+1 вдоль направления , где –  центр тяжести комплекса C^r+1, до тех пор, пока точка  не станет допустимой (рис. 6.13). Переходим к шагу 5;

- если точка  является допустимой (не выходит за границы области D) и f() < f(), то переходим к шагу 5;

- если точка  является недопустимой, но f() < f(), то переходим к шагу 6.

Рис. 6.13. Построение комплекса C^r+1

Шаг 5. Проверяем условие окончания поиска (см. ниже). Если условие окончания поиска выполнено, то в качестве точки x^* принимаем вершину комплекса C^r+1, к которой функция f(x) имеет наименьшее значение, вычисляем соответствующие значения f(x) и завершаем итерации. Иначе – переходим к шагу 3.

Шаг 6. Если , то полагаем ; если  то полагаем  (рис. 6.14). Переходим к шагу 3.

На рис. 6.12 точка  оказалась за границей области D. После операции сжатия комплекса вершины  комплекса вдоль направления (,( получаем вершину . Здесь  – центр тяжести комплекса.

На рис. 6.13 полагается, что f() > f(). Точка  оказалась границей области D. После операции сжатия комплекса вершины  комплекса вдоль направления (,) получаем вершину .

Рис. 6.14. Построение комплекса C^r+1

На рис. 6.14 полагается, что f() < f(). Точка  оказалась за границей области D – нарушено ограничение <). Точка  получена проектированием точки  на прямую x₂ = .

В качестве критерия окончания поиска может использоваться следующее условие: максимальная длина ребра комплекса C^r не превышает                         – требуемую точность решения по x. Может использоваться также следующее аналогичное условие: максимальная разность значений функции f(x) в двух вершинах комплекса C^r не превышает  – требуемую точность решения по f.

Изложенный алгоритм метода комплексов приводит к «уплощению» комплекса вблизи границы области допустимых значений D, что может значительно уменьшить эффективность метода. C целью преодоления этого недостатка через фиксированное количество итераций находятся максимальная и минимальная диагонали комплекса и, если их отношение превышает заданное, то по рассмотренной схеме производится построение нового комплекса.

6.4 Метод линейной аппроксимации

Сделаем ряд дополнительных допущений. Пусть множество допустимых значений D определяется только ограничениями типа неравенств и ограничивающие функции  являются непрерывными, дифференцируемыми и выпуклыми:

                                                  (6.24)

                                              (6.25)

Пусть функция f(x) также непрерывна, дифференцируема и выпукла во множестве D.

Метод линейной аппроксимации использует на каждой итерации линейную аппроксимацию целевой функции f(x) и ограничивающих функций  в окрестности текущей точки x^r

                              (6.26)

                     (6.27)

Вместо задачи (6.24) на каждой итерации решается вспомогательная задача линейного программирования

                                          (6.28)

где .

В изложенном виде метод может привести к выходу точки x^r+1 за пределы допустимой области (см. пример).

Пример. Рассмотрим следующую двумерную задачу условной оптимизации с тремя ограничениями типа неравенств (первое ограничение – нелинейное, второе и третье ограничения – линейные):

где

.

Положим, что текущая точка есть x^r = (2,4). Линеаризуем целевую функцию f(x) и ограничивающую функцию g₁(x) в окрестности этой точки. Поскольку  по формуле (6.26) имеем

Аналогично для ограничивающих функций по формуле (6.27) имеем:

Пример иллюстрирует рис. 6.15.

Примечание. Прямая  представляет собой след от пересечения плоскости, которая является касательной к поверхности z = g₁(x) в точке , с плоскостью 0x₁x₂. Эта прямая не обязательно является касательной к линии g₁(x) = 0 – прямая = 0 может пересекать кривую g₁(x) = 0, быть касательной к ней или не иметь с ней общих точек. Аналогично линия уровня  функции f(x) представляет собой след от пересечения плоскости, которая является касательной к поверхности z = f(x) в точке , с плоскостью z = x.

Чтобы избежать выхода текущей точки за границы области допустимых значений, следующее приближение x^r+1  к точке минимума x^* функции f(x) из множества D находится по формуле

                                       (6.29)

где  – решение вспомогательной задачи линейного программирования (6.28).

Рис. 6.15. Точка x^r+1 лежит вне области допустимых значений D

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

1-й способ выбора величины шага. Величина  находится как решение задачи одномерной оптимизации функции  на отрезке [0;1]:

             (6.30)

2-й способ выбора величины шага. Полагаем =1 и по формуле (6.29) находим вектор x^r+1. Вычисляем значение f(x^r+1) целевой функции в полученной точке. Если условие

f(x^r+1) < f(x^r)                                                              (6.31)

не выполнено, то уменьшаем величину шага  (например, в два раза) и повторно проверяем выполнение условия (6.31). Дробление шага  и вычисление x^r+1 производим до выполнения условия (6.31).

Алгоритм метода линейной аппроксимации

Рассмотрим вариант метода, в котором используется 1-й способ выбора величины шага .

Шаг 1. Задаем начальную точку  и полагаем счетчик числа итераций r = 0.

Шаг 2. Вычисляем градиенты функций  в точке x^r.

Шаг 3. Решаем задачу линейного программирования (6.28) – находим точку .

Шаг 4. Решаем одномерную задачу минимизации (6.30) – находим величину шага  и вектор x^r+1.

Шаг 5. Проверяем условие окончания поиска (см. ниже). Если условие окончания поиска выполнено, то полагаем  и завершаем итерации. Иначе – полагаем r = r + 1 и переходим к шагу 2.

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

или условие

где  – константа, определяющая требуемую точность решения по градиенту функции f(x).

Отметим следующие трудности, возникающие при использовании метода линейной аппроксимации:

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

2 Метод требует, чтобы точка x⁰ принадлежала множеству допустимых значений D. Если это требование не выполнено, то прежде приходится использовать какой-либо метод поиска точки, принадлежащей множеству допустимых значений.

Рис. 6.16. Направление поиска (x^r+1 – x^r), которое обеспечивает метод на основе линейной аппроксимации, далеко от оптимального направления (x* – x^r)

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

6.5 Метод проекции градиента

Рассмотрим многомерную задачу локальной условной оптимизации

                                                  (6.28)

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

                                               (6.29)

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

Проектирование точки на множество

Идея метода проекции градиента состоит в том, что если на некоторой итерации точка

                                                     (6.30)

полученная с помощью градиентного метода наискорейшего спуска (см. 5.2.1), оказывается вне множества допустимых значений D, то она возвращается на это множество. Возврат производится с помощью процедуры «проекция точки на множество». Напомним, что в формуле (6.30)  – длина шага на r-й итерации в направлении s^r;

единичный вектор направления антиградиента функции f(x) в точке x^r,  – некоторая векторная норма, например евклидова.

Определение. Проекцией точки  на замкнутое множество  называется ближайшая к x точка  множества D. Т.е. точка  называется проекцией точки  на замкнутое множество , если

                                                       (6.31)

где  – расстояние между точками  в некоторой метрике, например, .

Проекцию  точки x на замкнутое множество D будем обозначать  (рис. 6.17). Очевидно, что , если .

Рис. 6.17. К определению проекции точки на множество. Прямая l является касательной к границе области D в точке

Можно показать, что если D – замкнутое выпуклое множество пространства Rⁿ, то для любой точки  существует единственная ее проекция на это множество.

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

Задача (6.31) становится задачей квадратичного программирования, если множество D задается лишь линейными ограничениями типа неравенств и если функция  является квадратичной функцией y, например, если .

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

Алгоритм комбинации метода проекции градиента с методом дробления шага

Метод проекции градиента может быть скомбинирован со многими градиентными методами. Рассмотрим комбинацию метода проекции градиента с градиентным методом дробления шага.

Напомним, что в градиентном методе с дроблением шага величина шага  находится из условия

                            (6.32)

Алгоритм метода

Шаг 1. Задаем начальную точку x⁰, начальную величину шага  и коэффициент дробления шага . Полагаем счетчик числа итераций r = 0.

Шаг 2. По формуле (6.30) вычисляем координаты точки  и проекцию  этой точки на множество D.

Шаг 3. Вычисляем величину f(x^r+1) – значение функции f(x) в точке x^r+1.

Шаг 4. Если условие дробления шага выполнено (см. параграф 5.2.1), то переходим к следующему шагу. Иначе – переходим к шагу 6.

Шаг 5. Полагаем  – и переходим к шагу 2.

Шаг 6. Проверяем условие окончания поиска (см. ниже). Если условие окончания поиска выполнено, то полагаем  и завершаем итерации. Иначе – полагаем r = r + 1 и переходим к шагу 2.

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

или условие , где  – константа, определяющая требуемую точность решения по градиенту функции f(x).

Комбинацию метода проекции градиента и градиентного метода с дроблением шага иллюстрирует рис. 6.18, на котором показан фрагмент линий уровня функции Химмельблау.

Рис. 6.18. Траектория поиска минимума функции Химмельблау комбинацией метода проекции градиента и градиентного метода с дроблением шага