Моделирование и оптимизация систем управления. Раздел : методы оптимизации систем управления. Нелинейное программирование

№1651 

Кафедра металлургии стали 

Б.Н. Окороков, Б.Н. Валеев, И.Ю. Ермакова 

МОДЕЛИРОВАНИЕ И ОПТИМИЗАЦИЯ 
СИСТЕМ УПРАВЛЕНИЯ 

Раздел: Методы оптимизации систем управления. 
Нелинейное программирование 

Практикум 

для студентов специальностей 2102 

Рекомендован редакционно-издательским 
советом института 

МОСКВА 2001 

УДК 681.511.4:669.1 

О51 

О51 
Б.Н. Окороков, Б.Н. Валеев, И.Ю. Ермакова. Моделирование и 
оптимизация систем управления: Методы оптимизации систем 
управления. Нелинейное программирование: Практикум. – М.: 
МИСиС, 2001. – 78 с. 

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

Практикум рассчитан на самостоятельное изучение темы "Нелинейное математическое программирование" в рамках курса "Моделирование и 
оптимизация систем управления" студентами специальности  2102. 

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

СОДЕРЖАНИЕ 

Некоторые обозначения, принятые в тексте..........................................6 
1. Общие сведения....................................................................................7 
2. Этапы работы алгоритмов оптимизации..........................................12 
3. Сходимость численных методов оптимизации................................14 
4. Условия остановки (критерии окончания счета).............................16 
5. Направление убывания функционала и «методы спуска»..............17 
6. Выбор длины шага оптимизации из условия минимизации 
функционала вдоль заданного направления ...................................19 

7. Адаптивный способ отыскания коэффициентов αk, 
не требующий дополнительных вычислений 
характеристик целевой функции......................................................21 

8. Выбор длины шага..............................................................................23 

8.1 Априорный выбор коэффициентов, 
определяющих длину шага..............................................................23 

8.2. Дробление шага .................................................................................24 

9. Общие сведения и постановка задачи 
в методах нелинейного программирования....................................26 
9.1. Общая характеристика методов  
нелинейного программирования.....................................................26 

9.2. Основные понятия.............................................................................27 

9.2.1. Геометрическая интерпретация целевой функции 
и ограничений..................................................................27 

9.2.2. Особые точки и линии целевой функции......................29 
9.2.3. Глобальный и локальный оптимумы .............................31 

9.3. Краткая характеристика методов решения рассматриваемых 
задач нелинейного математического программирования ...........31 
9.3.1. Одномерная минимизация ..............................................31 
9.3.2. Градиентные методы .......................................................32 
9.3.3. Методы прямого поиска..................................................33 

10. Практические занятия для самостоятельной работы ....................35 

Практическое занятие 10.1 
Локализация экстремума функционала с одной переменной 
методом деления отрезка пополам. ................................................35 
10.1.1. Цель занятия...................................................................35 
10.1.2. Теоретическое введение................................................35 

 
3 

10.1.3. Описание алгоритма отыскания положения 
экстремума заданного функционала J(x) 
методом деления отрезка пополам ................................36 

10.1.4. Порядок выполнения задания.......................................39 
10.1.5. Содержание и объем отчета..........................................40 
10.1.6. Контрольные вопросы для самостоятельной 
подготовки .......................................................................41 

Практическое занятие 10.2 
Локализация экстремума функционала с одной переменной 
методом "золотого сечения"............................................................ 41 
10.2.1. Цель занятия...................................................................41 
10.2.2. Теоретическое введение................................................42 
10.2.3. Порядок выполнения задания.......................................45 
10.2.4. Содержание и объем отчета..........................................46 
10.2.5. Контрольные вопросы для самостоятельной 
подготовки .......................................................................47 

Практическое занятие 10.3 
Метод локализации экстремума функционала с одной переменной с 
помощью чисел Фибоначчи  
(метод Кифера – Джонсона)............................................................ 48 
10.3.1. Цель занятия...................................................................48 
10.3.2. Теоретическое введение................................................48 
10.3.3. Описание алгоритма поиска положения экстремума 
заданного функционала J(x) с использованием чисел 
Фибоначчи (метод Кифера – Джонсона)...........................49 

10.3.4. Порядок выполнения задания.......................................52 
10.3.5. Содержание и объем отчета..........................................53 
10.3.6 Контрольные вопросы для самостоятельной 
подготовки .......................................................................53 

Практическое занятие 10.4 
Локализация экстремума функционала с одной переменной 
методом поиска с обратным половинным шагом. ....................... 54 
10.4.1. Цель занятия...................................................................54 
10.4.2. Теоретическое введение................................................54 
10.4.3. Описание алгоритма определения положения 
экстремума заданного функционала J(x) методом 
поиска с обратным половинным шагом........................55 

10.4.4. Порядок выполнения задания.......................................57 
10.4.5. Содержание и объем отчета..........................................58 

 
4 

10.4.6. Контрольные вопросы для самостоятельной 
подготовки........................................................................58 

Практическое занятие 10.5 
Локализация экстремума функционала с несколькими 
переменными методом сканирования............................................59 
10.5.1. Цель занятия...................................................................59 
10.5.2. Теоретическое введение................................................59 
10.5.3. Описание алгоритма поиска положения экстремума 
заданного функционала J(x) методом сканирования. ..62 

10.5.4. Порядок выполнения задания.......................................64 
10.5.5. Содержание и объем отчета..........................................65 
10.5.6. Контрольные вопросы для самостоятельной 
подготовки........................................................................66 

Практическое занятие 10.6 
Локализация экстремума функционала с несколькими 
переменными методом градиента...................................................66 
10.6.1. Цель занятия...................................................................66 
10.6.2. Теоретическое введение................................................67 
10.6.3. Описание алгоритма поиска положения экстремума 
заданного функционала J(x) методом градиента..........71 

10.6.4. Порядок выполнения задания.......................................74 
10.6.5. Содержание и объем отчета..........................................75 
10.6.6. Контрольные вопросы для самостоятельной 
подготовки........................................................................75 

11. Рекомендуемая литература..............................................................77 

 
5 

НЕКОТОРЫЕ ОБОЗНАЧЕНИЯ, 
ПРИНЯТЫЕ В ТЕКСТЕ 

n
R – n-мерное ортогональное пространство; 
∈– знак принадлежности данному множеству или области; 

{
}
i
i
i
y
...,
,
y
,
y
,
x
...,
,
x
,
x
:
x
2
1
2
1
1
+
 – знак присвоения вектору 

x  определяемых переменных 
, составляющих данное множество {…}; 

i
i
y
y
y
x
x
x
...,
,
,
,
...,
,
,
2
1
2
1

(
)
i
i
i
y
...,
,
y
,
y
,
x
...,
,
x
,
x
x
2
1
2
1
1
+
 – зависимость данного вида 
(функциональная); 

X, U – области существования переменных или множества; 
... – знак абсолютного значения величины; 

...  – знак нормы; 

<…,…> – знак скалярного произведения; 
sup J(x) – верхняя граница целевой функции J(x); 
inf J(x) – нижняя граница целевой функции J(x); 
∀ x – для всех x. 

 
6 

1. ОБЩИЕ СВЕДЕНИЯ

∗

1.1. Среди задач оптимизации своей ролью и широтой 
спектра решаемых вопросов выделяются т.н. задачи статической 
оптимизации. К ним относятся и такие задачи, в которых значение 
целевой функции J (x) не зависит от времени. Например, расчет 
шихты для сталеплавильного процесса; определение координат 
окончания переходов в многопереходных процессах по минимуму 
целевых функций за весь процесс; решение систем линейных и 
нелинейных алгебраических уравнений численными методами; 
оценка параметров выдвигаемых гипотез при статистической обработке экспериментальных данных; экспериментальная оптимизация; решение систем дифференциальных уравнений; поиск экстремума сложных функций. 

В практикуме рассматриваются задачи оптимизации, позволяющие ознакомится с методами решения конечномерных статических задач условной оптимизации – задач нелинейного математического программирования, которые формулируются следующим образом: 

найти min J (x), 

x∈X, 

{
}
m
m
m
X
...,
,1
,0
)
(
,
,
...
,1
,0
)
(
,
:
+
=
=
=
≥
∈
=
i
x
g
i
x
g
R
x
x
i
i
n
, (1.1) 

где целевые функции J (x) и функции ограничения 
– вещественные скалярные функции. 

ig

Сразу оговорим, что решением указанных задач может быть 
min J(x); max J(x); inf J(x); sup J(x), т.е. нахождение минимума или 
максимума оптимизируемой функции, нижней или верхней границ 
функции J(x). В дальнейшем будем пользоваться операторами “min” 
и “max”, подразумевая, что при необходимости они должны быть заменены на операторы “inf” или “sup”, соответственно. 

∗ Для более глубокого изучения нелинейного программирования можно 
рекомендовать книгу Рыков А.С. Методы системного анализа: оптимизация. – М.: 
НПО«Экономика», 1999. –225с. 

 
7 

Итак, действительная скалярная функция J(x) определена на 
множестве Х n-мерного ортогонального пространства Rn. В точке x* 

функция J(x) достигает минимального значения на множестве Х, т.е. 

X
x
x
J
x
J
∈
=
)
(
min
)
(
*
. 

Требуется построить оценку x∈Rn точки х* с некоторой заданной 
погрешностью 
0
ε  
так, 
чтобы 
выполнялось 
неравенство 

0
*)
(
)
(
ε
≤
−
x
J
x
J
N
 на основе некоторого конечного числа определе
ний значений J(x), либо на основе конечного числа шагов, когда число 
вычислений функции J(x) на каждой итерации ограничено. 

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

На основании полученной информации строится приближение к решению задачи – к искомой точке минимума х*, или, если такая точка не единственная, – к множеству точек минимума. 

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

1.4. В численных методах оптимизации можно выделить три 
типа алгоритмов. 

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

Алгоритмы первого порядка – алгоритмы, использующие 
также информацию и о значениях первых производных. 

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

1.5. В нелинейном программировании наиболее часто используются следующие математические определения и утверждения. 

Скалярная функция J(x) n-мерного аргумента x называется 
дифференцируемой в точке x, если найдется такой вектор 
, 
при котором для 
 выполняется равенство 

n
R
b∈

n
R
h∈
∀

 
8 

(
)
h
O
h
b
x
J
h
x
J
+
+
=
+
,
)
(
)
(
. 
(1.3) 

Вектор b называется производной или градиентом функции 
J(x) в точке x и обозначается 
)
(
),
(
),
(
x
J
grad
x
J
x
J
∇
′
. 

Функция дифференцируема в точке x, если она допускает линейную аппроксимацию в этой точке. 

Подмножество X в Rn называется выпуклым, если 

(
)
[
]1,0
,
,
для
1
∈
λ
∈
∀
∈
⋅
λ
+
+
⋅
λ
n
R
y
x
X
y
x
. 
(1.4) 

Это определение означает, что выпуклое множество вместе с любыми двумя точками включает весь отрезок, соединяющий эти точки. 

Сумма двух множеств ∈ Rn образует также выпуклое множество. 

Пересечение любого числа выпуклых множеств – выпуклое. 

Функция J(x) называется выпуклой, если выполняется неравенство 

(
)
(
)
(
)
[
]1,0
,
,
),
(
1
)
(
1
∈
λ
∈
∀
⋅
λ
−
+
⋅
λ
≤
⋅
λ
−
+
⋅
λ
n
R
y
x
y
J
x
J
y
x
J
. (1.5) 

Функция J(x) называется строго выпуклой, если для 
 выполняется неравенство 
[
]1,0
∈
λ
∀

(
)
(
)
(
)
n
R
y
x
y
J
x
J
y
x
J
∈
∀
⋅
λ
−
+
⋅
λ
<
⋅
λ
−
+
⋅
λ
,
),
(
1
)
(
1
. 
(1.6) 

График выпуклой функции J(x) расположен ниже (точнее – 
не выше) любой своей хорды. 

Вогнутые функции удовлетворяют неравенству, обратному 
неравенству (1.6). 

Выпуклые функции обладают рядом полезных свойств: 
– если 
m
i
x
Ji
...
1
),
(
=
 – семейство выпуклых функций, а 

ci
,0
≥
 то функция 
 является выпуклой функцией; 
∑
=
⋅
=

m

i
i
i
x
J
c
x
J
1
)
(
)
(

– если 
m
i
x
Ji
...
1
),
(
=
 – выпуклые функции, то функция 
 – тоже выпуклая. 

m
i
i x
f
x
J
...
1
)
(
max
)
(
∈
=

Дифференцируемая выпуклая функция обладает следующими свойствами: 

 
9 

 
– 
n
R
h
x
x
h
x
J
x
J
h
x
J
∈
+
∀
∇
≥
−
+
,
,
),
(
)
(
)
(
, 
(1.7) 

– вторая производная функции 
)  – положительно определенная; 

(
2
x
J
∇

– выпуклая функция J(x) имеет только один минимум. 

Точка x* называется локальным максимумом J(x) на Rn, если 
найдется такое 
0
>
ε
, что 
) , x
(
)
(
,
*
x
J
x
J
D
x
≥
∈
∀
∈D, где D и ε – ок
рестность точки 
 (
*
x
{
} ε
≤
−
∈
=
*
,
:
x
x
R
x
x
D
n
). 

Точка x* называется глобальным минимумом функции J(x) на 
Rn, если для 
 выполняется неравенство 
. 
n
R
x∈
∀
)
(
)
(
*
* x
J
x
J
≥

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

Если функция J(x) сильно выпукла и непрерывна на выпуклом замкнутом множестве 
, то для 
n
R
x ∈
X
z ∈
∀
 множество 

{
X
x
x
J
X
x
x
X
}
∈
∈
=
:)
(
,
:
0
 ограничено, и существует единственная 

точка 
{
}
X
x
x
J
x
∈
=
:)
(
min
arg
*
. 

Условия существования экстремума для задач безусловной 
минимизации (
) следующие. 
n
R
x ∈

Необходимое условие минимума первого порядка. Если x* – 
точка минимума функции J(x) на пространстве Rn и J(x) дифференцируема в точке x*, то grad J(x*) = 0. 

Достаточное условие минимума первого порядка. Если J(x) – выпуклая функция, дифференцируемая в точке x* и grad J(x*) = 0, то точка x* 
– глобальный минимум J(x) на пространстве Rn. 

Необходимое условие минимума второго порядка. Если x* – 
точка минимума J(x) на Rn и J(x) дважды дифференцируема в точке x, 
то 
. 
0
)
(
*
2
≥
∇
x
J

Достаточное условие минимума второго порядка. Если 
J(x) – дважды дифференцируема и выполняется необходимое усло
 
10 

вие минимума первого порядка, а также выполняется условие 
, то x
0
)
(
*
2
≥
∇
x
J
* – точка локального минимума J(x) на Rn. 

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

Если x* – точка локального минимума функции J(x) на множестве Х, а функции J(x), gi(х), i = 1, …, m – непрерывно дифференцируемы в 
окрестности x* (условие гладкости), то, в соответствии с теоремой Кунс 
– Таккера, существует ненулевой вектор множителей Лагранжа 
, такой, что для функции Лагранжа 

выполняются условия: 

(
)
0
,
...,
,
,
1
1
0
≠
λ
∈
λ
λ
λ
=
λ
+
m
m
R

∑
=
⋅
λ
+
⋅
λ
=
λ
Λ

m

i
i
i
x
g
x
J
x
1
0
)
(
)
(
)
,
(

– стационарности 
n
j
x
x

j
...,
,1
,0
)
,
(
*
=
=
∂
λ
Λ
 или 

; 
0
)
(
grad
)
(
grad
1

*
*
0
=
⋅
λ
+
⋅
λ
∑
=

m

i
i
i
x
g
x
J

– дополняющей нежесткости 
; 
m
i
x
gi
i
...,
,1
,0
)
(
*
=
=
⋅
λ

– неотрицательности 
m
i
i
...,
,1
,0
=
≥
λ
. 

Теорема Кунс – Таккера 

1. Если x* – решение задачи выпуклого программирования, то 
найдется 
ненулевой 
вектор 
множителей 
Лагранжа 
, 
такой, 
что 
для 
функции 
Лагранжа 

выполняются условия: 

(
)
1
1
0
,...,
,
+
∈
λ
λ
λ
=
λ
m
m
R

∑
=
⋅
λ
+
⋅
λ
=
λ
Λ

m

i
i
i
x
g
x
J
x
1
0
)
(
)
(
)
,
(
 

– принципа 
минимума 
для 
функции 
Лагранжа 
; 
)
,
(
)
,
(
min
* λ
Λ
=
λ
Λ
x
x

– дополняющей нежесткости 
; 
m
i
x
gi
i
,...,
1
,0
)
(
*
=
=
⋅
λ

– неотрицательности 
m
i
i
,...,
1
,0
=
≥
λ
. 

2. Если для допустимой точки x* выполнены эти условия и 
условие Слейтера (т.е. существует точка 
, для которой 
), то x

X
x ∈
*

m
i
x
gi
...,
,1
,0
)
(
*
=
<
* – точка минимума функции от х. 

 
11 

2. ЭТАПЫ РАБОТЫ 
АЛГОРИТМОВ ОПТИМИЗАЦИИ 

Работа всех алгоритмов оптимизации включает два этапа: 
I этап – вычисление предусмотренных алгоритмом характеристик задачи; 

II этап – по полученной на I этапе информации строится приближение к решению. 

Второй этап, как правило, затруднений не вызывает, если при 
задании алгоритма указан способ выбора точек вычисления.  

Если все точки выбираются одновременно до начала вычислений, то алгоритм минимизации называется пассивным. 

Для решения большинства задач точки вычисления выбираются поочередно, т.е. точка xi+1 выбирается, когда уже выбраны точки предыдущих вычислений x1,..., xi, и в каждой из них произведены 
предусмотренные алгоритмом вычисления, результаты которых обозначаются, соответственно, через y1, y2,..., yi. Такие алгоритмы называются последовательными. 

Таким образом, траектория последовательного алгоритма определяется точкой х1∈Х и набором отображений вида 

{
}
1
,
...,
,
,
...,
,
:
1
1
1
≥
→
+
i
X
y
y
x
x
x
i
i
i
. 
(2.1) 

При этом 

(
)
i
i
i
i
y
y
x
x
x
x
...,
,
,
...,
,
1
1
1
1
+
+ =
. 
(2.2) 

На практике обычно используют наиболее простые виды этой 
зависимости, например: 

(
)
(
)
i
i
i
i
i
i
y
x
x
y
y
x
x
x
,
...,
,
,
...,
,
1
1
1
1
+
+
=
. 
(2.3) 

В этом случае выбор точки очередного вычисления зависит лишь 
от координат точки предыдущего вычисления и полученного результата: 

(
)
(
)
i
i
i
i
i
i
iy
iy
x
x
y
y
x
x
x
λ
+
+
λ
=
+
+
...
,
...,
,
,
...,
,
1
1
1
1
1
)
, 
(2.4) 

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

 
12 

В дальнейшем при описании методов минимизации мы будем 
пользоваться соотношением вида 

 
 
(2.5) 
...
2
,1
,0
,
,
1
=
∈
α
α
+
=
+
k
R
h
x
x
k
k
k
k
k

При этом конкретный алгоритм определяется заданием точки 
, правилами выбора векторов 
 и числа 
0
x
k
h
k
α  на основе полученной в результате вычислений информации, а также условием остановки процедур вычислений. 

Таким, образом, величины 
k
α , 
 точно так же, как и в 
формуле (2.2), определяются тем или иным видом функциональной 
зависимости от координат точек и результатами всех ранее проведенных вычислений. На практике используются наиболее простые 
виды зависимостей. 

k
h

Вектор 
 определяет направление (k+1)-го шага метода минимизации, коэффициент 

k
h

k
α  – длину этого шага. 

При этом следует иметь в виду, что при 
1
≠
k
h
 длина от
резка, соединяющего точки хk и хk+1, не равна 
k
α
. 

Обычно название метода минимизации определяется способом выбора 
, а его различные варианты связываются с разными 
способами выбора 

k
h

k
α . 

Наряду с термином «шаг метода» используют термин «итерация метода». 

Среди численных методов оптимизации можно условно выделить конечно-шаговые и бесконечно-шаговые методы. 

Конечно-шаговыми или конечными называются методы, гарантирующие отыскание решения задачи за конечное число шагов. 

Конечно-шаговые методы удается построить лишь для некоторых специальных типов задач оптимизации. 

 
13