Использование выпуклых продолжений функций для решения нелинейных задач оптимизации
Рассмотрены алгоритмы решения нелинейных выпуклых задач оптимизации с ограничениями, основанные на эффективной процедуре выпуклого продолжения целевой функции с допустимой области на все пространство. Особенность этих алгоритмов– их устойчивость относительно некоторых преобразований задачи, ухудшающ...
Збережено в:
| Дата: | 2010 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2010
|
| Назва видання: | Управляющие системы и машины |
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/82882 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Использование выпуклых продолжений функций для решения нелинейных задач оптимизации / Ю.П. Лаптин, А.П. Лиховид // Управляющие системы и машины. — 2010. — № 6. — С. 25-31. — Бібліогр.: 5 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-82882 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-828822025-02-09T11:53:49Z Использование выпуклых продолжений функций для решения нелинейных задач оптимизации Convex Prolongation of Functions for Solving Nonlinear Optimization Problems Використання опуклого продовження функцій для розв’язання нелінійних задач оптимізації Лаптин, Ю.П. Лиховид, А.П. Новые методы в информатике Рассмотрены алгоритмы решения нелинейных выпуклых задач оптимизации с ограничениями, основанные на эффективной процедуре выпуклого продолжения целевой функции с допустимой области на все пространство. Особенность этих алгоритмов– их устойчивость относительно некоторых преобразований задачи, ухудшающих ее масштабирование. Реализация предложенных алгоритмов обеспечивает подключение к программной среде языка AMPL, что позволяет сравнивать разработанные программные средства с существующими как коммерческими, так и не коммерческими. Приведены результаты вычислительных экспериментов. The algorithms are considered for solving nonlinear convex optimization problems with constraints, based on the efficient procedure of a convex prolongation of the objective function from the feasible set to the entire space. A distinctive feature of these algorithms is their stability with respect to certain transformations of the problem that can degrade its scaling. The implementation of the suggested algorithms provides for connection to the software environment of AMPL language, which allows to compare the developed software with the existing commercial and non commercial ones. The results of computational experiments are given. Розглянуто алгоритми розв'язання нелінійних опуклих задач оптимізації з обмеженнями, засновані на ефективній процедурі опуклого продовження цільової функції з допустимої області на весь простір. Особливість цих алгоритмів – їх стійкість щодо деяких перетворень задачі, що погіршують її масштабування. Реалізація запропонованих алгоритмів забезпечує підключення до програмного середовища мови AMPL, що дозволяє порівнювати розроблені програмні засоби з існуючими як комерційними, так і не комерційними. Наведено результати обчислювальних експериментів. 2010 Article Использование выпуклых продолжений функций для решения нелинейных задач оптимизации / Ю.П. Лаптин, А.П. Лиховид // Управляющие системы и машины. — 2010. — № 6. — С. 25-31. — Бібліогр.: 5 назв. — рос. 0130-5395 https://nasplib.isofts.kiev.ua/handle/123456789/82882 519.8 ru Управляющие системы и машины application/pdf Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Новые методы в информатике Новые методы в информатике |
| spellingShingle |
Новые методы в информатике Новые методы в информатике Лаптин, Ю.П. Лиховид, А.П. Использование выпуклых продолжений функций для решения нелинейных задач оптимизации Управляющие системы и машины |
| description |
Рассмотрены алгоритмы решения нелинейных выпуклых задач оптимизации с ограничениями, основанные на эффективной процедуре выпуклого продолжения целевой функции с допустимой области на все пространство. Особенность этих алгоритмов– их устойчивость относительно некоторых преобразований задачи, ухудшающих ее масштабирование. Реализация предложенных алгоритмов обеспечивает подключение к программной среде языка AMPL, что позволяет сравнивать разработанные программные средства с существующими как коммерческими, так и не коммерческими. Приведены результаты вычислительных экспериментов. |
| format |
Article |
| author |
Лаптин, Ю.П. Лиховид, А.П. |
| author_facet |
Лаптин, Ю.П. Лиховид, А.П. |
| author_sort |
Лаптин, Ю.П. |
| title |
Использование выпуклых продолжений функций для решения нелинейных задач оптимизации |
| title_short |
Использование выпуклых продолжений функций для решения нелинейных задач оптимизации |
| title_full |
Использование выпуклых продолжений функций для решения нелинейных задач оптимизации |
| title_fullStr |
Использование выпуклых продолжений функций для решения нелинейных задач оптимизации |
| title_full_unstemmed |
Использование выпуклых продолжений функций для решения нелинейных задач оптимизации |
| title_sort |
использование выпуклых продолжений функций для решения нелинейных задач оптимизации |
| publisher |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| publishDate |
2010 |
| topic_facet |
Новые методы в информатике |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/82882 |
| citation_txt |
Использование выпуклых продолжений функций для решения нелинейных задач оптимизации / Ю.П. Лаптин, А.П. Лиховид // Управляющие системы и машины. — 2010. — № 6. — С. 25-31. — Бібліогр.: 5 назв. — рос. |
| series |
Управляющие системы и машины |
| work_keys_str_mv |
AT laptinûp ispolʹzovanievypuklyhprodolženijfunkcijdlârešeniânelinejnyhzadačoptimizacii AT lihovidap ispolʹzovanievypuklyhprodolženijfunkcijdlârešeniânelinejnyhzadačoptimizacii AT laptinûp convexprolongationoffunctionsforsolvingnonlinearoptimizationproblems AT lihovidap convexprolongationoffunctionsforsolvingnonlinearoptimizationproblems AT laptinûp vikoristannâopuklogoprodovžennâfunkcíjdlârozvâzannânelíníjnihzadačoptimízacíí AT lihovidap vikoristannâopuklogoprodovžennâfunkcíjdlârozvâzannânelíníjnihzadačoptimízacíí |
| first_indexed |
2025-11-25T22:46:07Z |
| last_indexed |
2025-11-25T22:46:07Z |
| _version_ |
1849804213423439872 |
| fulltext |
УСиМ, 2010, № 6 25
УДК 519.8
Ю.П. Лаптин, А.П. Лиховид
Использование выпуклых продолжений функций для решения
нелинейных задач оптимизации
Рассмотрены алгоритмы решения нелинейных выпуклых задач оптимизации с ограничениями, основанные на эффективной
процедуре выпуклого продолжения целевой функции с допустимой области на все пространство. Особенность этих алгорит-
мов– их устойчивость относительно некоторых преобразований задачи, ухудшающих ее масштабирование. Реализация пред-
ложенных алгоритмов обеспечивает подключение к программной среде языка AMPL, что позволяет сравнивать разработанные
программные средства с существующими как коммерческими, так и не коммерческими. Приведены результаты вычислитель-
ных экспериментов.
The algorithms are considered for solving nonlinear convex optimization problems with constraints, based on the efficient procedure of
a convex prolongation of the objective function from the feasible set to the entire space. A distinctive feature of these algorithms is their
stability with respect to certain transformations of the problem that can degrade its scaling. The implementation of the suggested algo-
rithms provides for connection to the software environment of AMPL language, which allows to compare the developed software with
the existing commercial and non commercial ones. The results of computational experiments are given.
Розглянуто алгоритми розв'язання нелінійних опуклих задач оптимізації з обмеженнями, засновані на ефективній процедурі
опуклого продовження цільової функції з допустимої області на весь простір. Особливість цих алгоритмів – їх стійкість щодо
деяких перетворень задачі, що погіршують її масштабування. Реалізація запропонованих алгоритмів забезпечує підключення
до програмного середовища мови AMPL, що дозволяє порівнювати розроблені програмні засоби з існуючими як комерційни-
ми, так і не комерційними. Наведено результати обчислювальних експериментів.
Введение. Для решения нелинейных выпук-
лых задач оптимизации с ограничениями в [1]
предложено использовать специальное выпук-
лое продолжение целевой функции с допусти-
мой области на все пространство. Такой под-
ход особенно полезен в случае, когда целевая
функция определена на ограниченной области.
Построение выпуклого продолжения основано
на процедуре одномерного поиска, которая мо-
жет быть реализована достаточно эффективно.
Постановка задачи
Рассмотрим следующую задачу выпуклого
программирования: найти
* min ( )f f x (1)
при ограничениях
( ) 0,h x (2)
где nx R , , : nf h R R – выпуклые функ-
ции, принимающие конечные значения при
любых x .
Обозначим : ( ) 0nS x R h x . Предпо-
ложим, что S – замкнутое выпуклое множе-
Ключевые слова: выпуклое программирование, ме-
тоды оптимизации, штрафные функции, выпуклое про-
должение функций, программные средства оптимизации.
ство, задана допустимая точка 0 ,x S такая,
что 0 0.h x Для 0x x обозначим πS x
точку пересечения луча, исходящего из 0x и
проходящего через точку x, с границей множе-
ства S . Одномерный поиск для определения
πS x может быть реализован достаточно эф-
фективно.
Пусть задано некоторое число 0,E E f x ,
которое назовем параметром продолжения це-
левой функции. Положим
,S
S
x x
x E f x E
x x
(3)
, если
, если
E
E
f x x S
x
x x S
. (4)
Заметим, что если 0 0x , то величина ( )sr x
S
x
x
есть функция Минковского [3] для
множества S . Очевидно, что E x непрерыв-
ная функция. Рассмотрим задачу
inf ( ) :E E nx x R . (5)
26 УСиМ, 2010, № 6
Лемма 1. Пусть E f , тогда .E f
Доказательство очевидно, поскольку в этом
случае π 0Sf x E для всех x S .
Пусть f rS – граница множества S , x f rS ,
0
0
x x
p x
x x
. Обозначим ( , )f x p – произ-
водная функции f в точке x по направлению
p ,
' 0( ) ( ) ( , ( ))E x f x f x p x x x , (6)
inf ( ) :E E x x f rS . (7)
Теорема 1. Пусть f – выпуклая функция, S –
замкнутое выпуклое множество, S int dom f.
Тогда E – конечно и для всех *E E функ-
ция ( )E x – выпуклая.
Доказательство аналогично доказательству
теоремы 1 в работе [1] и основано на том, что в
условиях теоремы надграфик функции E x –
выпуклая коническая оболочка надграфика
функции f на множестве S .
Обозначим g f (x), gh (x) – субградиенты функ-
ций f и h в точке x .
Теорема 2. Пусть πSx x . Тогда вектор
0
0
( ) ( ( ), )
( ) ( )
( ( ), )
f
f h
h
E f x g x x x
g g x g x
g x x x
(8)
есть субградиент функции E x в точке x .
Доказательство. Рассмотрим линейные
функции ( ) ( ) ( ( ), )L ff y f x g x y x , ( )Lh y
= ( ) ( ( ), )hh x g x y x = ( ( ), )hg x y x . Положим
: ( ) 0n
L LS y R h y и рассмотрим ,L
) : ( )L Ly R S f y – надграфик функции fL
на множестве SL и выпуклую коническую обо-
лочку KL надграфика L относительно точки
0( , )Ez E x ,
( ) | 0,E E
L LΚ v z z z z . (9)
Множество ( )LΚ E есть надграфик некото-
рой выпуклой функции, которую обозначим
L y . По построению L x f x , в облас-
ти Ly S функция L y – линейна, т.е.
,L x f x g y x , где вектор g одно-
значно определяется по векторам ( )fg x , ( )hg x .
Более того, 0 0 0 0( ( )) ( ( ))E
L x x x x x x .
Поскольку надграфик функции ( )E y при-
надлежит надграфику функции ( )L y , то функ-
ция ( ) ( , )f x g y x – касательная для ( )E y ,
а вектор g – субградиент функции ( )E y во
всех точках 0 0( )y x x x .
Нетрудно проверить, что для вектора g
должны выполняться соотношения
0( ) ( , )f x g x x E , (10)
( , ) ( ( ), )fg y x g x y x (11)
для всех y таких, что
( ( ), ) 0hg x y x . (12)
Представим векторы g , fg в виде
g g g , где ( ( ), ) 0hg x g , ( )hg g x ,
f f fg g g , где ( ( ), ) 0h fg x g , ( )f hg g x ,
2
( ( ), ( ))
( )
f h
h
g x g x
g x
.
Очевидно, что из (11), (12) следует fg g ,
т.е.
2
( ( ), ( ))
( ) ( )
( )
f h
f h
h
g x g x
g g x g x
g x
.
Подставляя полученные выражения в (10),
получаем
2
( ( ), ( ))
( )
f h
h
g x g x
g x
0
0
( ) ( ( ), )
( ( ), )
f
h
E f x g x x x
g x x x
.
Откуда следует (8). Теорема доказана. ■
Замечание. Субградиент функции ( )E x ин-
вариантен относительно умножения функции
( )h x на произвольную дифференцируемую
функцию : nr R R такую, что ( ) 0,r x .nx R
Алгоритмы решения
Если величина E удовлетворяет условиям
леммы 1 и теоремы 1, то для решения задачи
(5) может применяться любой алгоритм мини-
УСиМ, 2010, № 6 27
мизации выпуклых функций. Рассмотрим слу-
чай, когда значения f
и E
неизвестны.
Пусть задан некоторый сходящийся алго-
ритм A безусловной минимизации выпуклых
функций, на каждой итерации которого вы-
числяются значение минимизируемой функ-
ции и ее субградиент.
Теорема 3. Пусть задано некоторое число
0 , значение величины E , алгоритм A при-
меняется для решения задачи (5), на итерации
k алгоритма значение функции вычисляется в
соответствии с (4), субградиент вычисляется в
соответствии с (8) и выполняются условия
( )kE f x , (13)
' 0( ) ( , ( ))k k k kE f x f x p x x x , (14)
где ( )k k
Sx x , kx – текущая точка на итера-
ции k . Тогда последовательность точек, гене-
рируемых алгоритмом A, сходится к решению
задачи (1) – (2).
Доказательство. Обозначим , 0,1,...kg k –
субградиент в точке kx , вычисляемый в со-
ответствии с (8). Рассмотрим функцию H(x) =
max ( ) ( , ) : 0,1,E k k k
k
x g x x k . Эта
функция выпукла и есть нижняя аппрокси-
мация функции ( )f x при x S . Обозначим
argmin ( ): ,nx H x x R argmin ( ): .x f x x S
Для простоты рассмотрим случай, когда x –
единственная точка минимума задачи (1) – (2).
Предположим, что утверждение теоремы не-
корректно, т.е. x x . Рассмотрим возможные
случаи – x S и x S .
x S , тогда *( ) ( ) ( ) ( ).H x f x f x H x
Это противоречит предположению о том, что
arg min ( ) : nx H x x R .
x S , тогда ( ) ( ) ( ( )EH x x E f x
0
0
)
x x
E
x x
, где ( )Sx x . В силу (13) выпол-
няется ( )f x E . Откуда ( ) ( )H x f x
( )H x , что также противоречит предположе-
нию об экстремальности точки x .
Таким образом, x x . Теорема доказана. ■
При неизвестных f
и E
необходимо уточ-
нять значение E итеративно. Рассмотрим мо-
дификацию A исходного алгоритма. Обозначим
kE значение параметра продолжения целевой
функции, используемое на итерации k , kx –
текущая точка итерации k . Пусть заданы на-
чальное значение 0E и параметры 1q , 0 ,
0B . Каждая итерация k алгоритма A со-
стоит из итерации алгоритма A , примененного
к функции E , и дополнительных действий:
1. Если kx S , полагается 1k kE E и осу-
ществляется переход к следующей итерации
алгоритма A .
2. Вычисляются в текущей точке kx кроме
значения функции E также величины E1 =
( )kf x и ' 0
2 ( ) ( , ( )) ,k k kE f x f x p x x x
1min{ ,E E 2 )E , где ( )k k
Sx x .
3. Если kE E , полагается 1k kE E и осу-
ществляется переход к следующей итерации
алгоритма A .
4. Полагается 1 max ,k k kE E q E E B ,
алгоритм A запускается из текущей точки kx
для уточненной функции E (с новым значе-
нием 0 1kE E ).
Алгоритм A завершает работу, когда сраба-
тывают критерии остановки алгоритма A .
Нетрудно видеть, что п. 4 алгоритма A вы-
полняется конечное число раз, после чего ус-
ловия (13), (14) выполняются на всех итераци-
ях, т.е. в силу теоремы 5 алгоритм сходится к
оптимальному решению. Количество срабаты-
ваний п. 4 алгоритма A зависит от величины
параметров q , B .
В рассмотренном алгоритме базовая точка x0,
относительно которой строится продолжение
функции f , считалась зафиксированной. Пер-
воначальное значение этой точки может ока-
заться неудачным, что приведет к необходимо-
сти выбора больших (по абсолютной величи-
не) значений величины E .
28 УСиМ, 2010, № 6
Рассмотрим задачу уточнения базовой точ-
ки после некоторого числа итераций алгорит-
ма. Пусть на предыдущих итерациях сгенери-
рованы точки 0, ( , ), 1,...,k k k
Sx x x x k K .
Обозначим y уточненную базовую точку. При-
мем, что y принадлежит выпуклой оболочке
точек , 1,...,kx k K .
Очевидно, что для величины E должны
выполняться следующие неравенства
( ) ( ( ), )k k k
fE f x g x x y , 1,...,k K , (15)
( ) 0kf x E , 1,...,k K . (16)
Естественно стремиться к тому, чтобы раз-
ница f E по ходу работы алгоритма не
принимала больших значений. Учитывая, что
1 1
, 0, 1
K K
k
k k k
k k
y x
, получаем, что для
выбора базовой точки y нужно решать задачу
линейного программирования: найти
,
max
E
E
(17)
при ограничениях (15), (16) и дополнительных
ограничениях
1
K
k
k
k
y x
, (18)
1
1
K
k
k
, (19)
0, 1,...,k k K . (20)
Уточнение базовой точки может проводить-
ся периодически для заданного интервала ите-
раций алгоритма или при нарушении дополни-
тельных заданных условий.
В программной реализации предлагаемого
подхода базовая точка x0 считается заданной и
не изменяется в ходе вычислений. В качестве
алгоритма безусловной минимизации исполь-
зовался r-алгоритм [3, 4], для определения
точки x (пересечения отрезка [x0, x] с грани-
цей множества S ) использовался дихотомиче-
ский поиск. Точность определения точки x
фиксирована и представляет собой параметр
алгоритма. Разработанные программные сред-
ства обеспечивают интерфейc со стандартной
программной средой AMPL [5]. Это позволяет
в ходе вычислительного эксперимента провес-
ти сравнение с самыми разными современны-
ми солверами.
Результаты вычислительных экспери-
ментов
Цель вычислительного эксперимента:
– сравнение метода негладких штрафов, ис-
пользующего r-алгоритм, и предлагаемого под-
хода на задачах, функции которых определены
на всем пространстве nR ;
– сравнение методов негладкой оптимиза-
ции и различных современных солверов на
плохо обусловленных задачах, в которых до-
пустимые множества выпуклые, но описыва-
ются невыпуклыми функциями;
– сравнение предлагаемого подхода и раз-
личных современных солверов на задачах, функ-
ции которых определены на ограниченных мно-
жествах.
Вычислительный эксперимент проводился
на тестовых задачах, сформированных на ос-
нове базовых задач вида: найти
0min ( )f f x (21)
при ограничениях
( ) 0, 1,...,kf x k m , (22)
где 1 2( , ,..., )nx x x x , m n .
Тестовые задачи формировались путем за-
мены ограничений вида (22) на
0 1( ) ( ) ( ) 0, 1,...,k k kx x f x k m , (23)
где 0 1( ) 0, ( ) 0, 1,...,k kx x k m (допустимое
множество задачи при этом не изменяется),
2
0 1
1
, 1,...,
( )
1, 1,...,
k
x x k m
x
k m m
,
1 2( ) sin ( ) , 1,...,k k kx x x k m ,
α 1 , 0 . Здесь 1 [ / 2]m m , x – оптималь-
ное решение базовой задачи, ,k kx x – k-е ком-
поненты векторов ,x x .
Целевая функция заменялась на следующую:
УСиМ, 2010, № 6 29
0
0
( ), если ( ) :
1,..., ,
( )
max{ ( ) : 1,..., },
в противном случае,
k
k
f x f x
k m
f x
f x k m
(24)
где ε 0 . В допустимой области : 0 ( )f x и
0 ( )f x совпадают, вне допустимой области при
ε 0 функция 0 ( )f x не определена.
Заметим, что при α 1 , 0 , γ 0 , ε
тестовая задача совпадает с базовой задачей
(21), (22), при α 1 , 0 , 0 , ε тесто-
вая задача имеет вырожденное масштабирова-
ние в окрестности оптимального решения, при
α 1 , 0 , малой величине штрафная функ-
ция тестовой задачи становится многоэкстре-
мальной.
Базовая задача 1. Найти
min ( , )f c x (25)
при ограничениях
1
0, 1,...,
n
i j
j
x x i n
n
, (26)
где 1 , 0, 1,...,
10i
i
c i n .
Допустимое множество есть конус, содер-
жащий вектор (1,..., 1) . При 1 конус выро-
ждается в луч, порожденный вектором (1,..., 1) .
Базовая точка 0 1, ,1x .
Решение – 0, 0x f .
Базовая задача 2. Найти
0min ( ) : nf f x x R (27)
где 0 ( ) max ( ) : 1, ,kf x f x k n , ( )kf x
2
1
( )
n
k
i i
i
x x
, 1( ,..., )k k k
nx x x – заданные точ-
ки, 1,...,k n . Здесь 0, если k
ix i k , 1,k
ix
если i k , 1,..., , 1,...,k n i n .
Эквивалентная постановка
min Y (28)
при ограничениях
( ) 0, 1, ,kf x Y k n . (29)
Базовая точка 0 (1, 0,..., 0)x , 0 2y . Реше-
ние –
1 1 1
,..., ,
n
x f y
n n n
.
Базовая задача 3. Найти
22 2
( , )
min
( , ) ( , )x
p x
f
p x x x p p
(30)
при ограничениях
22 2 2( , ) ( , ) , np x x x p p x R , (31)
( , ) 0, np x x R , (32)
где p – заданный вектор, 1p , 1 ,ip n
1,...,i n , 0 , 0 – заданные числа.
Норма градиента целевой функции на границе
допустимого множества при 0 равна .
Базовая точка x0 выбиралась с некоторым
смещением от луча, порожденного вектором р.
Если x – оптимальное решение, то x pt ,
где t R . Откуда ( , )p x t , t . Реше-
ние – , 1x p f
.
Все тестовые задачи реализованы в языке
AMPL и при сравнении с существующими сол-
верами решены на сервере NEOS (http://www-
neos.mcs.anl.gov/). Число переменных во всех
задачах (размерность вектора x ) равно 50. В ка-
честве начальной точки для всех солверов ис-
пользована базовая точка x0. Для метода выпук-
лых продолжений и метода негладких штраф-
ных функций использованы одинаковые пара-
метры r -алгоритма [3, 4]. Для всех солверов
использованы стандартные настройки. Резуль-
таты вычислительных экспериментов приведе-
ны далее. Если солвер не смог решить теку-
щую задачу или полученное решение наруша-
ет ограничения задачи, то вместо значения це-
левой функции ставится символ F (fail).
В табл. 1–4 приведены результаты вычисли-
тельных экспериментов по базовой задаче 1.
В табл. 1 сравниваются методы выпуклых
продолжений и негладких штрафных функций.
Для 1,10 и 1,05 штрафная функция не
30 УСиМ, 2010, № 6
ограничена снизу. Это связано с необходимо-
стью подбирать штрафной коэффициент инди-
видуально для каждой задачи. Метод выпук-
лых продолжений обеспечивает несколько бо-
лее высокую точность по целевой функции и
меньшее число вызовов функции в r-алгорит-
ме, чем метод негладких штрафных функций.
Каждый вызов при этом – существенно более
трудоемкая процедура, поскольку решается за-
дача одномерного поиска.
Т а б л и ц а 1. Сравнение метода выпуклых продолжений и
метода негладких штрафных функций в задаче
1, = 1,1, = 0, = 0, = 1e16, = 0,001.
Штрафной коэффициент – 1000
Метод
Рекордное зна-
чение целевой
функции
Число вызовов
функции
Выпуклое продолжение 0,0006658 875
1,50
Негладкие штрафы 0,0010041 1259
Выпуклое продолжение 0,0004572 922
1,45
Негладкие штрафы 0,0010863 1188
Выпуклое продолжение 0,0015920 990
1,40
Негладкие штрафы 0,0026862 959
Выпуклое продолжение 0,0015888 827
1,35
Негладкие штрафы 0,0023529 1037
Выпуклое продолжение 0,0009020 994
1,30
Негладкие штрафы 0,0023775 1036
Выпуклое продолжение 0,0011574 1098
1,25
Негладкие штрафы 0,0066865 1018
Выпуклое продолжение 0,0011774 1096
1,20
Негладкие штрафы 0,0011554 1045
Выпуклое продолжение 0,0068407 882
1,15
Негладкие штрафы 0,0027255 1044
Выпуклое продолжение 0,0080652 992
1,10
Негладкие штрафы F 668
Выпуклое продолжение 0,0026539 1162
1,05
Негладкие штрафы F 461
В табл. 2 сравниваются различные солверы
в задаче, имеющей вырожденность масштабиро-
вания в оптимальной точке. При отрицательных
все программные средства, кроме метода
выпуклых продолжений, находят некоррект-
ные решения. При положительных различия
в решениях, найденных различными солвера-
ми, не столь существенны.
В табл. 3 приведены результаты сравнения
различных солверов в задаче, где к вырожден-
ности масштабирования в оптимальной точке
добавлена ограниченность области определения
целевой функции.
Т а б л и ц а 2. Сравнение различных солверов (рекордное зна-
чение целевой функции) в задаче 1, = 1,1,
= 0, = 1e16, = 1e–16, = 1,1, штрафной
коэффициент – 1000 (вырожденность масшта-
бирования в точке x*)
SNOPT MINOS LOQO
Выпуклое
продолже-
ние
Неглад-
кие
штрафы
–3 F F F 0,8031 F
–2,5 F F F 0,4629 F
–2 F F F 0,2354 F
–1,5 F F F 0,0856 F
–1 F F F 0,01468 F
–0,5 F F F 0,0078 0,0199
0 0 0 0 0,0080 F
0,5 0,0104 0,00006 F 0,0017 F
1 0,2359 0,0258 F 0,0206 F
1,5 0,8902 0,1621 F 0,0899 F
2 1,6615 0,6147 F 0,2741 F
2,5 F 11,1109 F 0,5577 F
3 3,1324 F F 0,9132 F
Т а б л и ц а 3. Сравнение различных солверов (рекордное зна-
чение целевой функции) в задаче 1, = 1,1,
= 0, = 0,00001, = 1e–16, = 1,1 (вырожден-
ность масштабирования в точке x*, ограничен-
ность области определения целевой функции)
SNOPT MINOS LOQO
Выпуклое
продолжение
0,0 0,0000 0,0000 F 0,0080
0,5 0,0104 0,00006 F 0,0017
1,0 0,2359 F F 0,0206
1,5 1,0088 F F 0,0899
2,0 1,6615 F F 0,2741
2,5 1,2714 F 2,7193 0,5577
3,0 F F 4,646 0,9132
Результаты сравнения солверов в задачах,
содержащих осциллирующий множитель в
функции ограничений (табл. 4) также пока-
зывают преимущества метода выпуклых про-
должений.
Т а б л и ц а 4. Сравнение солверов (рекордное значение це-
левой функции) в задаче 1, = 1,1, = 0,
= 1e16, = 1e–16, = 1,15 (осциллирующий
множитель в функции ограничений)
SNOPT MINOS LOQO
Выпуклое
продолжение
Негладкие
штрафы
0 0 0 0 0,0068 0,0027
1 F F F 0,0816 F
2 F F F 0,1210 F
3 F F F 0,1326 F
4 F F F 0,1714 F
5 36,74 F F 0,1497 F
УСиМ, 2010, № 6 31
Результаты экспериментов по базовой зада-
че 2 аналогичны результатам по задаче 1 и по-
этому не приводятся.
Базовая задача 3 подбиралась как задача
трудная для метода выпуклых продолжений.
Результаты приведены в табл. 5. Метод выпук-
лых продолжений оказался более устойчивым
для плохо обусловленных задач.
Т а б л и ц а 5. Значения целевой функции, полученные раз-
личными солверами в зависимости от значений
и ( = 0,02)
Оптимальное
значение
SNOPT LOQO
Выпуклое
продолжение
= 0,00003
0, 0010 0,66567 0,9847087 94,3125 0,66567
0,0008 0,53253 0,533591 73,7437 0,53253
0,0006 0,39940 0,407735 56,6526 0,39940
0,0004 0,26627 0,279845 37,3732 0,26627
= 0,00002
0,0010 0,99900 1,01032 141,701 0,99900
0,0008 0,79920 0,80177 112,036 0,79920
0,0006 0,59940 0,69740 84,389 0,59940
0,0004 0,39960 0,40417 54,478 0,39960
0,0002 0,19980 0,26016 27,622 0,19980
Заключение. Использования выпуклых про-
должений функций позволяет строить эффек-
тивные алгоритмы для решения нелинейных вы-
пуклых задач оптимизации с ограничениями.
Сравнительный вычислительный анализ пока-
зал существенную устойчивость разработанно-
го подхода к плохой обусловленности задач.
Использованные тестовые задачи и предвари-
тельная версия программных средств размеще-
ны для свободного доступа на сайте http://elis.
dvo.ru/sites/default/files/OptimiZone/software/ndo
-icyb/index.html. Замечания просим направлять
по адресам – laptin_yu_p@mail.ru, o.lykhovyd@
gmail.com.
1. Лаптин Ю.П. Один подход к решению нелинейных
задач оптимизации с ограничениями // Кибернети-
ка и системный анализ. –2009. – № 3. – С. 182–187.
2. Пшеничный Б.Н. Выпуклый анализ и экстремаль-
ные задачи. – М.: Наука, 1980. – 319 с.
3. Шор Н.З. Методы минимизации недифференци-
руемых функций и их приложения. – Киев: Науко-
ва думка, 1979. – 199 c.
4. Шор Н.З., Журбенко Н.Г. Метод минимизации, ис-
пользующий операцию растяжения пространства в
направлении разности двух последовательных гра-
диентов // Кибернетика. – 1971. – № 3. – C. 51–59.
5. Fourer R., Gay D.M., Kernighan B.W. AMPL – a
Modeling Language for Mathematical Programming. –
Brooks/Cole – Thomson Learning, 2003 – 517 p.
Поступила 29.07.2010
Тел. для справок: (044) 526-2168, 451-6022 (Киев)
E-mail: laptin_yu_p@mail.ru, o.lykhovyd@gmail.com
© Ю.П. Лаптин, А.П. Лиховид, 2010
Внимание !
Оформление подписки для желающих
опубликовать статьи в нашем журнале обязательно.
В розничную продажу журнал не поступает.
Подписной индекс 71008
<<
/ASCII85EncodePages false
/AllowTransparency false
/AutoPositionEPSFiles true
/AutoRotatePages /None
/Binding /Left
/CalGrayProfile (Dot Gain 20%)
/CalRGBProfile (sRGB IEC61966-2.1)
/CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2)
/sRGBProfile (sRGB IEC61966-2.1)
/CannotEmbedFontPolicy /Error
/CompatibilityLevel 1.4
/CompressObjects /Tags
/CompressPages true
/ConvertImagesToIndexed true
/PassThroughJPEGImages true
/CreateJobTicket false
/DefaultRenderingIntent /Default
/DetectBlends true
/DetectCurves 0.0000
/ColorConversionStrategy /CMYK
/DoThumbnails false
/EmbedAllFonts true
/EmbedOpenType false
/ParseICCProfilesInComments true
/EmbedJobOptions true
/DSCReportingLevel 0
/EmitDSCWarnings false
/EndPage -1
/ImageMemory 1048576
/LockDistillerParams false
/MaxSubsetPct 100
/Optimize true
/OPM 1
/ParseDSCComments true
/ParseDSCCommentsForDocInfo true
/PreserveCopyPage true
/PreserveDICMYKValues true
/PreserveEPSInfo true
/PreserveFlatness true
/PreserveHalftoneInfo false
/PreserveOPIComments true
/PreserveOverprintSettings true
/StartPage 1
/SubsetFonts true
/TransferFunctionInfo /Apply
/UCRandBGInfo /Preserve
/UsePrologue false
/ColorSettingsFile ()
/AlwaysEmbed [ true
]
/NeverEmbed [ true
]
/AntiAliasColorImages false
/CropColorImages true
/ColorImageMinResolution 300
/ColorImageMinResolutionPolicy /OK
/DownsampleColorImages true
/ColorImageDownsampleType /Bicubic
/ColorImageResolution 300
/ColorImageDepth -1
/ColorImageMinDownsampleDepth 1
/ColorImageDownsampleThreshold 1.50000
/EncodeColorImages true
/ColorImageFilter /DCTEncode
/AutoFilterColorImages true
/ColorImageAutoFilterStrategy /JPEG
/ColorACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/ColorImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000ColorACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000ColorImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasGrayImages false
/CropGrayImages true
/GrayImageMinResolution 300
/GrayImageMinResolutionPolicy /OK
/DownsampleGrayImages true
/GrayImageDownsampleType /Bicubic
/GrayImageResolution 300
/GrayImageDepth -1
/GrayImageMinDownsampleDepth 2
/GrayImageDownsampleThreshold 1.50000
/EncodeGrayImages true
/GrayImageFilter /DCTEncode
/AutoFilterGrayImages true
/GrayImageAutoFilterStrategy /JPEG
/GrayACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/GrayImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000GrayACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000GrayImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasMonoImages false
/CropMonoImages true
/MonoImageMinResolution 1200
/MonoImageMinResolutionPolicy /OK
/DownsampleMonoImages true
/MonoImageDownsampleType /Bicubic
/MonoImageResolution 1200
/MonoImageDepth -1
/MonoImageDownsampleThreshold 1.50000
/EncodeMonoImages true
/MonoImageFilter /CCITTFaxEncode
/MonoImageDict <<
/K -1
>>
/AllowPSXObjects false
/CheckCompliance [
/None
]
/PDFX1aCheck false
/PDFX3Check false
/PDFXCompliantPDFOnly false
/PDFXNoTrimBoxError true
/PDFXTrimBoxToMediaBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXSetBleedBoxToMediaBox true
/PDFXBleedBoxToTrimBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXOutputIntentProfile ()
/PDFXOutputConditionIdentifier ()
/PDFXOutputCondition ()
/PDFXRegistryName ()
/PDFXTrapped /False
/CreateJDFFile false
/Description <<
/ARA <FEFF06270633062A062E062F0645002006470630064700200627064406250639062F0627062F0627062A002006440625064606340627062100200648062B062706260642002000410064006F00620065002000500044004600200645062A064806270641064206290020064406440637062806270639062900200641064A00200627064406450637062706280639002006300627062A0020062F0631062C0627062A002006270644062C0648062F0629002006270644063906270644064A0629061B0020064A06450643064600200641062A062D00200648062B0627062606420020005000440046002006270644064506460634062306290020062806270633062A062E062F062706450020004100630072006F0062006100740020064800410064006F006200650020005200650061006400650072002006250635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E0635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E>
/BGR <FEFF04180437043f043e043b043704320430043904420435002004420435043704380020043d0430044104420440043e0439043a0438002c00200437043000200434043000200441044a0437043404300432043004420435002000410064006f00620065002000500044004600200434043e043a0443043c0435043d04420438002c0020043c0430043a04410438043c0430043b043d043e0020043f044004380433043e04340435043d04380020043704300020043204380441043e043a043e043a0430044704350441044204320435043d0020043f04350447043004420020043704300020043f044004350434043f0435044704300442043d04300020043f043e04340433043e0442043e0432043a0430002e002000200421044a04370434043004340435043d043804420435002000500044004600200434043e043a0443043c0435043d044204380020043c043e0433043004420020043404300020044104350020043e0442043204300440044f0442002004410020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200441043b0435043404320430044904380020043204350440044104380438002e>
/CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e9ad88d2891cf76845370524d53705237300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002>
/CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc9ad854c18cea76845370524d5370523786557406300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002>
/CZE <FEFF005400610074006f0020006e006100730074006100760065006e00ed00200070006f0075017e0069006a007400650020006b0020007600790074007600e101590065006e00ed00200064006f006b0075006d0065006e0074016f002000410064006f006200650020005000440046002c0020006b00740065007200e90020007300650020006e0065006a006c00e90070006500200068006f006400ed002000700072006f0020006b00760061006c00690074006e00ed0020007400690073006b00200061002000700072006500700072006500730073002e002000200056007900740076006f01590065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f007400650076015900ed007400200076002000700072006f006700720061006d0065006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076011b006a016100ed00630068002e>
/DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000620065006400730074002000650067006e006500720020007300690067002000740069006c002000700072006500700072006500730073002d007500640073006b007200690076006e0069006e00670020006100660020006800f8006a0020006b00760061006c0069007400650074002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e>
/DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200076006f006e002000640065006e0065006e002000530069006500200068006f006300680077006500720074006900670065002000500072006500700072006500730073002d0044007200750063006b0065002000650072007a0065007500670065006e0020006d00f60063006800740065006e002e002000450072007300740065006c006c007400650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000410064006f00620065002000520065006100640065007200200035002e00300020006f0064006500720020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e>
/ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f00730020005000440046002000640065002000410064006f0062006500200061006400650063007500610064006f00730020007000610072006100200069006d0070007200650073006900f3006e0020007000720065002d0065006400690074006f007200690061006c00200064006500200061006c00740061002000630061006c0069006400610064002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e>
/ETI <FEFF004b00610073007500740061006700650020006e0065006900640020007300e4007400740065006900640020006b00760061006c006900740065006500740073006500200074007200fc006b006900650065006c007300650020007000720069006e00740069006d0069007300650020006a0061006f006b007300200073006f00620069006c0069006b0065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740069006400650020006c006f006f006d006900730065006b0073002e00200020004c006f006f0064007500640020005000440046002d0064006f006b0075006d0065006e00740065002000730061006100740065002000610076006100640061002000700072006f006700720061006d006d006900640065006700610020004100630072006f0062006100740020006e0069006e0067002000410064006f00620065002000520065006100640065007200200035002e00300020006a00610020007500750065006d006100740065002000760065007200730069006f006f006e00690064006500670061002e000d000a>
/FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f0075007200200075006e00650020007100750061006c0069007400e90020006400270069006d007000720065007300730069006f006e00200070007200e9007000720065007300730065002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e>
/GRE <FEFF03a703c103b703c303b903bc03bf03c003bf03b903ae03c303c403b5002003b103c503c403ad03c2002003c403b903c2002003c103c503b803bc03af03c303b503b903c2002003b303b903b1002003bd03b1002003b403b703bc03b903bf03c503c103b303ae03c303b503c403b5002003ad03b303b303c103b103c603b1002000410064006f006200650020005000440046002003c003bf03c5002003b503af03bd03b103b9002003ba03b103c42019002003b503be03bf03c703ae03bd002003ba03b103c403ac03bb03bb03b703bb03b1002003b303b903b1002003c003c103bf002d03b503ba03c403c503c003c903c403b903ba03ad03c2002003b503c103b303b103c303af03b503c2002003c503c803b703bb03ae03c2002003c003bf03b903cc03c403b703c403b103c2002e0020002003a403b10020005000440046002003ad03b303b303c103b103c603b1002003c003bf03c5002003ad03c703b503c403b5002003b403b703bc03b903bf03c503c103b303ae03c303b503b9002003bc03c003bf03c103bf03cd03bd002003bd03b1002003b103bd03bf03b903c703c403bf03cd03bd002003bc03b5002003c403bf0020004100630072006f006200610074002c002003c403bf002000410064006f00620065002000520065006100640065007200200035002e0030002003ba03b103b9002003bc03b503c403b103b303b503bd03ad03c303c403b503c103b503c2002003b503ba03b403cc03c303b503b903c2002e>
/HEB <FEFF05D405E905EA05DE05E905D5002005D105D405D205D305E805D505EA002005D005DC05D4002005DB05D305D9002005DC05D905E605D505E8002005DE05E105DE05DB05D9002000410064006F006200650020005000440046002005D405DE05D505EA05D005DE05D905DD002005DC05D405D305E405E105EA002005E705D305DD002D05D305E405D505E1002005D005D905DB05D505EA05D905EA002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E05D005DE05D905DD002005DC002D005000440046002F0058002D0033002C002005E205D905D905E005D5002005D105DE05D305E805D905DA002005DC05DE05E905EA05DE05E9002005E905DC0020004100630072006F006200610074002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E>
/HRV (Za stvaranje Adobe PDF dokumenata najpogodnijih za visokokvalitetni ispis prije tiskanja koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.)
/HUN <FEFF004b0069007600e1006c00f30020006d0069006e0151007300e9006701710020006e0079006f006d00640061006900200065006c0151006b00e90073007a00ed007401510020006e0079006f006d00740061007400e100730068006f007a0020006c006500670069006e006b00e1006200620020006d0065006700660065006c0065006c0151002000410064006f00620065002000500044004600200064006f006b0075006d0065006e00740075006d006f006b0061007400200065007a0065006b006b0065006c0020006100200062006500e1006c006c00ed007400e10073006f006b006b0061006c0020006b00e90073007a00ed0074006800650074002e0020002000410020006c00e90074007200650068006f007a006f00740074002000500044004600200064006f006b0075006d0065006e00740075006d006f006b00200061007a0020004100630072006f006200610074002000e9007300200061007a002000410064006f00620065002000520065006100640065007200200035002e0030002c0020007600610067007900200061007a002000610074007400f3006c0020006b00e9007301510062006200690020007600650072007a006900f3006b006b0061006c0020006e00790069007400680061007400f3006b0020006d00650067002e>
/ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f00620065002000500044004600200070006900f900200061006400610074007400690020006100200075006e00610020007000720065007300740061006d0070006100200064006900200061006c007400610020007100750061006c0069007400e0002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e>
/JPN <FEFF9ad854c18cea306a30d730ea30d730ec30b951fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a306b306f30d530a930f330c8306e57cb30818fbc307f304c5fc59808306730593002>
/KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020ace0d488c9c80020c2dcd5d80020c778c1c4c5d00020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e>
/LTH <FEFF004e006100750064006f006b0069007400650020016100690075006f007300200070006100720061006d006500740072007500730020006e006f0072011700640061006d00690020006b0075007200740069002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b00750072006900650020006c0061006200690061007500730069006100690020007000720069007400610069006b007900740069002000610075006b01610074006f00730020006b006f006b007900620117007300200070006100720065006e006700740069006e00690061006d00200073007000610075007300640069006e0069006d00750069002e0020002000530075006b0075007200740069002000500044004600200064006f006b0075006d0065006e007400610069002000670061006c006900200062016b007400690020006100740069006400610072006f006d00690020004100630072006f006200610074002000690072002000410064006f00620065002000520065006100640065007200200035002e0030002000610072002000760117006c00650073006e0117006d00690073002000760065007200730069006a006f006d00690073002e>
/LVI <FEFF0049007a006d0061006e0074006f006a00690065007400200161006f00730020006900650073007400610074012b006a0075006d00750073002c0020006c0061006900200076006500690064006f00740075002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006100730020006900720020012b00700061016100690020007000690065006d01130072006f00740069002000610075006700730074006100730020006b00760061006c0069007401010074006500730020007000690072006d007300690065007300700069006501610061006e006100730020006400720075006b00610069002e00200049007a0076006500690064006f006a006900650074002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006f002000760061007200200061007400760113007200740020006100720020004100630072006f00620061007400200075006e002000410064006f00620065002000520065006100640065007200200035002e0030002c0020006b0101002000610072012b00200074006f0020006a00610075006e0101006b0101006d002000760065007200730069006a0101006d002e>
/NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.)
/NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d00200065007200200062006500730074002000650067006e0065007400200066006f00720020006600f80072007400720079006b006b0073007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e>
/POL <FEFF0055007300740061007700690065006e0069006100200064006f002000740077006f0072007a0065006e0069006100200064006f006b0075006d0065006e007400f300770020005000440046002000700072007a0065007a006e00610063007a006f006e00790063006800200064006f002000770079006400720075006b00f30077002000770020007700790073006f006b00690065006a0020006a0061006b006f015b00630069002e002000200044006f006b0075006d0065006e0074007900200050004400460020006d006f017c006e00610020006f007400770069006500720061010700200077002000700072006f006700720061006d006900650020004100630072006f00620061007400200069002000410064006f00620065002000520065006100640065007200200035002e0030002000690020006e006f00770073007a0079006d002e>
/PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020006d00610069007300200061006400650071007500610064006f00730020007000610072006100200070007200e9002d0069006d0070007200650073007300f50065007300200064006500200061006c007400610020007100750061006c00690064006100640065002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e>
/RUM <FEFF005500740069006c0069007a00610163006900200061006300650073007400650020007300650074010300720069002000700065006e007400720075002000610020006300720065006100200064006f00630075006d0065006e00740065002000410064006f006200650020005000440046002000610064006500630076006100740065002000700065006e0074007200750020007400690070010300720069007200650061002000700072006500700072006500730073002000640065002000630061006c006900740061007400650020007300750070006500720069006f006100720103002e002000200044006f00630075006d0065006e00740065006c00650020005000440046002000630072006500610074006500200070006f00740020006600690020006400650073006300680069007300650020006300750020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e00300020015f00690020007600650072007300690075006e0069006c006500200075006c0074006500720069006f006100720065002e>
/RUS <FEFF04180441043f043e043b044c04370443043904420435002004340430043d043d044b04350020043d0430044104420440043e0439043a043800200434043b044f00200441043e043704340430043d0438044f00200434043e043a0443043c0435043d0442043e0432002000410064006f006200650020005000440046002c0020043c0430043a04410438043c0430043b044c043d043e0020043f043e04340445043e0434044f04490438044500200434043b044f00200432044b0441043e043a043e043a0430044704350441044204320435043d043d043e0433043e00200434043e043f0435044704300442043d043e0433043e00200432044b0432043e04340430002e002000200421043e043704340430043d043d044b04350020005000440046002d0434043e043a0443043c0435043d0442044b0020043c043e0436043d043e0020043e0442043a0440044b043204300442044c002004410020043f043e043c043e0449044c044e0020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200431043e043b043504350020043f043e04370434043d043804450020043204350440044104380439002e>
/SKY <FEFF0054006900650074006f0020006e006100730074006100760065006e0069006100200070006f0075017e0069007400650020006e00610020007600790074007600e100720061006e0069006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b0074006f007200e90020007300610020006e0061006a006c0065007001610069006500200068006f0064006900610020006e00610020006b00760061006c00690074006e00fa00200074006c0061010d00200061002000700072006500700072006500730073002e00200056007900740076006f00720065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f00740076006f00720069016500200076002000700072006f006700720061006d006f006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076016100ed00630068002e>
/SLV <FEFF005400650020006e006100730074006100760069007400760065002000750070006f0072006100620069007400650020007a00610020007500730074007600610072006a0061006e006a006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b006900200073006f0020006e0061006a007000720069006d00650072006e0065006a016100690020007a00610020006b0061006b006f0076006f00730074006e006f0020007400690073006b0061006e006a00650020007300200070007200690070007200610076006f0020006e00610020007400690073006b002e00200020005500730074007600610072006a0065006e006500200064006f006b0075006d0065006e0074006500200050004400460020006a00650020006d006f0067006f010d00650020006f0064007000720065007400690020007a0020004100630072006f00620061007400200069006e002000410064006f00620065002000520065006100640065007200200035002e003000200069006e0020006e006f00760065006a01610069006d002e>
/SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f00740020006c00e400680069006e006e00e4002000760061006100740069007600610061006e0020007000610069006e006100740075006b00730065006e002000760061006c006d0069007300740065006c00750074007900f6006800f6006e00200073006f00700069007600690061002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e>
/SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d002000e400720020006c00e4006d0070006c0069006700610020006600f60072002000700072006500700072006500730073002d007500740073006b00720069006600740020006d006500640020006800f600670020006b00760061006c0069007400650074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e>
/TUR <FEFF005900fc006b00730065006b0020006b0061006c006900740065006c0069002000f6006e002000790061007a006401310072006d00610020006200610073006b013100730131006e006100200065006e0020006900790069002000750079006100620069006c006500630065006b002000410064006f006200650020005000440046002000620065006c00670065006c0065007200690020006f006c0075015f007400750072006d0061006b0020006900e70069006e00200062007500200061007900610072006c0061007201310020006b0075006c006c0061006e0131006e002e00200020004f006c0075015f0074007500720075006c0061006e0020005000440046002000620065006c00670065006c0065007200690020004100630072006f006200610074002000760065002000410064006f00620065002000520065006100640065007200200035002e003000200076006500200073006f006e0072006100730131006e00640061006b00690020007300fc007200fc006d006c00650072006c00650020006100e70131006c006100620069006c00690072002e>
/UKR <FEFF04120438043a043e0440043804410442043e043204430439044204350020044604560020043f043004400430043c043504420440043800200434043b044f0020044104420432043e04400435043d043d044f00200434043e043a0443043c0435043d044204560432002000410064006f006200650020005000440046002c0020044f043a04560020043d04300439043a04400430044904350020043f045604340445043e0434044f0442044c00200434043b044f0020043204380441043e043a043e044f043a04560441043d043e0433043e0020043f0435044004350434043404400443043a043e0432043e0433043e0020043404400443043a0443002e00200020042104420432043e04400435043d045600200434043e043a0443043c0435043d0442043800200050004400460020043c043e0436043d04300020043204560434043a0440043804420438002004430020004100630072006f006200610074002004420430002000410064006f00620065002000520065006100640065007200200035002e0030002004300431043e0020043f04560437043d04560448043e04570020043204350440044104560457002e>
/ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.)
>>
/Namespace [
(Adobe)
(Common)
(1.0)
]
/OtherNamespaces [
<<
/AsReaderSpreads false
/CropImagesToFrames true
/ErrorControl /WarnAndContinue
/FlattenerIgnoreSpreadOverrides false
/IncludeGuidesGrids false
/IncludeNonPrinting false
/IncludeSlug false
/Namespace [
(Adobe)
(InDesign)
(4.0)
]
/OmitPlacedBitmaps false
/OmitPlacedEPS false
/OmitPlacedPDF false
/SimulateOverprint /Legacy
>>
<<
/AddBleedMarks false
/AddColorBars false
/AddCropMarks false
/AddPageInfo false
/AddRegMarks false
/ConvertColors /ConvertToCMYK
/DestinationProfileName ()
/DestinationProfileSelector /DocumentCMYK
/Downsample16BitImages true
/FlattenerPreset <<
/PresetSelector /MediumResolution
>>
/FormElements false
/GenerateStructure false
/IncludeBookmarks false
/IncludeHyperlinks false
/IncludeInteractive false
/IncludeLayers false
/IncludeProfiles false
/MultimediaHandling /UseObjectSettings
/Namespace [
(Adobe)
(CreativeSuite)
(2.0)
]
/PDFXOutputIntentProfileSelector /DocumentCMYK
/PreserveEditing true
/UntaggedCMYKHandling /LeaveUntagged
/UntaggedRGBHandling /UseDocumentProfile
/UseDocumentBleed false
>>
]
>> setdistillerparams
<<
/HWResolution [2400 2400]
/PageSize [612.000 792.000]
>> setpagedevice
|