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

№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