Некоторые вопросы определения коэффициентов негладких штрафных функций
Рассматриваются процедуры автоматического определения значений штрафных коэффициентов по ходу работы оптимизационного алгоритма. Устанавливается связь с известными результатами....
Gespeichert in:
| Datum: | 2012 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Schriftenreihe: | Теорія оптимальних рішень |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/85019 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Некоторые вопросы определения коэффициентов негладких штрафных функций / Ю.П. Лаптин // Теорія оптимальних рішень: Зб. наук. пр. — 2012. — № 11. — С. 73-79. — Бібліогр.: 6 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-85019 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-850192015-07-19T03:02:13Z Некоторые вопросы определения коэффициентов негладких штрафных функций Лаптин, Ю.П. Рассматриваются процедуры автоматического определения значений штрафных коэффициентов по ходу работы оптимизационного алгоритма. Устанавливается связь с известными результатами. Розгядаються процедури автоматичного визначення значень штрафних коефіцієнтів по ходу роботи оптімізаційного алгоритму. Аналізуються зв’язки з відомими результатами. We consider an approach to construct an automatic procedure for determining the values of penalty coefficients in the process of optimization algorithm. Connections with known results are analized. 2012 Article Некоторые вопросы определения коэффициентов негладких штрафных функций / Ю.П. Лаптин // Теорія оптимальних рішень: Зб. наук. пр. — 2012. — № 11. — С. 73-79. — Бібліогр.: 6 назв. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/85019 519.8 ru Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| description |
Рассматриваются процедуры автоматического определения значений штрафных коэффициентов по ходу работы оптимизационного алгоритма. Устанавливается связь с известными результатами. |
| format |
Article |
| author |
Лаптин, Ю.П. |
| spellingShingle |
Лаптин, Ю.П. Некоторые вопросы определения коэффициентов негладких штрафных функций Теорія оптимальних рішень |
| author_facet |
Лаптин, Ю.П. |
| author_sort |
Лаптин, Ю.П. |
| title |
Некоторые вопросы определения коэффициентов негладких штрафных функций |
| title_short |
Некоторые вопросы определения коэффициентов негладких штрафных функций |
| title_full |
Некоторые вопросы определения коэффициентов негладких штрафных функций |
| title_fullStr |
Некоторые вопросы определения коэффициентов негладких штрафных функций |
| title_full_unstemmed |
Некоторые вопросы определения коэффициентов негладких штрафных функций |
| title_sort |
некоторые вопросы определения коэффициентов негладких штрафных функций |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2012 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/85019 |
| citation_txt |
Некоторые вопросы определения коэффициентов негладких штрафных функций / Ю.П. Лаптин // Теорія оптимальних рішень: Зб. наук. пр. — 2012. — № 11. — С. 73-79. — Бібліогр.: 6 назв. — рос. |
| series |
Теорія оптимальних рішень |
| work_keys_str_mv |
AT laptinûp nekotoryevoprosyopredeleniâkoéfficientovnegladkihštrafnyhfunkcij |
| first_indexed |
2025-07-06T12:10:48Z |
| last_indexed |
2025-07-06T12:10:48Z |
| _version_ |
1836899476612055040 |
| fulltext |
Теорія оптимальних рішень. 2012 73
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Рассматриваются процедуры
автоматического определения
значений штрафных коэффици-
ентов по ходу работы оптимиза-
ционного алгоритма. Устанавли-
вается связь с известными ре-
зультатами.
Ю.П. Лаптин, 2012
ÓÄÊ 519.8
Þ.Ï. ËÀÏÒÈÍ
ÍÅÊÎÒÎÐÛÅ ÂÎÏÐÎÑÛ
ÎÏÐÅÄÅËÅÍÈß ÊÎÝÔÔÈÖÈÅÍÒÎÂ
ÍÅÃËÀÄÊÈÕ ØÒÐÀÔÍÛÕ ÔÓÍÊÖÈÉ
Точные штрафные функции были впервые
предложены в работах [1, 2]. В дальнейшем
этому направлению было посвящено боль-
шое количество публикаций. Укажем лишь
некоторые [3-5]. В настоящее время метод
штрафных функций является основным
средством при использовании r-алгоритма
Н.З. Шора для решения оптимизационных
задач с ограничениями. Однако использова-
ние точных штрафных функций связано с
определенными проблемами – отсутствуют
простые методики вычисления приемлемых
значений штрафных коэффициентов. Выбор
значений коэффициентов, обычно, возлага-
ется на пользователя, что приводит либо к
завышению используемых значений, либо к
необходимости многократного решения од-
ной и той же задачи для удовлетворительно-
го подбора штрафных коэффициентов. В ра-
боте [6] рассматривался подход, позволяю-
щий построить процедуру автоматического
определения значений штрафных коэффици-
ентов по ходу работы оптимизационного ал-
горитма. В настоящей работе предлагается
обобщение этого подхода и приводится ряд
полезных результатов.
Рассматривается задача: найти
{ }min ( ) :f f x x C
∗
= ∈ , (1)
где { }: ( ) 0n
C x R h x= ∈ ≤ , , : n
f h R R→ –
выпуклые функции, принимающие конечные
Ю.П. ЛАПТИН
74 Теорія оптимальних рішень. 2012
значения при любых x , C – компактное множество. Будем рассматривать
штрафные функции вида
( , ) ( ) ( )S x s f x s h x
+= + ⋅ , , 0s R s∈ ≥ , (2)
где max{0, }h h
+ = , и выпуклую задачу: найти
{ }( ) min ( , ) : n
S s S x s x R
∗ = ∈ . (3)
Штрафная функция ( , )S x s называется точной при заданных значениях
штрафных коэффициентов s , если ( )S s f
∗ ∗= и решения задач (1) и (3) сов-
падают.
Пусть
'( , , )S x s p ,
'( , )f x p ,
'( , )h x p – производные функций S , f , h в
точке
n
x R∈ по направлению p при фиксированном значении s ,
( , ) ( ) ,p x y y x y x y x= − − ≠ .
Лемма 1. Пусть для любого x C∉ найдется y C∈ такое, что
'( , , ( , )) 0S x s p x y < , (4)
тогда ( , )S x s – точная штрафная функция.
Доказательство очевидно, поскольку если оптимальное решение x% задачи
(3) не принадлежит допустимому множеству C , то для ( , )S x s всегда найдется
направление убывания ( , )p x y% в этой точке, что противоречит предположению
об оптимальности точки x% .
Лемма 1 позволяет формулировать простые условия, которые должны вы-
полняться на каждом шаге оптимизационных алгоритмов при решении задачи
(3), если ( , )S x s точная штрафная функция. Для этого должно быть определено
правило, по которому для текущей точки
k
x , сгенерированной на итерации k
алгоритма, ставится в соответствие точка
k
y C∈ , если
k
x C∉ . Такие правила
можно задавать различным образом, например, всегда полагать
0k
y y= , где
0
y , такая что
0 0: ( ) 0y h y < – начальная допустимая точка, или
k
y выбирать
среди допустимых точек, сгенерированных на предыдущих итерациях.
Однако, такие необходимые условия оказываются недостаточными – усло-
вия могут выполняться для всех точек, генерируемых оптимизационным алго-
ритмом при решении задачи (3), но не выполняться для предельной точки. Дос-
таточные условия будут приведены в теореме 1.
НЕКОТОРЫЕ ВОПРОСЫ ОПРЕДЛЕНИЯ КОЭФФИЦИЕНТОВ НЕГЛАДКИХ ШТРАФНЫХ ФУНКЦИЙ
Теорія оптимальних рішень. 2012 75
Рассмотрим эти вопросы более подробно. Пусть x% – решение задачи (3), за-
даны сходящиеся последовательности , , 0,1, ...k n k
x R y C k∈ ∈ = ,
k
x x→ %
при k → ∞ , Обозначим lim k
k
y y
→∞
=% . Пусть значение s зафиксировано и для
каждого
k
x , такого что
k
x C∉ , выполняется
' ( , , ( , )) 0k k k
S x s p x y < . (5)
Следующий пример одномерной задачи демонстрирует, что в предельной
точке x% неравенство (5) может не выполняться:
( )f x x= − , { }1 2( ) max ( ), ( )h x h x h x= , где 1( ) 1h x x= − , 2 ( ) 2 3h x x= − .
Решением задачи (1) в этом случае есть 1, 1x f
∗ ∗
= = − . Пусть
2 1 , 0,1, ...k
x k k= + = , 0, 0,1, ...k
y k= = , штрафной коэффициент 0,75s = .
Нетрудно видеть, что 2x =% есть решение задачи (3), условия (5) выполняются,
но 2x =% не является решением задачи (1).
Пусть
k
x C∉ . Обозначим ( , )k k
C x yπ точку пересечения отрезка
,k k
x y
с границей множества C , ( , )k k k
Cx x y= π .
Теорема 1. Пусть заданы 0ε > , 0s > такие, что для каждого
k
x ,
k
x C∉ , 0,1, ...k = выполняется
' ( , , ( , ))k k k
S x s p x x ≥ ε . (6)
тогда x% является решением задачи (1), т.е. ( , )S x s – точная штрафная функция.
Доказательство. Понятно, что если x C∈% , то x% – решение задачи (1).
Предположим, что x C∉% . В силу сходимости последовательностей
, , 0,1, ...k k
x y k = последовательность , 0,1, ...k
x k = сходится к точке
( , )Cz x y= π % %% . В силу выпуклости функции ( , )S x s имеем
' ( , ) ( , )
( , , ( , ))
S x s S z s
S x s p x z
x z
−
− ≥
−
% %
% % %
% %
, (7)
'( , ) ( , )
( , , ( , ))
k k
k k k
k k
S x s S x s
S x s p x x
x x
−
≥
−
. (8)
В силу непрерывности функции ( , )S x s получаем
( , ) ( , ) ( , ) ( , )
lim
k k
k kk
S x s S z s S x s S x s
x z x x→∞
− −
=
− −
% %
% %
и, с учетом (6) и (8),
Ю.П. ЛАПТИН
76 Теорія оптимальних рішень. 2012
( , ) ( , )
2
S x s S z s
x z
− ε
≥
−
% %
% %
. Откуда
' ( , , ( , ))
2
S x s p x z
ε
≤ −% % % . Т.е. в точке x% существует
направление убывания ( , ))p x z% % , что противоречит предположению об опти-
мальности точки x% . ■
Для решения задачи (3) при использовании данного подхода может исполь-
зоваться любой глобально сходящийся алгоритм выпуклой безусловной оптими-
зации. Последовательность , 0,1, ...k n
x R k∈ = в этом случае генерируется
оптимизационным алгоритмом. Последовательность , 0,1, ...k
y C k∈ = долж-
на задаваться некоторым специальным образом. На каждом шаге оптимизаци-
онного алгоритма необходимо проверять условие (6), что требует решения од-
номерной задачи поиска точки пересечения отрезка ,k k
x y
с границей мно-
жества C .
В случае, когда неравенство (6) на некоторой итерации алгоритма наруша-
ется, будем увеличивать (на этой итерации) штрафной коэффициент s так, что-
бы неравенство (6) выполнилось. При этом увеличение штрафного коэффициен-
та будем производить на величину не менее B , где 0B > – заданный пара-
метр. Легко видеть, что если существует конечное s такое, что при s s> нера-
венство (6) выполняется на всех итерациях алгоритма, то количество таких уве-
личений штрафного коэффициента по ходу работы оптимизационного алгорит-
ма будет конечно. Условия существования конечного s будут сформулированы
в теореме 2.
Неравенство (4) перепишем в виде
' '( , ( , )) ( , ( , )) 0f x p x y s h x p x y+ ⋅ < . (9)
Заметим, что
'( , ( , )) 0h x p x y < , если x C∉ и y C∈ .
Положим
'
'
( , ( , ))
( , ) max 0,
( , ( , ))
f x p x y
r x y
h x p x y
= −
,
{ }0 0( ) sup ( , ) : ( , ),Cr y r x x x x y x C= = π ∉ ,
0
y C∈
(10)
Лемма 2. Пусть задана точка
0
y C∈ , такая что
0( ) 0h y < , тогда
0( )r y < +∞ .
Доказательство. В силу ограниченности множества C функция f липши-
цева, и существует 0M > , такое что ( , ( , ))f x p x x M′ ≤ для любых x C∉ ,
НЕКОТОРЫЕ ВОПРОСЫ ОПРЕДЛЕНИЯ КОЭФФИЦИЕНТОВ НЕГЛАДКИХ ШТРАФНЫХ ФУНКЦИЙ
Теорія оптимальних рішень. 2012 77
0( , )Cx x y= π . Положим { }0 0max : ( , ),Cm x y x x y x C= − = π ∉ . В силу
выпуклости функции h имеем
0
0
( ) ( )
( , ( , ))
h x h y
h x p x x
x y
−
′ ≥
−
. Откуда
0 1( , ( , )) ( )h x p x x h y m
−′ ≥ , (11)
и
0
0
( )
( )
mM
r y
h y
≤ . ■
Теорема 2. Пусть задана последовательность , 0,1, ...k n
x R k∈ = , сходя-
щаяся к решению x% задачи (3),
0 , 1, 2, ...k
y y k= = ,
0( ) 0h y < . Тогда сущест-
вуют s < ∞ такое, что при s s> выполняются условия теоремы 1.
Доказательство. Положим
0( )s r y= . Нетрудно видеть, что
' ' '
' ' '
'
' '
'
( , , ( , )) ( , ( , )) ( ) ( , ( , ))
( , ( , )) ( , ( , )) ( ) ( , ( , ))
( , ( , ))
( , ( , )) ( ) ( , ( , ))
( , ( , ))
(
k k k k k k k k k
k k k k k k k k k
k k k
k k k k k k
k k k
S x s p x x f x p x x s s s h x p x x
f x p x x s h x p x x s s h x p x x
f x p x x
h x p x x s s s h x p x x
h x p x x
s s
= + + − ⋅ =
= + ⋅ + − ⋅ =
−
= − + − ⋅ ≥
≥ −
') ( , ( , )).k k k
h x p x x⋅
Учитывая (11) и полагая
0 1( ) ( )s s h y m
−ε = − , получаем утверждение теоре-
мы. ■
Приведенные результаты позволяют строить достаточно эффективные про-
цедуры автоматического определения значений штрафных коэффициентов по
ходу работы алгоритмов безусловной оптимизации. Простейшая процедура за-
ключается в использовании начальной точки
0
y , такой что
0( ) 0h y < , на всех
итерациях алгоритма для проверки условия (6). Однако при неудачном выборе
точки
0
y значения штрафных коэффициентов могут устанавливаться достаточ-
но большими. Уменьшить эти значения можно за счет специального выбора то-
чек
k
y на каждой итерации алгоритма. Вопросы оценки возможных значений
штрафных коэффициентов рассматриваются далее.
Будем выбирать точки
k
y на каждой итерации оптимизационного алгорит-
ма так, чтобы неравенство
' ' '( , , ( , )) ( , ( , )) ( , ( , )) 0k k k k k k k k k
S x s p x x f x p x x s h x p x x= + ⋅ > (12)
Ю.П. ЛАПТИН
78 Теорія оптимальних рішень. 2012
выполнялось при наименьшем значении штрафного коэффициента, здесь
( , )k k k
Cx x y= π . Обозначая, как и ранее,
'
'
( , ( , ))
( , ) max 0,
( , ( , ))
f x p x y
r x y
h x p x y
= −
,
положим
{ }( ) min ( , ) : ( , ),k k k k k
Cr x r x x x x y y C= = π ∈ , (13)
{ }arg min ( , ) : ( , ),k k k k k
Cy r x x x x y y C= = π ∈ , (14)
{ }sup ( ) :r r x x C
∗
= ∉ . (15)
Используя для выбора
k
y правило (14), и выбирая s r
∗> , получим выпол-
нение неравенств (12) на каждой итерации оптимизационного алгоритма. Таким
образом, справедлива
Лемма 3. Пусть s r
∗> , тогда ( , )S x s – точная штрафная функция.
Естественным является вопрос о том, как соотносятся полученные результа-
ты с известными.
Пусть задача (1) является задачей линейного программирования: найти
min ,f c x
∗
= , (16)
, 0, 1,...,i ia x b i m+ ≤ = . (17)
Для этой задачи ( ) ,f x c x= , { }( ) max ( ), 1,...,ih x h x i m= = , где
( ) , , 1,...,i i ih x a x b i m= + = .
Теорема 3. Пусть задача (16), (17) имеет единственное решение x
∗
. Тогда
1
m
i
i
r u
∗ ∗
=
=∑ , где , 1,...,iu i m
∗ = – оптимальные значения двойственных перемен-
ных.
Доказательство не приводится ввиду ограниченности объема статьи.
В работе рассмотрен подход, позволяющий строить достаточно эффектив-
ные процедуры автоматического определения значений штрафных коэффициен-
тов по ходу работы алгоритмов безусловной оптимизации. При этом каждой
точке k
x , генерируемой на итерации k алгоритма, должна ставиться в соответ-
ствие некоторая точка k
y из допустимого множества C исходной задачи. Для
точек k
x и k
y выполняется проверка условия (6). Простейшая процедура за-
НЕКОТОРЫЕ ВОПРОСЫ ОПРЕДЛЕНИЯ КОЭФФИЦИЕНТОВ НЕГЛАДКИХ ШТРАФНЫХ ФУНКЦИЙ
Теорія оптимальних рішень. 2012 79
ключается в использовании начальной точки
0
y , такой что
0( ) 0h y < , на всех
итерациях алгоритма, т.е. 0k
y y= . Показано, что наилучший выбор точек k
y
при решении задачи линейного программирования приводит к известному ре-
зультату – для штрафного коэффициента r
∗
выполняется
1
m
i
i
r u
∗ ∗
=
=∑ , где iu
∗
–
оптимальные значения двойственных переменных. Для повышения эффектив-
ности предлагаемого подхода необходимо разрабатывать правила (желательно
простые) формирования допустимых точек k
y .
Ю.П. Лаптін
ДЕЯКІ ПИТАННЯ ВИЗНАЧЕННЯ КОЕФІЦІЕНТІВ НЕГЛАДКИХ ШТРАФНИХ ФУНКЦІЙ
Розгядаються процедури автоматичного визначення значень штрафних коефіцієнтів по ходу
роботи оптімізаційного алгоритму. Аналізуються зв’язки з відомими результатами.
Yu.P.Laptin
SOME QUESTIONS FOR DETERMINING THE VALUES OF NONSMOOTH PENALTY
FUNCTIONS
We consider an approach to construct an automatic procedure for determining the values of penalty
coefficients in the process of optimization algorithm. Connections with known results are analized.
1. Еремин И.И. Метод "штрафов" в выпуклом про-граммировании // Докл. АН СССР.
1967. Т. 173, № 4. С. 748-751.
2. Zangwill W. Non-linear programming via penalty function // Manag. Sci. 1967. P. 344-358.
3. Пшеничный Б.Н. Метод линеаризации. – М.: Наука. – 1983. – 136 с.
4. Shor N. Z. Nondifferentiable Optimization and Polynomial Problems. – Amsterdam /
Dordrecht / London: Kluwer Academic Publishers, 1998. – 381 p.
5. Евтушенко Ю.Г., Жадан В.Г. Точные вспомогательные функции в задачах оптими-
зации // ЖВМ и МФ, 1990. 30. № 1. с. 43-57.
6. Лаптин Ю.П. Некоторые вопросы использования негладких штрафных функций //
Теорія оптимальних рішень. 2011, № 10. с. 127 – 135.
Получено 14.05.2012
|