- •Аннотация
- •Оглавление
- •Предисловие
- •ГЛАВА 1. Задачи оптимизации. Основные определения
- •1.1. Задачи оптимизации
- •1.2. Минимум функции одной переменной
- •1.3. Унимодальные функции
- •1.4. Выпуклые функции
- •1.5. Условие Липшица
- •1.6. Классическая минимизация функции одной переменной
- •Вопросы и задания для самоконтроля
- •ГЛАВА 2. Одномерная минимизация функций. Прямые методы
- •2.1. О прямых методах
- •2.2. Метод перебора
- •2.3. Метод поразрядного поиска
- •2.4. Метод дихотомии
- •2.5. Метод золотого сечения
- •2.6. Сравнение методов перебора, дихотомии и золотого сечения
- •2.7. Метод парабол
- •Вопросы и задания для самоконтроля
- •Задание для численной реализации в среде программирования MATLAB
- •ГЛАВА 3. Одномерная минимизация. Методы, использующие информацию о производных целевой функции
- •3.1. Метод средней точки
- •3.2. Метод хорд
- •3.3. Метод Ньютона
- •3.4. Возможные модификации метода Ньютона
- •3.5. Методы минимизации многомодальных функций
- •Вопросы и задания для самоконтроля
- •Задание для численной реализации в среде программирования MATLAB
- •ГЛАВА 4. Задача минимизации функции многих переменных. Необходимые и достаточные условия безусловного экстремума
- •4.1. Постановка задачи и определения
- •4.2. Свойства выпуклых множеств и выпуклых функций
- •4.3. Необходимые и достаточные условия безусловного экстремума
- •Вопросы и задания для самоконтроля
- •5.1. Выпуклые квадратичные функции
- •5.2. Общие принципы многомерной минимизации
- •5.3. Метод градиентного спуска
- •5.4. Метод наискорейшего спуска
- •5.5. Метод сопряженных направлений
- •5.6. Метод сопряженных градиентов
- •5.7. Метод Ньютона
- •5.8. Квазиньютоновские методы
- •Вопросы и задания для самопроверки
- •Задание для численной реализации в среде программирования MATLAB
- •ГЛАВА 6. Прямые методы безусловной минимизации многомерных задач
- •6.1. Проблема минимизации многомерных задач
- •6.2. Минимизация функций по правильному (регулярному) симплексу
- •6.3. Минимизация функций при помощи нерегулярного симплекса
- •6.4. Метод циклического покоординатного спуска
- •6.5. Метод Хука–Дживса
- •6.6. Методы случайного поиска
- •Вопросы и задания для самопроверки
- •Задание для численной реализации в среде программирования MATLAB
- •7.1. Условный экстремум при ограничениях типа равенств
- •7.2. Условный экстремум при ограничениях типа неравенств
- •Вопросы и задания для самопроверки
- •ГЛАВА 8. Линейное программирование
- •8.1. Определения. Примеры задач линейного программирования
- •8.2. Общая и каноническая задачи линейного программирования
- •8.3. Геометрическое истолкование задач линейного программирования
- •8.4. Аналитическое решение задач линейного программирования
- •Вопросы и задания для самоконтроля
- •Литература
Пример 1.8. Доказать, что из выпуклости функции f (x) на отрезке [a, b]
следует ее унимодальность на [a, b] , если ограничиваться только
дифференцируемыми на [a, b] функциями. |
|
не убывает на |
этом отрезке. |
|||
□ Пусть f (x) выпукла |
на |
[a, b] , тогда |
f (x) |
|||
|
|
|
′ |
|
|
|
Допустим противное, т.е. что |
f (x) не унимодальна на [a, b] . |
Тогда существуют |
||||
x1 , x2 , x3 [a, b] такие, что |
f (x1 ) < f (x2 ) и |
f (x3 ) < f (x2 ) . А |
это |
противоречит |
||
дифференциальному критерию "а" выпуклости f (x) |
на [a, b] . ■ |
|
|
1.5. Условие Липшица
Применение некоторых методов одномерной минимизации возможно только в том случае, если скорость изменения целевой функции f (x) на любых участках отрезка [a, b] ограничена некоторым числом, одним и тем же для всех участков. В
этом случае говорят, что f (x) удовлетворяет на отрезке [a, b] условию Липшица.
Целевые функции большинства практических задач оптимизации таким свойством обладают.
Определение. Функция f (x) удовлетворяет на отрезке [a, b] |
условию |
|||||||
Липшица, если существует такое число L > 0 (константа Липшица), что |
|
|||||||
|
f (x′) − f (x′′) |
|
≤ L |
|
x′− x′′ |
|
|
(1.7) |
|
|
|
|
|||||
для всех x′ и x′′, принадлежащих [a, b] . |
|
|||||||
Необходимо обратить внимание на следующее. |
|
1.Если неравенство (1.7) выполняется с константой L , то оно справедливо и для всех L′ > L . Поэтому для функции, удовлетворяющей условию Липшица, существует бесконечное множество констант L из (1.7). При использовании алгоритмов минимизации, включающих L как параметр, наилучшие результаты достигаются, как правило, если в качестве L берется минимальная из констант Липшица.
2.Из условия (1.7) сразу следует непрерывность f (x) на отрезке [a, b] .
Поэтому, согласно теореме Вейерштрасса, функция f (x) , удовлетворяющая на отрезке [a, b] условию Липшица, имеет на нем хотя бы одну точку минимума, хотя не является, вообще говоря, унимодальной.
14
3. Условие (1.7) означает, что модуль углового коэффициента любой хорды графика f (x) не превосходит L . Переходя в (1.7) к пределу при x′− x′′ → 0 ,
убеждаемся, что если в некоторой точке существует касательная к графику f (x) , то
модуль ее углового коэффициента также не может превышать |
L . Так, функция |
||
f (x) = |
x на отрезке [0, 1] условию Липшица не удовлетворяет, |
потому что при |
|
x → +0 |
угловой коэффициент |
касательной к ее графику k |
неограниченно |
возрастает (рис. 1.5). |
|
|
|
|
y |
f(x) |
|
k=1,1
1,6
5
0,01 0,1 |
0,2 |
1 |
x |
Рис.1.5. График функции |
f (x) = |
x , x [0, 1] , не удовлетворяющей условию |
|
Липшица |
|
|
|
4. Если функция f (x) имеет на отрезке [a, b] непрерывную производную, то
она удовлетворяет на этом отрезке условию Липшица с константой L = max |
|
f |
′ |
|
. |
|||||||||||||||||||||||||||
|
|
|||||||||||||||||||||||||||||||
|
(x) |
|
||||||||||||||||||||||||||||||
|
|
|
Пример 1.9. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
[a, b] |
|
|
|
|
|
|||||||
|
|
|
Найти наименьшую |
|
из |
констант |
|
Липшица |
функции |
f (x) = |
||||||||||||||||||||||
|
1 |
x3 |
+ 2x2 |
−5x + 6 |
на отрезках а) |
x [0, 1] |
, б) |
x [0, 10] . |
|
|
|
|
|
|
|
|
|
|
||||||||||||||
3 |
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
□ Производная функции f |
′ |
2 |
+ 4x −5 = (x +5) (x −1) , |
|
поэтому в случае "а" |
||||||||||||||||||||||||
|
|
|
(x) = x |
|
|
|||||||||||||||||||||||||||
|
L = max |
|
f |
′ |
|
= |
|
f |
′ |
|
= 5 , а в случае "б" |
|
L = max |
|
′ |
|
= |
|
′ |
|
=135 |
. ■ |
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
|
|
(x) |
|
|
(0) |
|
|
|
f (x) |
|
|
f (10) |
|
|
|
|
||||||||||||||||
|
|
|
[0, 1] |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
[0, 10] |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
15
|
|
Пример 1.10. Показать, что для дифференцируемой на отрезке [a, b] |
функции |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
f (x) |
|
величина |
L = max |
|
f |
′ |
|
|
|
|
представляет собой |
минимальную из |
|
констант |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
(x) |
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
[a, b] |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
Липшица f (x) на [a, b] . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||
|
|
□ Пусть существует |
|
|
L1 |
< L = max |
|
f ′(x) |
|
|
такая, |
что |
|
f (x′) − f (x′′) |
|
≤ L1 |
|
|
x′− x′′ |
|
для |
||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
[a, b] |
|
|
|
и переходя к пределу при |
|
|
|
|
|
|
|
|
|
, получим |
||||||||||||||||||||||||
всех |
|
′ |
|
′′ |
[a, b]. |
Тогда, |
|
фиксируя x |
′ |
x |
′′ |
|
|
′ |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
x , x |
|
|
|
|
|
|
|
→ x |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
′ |
|
′ |
|
≤ L1 |
, |
|
|
|
а |
|
|
|
вследствие |
произвольности |
|
|
точки |
′ |
[a, b] |
|
|
|
|
получим |
||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
f (x ) |
|
|
|
|
|
|
|
|
x |
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
max |
|
|
′ |
|
≤ L1 |
< L |
. Полученное противоречие доказывает утверждение. ■ |
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
f (x) |
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
[a, b] |
Пример 1.11. Найти наименьшую из |
констант |
Липшица |
функции |
f (x) = |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
4x3 −30x2 |
+ 72x +12 на отрезках а) |
x [0, 2] , б) x [2, 3]. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
□ |
|
Производная |
функции |
f |
′ |
|
|
|
=12x |
2 |
−60x + 72 =12(x − 2) (x −3) , |
поэтому в |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
(x) |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
случае "а" |
L = max |
|
|
f |
′ |
|
= |
|
f |
′ |
|
|
= 72 , а в случае "б" |
L = max |
|
|
f |
′ |
|
|
= |
|
f |
′ |
|
|
|
|
= 3 . ■ |
||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
(x) |
|
|
(0) |
|
|
|
|
(x) |
|
|
|
(2,5) |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
[0, 2] |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
[2, 3] |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
Пример 1.12. Найти наименьшую из |
констант |
Липшица |
функции |
f (x) = |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
x3 + 6x2 |
−15x на отрезках а) |
x [0, 1] , б) |
x [0, 10] . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||
|
|
□ Производная функции f |
′ |
|
|
|
|
|
2 |
+12x −15 = 3(x +5) (x −1) , |
|
|
поэтому в случае |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
(x) = 3x |
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
"а" |
L = max |
|
f |
′ |
|
= |
|
f |
′ |
|
|
=15 , а в случае "б" |
L = max |
|
′ |
|
|
= |
|
f |
′ |
|
|
= 405 . ■ |
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
(x) |
|
|
(0) |
|
|
|
f (x) |
|
(10) |
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
[0, 1] |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
[0, 10] |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1.6. Классическая минимизация функции одной переменной
Из математического анализа известны следующие условия локального экстремума функции f (x) , дифференцируемой достаточное количество раз.
1.Если функция f (x) дифференцируема в точке ~x и достигает в ней локального экстремума, то f ′(~x ) = 0 (необходимое условие экстремума).
2.Пусть функция f (x) n раз дифференцируема в точке ~x и в этой точке все
производные |
f (x) до |
(n −1) -го порядка включительно равны нулю, а |
f |
(n) |
~ |
||||
|
(x) ≠ 0 . |
||||||||
Тогда, если n |
− нечетно, то точка x не является точкой локального экстремума |
||||||||
|
|
|
|
|
~ |
|
|
|
|
функции f (x) . Если же n − четное число, то: |
|
|
|
|
|||||
а) при |
f |
(n) |
~ |
~ |
− точка локального минимума |
f (x) ; |
|
|
|
|
(x) > 0 |
x |
|
|
|
||||
б) при |
f |
(n) |
~ |
~ |
− точка локального максимума |
f (x) |
|
|
|
|
(x) < 0 |
x |
|
|
|
(достаточные условия экстремума).
16
Перечисленные условия позволяют предложить следующий путь решения задачи минимизации (1.5):
1. с помощью условия 1 находим все точки возможного экстремума функции f (x) на интервале (a, b) , т.е. корни уравнения
′ |
(1.8) |
f (x) = 0, |
(стационарные точки функции f (x) , принадлежащие интервалу (a,b) );
2.найденные стационарные точки исследуем в соответствии с условием 2, выделяя из них только точки локальных минимумов f (x) ;
3.значения f (x) в точках локальных минимумов и на концах отрезка [a, b]
сравниваем между собой. Наименьшему из этих значений соответствует точка глобального минимума f (x) на [a, b] .
Применение условия 2 требует вычисления высших производных функции f (x) , поэтому в большинстве случаев бывает проще сравнить значения f (x) во
всех стационарных точках, не интересуясь их характером. С учетом этого можно
предложить |
|
следующий |
алгоритм |
минимизации |
|
f (x) |
на |
отрезке |
[a, b] |
|||||||||||
(классический метод, который разберем на примере). |
|
|
|
|
|
|
|
|
||||||||||||
Пример 1.13. Решить задачу f (x) = x3 −3x +1 → min, |
x [−2, 2]. |
|
|
|
|
|||||||||||||||
□ Шаг 1. Находим корни уравнения |
f |
′ |
= 3x |
2 |
−3 = 0 |
из интервала (−2, 2) : |
||||||||||||||
(x) |
|
|||||||||||||||||||
x1 = −1, x2 =1. |
Полагаем x0 |
= −2, x3 |
= 2. |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
Шаг |
|
2. |
Вычисляем |
значения |
|
f (x) |
|
в |
точках |
xi , |
i = 0, ..., 3 : |
|||||||||
f (x0 ) = −17, |
|
f (x1 ) = 3, |
f (x2 ) = −1, |
f (x3 ) =1. |
|
|
|
|
|
|
|
|
|
|
|
|||||
Шаг 3. Находим f |
= min(−17, 3, −1, 1) = −17 = f (x0 ). Поэтому x = −2, f = −17. ■ |
|||||||||||||||||||
Пример 1.14. Найти f (x) = x3 −27x +5 → min, |
x [−4, 4]. |
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
□ |
Найдем |
корни уравнения |
′ |
= 3x |
2 |
− 27 = 0 из |
|||||||||
|
|
|
|
|
f (x) |
|
||||||||||||||
интервала |
x (−4, 4) : |
|
x1 |
= −3, x2 = 3. |
Положим |
|
x0 = −4, x3 |
= 4. |
|
|
Так |
как |
||||||||
f ′′(x1 ) = |
f ′′(−3) = −18 < 0 , |
то |
x1 |
− |
точка |
локального максимума. |
Так |
как |
||||||||||||
f ′′(x2 ) = |
f ′′(3) =18 > 0, |
|
то |
|
x2 |
|
|
точка |
|
|
локального |
|
|
минимума. |
||||||
f (3) = −49, |
f (−4) = 49, |
f (4) = −39. Производя перебор, получим |
x = 3, f = −49. |
■
17