Методы глобальной оптимизации сложных систем

Êàôåäðà èíæåíåðíîé êèáåðíåòèêè

Ã.Ì. Îñòðîâñêèé
Þ.Ì. Âîëèí

Ìåòîäû ãëîáàëüíîé
îïòèìèçàöèè 
ñëîæíûõ ñèñòåì

Ó÷åáíîå ïîñîáèå

Ðåêîìåíäîâàíî ðåäàêöèîííî-èçäàòåëüñêèì
ñîâåòîì èíñòèòóòà

Ìîñêâà  Èçäàòåëüñòâî «Ó×ÅÁÀ»
2005

УДК 517.9
О-77

Р е ц е н з е н т
д-р техн. наук, проф., заслуженный деятель
науки РФ Л.С. Гордеев (РХТУ им. Д.И. Менделеева)

Островский Г.М., Волин Ю.М.
О-77 Методы глобальной оптимизации сложных систем: Учеб. пособие. – М.: МИСиС, 2005. – 105 с.

Дается элементарное введение некоторых понятий выпуклого анализа
как теоретической основы методов глобальной оптимизации. Рассматривается проблема поиска глобального решения в трех классах задач математического программирования: задачах дифференцируемой оптимизации, задачах дискретно-непрерывного программирования и задачах полубесконечного программирования. Описываются детерминированные методы решения этих задач, основанные на идеях метода ветвей и границ. Поскольку
эффективность  алгоритмов, основанных на методе ветвей и границ, в основном зависит от эффективности процедуры получения нижней оценки
(ее точности и трудоёмкости), то большое внимание уделено алгоритмам её
получения.
Соответствует государственному образовательному стандарту дисциплины «Современные методы оптимизации сложных систем».
Предназначено для студентов четвёртого курса специальности «Прикладная математика».

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

ОГЛАВЛЕНИЕ

Введение....................................................................................................4
1. Элементы выпуклого анализа..............................................................5
1.1. Выпуклые области, выпуклые  функции и их свойства.............5
1.2. Многогранник и его свойства.....................................................14
2. Решение задач  глобальной оптимизации ........................................28
2.1. Формулировка задачи..................................................................28
2.2. Метод ветвей и границ................................................................31
2.3. Построение выпуклых нижних оценочных функций для
некоторого класса функций...............................................................42
2.4. Конструирование выпуклых нижних оценочных функций для
произвольных функций......................................................................59
2.5. Использование метода ветвей  и границ для решения
специальных задач..............................................................................72
2.6. Метод ветвей и границ уменьшенной размерности .................74
2.7. Метод линеаризации ...................................................................78
2.8. Использование методов интервальной математики.................80
2.9. Дискретно-непрерывное нелинейное програмирование..........86
2.10. Полубесконечное программирование......................................94
Заключение..............................................................................................98
Библиографический список...................................................................99
Приложение...........................................................................................101

ВВЕДЕНИЕ

Широкое использование методов математического программирования для решения технических задач началось в 60-е годы прошлого
столетия. В настоящее время они стали важной составной частью
проектирования и планирования технологических процессов, поскольку целью любого проектирования или планирования является
получение оптимальной конструкции, режима, плана. Использование
нелинейных математических моделей создает возможность появления многоэкстремальности в задачах оптимизации. Например, проблема поиска глобального оптимума может возникнуть при оптимизации технологического процесса с множественностью стационарных состояний, в задачах проектной оптимизации с невыпуклыми
функциями капитальных затрат. Важность этой проблемы для приложений и большая трудоемкость ее решения обусловили интенсивное развитие методов решения задач глобальной оптимизации в последнее время. Если вначале развивались в основном эвристические
и стохастические методы глобальной оптимизации, часто не гарантировавшие получения глобального оптимума, то в последнее время
большой интерес вызывают детерминированные методы глобальной
оптимизации.
Мы рассмотрим здесь проблему глобальной оптимизации для трех
классов задач математического программирования: задач дифференцируемой оптимизации, задач дискретно-непрерывного программирования и задач полубесконечного программирования. Основное
внимание будет уделено первому классу задач. В настоящее время
получили большое развитие методы решения задач глобальной оптимизации, основанные на идеях метода ветвей и границ (branch and
bound method). Поэтому здесь будут рассмотрены детерминированные методы решения этих задач, основанные на этих идеях. Основная задача при использовании метода ветвей и границ состоит в разработке эффективного алгоритма получения нижней оценки (при
минимизации) целевой функции задачи оптимизации, от которого в
значительной степени зависит эффективность всего алгоритма метода ветвей и границ. Эффективность алгоритма получения нижней
оценки (границы) характеризуется, прежде всего, точностью получаемой нижней оценки и трудоемкостью ее получения. Здесь будут
рассмотрен ряд подходов к получению нижней оценки.

1. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА∗∗∗∗

1.1. Выпуклые области, выпуклые
функции и их свойства

Рассмотрим некоторую область D. Если для любой пары точек x1,
x2∈D (рис. 1.1) отрезок [x1, x2], включающий конечные точки x1, x2,
принадлежит области D, то область называется выпуклой, в противном случае она называется невыпуклой. На рис. 1.1 область D1 – невыпуклая, а область D2 – выпуклая.

x1

x2

x2

x1

D1
 D2

Рис. 1.1. Невыпуклые и выпуклые области

Дадим теперь определение выпуклой функции. Рассмотрим некоторую одномерную функцию 
( )
f x  в интервале [
,
]
L
U
x
x
. Выберем

любые две точки 
1
2
,
[
,
]
L
U
x x
x
x
∈
. Проведем прямую линию через

точки 
1
1
1
(
,
)
A
x
f
=
 
и 
2
2
2
(
,
)
A
x
f
=
такие, 
что 
1
1
(
)
f
f x
=
 
и

2
2
(
)
f
f x
=
(рис. 1.2). Уравнение этой прямой имеет вид

(
)
1
1
2
1
2
1
x
x
x
x
f
f
f
f
−
−
−
+
=
.

Представим точку внутри отрезка [x1, x2] в виде

(
)
1
2
1
,    0
1.
=
− α
+ α
≤ α ≤
x
x
x
(1.1)

Это соотношение эквивалентно соотношению

1
2
1
2
1
2
,
1.
= λ
+ λ
λ + λ ≤
x
x
x
(1.2)

____________
∗ Здесь рассматриваются некоторые элементы выпуклого анализа, которые будут использоваться при изложении методов глобальной минимизации. Детальное описание этого вопроса может быть найдено в [1].

f

x

A2

A1

x1

f2

f1

x2

Рис. 1.2. Выпуклая функция

С использованием выражения (1.1) уравнение прямой A1A2 может
быть преобразовано следующим образом:

(
)

(
) (
)

(
)
(
)

1
2
1
2
1
1
2
1

2
1
2
1
1
2
1

1
2
1
1
2

( )
1

1
,
0
1.

−


α =
+
− α
+ α
−
=


−
−
=
+
α
−
=
−

=
+
−
α =
− α
+ α
≤ α ≤

f
f
f
f
x
x
x
x
x
f
f
f
x
x
x
x

f
f
f
f
f

(1.3)

Это параметрическая форма прямой. Функция, определенная на
отрезке [xL, xU], называется выпуклой, если для любой пары x1, x2

∈[xL, xU], выполняется следующее условие:

( )
( )
1
2
;
[
,
],
≤
∀ ∈
f x
f x
x
x x
 
 (1.4)

Другими словами, функция f(x) должна лежать ниже прямой,
соединяющей точки x1 и  x2.
Подставив в (1.4) выражения для x и f из (1.2) и (1.3), получим
другую форму условия выпуклости:

(
)
(
) ( )
(
)
1
2
1
2
1
1


− α
+ α
≤
− α
+ α


f
x
x
f x
f x
, 
1
0
≤
≤ α
.
(1.5)

Функция f(x) называется строго выпуклой, если в (1.5) выполняется строгое неравенство (за исключением концевых точек)

(
)
(
) ( )
(
)
1
2
1
2
1
1
,


− α
+ α
<
− α
+ α


f
x
x
f x
f x
 
1
0
<
< α
.
(1.6)

Вогнутая функция удовлетворяет условию

(
)
(
) ( )
(
)
1
2
1
2
[ 1
]
1
,
−α
+α
≥
−α
+α
f
x
x
f x
f x
,1
0
≤
≤α
 
1
2
,
[
,
].
∀
∈
L
U
x x
x x
(1.7)

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

 
(
)
( )
(
)
1
2
1
2
[ 1
]
max[
,
],
f
x
x
f x
f x
−α
+α
≤
 0
1,
≤α≤  
1
2
,
[
,
]
∀
∈
L
U
x x
x
x
. (1.8)

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

(
)
( )
(
)
1
2
1
2
[ 1
]
min[
,
],
f
x
x
f x
f x
−α
+ α
≥
 0
1
≤α≤ , 
1
2
,
[
,
]
∀
∈
L
U
x x
x
x
. (1.9)

Функция f(x) называется строго квазивыпуклой, если в (1.8) выполняется строгое неравенство (за исключением концевых точек).
Аналогично, функция f(x) называется строго квазивогнутой, если в
(1.9) выполняется строгое неравенство (за исключением концевых
точек). Соотношения (1.5) – (1.9) верны и в n-мерном пространстве.
В этом случае x 1, x 2 – точки n-мерного пространства.
Покажем, что класс выпуклых функций включает класс квазивыпуклых функций (однако обратное неверно). Пусть функция f(x)
является выпуклой. Предположим, что

(
)
( )
2
1
f x
f x
≥
.

Для любых двух точек x1, x2 условие (1.4) выполняется, поэтому
имеем

(
)
(
) ( )
(
)
(
) (
)
(
)

(
)
( )
(
)

1
2
1
2
2
2

2
1
2

1
1
1

max
,
.

f
x
x
f x
f x
f x
f x

f x
f x
f x

α
α
α
α
α
α


−
+
≤
−
+
≤
−
+
=





=
=



Но это условие есть условие того, что функция f(x) является квазивыпуклой. Вогнутая функция может быть квазивыпуклой функцией. Капитальные затраты технического оборудования часто выражаются с помощью функции 
α
x  (где α < 1). Легко проверить, что эта
функция есть вогнутая функция.
Данные определения выпуклости, вогнутости, квазивыпуклости,
квазивогнутости, строгой выпуклости и вогнутости применимы и в
многомерном случае. Ясно, что свойство выпуклости (вогнутости)
функции зависит от области, в которой эта функция рассматривается.
 Рассмотрим теперь второе определение выпуклой функции:
Дифференцируемая функция f(x) является выпуклой, если для любой
точки x  отрезка [xL, xU] выполняется условие

( )
( )
(
)
grad
( )
,
,
[
,
]
T
L
U
f x
f x
f x
x
x
x x
x
x


≥
+
−
∀
∈


.
(1.10)

На рис. 1.3 показана геометрическая интерпретация этого условия. На этом рисунке прямая 
( )
( ) (
)
x
x
x
f
x
f
y
T
−
∇
+
=
)
(
 есть касательная к функции f(x) в точке x . Условие (1.10) означает, что в
точке x  функция f(x) должна лежать выше касательной к ней в этой
точке. Докажем, что, если выполняется условие (1.10), функция
)
(x
f
 является выпуклой.

А1

f

x
x2

f(x)

А2

х
x1

Рис. 1.3. Геометрическая интерпретация условия (1.10)

Предположим противное, т.е. что функция 
)
(x
f
 не является вы
пуклой. Это значит, что найдутся точки в интервале 
1
2
[
,
]
x x
, в которых значение функции 
)
(x
f
 будет выше прямой А1А2. Выберем среди них точку x , в которой значение функции 
)
(x
f
 находится на
наибольшем расстоянии от прямой А1А2. В этой точке касательная к
функции 
)
(x
f
будет параллельна прямой А1А2. Уравнение этой касательной имеет вид

( )
( )
(
)
grad
.
T
f x
f x
x
x
y
+ 

−
=



В некоторой окрестности D точки x  все значения функции
)
(x
f
находятся ниже касательной, т.е. выполняется условие

( )
( )
(
)
grad
( ),
.
T
f x
f x
x
x
f x
x
D
+ 

−
≤
∀ ∈



Но это условие противоречит условию (1.10). Следовательно, не
может существовать точка выше прямой А1А2.
Рассмотрим теперь третье определение выпуклой функции:
Дважды дифференцируемая функция f(x) является выпуклой в
области D, если гессиан ∇2f является положительной полуопределенной матрицей во всех точках этой области.
Разложим в ряд Тейлора функции 
)
(x
f
 в некоторой точке x ,
сохраняя члены не выше второго порядка малости.

( )
( )
(
)
(
)
( )(
)
2
0,5
=
+ ∇
−
+
−
∇
−
T
T
f x
f x
f
x
x
x
x
f x
x
x .

В соответствии с определением положительной полуопределенной матрицы имеем

(
)
( )(
)
2
0
T
x
x
f x
x
x
−
∇
−
≥
.

Таким образом,

( )
(
)
( )
0,5
T
f x
f x
f
x
x


−
+ ∇
−
=


(
)
( )(
)
2
0
T
x
x
f x
x
x
−
∇
−
≥
.

Это условие совпадает с условием (1.10). Поскольку это условие
выполняется во всех точках области D, то функции 
)
(x
f
 является
выпуклой в этой области.

Теорема 1. Пусть функция ϕ(x) является квазивыпуклой в области
D. Тогда область 
{
}
: ( )
0
=
ϕ
≤
D
x
x
 является выпуклой.

Доказательство. Возьмем две точки x1, x2 ∈ D такие, что
1
(
)
0
ϕ
≤
x
 и 
2
(
)
0
ϕ
≤
x
. В соответствии с определением квазивыпуклой
функции для любой точки отрезка [x1, x2] удовлетворяется условие

( )
( )
(
)
1
2
max
,
0.


ϕ
≤
ϕ
ϕ
≤


x
x
x

Отсюда любая точка отрезка [x1, x2] принадлежит области D. Таким образом, область D является выпуклой.

Теорема 2. 
Локальный 
минимум 
выпуклой 
или 
строго
квазивыпуклой функции f(x) в выпуклой, ограниченной области R
является глобальным минимумом в этой области.
Доказательство. Рассмотрим вначале случай, когда область R
совпадает со всем пространством X, а функция f(x) является
выпуклой (случай выпуклой, безусловной минимизации). Докажем

эту теорему для одномерной функции. Предположим, что точка A1 с
абсциссой x1 является локальным минимумом (рис. 1.4). Тогда существует окрестность D (содержащая точку A1), в которой выполняется
условие

( )
( )
1 ,               
.
≥
∀ ∈
f x
f x
x
D

B1

B2

f(x1)
f(x2)

A1
A2
x

y

Рис. 1.4. Иллюстрация к теореме 2

Докажем, что x1 есть глобальный минимум. Предположим противное, что глобальный минимум находится в другой точке А2 с абсциссой 
2
x
x =
.
Проведем прямую через точки B1 B2. Уравнение этой прямой имеет вид

(
)
( )
1
1 ,
=
−
+
y
k x
x
f x
 
(1.11)

где
0
)
(
)
(

1
2

1
2
<
−
−
=

x
x

x
f
x
f
k
.

Так как точка А1 является локальным минимумом, то около нее
существует окрестность D, в которой

( )
( )
1 ,                
.
≥
∀ ∈
f x
f x
x
D  
(1.12)

В окрестности D выберем точку 
3
x  на отрезке [x1,x2] (x3∈D).

(
)
3
1
3
1
0 ,
.
x
x
x
x
=
+ α
α >
>

Тогда