Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

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

Покупка
Артикул: 752907.01.99
Доступ онлайн
2 000 ₽
В корзину
Дается элементарное введение некоторых понятий выпуклого анализа как теоретической основы методов глобальной оптимизации. Рассматривается проблема поиска глобального решения в трех классах задач математического программирования: задачах дифференцируемой оптимизации, задачах дискретно-непрерывного программирования и задачах полубесконечного программирования. Описываются детерминированные методы решения этих задач, основанные на идеях метода ветвей и границ. Поскольку эффективность алгоритмов, основанных на методе ветвей и границ, в основном зависит от эффективности процедуры получения нижней оценки (ее точности и трудоёмкости), то большое внимание уделено алгоритмам её получения. Соответствует государственному образовательному стандарту дисциплины «Современные методы оптимизации сложных систем». Предназначено для студентов четвёртого курса специальности «Прикладная математика».
Островский, Г. М. Методы глобальной оптимизации сложных систем : учебное пособие / Г. М. Островский, Ю. М. Волин. - Москва : ИД МИСиС, 2005. - 105 с. - Текст : электронный. - URL: https://znanium.com/catalog/product/1231392 (дата обращения: 28.03.2024). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов. Для полноценной работы с документом, пожалуйста, перейдите в ридер.
Êàôåäðà èíæåíåðíîé êèáåðíåòèêè

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

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

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

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

Ìîñêâà  Èçäàòåëüñòâî «Ó×ÅÁÀ»
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
=
+ α
α >
>

Тогда

( )
(
)
( )
( )
1
1
1
1
3
x
f
k
x
f
x
x
k
x
y
+
=
+
+
−
=
α
α
.

Так как

0,            
0,
<
α >
k

то имеем

(
)
( )
3
1
3
                 
<
∈
y x
y x
x
D .

Однако 
3
x ∈ D, следовательно,

(
)
( )
( )
(
)
3
1
1
3 .
≥
=
>
f x
f x
y x
y x

Таким образом, точка 
3
3
,
(
)




x
f x
находится выше прямой (1.11), но

это противоречит предположению, что функция f(x) является выпуклой функцией. Таким образом, для частного случая теорема доказана.
Теперь рассмотрим случай, когда f(x) есть строго квазивыпуклая
функция, а область R совпадает со всем пространством X. Предположим, что точка x1 является локальным минимумом. Это означает, что
для всех точек в окрестности D выполняется неравенство (1.12).
Предположим противное, что глобальный минимум находится в другой точке 
2
x
x =
. Поэтому мы имеем

( )
(
)
1
2
f x
f x
>
.

Для точки 
1
3
x
x >
 в окрестности D на отрезке [x1, x2] имеет место
условие

f (x3) ≥ f (x1) > f (x2).

Поэтому

f (x3) ≥ max [ f (x1); f (x2)].

Но это неравенство противоречит предположению, что функция
f(x) является строго квазивыпуклой функцией, так как для строго квазивыпуклой функции должно выполняться условие (см. (1.8)

f (x3) < max [ f(x1); f(x2)].

Таким образом, локальный минимум совпадает с глобальным.

Доступ онлайн
2 000 ₽
В корзину