Материал: Бородакий Нелинейное программирование в современных задачах оптимизации 2011

1.4. Минимизация функций с ограничениями

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

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

Множество X называют допустимой областью, а точку x X –

1.4.1. Метод штрафных функций

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

Например, если скалярная переменная x ограничена условием x ≤1 , то можно использовать следующую замену переменной:

x = sin θ или x = cos θ.

Если переменная x ограничена условием x ≥ 0 , то снять ограничения можно заменой x = y2 . При этом переменная y не ограничена.

Если a ≤ x ≤ b , то возможна замена: x = a + (b − a) sin 2 θ. Эти приемы имеют ограниченное применение, тем не менее ими пренебрегать нельзя.

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

76

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

F(x,l) = f (x) + ∑ψi (gi (x),li ) ,

значения.

Идея метода штрафных функций состоит в том, чтобы вместо задачи (1.17) рассматривать задачу минимизации функции F(x,l ) при больших li .

В общем случае F(x, l ) строится так, чтобы она была гладкой и

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

Например, штрафная функция может быть построена как взвешенная сумма квадратов невязок

Замена решения задачи (1.17) минимизацией функции F(x,l )

при больших l позволяет приблизиться к решению исходной задачи.

Однако здесь возникают следующие вычислительные трудности.

1. Если функции gi (x) – невыпуклые, то F(x,l ) также не будет выпуклой по x . Поэтому она может обладать локальными минимумами. Так как все изученные нами методы предназначены для нахождения локального минимума, то при плохом начальном приближении x0 будет найден локальный минимум функции

F(x, l ) , не совпадающий с минимумом исходной задачи.

Если функции gi (x) – выпуклые, то F(x,l ) также будет

выпуклой, и данная проблема устраняется.

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

3. Функция F(x, l ) в точках x , для которых gi (x) = 0 , при некоторых l не имеет вторых производных, т.е. градиент в этих

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

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

78

1.4.2. Метод Фиакко и Мак-Кормика (метод барьерных функций или метод внутренней точки)

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

Итак, надо найти min f (x) при ограничениях gi (x) ≤ 0 , где функции gi (x) – выпуклые и допустимая область не пуста.

Составим вспомогательную функцию

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

величина. При k → 0 минимум функции F(x, k) стремится к минимуму функции f (x) с ограничениями gi (x) ≤ 0 .

Для повышения точности важно выбирать малые значения k . Однако при малых k небольшие изменения x приводят к резким изменениям функции F(x, k) . Другими словами, изменения

градиента F(x, k) вблизи границ допустимой области становятся

более резкими. Это затрудняет поиск минимума и значительно снижает ценность метода.

1.4.3. Методы возможных направлений

Методы возможных направлений – наиболее исследованный класс методов выпуклого программирования (задачи выпуклого программирования – это такие задачи нелинейного программирования, в которых целевые функции и функции ограничений выпуклы). Подробное описание данных методов было произведено в работах Зойтендейка [2].

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

79

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

Рассмотрим сущность этих методов.

Имеем задачу нелинейного программирования: найти min f (x) при ограничениях

gi (x) < 0, i =1, m ,

где gi (x) , f (x) – непрерывно дифференцируемые функции.

Последовательность точек будем, как всегда, строить по итерационной формуле

xk+1 = xk + λk Sk .

Как известно, имея допустимую точку x , удовлетворяющую всем ограничениям, необходимо принять два решения:

1) выбрать направление S , которое должно быть возможным и приемлемым, т.е. на этом направлении должны лежать точки, принадлежащие допустимой области X (возможность), и функция f (x) должна в этом направлении убывать (приемлемость);

2) решить, какой величины шаг должен быть сделан в выбранном направлении S .

Вообще говоря, существует много возможных и приемлемых

Функция убывает в направлении S , если это скалярное произведение меньше нуля, т.е. направление S образует острый угол с антиградиентом (рис. 1.27).

Рис. 1.27. К выбору допустимых направлений

80