Основные методы нелинейного программирования

3.1. Градиентные методы

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

Так при отсутствии ограничений одна из простейших разновидностей градиентных методов - метод наискорейшего спуска предлагает выбрать некоторую точку (план) X_k и начальный шаг H_k, вычислить градиент функции в выбранной точке grad F(X_k) и осуществить переход по градиенту (при максимизации) с выбранным шагом. Если значение функции в новой точке больше предыдущего, новая точка принимается за исходную и повторяется такая же процедура. При попадании в точку с меньшим значением уменьшается шаг (например, вдвое) и переход повторяется от исходной точки. Переходы продолжаются до достаточно малого шага .

Например, если нужно решить систему уравнений

(X²+1)(Y-1)=3,Y=ln(X+1),

то можно заменить эту задачу задачей минимизации функции F(X,Y)=[(X²+1)(Y-2)-3]2+[Y-ln(X+1)]² (если система имеет решение, то искомый минимум равен нулю).

Градиент этой функции определяется вектором

Grad F(X,Y) = {2[(X²+1)(Y-2)-3] 2X (Y-2) - 2[Y-ln(X+1)]/(X+1),
2 [(X²+1)(Y-2)-3](X²+1) - 2[Y-ln(X+1)]}.

Выбираем начальную точку M₀(2,1) и шаг h=1.Здесь значение функции F(M₀)=64, градиент в этой точке grad F(M₀) =[ 64.066, -80.197], нормированный градиент (вектор единичной длины, составленный из компонент, деленных на корень из суммы их квадратов) grad_н F(M₀) = [0.62, -0.78]. Смещаемся в направлении, обратном градиенту (ищем минимум), с выбранным шагом в точку М₁=М₀-h grad_н F(M₀)=(2-1 0.62, 1+1 0.78)=(1.38, 1.78) и обнаруживаем, что F(M1)=14 < F(M₀).

Аналогичный переход с учетом gradн F(M₁) = [0.19, -0.98] приводит в точку М₂(1.19, 2.76), где F(M₂) 5.26, grad_н F(M₂) = [-0.96, -0.27]. Переход в очередную точку М₃(2.15, 3.03) дает F(M₃) 11.33 > F(M₂).Соответственно уменьшаем шаг вдвое (h=0.5) и получаем точку М₄(2.15, 3.03), где F(M₄)=3.78, grad_н F(M₂) = [0.12, 0.99].

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

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

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

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

3.2 Методы Монте-Карло

Методы Монте-Карло. Здесь отыскивается n - мерный параллелепипед, включающий в себя множество планов, и затем моделируются N случайных точек с равномерным законом распределения в параллелепипеде (практически во всех программных средах предусмотрено наличие соответствующих датчиков псевдослучайных чисел).

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

3.3 Методы выпуклого программирования. Метод множителей Лагранжа

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

Если множество планов - выпуклый многогранник, то эти методы допускают использование симплексного метода.

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

F(X₁, X₂, .. ,X_n) = f₁(X₁) + f₂(X₂) + ... + f_n(X_n).

При решении многих задач нелинейного программирования определенный эффект дает метод множителей Лагранжа.

Пусть требуется найти экстремумы функции F(X) при условиях f_i(X)=0 (i = 1 .. m).

Функция называется функцией Лагранжа и коэффициенты _i - множителями Лагранжа.

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

Например, при поиске максимума F(X₁, X₂) = X₁+X₂ при единственном условии X₁²+X₂²=1 строится функция Лагранжа

Строим систему уравнений

решение которой дает и экстремальные значения целевой функции

Для определения типа найденного экстремума можно построить матрицу вторых производных F(X), вычисленных в экстремальной точке, и определить знаки главных ее миноров. Если все они положительны, то найден минимум; если они чередуются, начиная с минуса, то найден максимум (правило Сильвестра).

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

3.3.1 . Теорема Куна-Таккера

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

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

Теорема (Куна-Таккера) Точка может являться решением задачи нелинейного программирования только в том случае, если в ней выполнены следующие условия:

1) ;

2) ;

3) , .

ПримерНайти наибольшее и наименьшее значения функции при заданных ограничениях при ограничениях и .

Решение. Запишем ограничения в стандартном виде

Первое условие теоремы Куна-Таккера позволяет записать два уравнения:

,

.

Второе условие теоремы позволяет записать еще два уравнения: , .

Подставляя в них функции и вычислив производные, получаем систему из 4 уравнений с 4 неизвестными:

Рассмотрим несколько ветвей решения системы уравнений:

1)

2) .

Вторая система распадается на два случая:

2а) ; 2б) ;

3) ;

4) ,

Эта система распадается на две

4а) ; 4б) .

После того как система решена результаты собираются в таблицу:

Р	х	у			f
Р1					-
Р2			-1
Р3				-1
Р4			-1	-2
Р5	-1		-1	-2

Таблица 2: Результаты системы, через теорему Куна-Таккера

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

3.4 Дробно-линейное программирование

Математическая модель задачи

Дробно-линейное программирование относится к нелинейному программированию, так как имеет целевую функцию, заданную в нелинейном виде.

Задача дробно-линейного программирования в общем виде записывается следующим образом:

при ограничениях:

где cj, dj, bi, aij — постоянные коэффициенты и djxj ≠ 0.

Рассмотрим задачу дробно-линейного программирования в виде

(3.4.1)

при ограничениях:

(3.4.2)

Будем считать, что d1x1 + d2x2 ≠ 0.

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

Из выражения (3.4.1) найдем х2:

Прямая x2 = kx1 проходит через начало координат. При некотором фиксированном значении L угловой коэффициент k прямой тоже фиксирован и прямая займет определенное положение. При изменении значений L прямая х2 = kx1 будет поворачиваться вокруг начала координат (рисунок 1).

Рисунок 1

Установим, как будет вести себя угловой коэффициент k при монотонном возрастании L. Найдем производную от k по L:

Знаменатель производной всегда положителен, а числитель от L не зависит. Следовательно, производная имеет постоянный знак и при увеличении L угловой коэффициент будет только возрастать или только убывать, а прямая будет поворачиваться в одну сторону. Если угловой коэффициент прямой имеет положительное значение, то прямая вращается против часовой стрелки, при отрицательном значении k — по часовой стрелке. Установив направление вращения, находим вершину или вершины многогранника, в которых функция принимает max(min) значение, либо устанавливаем неограниченность задачи.