МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ
ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ОБРАЗОВАНИЯ
ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ
МЕТОДЫ ОПТИМИЗАЦИИ
Учебно-методическое пособие
Составители: Е. П. Белоусова, Т. И. Смагина
Воронеж
Издательский дом ВГУ
2017
Стр.1
1. Конечномерная оптимизация (Математическое программирование)
§1. Конечномерные задачи без ограничений
Рассмотрим задачу
f(x) → extr, x ∈ Rn.
(1.1)
1. Необходимое условие экстремума первого порядка.
Пусть f : En → R и имеет непрерывные частные производные ∂f/∂xi,
i = 1, n. Точка x0 называется точкой локального максимума функции f, если
существует окрестность B(x0, r) такая, что для всех x ∈ B(x0, r) выполнено
неравенство f(x0) f(x).
Здесь B(x0, r) = {x ∈ En : x − x0 < r}.
Теорема Ферма. Если x0 - точка локального экстремума дифференцируемой
функции f, то ∂f/∂xi = 0 для всех i = 1, n. Или
f (x0) = grad f(x0) = 0.
Здесь grad f(x) - это вектор из частных производных функции f(x) по
переменным x1, ..., xn. Точка x0 такая, что grad f(x0) = 0 называется стационарной.
2.
Необходимое условие экстремума второго порядка. Достаточное
условие. Пусть f дважды непрерывно дифференцируема. Разложим ее
в ряд Тейлора в окрестности точки x0:
f(x0 + h) = f(x0) + (f (x0), h) + 1/2(f (x0)h, h) + o( h 2).
(1.2)
Матрица f (x0) = (∂2f/∂xi∂xj)(x0) является симметричной. Симметричная
матрица A называется положительно определенной [неотрицательно определенной],
если для всех 0 = x ∈ Rn выполнено неравенство (Ax, x) > 0
[(Ax, x) 0].
3
Стр.3
§2. Задачи с ограничениями типа равенств.
Необходимые и достаточные условия экстремума. Пусть fk : En →
R, k = 0,m - дважды дифференцируемые функции. Требуется найти экстремум
функции f0(x) при ограничениях fk(x) = 0, k = 1,m, т.е. решить
задачу
f0 → extr, fk(x) = 0, k = 1, m.
Построим функцию Лагранжа
L(x, λ0, λ) = λ0f0(x) +
где λ0 ∈ R, λ = (λ1, ..., λm) ∈ Em - множители Лагранжа.
Задача на экстремум с ограничениями типа равенств сводится к задаче на
m
k=1
безусловную оптимизацию для функции Лагранжа.
Теорема (принцип Лагранжа). Пусть x0 - точка локального экстремума
в задаче (2.1) и функции f0, fk, k = 1,m – непрерывно дифференцируемы
в окрестности точки x0. Тогда существует ненулевой вектор множителей
Лагранжа (λ0, λ) = (λ0, λ1, ..., λm) такой, что для функции Лагранжа выполняется
условие стационарности
Lx(x0, λ) = 0 ⇔ λ0f 0(x) +
Lλ(x0, λ0, λ) = 0 ⇔ fk(x0) = 0, k = 1, ..., m.
m
k=1
Замечание. Для определения x0, λ0, λ получаем систему из n+m уравнений,
а неизвестных n+m+1. Поэтому каждой точке локального экстремума
соответствует бесконечное множество наборов множителей Лагранжа.
Если среди систем множителей Лагранжа, соответствующих точке локального
экстремума, нет множителей с λ0 = 0, то такая точка называется точкой
нормального экстремума. Для нормальной точки локального экстремума
множители Лагранжа определяются однозначно.
6
λkf k(x0) = 0.
(2.2)
λkfk(x),
(2.1)
Стр.6
Следует рассмотреть два случая:
1) λ0 = 0; обычно отсюда следует, что и λ = 0, т.е. этот случай не подходит;
2) λ0 = 0; тогда полагают λ0 = 1.
Решая систему (2.2), находят все стационарные (подозрительные на экстремум)
точки. Дальнейшее исследование проводят так же, как и в случае
безусловного экстремума.
Условия экстремума второго порядка связаны со знаком матрицы вторых
производных Lxx функции Лагранжа.
Теорема (необходимое условие минимума). Пусть выполнены следующие
условия:
1) x0 - точка локального минимума в задаче (2.1);
2) функции fk(x), k = 1,m дважды непрерывно дифференцируемы в
окрестности этой точки (условие гладкости);
3) градиенты f 1(x0), ..., f m(x0) линейно независимы, т.е
dimL{f 1(x0), ..., f m(x0) = m} (условие регулярности). Оно эквивалентно тому,
что λ0 = 0.
Тогда существует набор множителей Лагранжа
(λ0, λ) = (λ0, λ1, ..., λm) такой, что для функции Лагранжа задачи (2.1) выполняются
условия стационарности
Lx(x0, λ0, λ) = 0 ⇔ λ0f 0(x0) +
m
k=1
λkf k(x0) = 0, (2.3)
Lλ(x0, λ0, λ) = 0 ⇔ fk(x0) = 0, k = 1, m,
где Lx - вектор из частных производных функции Лагранжа по переменным
x и неотрицательности:
(Lxx(x0, λ0, λ)h, h) 0 ∀h : таких, что (f k(x0), h) = 0, k = 1,m (2.4),
7
Стр.7
где Lxx - матрица из вторых частных производных функции Лагранжа по
переменным x.
Теорема (достаточное условие минимума). Пусть существует точка
x0, что выполнены условия 2) гладкости и 3) регулярности предыдущей теоремы
и существует набор множителей Лагранжа (λ0, λ), что для функции
Лагранжа задачи (2.2) выполняются условие стационарности:
Lx(x0, λ0, λ) = 0 ⇔ λ0f 0(x0) +
m
k=1
λkf k(x0) = 0 k = 1,m;
Lλ(x0, λ0, λ) = 0 ⇔ fk(x0) = 0, k = 1,m
и условие положительности:
(Lxx(x0, λ)h, h) > 0 ∀h = 0 : таких, что (f k(x), h) = 0, k = 1, m.
Тогда x0 - точка локального минимума в задаче (2.2).
Всякое замкнутое ограниченное множество в Rn является компактным,
поэтому верна
Теорема Вейерштрасса. Непрерывная функция на непустом ограниченном
замкнутом множестве в Rn достигает абсолютных максимума и минимума.
Следствие1.
Если f(x) непрерывна на Rn и lim|x|→∞ = +∞ (lim|x|→∞ =
−∞), то f достигает своего абсолютного минимума (максимума) на любом
замкнутом подмножестве в Rn.
Правило решения. Для решения задачи (2.2) с ограничениями типа равенств
следует:
1) составить функцию Лагранжа
L(x, λ0, λ) = λ0f0(x) +
8
m
k=1
λkfk(x);
Стр.8
2) выписать условие стационарности функции Лагранжа
Lx(x0, λ0, λ) = 0 ⇔
и ограничения - равенства fk(x) = 0, k = 1,m;
3) из полученной системы найти стационарные точки x0. Целесообразно
проанализировать два случая:
а)λ0 = 0. Данный вырожденный случай на практике случается достаточно
m
k=0
редко. В большинстве задач это предположение приводит к тривиальности
всех множителей Лагранжа. В некоторых примерах удается сразу убедиться
в линейной независимости градиентов ограничений при всех допустимых x.
Тогда этот вариант рассматривать не надо.
b)λ0 = 0. В этом случае удобно принять λ0 = 1.
4) Найденные стационарные точки исследуются на локальный экстремум с
помощью достаточного условия. Иногда стоит проверить квадратичную форму
Lxx на строгую знакоопределенность на всем пространстве Rn с помощью
критерия Сильвестра и лишь затем (если это будет необходимо) выяснять
вопрос о знаке Lxx на множестве, определяемом ограничениями задачи.
5) Если не выполняется достаточное условие, то надо проверить выполнение
необходимого условия экстремума.
Задача. Найти параметры цистерны, которая при заданной площади поверхности
S имеет минимальный объём V .
Если обозначить через x1 высоту, а через x2 радиус основания, то приходим
к задаче
V = πx2
при ограничении S = 2πx2
x2
1 + x2
2 + 2πx1x2.
Пример 1. Решить задачу f0(x) = 4x1 + 3x2 → extr при ограничении
2 = 1.
9
2x1 → min
λkf k(x0) = 0
Стр.9
Решение. Составим функцию Лагранжа
L(x, λ0, λ) = λ0(4x1 + 3x2) + λ1(x2
1 + x2
2 − 1).
Для нахождения стационарной точки выпишем необходимое условие
Lx1
Lx2
Lλ1 : x2
: 4λ0 + 2λ1x1 = 0
: 3λ0 + 2λ1x2 = 0
1 + x2
2 − 1 = 0.
1). Рассмотрим случай λ0 = 0. Тогда λ1x1 = 0 и λ1x2 = 0, откуда следует,
что либо λ1 = 0 (чего не может быть), либо x1 = 0 и x2 = 0, чего также не
может быть, ибо тогда не выполняется ограничение задачи.
Таким образом, λ0 = 0 и можно положить λ0 = 1. Из системы
находим, что λ1 = − 2
что x1 = ±4
A(4
5, 3
для точки B .
Найдём матрицу вторых производных. Имеем
5) и B(−4
x1 и x1 = 4
4 + 2λ1x1 = 0
3 + 2λ1x2 = 0
3x2. Из ограничения задачи x2
5, −3
5). Множитель Лагранжа λ1 = −5
поэтому матрица Lxx < 0 в точке A и Lxx > 0 для точки B . Поэтому
(4
Lxx = 2λ1 0
0 2λ1 ,
5, 3
x4
5) ∈ loc max, а (−4
5, −3
5) ∈ loc min.
1 + x4
Пример 2. Решить задачу f0 = x2
2 = 1.
1 + x2
2 → extr при ограничении
Решение. Составим функцию Лагранжа
L(x, λ0, λ) = λ0(x2
1 + x2
10
1+x2
2 = 1 следует,
5 и x2 = ±3
5. Таким образом, получены две стационарные точки
2 для точки A и λ1 = 5
2
2) + λ1(x4
1 + x4
2).
Стр.10