Методы оптимизации

УДК 681.51.01:517.977.5 
С 50 

Р е ц е н з е н т 
доцент, кандидат технических наук В.М. Клемперт 

Смирнов А.П. 

С50 
Методы оптимизации: Учеб. пособие. - М.: МИСиС, 2003.
131с. 

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

Учебное пособие предназначено для студентов, обучающихся по специальностям 220200 и 351400, и может быть полезно также всем изучающим моделирование и оптимизацию систем. 

© Московский государственный институт 
стали и сплавов (Технологический 
университет) (МИСиС), 2003 

ОГЛАВЛЕНИЕ 

1. Основные понятия и проблемы оптимизации 
6 

1.1. Задача оптимизации 
6 

1.2. Геометрическое представление процесса поиска экстремума 
7 

1.3. Условия существования минимума 
9 

1.4. Общий вид алгоритма поиска минимума функции 
10 

1.5. Методы одномерного поиска в заданном направлении 
11 

1.6. Оценка производных 
13 

Контрольные вопросы 
14 

2. Методы безусловной оптимизации 
15 

2.1. Классификация методов безусловной оптимизации 
15 

2.2. Методы нулевого порядка 
15 

2.2.1. Симплексный метод 
16 

2.2.2. Метод сопряженных направлений 
18 

2.2.3. Методы случайного поиска 
23 

2.3. Методы первого порядка 
25 

2.3.1. Метод градиента 
25 

2.3.2. Метод наискорейшего спуска 
26 

2.3.3. Метод сопряженных градиентов 
27 

2.4. Методы второго порядка 
30 

2.4.1. Метод Ньютона 
30 

2.4.2. Метод тяжелого шарика 
31 

Контрольные вопросы 
32 

3. Методы условной оптимизации 
33 

3.1. Задача условной оптимизации 
33 

3.2. Нелинейное программирование 
33 

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

3.2.2. Метод Лагранжа 
35 

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

3.2.4. Метод множителей 
39 

3.2.5. Иллюстрация работы методов для функции одного 
аргумента 
41 

3.2.5.1. Метод Лагранжа 
41 

3.2.5.2. Метод штрафных функций (квадратичный штраф) 
42 

3.2.5.3. Метод множителей 
44 

3.2.6. Пример применения условий Куна - Таккера 

для функции двух переменных 
47 

3.2.7. Пример задачи невыпуклого программирования 
53 

3 

Контрольные вопросы 
56 

3.3. Линейное программирование 
57 

3.3.1. Общая характеристика задачи 
57 

3.3.2. Геометрия задачи ЛП 
58 

3.3.3. Стандартная и каноническая формы задачи ЛП 
59 

3.3.4. Симплекс-метод 
61 

3.3.4.1. Организация перемещения точки поиска 
61 

3.3.4.2. Выражение целевой функции/^х) через свободные 
переменные 
62 

3.3.4.3. Правило выбора пары х. и х. 
63 

3.3.4.4. Алгоритм симплекс-метода 
64 

3.3.5. Методы получения начального ДБР 
65 

3.3.6. Пример постановки и решения задачи ЛП 
67 

3.3.6.1. Постановка задачи 
67 

3.3.6.2. Решение задачи симплекс-методом 
68 

3.3.6.3. Графическое решение задачи 
71 

Контрольные вопросы 
74 

4. Алгоритмы дискретной оптимизации 
75 

4.1. Общие сведения о задачах 
75 

4.2. Динамическое программирование (ДП) 
77 

4.2.1. Описание задачи ДП 
77 

4.2.2. Постановка задачи ДП 
78 

4.2.3. Формальная терминология задачи ДП 
78 

4.2.4. Описание алгоритма 
79 

4.2.5. Примеры решения задач ДП 
80 

4.2.6. Типичные задачи динамического программирования распределение ресурсов 
91 

4.3. Метод ветвей и границ 
93 

4.4. Дискретное (целочисленное) линейное программирование 
94 

4.4.1. Постановка задачи 
94 

4.4.2. Решение задачи ЦЛП методом ветвей и границ 
95 

4.4.3. Решение задачи ЦЛП методом Гомори 
98 

4.5. Задачи оптимизации на графах и сетях 
102 

4.5.1. Выбор на графе замкнутого пути с минимальной 
стоимостью («задача коммивояжера») 
102 

4.5.2. Задача о максимальном потоке в сети 
ПО 

Контрольные вопросы 
118 

Литература 
119 

4 

ПРИЛОЖЕНИЯ 
120 

Приложение!. Некоторые 
функции 
для 
тестирования 

работоспособности 
алгоритмов 
поиска 

минимума 
120 

Приложение 2. Доказательство 
для 
метода 
сопряженных 

градиентов 
120 

Приложение 3. Условия минимума второго порядка для задачи 

с неравенствами 
124 

Приложение 4. Вывод формул для метода множителей 
127 

5 

1. ОСНОВНЫЕ ПОНЯТИЯ и ПРОБЛЕМЫ 
ОПТИМИЗАЦИИ 

1.1. Задача оптимизации 

При разработке проектов систем различного рода возникает необходимость наилучшего в определенном смысле выбора параметров системы. Для этого необходимо решение задач двух основных типов. 

Первая задача ставится следующим образом (рис. 1.1): имеется 
система S с фиксированным входным вектором X(t), управляемым 
входным вектором U(t) и выходным вектором Z(t), связанным с ДО и 
U(t) некоторым оператором. Здесь ?- это время. 

X(t) 

Щ) 

> 

-> 

S 

Z(t) 

> 1 

F 
J 

Рис. 1.1. Структура модели динамической оптимизации 

Определен некоторый целевой функционал 
Y-F(X(t),U(t),Z(t)). 
Требуется найти функцию U(t), которая обеспечивает экстремум Y. 

Такие задачи обычно рассматриваются в курсе теории управления. Они относятся к классу задач динамической оптимизации. 

Имеется обширный класс задач исследования и проектирования 
систем, где входные и выходные векторные переменные не зависят 
от времени. При этом обычно говорят, что рассматривается статическая модель системы (рис. 1.2). 

X 

S 
i F т 

Рис. 1.2. Структура модели статической оптимизации 

\ 

Z 
Y 

6 

в рамках такой модели бывает определена целевая функция 
Y-F{X,Z). 
При этом считается, что все входные переменные системы X могут выбираться из некоторой заданной области, а все неизменяемые входные параметры включены в оператор S. Переменные Z 
при этом могут рассматриваться как функции Z{X) и тогда Y будет 
являться функцией только X 

Требуется выбрать значения X, дающие экстремум функции 
7= F\X). Такая задача называется задачей статической оптимизации. 

Если область, из которой можно выбрать значения X, составляет 
все пространство (выбор не ограничен), соответствующая задача называется задачей безусловной оптимизации. 

В противном случае область выбора ограничена с помощью системы неравенств G{X) > 0. Иногда это могут быть равенства. В этом 
случае говорят, что имеется задача условной оптимизации, понимая 
под условиями соответствующие уравнения или неравенства, ограничивающие область выбора. 

1.2. Геометрическое представление процесса 
поиска экстремума 

Процесс 
функционирования 
алгоритмов 
поиска 
экстремума 
функции удобно проиллюстрировать, показав траекторию поиска в 
плоскости линий уровня функции двух переменных у = 
f{x„x,). 

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

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

7 

Рис. 1.3. Построение линий уровня 

Уравнение ЛИНИЙ уровня функции y = f{x„x,) 
записывается следующим образом: 

Если из этого уравнения можно выразить хг, то уравнение линии 
уровня можно записать в явном виде: 

x,=V{x„c). 

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

Алгоритмы поиска минимума обеспечивают пошаговое движение 
к минимуму, начиная из некоторой произвольной начальной точки в 
области определения функции. Пример такого движения на плоскости линий уровня показан на рис. 1.4. Траектория поиска закапчивается в районе точки минимумах*. 

В алгоритмах поиска минимума часто используется понятие градиента функции. Напомним, что градиентом называется вектор, компонентами которого являются частные производные функции но ее 
аргументам. Для функции двух неременных этот вектор нерпендикулярен касательной к линии уровня в рассматриваемой точке и указывает направление максимального возрастания функции, то есть максимальное значение приращения функции А/ при фиксированном 
модуле вектора Ас. 

8 

Рис. 1.4. Типовая траектория поиска минимума функции 

1.3. Условия существования минимума 

Запишем разложение функции Дх) в ряд Тейлора в окрестности 
точки / с точностью до малых 3-го порядка. Заметим, что х и dx везде будут выступать в качестве векторов, за исключением некоторых 
случаев, о которых будет сказано особо. Индекс Т обозначает транспонирование. 

Лх) =Ях) + G V ) - A X + (1/2).АхТ.Я(/)-Ах + 0,(Ах), 
(1.1) 

где G(/) 
вектор-градиент в точке х(0); 

Щх) 
матрица вторых производных (матрица Гессе). 

Напомним, что условие стационарности точки х есть равенство 
нулю градиента: G(/) = 0. 

В точке минимума приращение функции ^f{x)=Ax)-Ax) 
должно 
быть больше нуля при любомх, удовлетворяющем условию | | х - / 1 | < 8 . 

Это условие записывают также следующим образом: х принадлежит sv4x, 8), то есть точка х принадлежит множеству точек сферы 

9 

радиусом s с центром в точке / . Тогда из (1.1) следует положительность квадратичной формы: 

Лх"-Я(/)-Лх>0. 

Последнее выражение означает положительную определенность 
матрицы Я в точке/. 

Заметим, что при построении алгоритмов поиска минимума 
должно быть введено условие останова. Это условие для гладких 
функций обычно состоит в проверке близости модуля градиента к 
нулю. С другой стороны, алгоритмы поиска должны быть рассчитаны на то, что в точке минимума градиент может не существовать. 
Тогда в общем случае правило останова должно быть реализовано в 
виде непосредственной проверки условия АДх) > 0. 

1.4. Общий вид алгоритма поиска минимума функции 

Алгоритм поиска минимума некоторой функции Дх) в общем виде 
представляет собой итерационную процедуру вида 

x{k+\)-x{k) 
+ a{k)-S{k\ 

где х{к) - предыдущая точка в пространстве переменных; 
х(^+1) - следующая точка; 
S{k) - вектор направления перемещения; 
а{к) - скалярный множитель, определяющий величину шага в направлении ЭД; 
yt-номер итерации. 

Операции алгоритма состоят в следующем: 
1) задать yt = О и начальную точку х(0); 
2) вычислить значение функцииХх(у1)); 

3) вычислить направление S{k) из условия уменьшения функЦииДх); 

4) вычислить очередную точку х{к+\)-х{к) 
+ a{k)-S{k); 

5) вычислить значение/(х(^+1)); 
6) вычислить и проверить выполнение условия останова. 

Если условие выполнено, идти к 9. 
1)к^к+1; 
8) идти к 3; 
9) вывод результатов. STOP. 

10 

Методы поиска минимума отличаются друг от друга способом вычисления направления и множителя а{к\ а также условиями останова. 

Наиболее общим условием останова является сравнение нормы 
разности hx{k) ^х{к+\) -х{к) с заданным числом s^ . 

Останов алгоритма в общем случае еще не означает, что найдена 
точка минимума. Чтобы это утверждать, нужно проверить классическое условие минимума АДх(^+1)) ^f{x) -f{x{k+\)) > О для всех х из 
sph(x(^+l), 8, то есть из 8-окрестности точки х(^+1). 

Одним из распространенных способов вычисления множителя 
а{к) является следующий: а{к) = arg тшЯх{к) + X-S{k)\ где минимум 
берется по переменной^. 

Это означает, что точка x(yt+l) определяется как минимум функции/х) в направлении S{k). При этом используется один из способов 
поиска минимума функции одной переменной, а конкретное значение а{к) в алгоритме не используется. Указанный поиск называется 
одномерным поиском в заданном направлении. 

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

1.5. Методы одномерного поиска в заданном направлении 

Классические методы одномерного поиска предполагают, что 
указанная выше функция от X имеет единственный экстремум в направлении S{k). Для любого алгоритма поиска выбирается некоторая 
начальная точка х(0) и задается так называемый шаг грубого поиска 
h. (Значение h обычно на порядок больше, чем заданная точность 
одномерного поиска е..) Затем определяется Лх(0)), вычисляется новая точка х(1) =х(0) + h-S{k) иЛх(1)). 

Если 
Лх(1))<Лх(0)), 
то 
определяется 
следующая 
точка 
х{к+\)-х{к) 
+ h-S{k) и так далее, пока не будет выполнено условие 
Мк+\))>ЛАК)). 
Затем производится так называемая фиксация области минимума. Очевидно, что в общем случае минимум должен 
находиться между точками х{к+\) и х{к-1). Обозначим а = х{к+\) и 
b = х(к- 1), где а и й - концы отрезка, содержащего минимум. 

Если при первом шаге оказалось, что Хх(1)) >Хх(0)), то делается 
обратный шаг: х (I) -х(0) - h-S(0). Если при э т о м / х (1)) >Хх(0)), 
топрисваиваетсяа=х(1),й=х(1). 

Если жеЛх(1))<Лх(0)), делается замена Л = -Л и производится 
процедура поиска области минимума, как указано выше. 

11 

Далее действует алгоритм точного поиска на отрезке [а, Ы 
Большинство методов точного поиска основано на следующем 
правиле: на отрезке [а, Ь\ помещаются две точки, симметричные относительно его середины. Назовем левую точку с, а правую точкус/.ВычислимДс)иДсО(рис.1.5). 

*-z 

Рис. 1.5. Возможное положение минимума на отрезке {а,Щ 

Из рис. 1.5 видно, что дальнейшая локализация области минимума 
может быть сделана по следующему алгоритму: 

-еслиДс)<ДсО,то6 = с/; 
-еслиДс)>ДсО,тоа = с; 
-еслиДс)=ДсО,тоа = с,6 = с/. 
Полученный в результате новый отрезок [а,Ь] подвергается той 
же операции. Останов указанного цикла происходит при условии ||6-а|| < s,. 

После этого минимум фиксируется в точке х = (а + Ь) / 2. 
Конкретные алгоритмы поиска различаются способом задания точек с и d. Ниже приведены два типа алгоритмов. 

Метод «золотого сечения» 
Если обозначить длину отрезка [а,Ь] L, а длину отрезка 
[а,с]-т, 
то отрезок [а, Ь] делится в отношении 

т 
_L-m 

L-m 
L 

12 

Отсюда, поскольку m<L, следует: ш = L(3 - Vs)/2 » 0,382L . 
Т о г д а ^ - т = 0,618^. 

Поэтому расчет точек с и d производится по формулам 

с = а + 0,382(й- а), 
t/ = а + 0,618 (й-а). 

Напомним, что все переменные здесь - векторы. 
Метод дихотомии 
Выбирается некоторое число г,. Точки с и d вычисляются по 
формулам 

с = (а + й)/2-8ЛЙ-а), 
d-{a + 
b)l2+E,{b-a). 

Значение s, выбирается достаточно малым, но с тем расчетом, 
чтобы значения/с) n / J ) были различимы. 

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

1.6. Оценка производных 

В методах первого и второго порядка требуется оценка соответствующих частных производных. 

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

Линейная оценка производных первого порядка производится 
следующим образом. Если задана некоторая точка х{к), то вначале 
нужно вычислить ЛХ(У1)). Затем по каждой из компонент вектора х 
делается пробный шаг х,{к) ^ х,{к) + Ъ^ , х,(к) ^ х,(к) + 5^, гт 8, достаточно малое число. Затем вычисляются значения функции в 
пробных точках: f(x,(k),x,(k)) 
и f(x,(k),x,(k)). 
Оценки производных вычисляются по формулам 

df(x(k)) 
f(x^{k),x^{k))-f{x(k)) 

13 

df(x(k)) 
f(x^(k),X2(k))-f(x(k)) 

Квадратичная аппроксимация делается путем замены функции/х) 
параболой, коэффициенты которой определяются через значения 
функции в трех пробных точках. По полученным коэффициентам записывается выражение для соответствующей частной производной. 

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

Контрольные вопросы 

1. Чем отличаются целевые функции в динамической и статической 
задачах оптимизации? 

2. Что такое линия уровня функции? 
3. Каким образом условия существования минимума реализуются в 
алгоритме поиска минимума? 

4. Каковы основные операции в алгоритме поиска минимума функции? 

5. Опишите процедуру одномерного поиска минимума методом 
«золотого сечения». 

6. С какой целью в методе «золотого сечения» используется грубый 
шаг? 

7. Почему этот поиск называется одномерным? 
8. Как описать в программе процедуру деления отрезка [а,Ь]1 
9. Какие методы численной оценки производных вы знаете? 
10. Опишите порядок действий при оценке производных первого порядка в трехмерном пространстве переменных. 

14