Использование штрафных функций для решения некоторых задач оптимизации
Рассматриваются проблемы использования точных штрафных функций при решении оптимизационных задач с ограничениями. Предложены подходы, позволяющие определять штрафные коэффициенты по ходу работы оптимизационного алгоритма. Сформулированы достаточные условия, при которых решение вспомогательной задач...
Gespeichert in:
| Veröffentlicht in: | Теорія оптимальних рішень |
|---|---|
| Datum: | 2013 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/85049 |
| 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: | Использование штрафных функций для решения некоторых задач оптимизации / Ю.П. Лаптин // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 95-101. — Бібліогр.: 7 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860141386307731456 |
|---|---|
| author | Лаптин, Ю.П. |
| author_facet | Лаптин, Ю.П. |
| citation_txt | Использование штрафных функций для решения некоторых задач оптимизации / Ю.П. Лаптин // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 95-101. — Бібліогр.: 7 назв. — рос. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | Рассматриваются проблемы использования точных штрафных функций при решении оптимизационных задач с ограничениями. Предложены подходы, позволяющие определять штрафные коэффициенты по ходу работы оптимизационного алгоритма. Сформулированы достаточные условия, при которых решение вспомогательной задачи является решением исходной задачи.
Розглядаються проблеми використання точних штрафних функцій при розв’язанні оптимізаційних задач з обмеженнями. Запропоновані підходи, що дозволяють визначати штрафні коефіцієнти по ходу роботи оптимізаційного алгоритму. Сформульовані достатні умови, за яких розв’язок допоміжної задачі є розв’язком вихідної задачі.
There are considered the problems of use of exact penalty functions for solving optimization problems with constraints. The approaches are proposed that allow to determine the coefficients of penalty in the course of an optimization algorithm. Sufficient conditions are formulated under which the solution of the auxiliary problem is the solution of the original problem.
|
| first_indexed | 2025-12-07T17:49:42Z |
| format | Article |
| fulltext |
Теорія оптимальних рішень. 2013 95
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Рассматриваются проблемы ис-
пользования точных штрафных
функций при решении оптимиза-
ционных задач с ограничениями.
Предложены подходы, позволяю-
щие определять штрафные ко-
эффициенты по ходу работы
оптимизационного алгоритма.
Сформулированы достаточные
условия, при которых решение
вспомогательной задачи является
решением исходной задачи.
Ю.П. Лаптин, 2013
ÓÄÊ 519.8
ÓÄÊ 519.8
Þ.Ï. ËÀÏÒÈÍ
ÈÑÏÎËÜÇÎÂÀÍÈÅ ØÒÐÀÔÍÛÕ
ÔÓÍÊÖÈÉ ÄËß ÐÅØÅÍÈß
ÍÅÊÎÒÎÐÛÕ ÇÀÄÀ× ÎÏÒÈÌÈÇÀÖÈÈ
Введение. В настоящее время метод точных
штрафных функций широко используется
при решении задач оптимизации с ограниче-
ниями [1–5]. Однако применение этого мето-
да связано с определенными проблемами –
отсутствуют простые методики вычисления
приемлемых значений штрафных коэффици-
ентов, необходимо проверять непростые
условия регулярности, гарантирующие полу-
чение решения исходной задачи. Для выпук-
лых задач подходы, позволяющие опреде-
лять штрафные коэффициенты по ходу рабо-
ты оптимизационного алгоритма, рассматри-
вались в [6]. В данной работе эти подходы
уточняются и обобщаются на случай невы-
пуклых задач. Полученные результаты
полезны при построении оптимизационных
алгоритмов.
Рассматривается задача: найти
{ }min ( ) :f f x x
∗ = ∈ Ω , (1)
где { }: ( ) 0nx R h xΩ = ∈ ≤ , , : nf h R R→
– либо выпуклые функции, либо являются
суперпозициями выпуклой и непрерывно
дифференцируемых функций и принимают
конечные значения при любых ,x Ω –
компактное множество,
и задача: найти
{ }min ( ) : ,nF F x x R∗
λ λ= ∈ (2)
где ( )F xλ – штрафная функция вида
( ) ( ) ( ),F x f x h x
+
λ = + λ ⋅ (3)
здесь , 0,Rλ ∈ λ ≥ max{0, }.h h
+ =
Ю.П. ЛАПТИН
96 Теорія оптимальних рішень. 2013
Рассматриваемые задачи могут быть невыпуклыми и многоэкстремальны-
ми. При определенных условиях локальные решения задачи (2) являются также
локальными решениями задачи (1). Это позволяет для поиска решений задачи
(1) использовать решение задачи (2) и применять для этого развитые алгоритмы
безусловной оптимизации [7]. При этом возникает ряд проблем, среди которых
– определение приемлемых значений штрафного коэффициента λ и правила
отсева локальных решений задачи (2), не являющихся решениями задачи (1).
Обозначим
' ( , ),F x pλ
'( , ),f x p
'( , )h x p – односторонние производные
функций ,Fλ ,f h в точке n
x R∈ по направлению .p Определим ( ),h x↓
ско-
рость наискорейшего спуска функции h в точке ,x
{ }( ) min ( , ) : 1h x h x p p↓ ′= = ,
Следуя [4], рассмотрим множество { }: ( ) ,nx R h xδΩ = ∈ ≤ δ где 0.δ >
Пусть при некотором 0a > для точек из δΩ выполняется условие
( ) , \h x a x
↓
δ≤ − ∀ ∈Ω Ω . (4)
Тогда, если функция f липшицева на \ ,δΩ Ω то существует ∗λ такое, что
при
∗λ > λ все точки локального минимума задачи (2), принадлежащие множе-
ству ,δΩ являются и точками локального минимума задачи (1). Можно пока-
зать, что при
∗λ > λ для \x δ∀ ∈Ω Ω выполняется
{ }'min ( , ) : 1 0.F x p pλ = < (5)
Если при решении задачи (2) некоторым сходящимся алгоритмом все поро-
ждаемые точки попадают в множество \ ,δΩ Ω то условие (5) можно бы исполь-
зовать для подбора значения ∗λ – если это условие не выполняется, текущее
значение коэффициента λ следует увеличить.
Однако при таком подходе возникает две проблемы:
• трудоемкость решения задачи (5) может быть слишком высокой;
• условие (5) может выполняться для любой точки последовательности,
формируемой оптимизационным алгоритмом, но не выполняться для
предельной точки.
Для преодоления этих проблем рассмотрим несколько другой подход.
Теорема 1. Пусть заданы числа 0, 0,δ > β > 0,λ > последовательность
, 0,1, ...k n
x R k∈ = , сходится к локальному минимуму x% задачи (2), каждой
точке k
x ,
kx ∉Ω поставлен в соответствие вектор , 1k n k
p R p∈ =
и выполняются условия
ИСПОЛЬЗОВАНИЕ ШТРАФНЫХ ФУНКЦИЙ ДЛЯ РЕШЕНИЯ …
Теорія оптимальних рішень. 2013 97
[ ]{ }max ( , ) : 0, , ( ) 0 ,k k k k kF x tp p t h x tpλ′ + ∈ δ + > ≤ −β (6)
Тогда x% является локальным минимумом задачи (1).
Доказательство. Если x ∈ Ω% , то, очевидно, x% является локальным мини-
мумом задачи (1). Предположим x ∉ Ω% . Без ограничения общности можно счи-
тать, что последовательность векторов , 0,1,...k
p k = , сходится к некоторому
вектору p% . Обозначим
{ }min : 0, .t t t x tp= > + ∈Ω% % % (7)
Точка x t p+ ⋅%% % лежит на границе множества Ω . Положим min( , ).tδ = δ% %
Покажем, что существует номер K такой, что ( ) 0k k
h x tp+ > , при
0, ,
2
t
δ
∈
%
k K> . Предположим противное, т. е. для любого i найдется ik i> ,
для которого существует точка 0,
2ikt
δ
∈
%
такая, что ( ) 0i i
i
k k
kh x t p+ ≤ . Без
ограничения общности можно считать, что последовательность , 1,...
ikt i = ,
сходится. Обозначим lim
ik
i
t t
→∞
= . Имеем ,
2
t t
δ
≤ <
%
% ( ) 0,h x t p+ ⋅ ≤% % т. е.
x t p+ ⋅ ∈ Ω% % что противоречит (7).
В силу (6) можно показать, имеет место
1( ) ( ) ( ),k k k
F x tp F x t tλ λ+ ≤ − β + ο 0, ,
2
t
δ
∈
%
.k K> (8)
Покажем, что ( , ) .F x pλ′ ≤ −β% % Предположим противное, т. е. ( , ) .F x pλ′ > −β% %
Выберем число 0γ > так, что ( , ) .F x pλ′ = −β + γ% % В силу дифференцируемости
по направлению для 0t ≥ имеет место разложение
( )F x tpλ + =% %
2 2( ) ( , ) ( ) ( ) ( ).F x F x p t t F x t t tλ λ λ′+ + ο = − β + γ + ο% % % %
В силу 1( )
0,
t
t
→
ο
2 ( )
0
t
t
ο
→ при 0t → можно выбрать 0,
2
δ
τ ∈
%
так,
что 1( )
,
3
ο τ γ
≤
τ
2 ( )
.
3
ο τ γ
≤
τ
Откуда ( ) ( ) ,
3
k k k
F x p F xλ λ
γ
+ τ ≤ − βτ + τ
( )F x pλ + τ ≥% %
2
( ) ( )
3 3
F x F xλ λ
γ γ
− βτ + γτ − τ = − βτ + τ% % и ( )F x pλ + τ ≠% %
lim ( )k k
k
F x pλ→∞
≠ + τ , что противоречит условию непрерывности функции .Fλ
Ю.П. ЛАПТИН
98 Теорія оптимальних рішень. 2013
Таким образом, показано, что ( , ) .F x pλ′ ≤ −β% % Но, тогда точка x% не является
локальным минимумом задачи (2), т. е. предположение x ∉ Ω% неверно. Теорема
доказана.
Пусть задано число 0σ > и выполняются условия теоремы 1. Предполо-
жим, что для каждой точки , 0,1, ...k n
x R k∈ = ,
kx ∉Ω также выполняется
[ ]{ }max ( , ) : 0, , ( ) 0 .k k k k kh x tp p t h x tp′ + ∈ δ + > ≤ −σ (9)
Тогда при выполнении условия (9), если условие (6) не выполняется на не-
котором шаге оптимизационного алгоритма, штрафной коэффициент λ может
быть увеличен на конечную величину так, чтобы условие (6) выполнилось.
Наиболее сложным при использовании полученных результатов является
выбор векторов .k
p В некоторых случаях это может быть сделано достаточно
эффективно. Рассмотрим ситуацию, когда функции ,f h – выпуклые. Пусть за-
дана точка 0
x такая, что
0( ) 0.h x < В качестве вектора kp выберем вектор, по-
рождающий прямую, исходящую из точки
k
x и проходящую через 0
x . Тогда,
можно показать, что
1) существует 0σ > такое, что условие (9) выполняется для любой точки
;k
x ∉Ω
2) существует 0∗λ > такое, что при
∗λ > λ условие (6) выполняется для
любой точки .k
x ∉Ω
Таким образом, для задачи выпуклого программирования процедура подбо-
ра значения штрафного коэффициента λ достаточно простая
В невыпуклом случае ситуация существенно усложняется. В общем случае
задача (1) многоэкстремальная, допустимое множество может быть многосвяз-
ным. Штрафная добавка ( )h x+
может иметь локальные минимумы в недо-
пустимой области
Будем предполагать заданной допустимую точку 0
x ∈Ω такую, что
0( ) 0h x < . Обозначим
0Ω односвязную компоненту допустимого множества
задачи (1), содержащую точку 0.x Будем искать точку x
∗
локального минимума
задачи (1) при дополнительном требовании
0.x
∗ ∈Ω
Естественно предполагать, что если точки последовательности, порождае-
мой при решении «штрафной» задачи (2), не слишком далеко удаляются от гра-
ницы множества 0,Ω то условие (9) будет выполняться и предельная точка бу-
дет принадлежать множеству 0Ω . Для контроля за степенью удаления от гра-
ницы
0Ω введем вспомогательные понятия.
ИСПОЛЬЗОВАНИЕ ШТРАФНЫХ ФУНКЦИЙ ДЛЯ РЕШЕНИЯ …
Теорія оптимальних рішень. 2013 99
Траекторией ( , ),x tθ исходящей из точки x и проходящей через точку 0 ,x
назовем непрерывно дифференцируемую по t вектор-функцию : n
R Rθ → та-
кую, что ( ,0)x xθ = и
0 0( , )
x
x t xθ = при некотором
0 0.
x
t > Предполагается,
что
' ( , ) 1
t
x tθ = для любого 0.t ≥ Для непрерывной функции : ,nR Rϕ →
имеющей односторонние производные по направлениям, обозначим
0
( ( , )) ( ( , ))
( , ) lim .
t
x t t x t
x t
t
θ ∆ →+
ϕ θ + ∆ − ϕ θ
′ϕ =
∆
Для контроля за степенью удаления от границы
0Ω для каждой точки
, 0,1, ...,k n
x R k∈ = порождаемой при решении задачи (2), будем анализиро-
вать поведение функции h вдоль траектории ( , ), 0kx t tθ ≥ – проверять условие
{ }0max ( , ) : 0, , ( ( , )) 0 ,k
k k
x
h x t t t h x tθ′ ∈ θ > ≤ −σ (10)
а для уточнения штрафного коэффициента λ – условие
[ ]{ }max ( , ) : 0, , ( ( , )) 0 .k kF x t t h x tλθ′ ∈ δ θ > ≤ −β (11)
Здесь 0, 0, 0.δ > β > σ >
Можно показать, что при выполнении этих условий для предельной точки
x% (локального минимума задачи (2)) имеет место
0.x ∈Ω%
Существенной проблемой является выбор траекторией ( , ).x tθ Простейшей
траекторией является прямая, исходящая из точки x и проходящая через точку
0.x Понятно, что расширение класса возможных траекторий предоставляет до-
полнительные возможности.
Рассмотрим задачу: найти
{ }min ( ) : , ( ), ,
y x
f f y y y x x∗ = ∈Ω = Φ ∈Ω (12)
где { }: ( ) 0 ,y
y
y Y h yΩ = ∈ ≤ { }: ( ) 0 ,x
x
x X h xΩ = ∈ ≤ ,yn
Y R= ,xn
X R=
, :yf h Y R→ , :xh X R→ – выпуклые функции, принимающие конечные
значения при любых , ,x y ,
x y
Ω Ω – компактные множества. Будем предпола-
гать, что
x y
n n= и : X YΦ → – непрерывно дифференцируемое взаимноодно-
значное отображение. В случае, когда Φ – линейное невырожденное отобра-
жение, задача (12) есть задача выпуклого программирования.
Ю.П. ЛАПТИН
100 Теорія оптимальних рішень. 2013
Обозначим { }: , ( )
y y
x x X xΦΩ = ∈ Φ ∈Ω – прообраз множества
y
Ω в про-
странстве ,X Ω – множество допустимых точек задачи (12), .F
x yΩ = Ω ΩI
Будем предполагать заданной допустимую точку 0
x
x ∈Ω такую, что
0 0( ) 0, ( ) 0x yh x h y< < , где 0 0( ).y x= Φ
Для произвольной точки x ∉ Ω возможными траекториями будем считать
прямую ( , )
x
x tθ в пространстве ,X соединяющую точки x и
0 ,x и прямую
( , )
y
y tθ в пространстве ,Y соединяющую точки ( )y F x= и
0 0( ).y x= Φ
Прообразом прямой ( , )
y
y tθ будет некоторая траектория (кривая) ( , )y x t
Φθ
в пространстве ,X соединяющая точки x и
0.x
Проверка условий (10), (11) может выполняться сначала для траектории
( , )
x
x tθ и, если эти условия не выполняются, производиться для траектории
( , ).y x t
Φθ Как возможные траектории могут также рассматриваться линейные
комбинации ( , )
x
x tθ и ( , ).y x t
Φθ
Необходимо отметить, что проверка условий (10) является, в общем случае,
достаточно трудоемкой. Также и построение последовательностей, удовлетво-
ряющих условиям (10), (11), связано со значительными проблемами – могут по-
требоваться достаточно сложные процедуры поиска подходящей точки на теку-
щей итерации оптимизационного алгоритма, а также процедуры выбора новой
базовой точки
0.x
Ю.П. Лаптін
ВИКОРИСТАННЯ ШТРАФНИХ ФУНКЦІЙ
ДЛЯ РОЗВ’ЯЗАННЯ ДЕЯКИХ ЗАДАЧ ОПТИМІЗАЦІЇ
Розглядаються проблеми використання точних штрафних функцій при розв’язанні опти-
мізаційних задач з обмеженнями. Запропоновані підходи, що дозволяють визначати штрафні
коефіцієнти по ходу роботи оптимізаційного алгоритму. Сформульовані достатні умови, за
яких розв’язок допоміжної задачі є розв’язком вихідної задачі.
Yu.P. Laptin
USING PENALTY FUNCTIONS FOR SOLVING SOME OPTIMIZATION PROBLEMS
There are considered the problems of use of exact penalty functions for solving optimization
problems with constraints. The approaches are proposed that allow to determine the coefficients of
penalty in the course of an optimization algorithm. Sufficient conditions are formulated under
which the solution of the auxiliary problem is the solution of the original problem.
ИСПОЛЬЗОВАНИЕ ШТРАФНЫХ ФУНКЦИЙ ДЛЯ РЕШЕНИЯ …
Теорія оптимальних рішень. 2013 101
1. Пшеничный Б.Н. Метод линеаризации. – М.: Наука. – 1983. – 136 с.
2. Shor N.Z. Nondifferentiable Optimization and Polynomial Problems. – Amsterdam / Dordrecht
/ London: Kluwer Academic Publishers, 1998. – 381 p.
3. Евтушенко Ю.Г., Жадан В.Г. Точные вспомогательные функции в задачах оптимизации
// ЖВМ и МФ. – 1990. – Т. 30. – № 1. – С. 43–57.
4. Демьянов В.Ф. Условия экстремума и вариационное исчисление. – М.: Высш. шк., 2005. –
335 с.
5. Данилин Ю.М. Линеаризация и штрафные функции // Кибернетика и системный анализ. –
2002. – № 5. – С. 65–78.
6. Лаптин Ю.П. Некоторые вопросы опредления коэффициентов негладких штрафных
функций // Теорія оптимальних рішень. – 2012. – С. 73–79.
7. Шор Н.З. О классе почти-дифференцируемых функций и одном методе минимизации
функций этого класса // Кибернетика. – 1972. – № 4. – С. 9 – 17.
Получено 19.03.2013
|
| id | nasplib_isofts_kiev_ua-123456789-85049 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-12-07T17:49:42Z |
| publishDate | 2013 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Лаптин, Ю.П. 2015-07-18T16:58:18Z 2015-07-18T16:58:18Z 2013 Использование штрафных функций для решения некоторых задач оптимизации / Ю.П. Лаптин // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 95-101. — Бібліогр.: 7 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/85049 519.8 Рассматриваются проблемы использования точных штрафных функций при решении оптимизационных задач с ограничениями. Предложены подходы, позволяющие определять штрафные коэффициенты по ходу работы оптимизационного алгоритма. Сформулированы достаточные условия, при которых решение вспомогательной задачи является решением исходной задачи. Розглядаються проблеми використання точних штрафних функцій при розв’язанні оптимізаційних задач з обмеженнями. Запропоновані підходи, що дозволяють визначати штрафні коефіцієнти по ходу роботи оптимізаційного алгоритму. Сформульовані достатні умови, за яких розв’язок допоміжної задачі є розв’язком вихідної задачі. There are considered the problems of use of exact penalty functions for solving optimization problems with constraints. The approaches are proposed that allow to determine the coefficients of penalty in the course of an optimization algorithm. Sufficient conditions are formulated under which the solution of the auxiliary problem is the solution of the original problem. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Использование штрафных функций для решения некоторых задач оптимизации Використання штрафних функцій для розв’язання деяких задач оптимізації Using penalty functions for solving some optimization problems Article published earlier |
| spellingShingle | Использование штрафных функций для решения некоторых задач оптимизации Лаптин, Ю.П. |
| title | Использование штрафных функций для решения некоторых задач оптимизации |
| title_alt | Використання штрафних функцій для розв’язання деяких задач оптимізації Using penalty functions for solving some optimization problems |
| title_full | Использование штрафных функций для решения некоторых задач оптимизации |
| title_fullStr | Использование штрафных функций для решения некоторых задач оптимизации |
| title_full_unstemmed | Использование штрафных функций для решения некоторых задач оптимизации |
| title_short | Использование штрафных функций для решения некоторых задач оптимизации |
| title_sort | использование штрафных функций для решения некоторых задач оптимизации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/85049 |
| work_keys_str_mv | AT laptinûp ispolʹzovanieštrafnyhfunkciidlârešeniânekotoryhzadačoptimizacii AT laptinûp vikoristannâštrafnihfunkcíidlârozvâzannâdeâkihzadačoptimízacíí AT laptinûp usingpenaltyfunctionsforsolvingsomeoptimizationproblems |