Методы оптимизации функций многих переменных
,
метод дробления
шага.
,
метод Нелдера-Мида.
,
метод сопряженных
градиентов.
,
метод Ньютона.
Контрольные вопросы:
Объяснить алгоритмы следующих методов
Метод конфигураций (Хука-Дживса).
Метод деформируемого многогранника (Нелдера Мида).
Метод наискорейшего спуска.
Метод сопряженных направлений и его модификации.
Метод Ньютона и его модификации.
Метод дробления шага.
Лабораторная работа № 2.
1. Методы условной оптимизации
Цель лабораторной работы - закрепление навыков аналитического решения задач оптимизации со смешанными ограничениями с использованием теоремы Куна-Таккера, нахождение седловой точки функции Лагранжа, использование теории двойственности для оценки чувствительности решения задачи оптимизации.
1.1 Теоретический обзор. Решение задачи минимизации со смешанными ограничениями
Общая задача нахождения экстремума функции при наличии ограничений - равенств и ограничений - неравенств записывается в следующем виде:
f (x) → extr, (6)
xОX= {xОEn: gi (x) ≤0, i=1,2,…,r; gi (x) =0, i=r+1, …, m, m-r<n},
где среди функций f (x) и gi (x) могут быть нелинейные.
Активные ограничения - неравенства в точке х* ─ это ограничения, которые выполняются в данной точке в виде равенства.
Пассивные ограничения - неравенства в точке х* ─ это ограничения, которые выполняются в данной точке в виде строгого неравенства.
Если градиенты активных ограничений-неравенств и ограничений-равенств в точке х* линейно независимы, то говорят, что в оптимальной точке выполнено условие регулярности.
Обобщенная функция Лагранжа для задачи со смешанными ограничениями задается как
L
(x,λ0,λ)
=λ0f
(x) +
λigi
(x). (7)
При выполнении условия регулярности λ0≠0 и можно положить этот коэффициент равным 1.
Теорема
Куна - Таккера
(дифференциальная
форма необходимого
условия минимума).
Пусть точка
х* - точка локального
минимума в
задаче математического
программирования
(6), функции f,gr+1,…,gm
дважды непрерывно
дифференцируемы
в точке х, функции
g1,…,gr
дважды непрерывно
дифференцируемы
в некоторой
окрестности
точки x.
Тогда существует
число
и вектор
такие, что
выполняются
следующие
условия:
условие стационарности обобщенной функции Лагранжа по х:
gradxL
(x*,
,
)
=0;
условие нетривиальности:
2+
2>0,т.е.
хотя бы один
из множителей
Лагранжа отличен
от нуля;
условие неотрицательности:
≥0,
≥0,
i=1, …, r,
т.е. множители Лагранжа, соответствующие целевой функции и ограничениям - неравенствам, неотрицательны;
условия дополняющей нежесткости:
gi (x*) =0, i=1, 2, …, r.
Если при этом выполнено условие регулярности, то для выпуклых функций f, gr+1,…, gm и линейных функций g1,…, gr условия теоремы Куна - Таккера являются одновременно необходимыми и достаточными условиями глобального минимума.
Достаточное условие минимума первого порядка.
Пусть
имеется точка
(х*,
),
удовлетворяющая
условию стационарности
обобщенной
функции Лагранжа
по х при
≠0,
суммарное число
активных
ограничений-неравенств
в точке х* и
ограничений-равенств
совпадает с
числом переменных
n. Если
>0
для всех активных
ограничений
gj
(x), то точка
х* - точка условного
локального
минимума в
задаче (6).
Достаточное условие минимума второго порядка.
Пусть
имеется точка
(х*,
),
удовлетворяющая
условию стационарности
обобщенной
функции Лагранжа
по х при
≠0.
Если в этой
точке d2L
(х*,
)
>0 для всех ненулевых
dx таких,
что для активных
в точке х*
ограничений-неравенств
dgj
(x*) =0,
>0
и dgj
(x*) ≤0,
=0,
то точка х*
является точкой
локального
минимума.
Общая схема решения задачи условной минимизации функции:
Составляется обобщенная функция Лагранжа вида (7).
Выписываются необходимые условия минимума, сформулированные в теореме Куна - Таккера. К этим условиям добавляются ограничения, задающие допустимое множество Х. Полученная система алгебраических уравнений и неравенств используется для поиска условно-стационарных (подозрительных на экстремум) точек. Целесообразно проанализировать отдельно случаи λ0=0 и λ0=1 (или λ0 - любое положительное число). Однако если выполнено одно из условий регулярности, то вариант λ0=0 рассматривать не надо.
В найденных точках проверяется выполнение достаточных условий минимума и проводится анализ на глобальный экстремум.
Чувствительность решения ЗНП.
Множители Лагранжа могут быть использованы для оценивания влияния малых изменений правых частей ограничений на оптимальное решение задачи нелинейного программирования. Пусть х*=х* (b) - решение ЗНП
f (x) → min, (8)
xОX= {xОEn: gi (x) ≤bi, i=1,2,…, m; х≥0}
при некотором векторе b свободных членов в ограничениях - неравенствах, а v (b) соответственно значение целевой функции при этом решении ЗНП, т.е. v (b) =f (x*). Тогда справедлива следующая оценка изменения целевой функции: ∆v=f (b+∆b) - f (b) при изменении вектора b на некоторый малый вектор-приращение ∆b:
∆f≈ (∆b,λ*), (9)
где λ* - вектор множителей Лагранжа, соответствующий решению х* (b).
1.2 Седловые точки функции Лагранжа
Существование экстремума тесно связано с наличием у функции Лагранжа (6) так называемой седловой точки.
Рассматривается задача выпуклого программирования с ограничениями-неравенствами
f (x) → min, (10)
xОX= {xОEn: gi (x) ≤0, i=1,2,…, m; х≥0}.
Предполагается, что выполнено условие регулярности, т.е. можно рассматривать только вариант λ0=1.
Определение.
Точка (х*,
λ*), где х*О
Х,
ОЕm,
λ*≥0,
называется
седловой точкой
функции Лагранжа
L (x,λ),
если
L (x*,λ) ≤ L (x*, λ*) ≤ L (x, λ*). (11)
Утверждение 1 (критерий для седловой точки функции Лагранжа). Точка (х*, λ*) - является седловой для функции Лагранжа L (x,λ) в том и только в том случае, когда выполнены следующие условия:
L (х*, λ*) =min {L (x, λ*) ׀ x О Х}, (12)
L (х*, λ*) =max {L (x*,λ) ׀ λ ≥0}, (13)
gi
(x*) =0,
i=1,
2,..., m,
(14)
х*≥0,λ*≥0.
Условие (12) минимума функции Лагранжа по х эквивалентно выполнению в точке (х*, λ*) неравенства
≥0.
(12′)
Условие (13) максимума функции Лагранжа по λ эквивалентно выполнению в точке (х*, λ*) неравенства
≤0.
(13′)
Утверждение 2. х* - оптимальное решение задачи (3) в том и только в том случае, когда существует такой вектор λ* ≥0, что (х*, λ*) - седловая точка функции Лагранжа L (x,λ).
1.3 Решение задач квадратичного программирования методом седловой точки
Рассмотрим задачу квадратичного программирования, т.е.
f
(x) =
(Сx,x)
+ (d,x)
min, (15),
g (x)
=Ax ≤
b,
где С - матрица размера n*n; d, х - векторы-столбцы n*1; А - матрица размера m*n; b - вектор-столбец m*1. Для задачи квадратичного программирования критерий существования седловой точки приобретает вид задачи решения СЛАУ. Действительно, функция Лагранжа в этом случае запишется в виде
L
=
dkxk+![]()
ckjxkxj+
λi
(
aijxj-bi),
(16)
где ckj - элементы матрицы С; dk - элементы вектора d; bi - элементы вектора свободных членов b; aij - элементы матрицы А; λi - коэффициенты Лагранжа. Необходимые и достаточные условия оптимальности решения х* принимают вид
vj
dj+2
ckjxk+
λiaij,
vj
≥0, (j=1,…,n),
(17)
yi
aijxj-bi,
- yi
≤0, (i=1,...,m),
(18)
xjvj=0, xj≥0, (j=1,...,n), (19)
λi (-yi) =0, λi≥0. (20)
Равенства (17), (18) образуют систему n+m линейных уравнений с 2 (n+m) неизвестными x1,…,xn,v1,…,vn, λ1,…, λm,y1,…,ym. Решения этой системы, при которых выполняются равенства (19), (20), дают координаты седловой точки (х*,λ*). Соответственно n координат х* дают оптимальное решение задачи (15).
2. Порядок выполнения лабораторной работы
Построить допустимую область задачи и линии уровня.
Записать функцию Лагранжа и необходимые условия экстремума, из которых аналитически или используя прикладные пакеты найти условно-стационарные точки.
Для каждой точки указать активные и пассивные ограничения. Проверить выполнение достаточных условий экстремума в найденных стационарных точках. Найти глобальный минимум функции. Используя критерий (утверждение 1), проверить, что найденная точка является седловой точкой функции Лагранжа.
Проверить справедливость оценки (9), решив задачу при положительных и отрицательных малых значениях приращения ∆b.
Решить задачу квадратичного программирования методом седловой точки. Для этого записать систему (17) - (18), найти ее решения, удовлетворяющие условиям (19) - (20).
3. Пример выполнения лабораторной работы
Минимизировать
нелинейную
функцию
при условиях
и
,
применяя метод
функции Лагранжа.
Проверить
справедливость
оценки изменения
целевой функции
(9).
![]()

![]()
Допустимая
область - часть
сферы
,
лежащая в
подпространстве
,
a= (1, 1,1).

Рассмотрим
случай
.
Если при этом
,
то
.
Из (21) -
(23) ®
,
что противоречит
(28).
Если
,
то
(иначе получаем
противоречия
в (21) - (23)).
Из (21) -
(23) ®
.
Подставим в
(26):
.
Отсюда
,
что противоречит
исходному
предположению
.
Рассмотрим
теперь случай
.

Если
,
то получаем
точку
(из (1′) … (3′), (7′)).
Остальные "симметричные" точки здесь и далее приводить не будем.
Если
,
,
,
то
,
,
.
Далее получаем точки
и
.
,
.
Для
значение
,
для
значение
.

Если
,
,
то
Если
,
то
и
.
Следовательно,
и
.
Однако,
,
значит, пришли
к
противоречию.
Таким
образом,
.
Суммирование первых трех уравнений дает уравнение
,
в котором последнее слагаемое равно нулю, поэтому
.
С другой стороны,
и
.
Следовательно,
,
откуда
.
Если
,
то
.
Разделим
равенства на
:
.
Однако, если
,
то их произведение
не может быть
равно
.
Значит,
.
Если
,
получаем следующую
систему:

.
Получаем точку
(в силу симметрии переменных х1, х2, х3 координаты можно переставить),
,
.
Предположив
,
получим те же
результаты.
Найдены следующие точки:
,
,
;
,
,
,
;
,
,
,
;
,
,
,
.
Запишем второй дифференциал обобщенной функции Лагранжа.