Некоторые вопросы использования негладких штрафных функций
Рассматривается процедура автоматического определения значений штрафных коэффициентов по ходу работы оптимизационного алгоритма. Анализируются возможности предлагаемого подхода для разработки схем декомпозиции квазиблочных задач оптимизации со связывающими переменными. Розглядається підхід, який доз...
Gespeichert in:
| Veröffentlicht in: | Теорія оптимальних рішень |
|---|---|
| Datum: | 2011 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/46783 |
| 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: | Некоторые вопросы использования негладких штрафных функций / Ю.П. Лаптин // Теорія оптимальних рішень: Зб. наук. пр. — 2011. — № 10. — С. 122-128. — Бібліогр.: 6 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-46783 |
|---|---|
| record_format |
dspace |
| spelling |
Лаптин, Ю.П. 2013-07-06T17:22:35Z 2013-07-06T17:22:35Z 2011 Некоторые вопросы использования негладких штрафных функций / Ю.П. Лаптин // Теорія оптимальних рішень: Зб. наук. пр. — 2011. — № 10. — С. 122-128. — Бібліогр.: 6 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/46783 519.8 Рассматривается процедура автоматического определения значений штрафных коэффициентов по ходу работы оптимизационного алгоритма. Анализируются возможности предлагаемого подхода для разработки схем декомпозиции квазиблочных задач оптимизации со связывающими переменными. Розглядається підхід, який дозволяє побудувати процедуру автоматичного визначення значень штрафних коефіцієнтів по ходу роботи оптимізаційного алгоритму. Аналізуються можливості запропонованого підходу для розробки схем декомпозиції квазіблочних задач оптимізації зі зв'язуючими змінними. We consider an approach to construct an automatic procedure for determining the values of penalty coefficients in the process of optimization algorithm. The possibilities of the proposed approach for the development of decomposition schemes for quasi-block optimization problems with binding variables are analysed. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Некоторые вопросы использования негладких штрафных функций Деякі питання використання негладких штрафних функцій Some questions of nonsmooth penalty functions Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Некоторые вопросы использования негладких штрафных функций |
| spellingShingle |
Некоторые вопросы использования негладких штрафных функций Лаптин, Ю.П. |
| title_short |
Некоторые вопросы использования негладких штрафных функций |
| title_full |
Некоторые вопросы использования негладких штрафных функций |
| title_fullStr |
Некоторые вопросы использования негладких штрафных функций |
| title_full_unstemmed |
Некоторые вопросы использования негладких штрафных функций |
| title_sort |
некоторые вопросы использования негладких штрафных функций |
| author |
Лаптин, Ю.П. |
| author_facet |
Лаптин, Ю.П. |
| publishDate |
2011 |
| language |
Russian |
| container_title |
Теорія оптимальних рішень |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Деякі питання використання негладких штрафних функцій Some questions of nonsmooth penalty functions |
| description |
Рассматривается процедура автоматического определения значений штрафных коэффициентов по ходу работы оптимизационного алгоритма. Анализируются возможности предлагаемого подхода для разработки схем декомпозиции квазиблочных задач оптимизации со связывающими переменными.
Розглядається підхід, який дозволяє побудувати процедуру автоматичного визначення значень штрафних коефіцієнтів по ходу роботи оптимізаційного алгоритму. Аналізуються можливості запропонованого підходу для розробки схем декомпозиції квазіблочних задач оптимізації зі зв'язуючими змінними.
We consider an approach to construct an automatic procedure for determining the values of penalty coefficients in the process of optimization algorithm. The possibilities of the proposed approach for the development of decomposition schemes for quasi-block optimization problems with binding variables are analysed.
|
| issn |
XXXX-0013 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/46783 |
| citation_txt |
Некоторые вопросы использования негладких штрафных функций / Ю.П. Лаптин // Теорія оптимальних рішень: Зб. наук. пр. — 2011. — № 10. — С. 122-128. — Бібліогр.: 6 назв. — рос. |
| work_keys_str_mv |
AT laptinûp nekotoryevoprosyispolʹzovaniânegladkihštrafnyhfunkcii AT laptinûp deâkípitannâvikoristannânegladkihštrafnihfunkcíi AT laptinûp somequestionsofnonsmoothpenaltyfunctions |
| first_indexed |
2025-11-27T08:10:04Z |
| last_indexed |
2025-11-27T08:10:04Z |
| _version_ |
1850807723284758528 |
| fulltext |
122 Теорія оптимальних рішень. 2011, № 10
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Рассматривается процедура ав-
томатического определения зна-
чений штрафных коэффициентов
по ходу работы оптимизационно-
го алгоритма. Анализируются
возможности предлагаемого под-
хода для разработки схем деком-
позиции квазиблочных задач оп-
тимизации со связывающими пе-
ременными.
Ю.П. Лаптин, 2011
ÓÄÊ 519.8
Þ.Ï. ËÀÏÒÈÍ
ÍÅÊÎÒÎÐÛÅ ÂÎÏÐÎÑÛ
ÈÑÏÎËÜÇÎÂÀÍÈß ÍÅÃËÀÄÊÈÕ
ØÒÐÀÔÍÛÕ ÔÓÍÊÖÈÉ
Негладкие штрафные функции широко ис-
пользуются при решении оптимизационных
задач [1–4]. Однако их использование связа-
но с определенными проблемами – отсутст-
вуют простые методики вычисления прием-
лемых значений штрафных коэффициентов.
Выбор значений коэффициентов, обычно,
возлагается на пользователя, что приводит
либо к завышению используемых значений,
либо к необходимости многократного реше-
ния одной и той же задачи для удовлетвори-
тельного подбора штрафных коэффициентов.
В работе рассматривается подход, позво-
ляющий построить процедуру автоматиче-
ского определения значений штрафных ко-
эффициентов по ходу работы оптимизацион-
ного алгоритма. Анализируются возможно-
сти предлагаемого подхода для разработки
схем декомпозиции квазиблочных задач оп-
тимизации со связывающими переменными.
Предлагаемая процедура определения значе-
ний штрафных коэффициентов оказывается
также полезной при использовании выпук-
лых продолжений целевой функции [5] в
схемах декомпозиции. Рассматриваемые
подходы позволяют существенно упростить
реализацию схем декомпозиции.
1. Процедуры уточнения штрафных
коэффициентов. Рассматривается задача:
найти
{ }min ( ) :f f x x C
∗ = ∈ , (1)
НЕКОТОРЫЕ ВОПРОСЫ ИСПОЛЬЗОВАНИЯ НЕГЛАДКИХ ШТРАФНЫХ ФУНКЦИЙ
Теорія оптимальних рішень. 2011, № 10 123
где { }: ( ) 0, 1,...,
n
iC x R h x i m= ∈ ≤ = , , : n
if h R R→ – выпуклые функции.
Предполагается, что C – ограниченное замкнутое множество и задана допусти-
мая точка 0
x C∈ , такая, что
0( ) 0, 1,...,ih x i m< = .
Пусть , if h принимают конечные значения при любых x . Будем рассмат-
ривать штрафные функции вида
1
( , ) ( ) ( )
m
i i
i
S x s f x s h x
+
=
= +∑ , , 0, 1,...,m
is R s i m∈ ≥ = , (2)
или
( , ) ( ) ( )S x s f x s h x
+= + ⋅ , , 0s R s∈ ≥ , (3)
где { }( ) max ( ), 1,...,ih x h x i m= = , max{0, }x x
+ = . Рассмотрим задачу: найти
{ }( ) min ( , ) :
n
S s S x s x R
∗
= ∈ . (4)
Штрафная функция ( , )S x s точная при заданных значениях штрафных ко-
эффициентов s , если ( )S s f∗ ∗= и решения задач (1) и (4) совпадают.
Пусть
' ( , , )S x s p – производная функции S в точке n
x R∈ по направле-
нию p при фиксированном значении s ,
0 0( ) ( )p x x x x x= − − .
Лемма 1. Пусть 0ε > и
' ( , , ( ))S x s p x ≥ ε (5)
при любом x C∉ , тогда ( , )S x s – точная штрафная функция.
Доказательство. Пусть x
∗
– оптимальное решение задачи (4). Очевидно,
что если x C
∗
∈ , то x
∗
является оптимальным решением задачи (1). Пусть
x C
∗
∉ . Обозначим ( )C x
∗π точку пересечения отрезка 0
,x x
∗
с границей
множества C . Нетрудно видеть, что в силу (5) имеет место
( , ) ( ( ), )CS x s S x s∗ ∗> π . Это противоречит предположению об оптимальности
точки x
∗
.
Теорема 1. Существует конечное s , такое, что условие леммы 1 выполня-
ется при любых s s> , где
m
s R∈ , если используется штрафная функция вида
(2), и s R∈ ,для штрафной функции (3).
Обозначим ( , )Sg x s субградиент функции ( , )S x s в точке x при фиксиро-
ванном s . Вместо (5) может использоваться неравенство
Ю.П. ЛАПТИН
124 Теорія оптимальних рішень. 2011, № 10
( )( , ), ( )Sg x s p x ≥ ε . (6)
Очевидно, что если в точке x выполняется (6), то также выполняется и (5).
Пусть значения штрафных коэффициентов s зафиксированы, для решения за-
дачи (4) используется глобально сходящийся алгоритм A безусловной миними-
зации выпуклых функций.
Теорема 2. Пусть на каждой итерации k алгоритма A выполняется усло-
вие: если
k
x C∉ , то для этой точки имеет место неравенство (6). Тогда алго-
ритм A сходится к решению задачи (1).
Для штрафной функции (2) неравенство (6) принимает вид
( ) ( ) { }
( )
( ), ( ) ( ), ( ) , ( ) : ( ) 0
if i h i
i I x
g x p x s g x p x I x i h x
∈
+ ≥ ε = >∑ , (7)
соответственно, для функции вида (3)
( ) ( )( ), ( ) ( ), ( ) ,f hg x p x s g x p x x C+ ≥ ε ∉ . (8)
При практическом использовании приведенных соотношений в случае, ко-
гда неравенство (7) или (8) на некоторой итерации алгоритма A нарушается,
будем увеличивать (на этой итерации) какой-либо из штрафных коэффициентов
, ( )is i I x∈ так, чтобы неравенство (6) выполнилось. При этом увеличение вы-
бранного штрафного коэффициента будем производить на величину не менее
B , где 0B > – заданный параметр. В силу конечности s количество таких
увеличений штрафных коэффициентов по ходу работы алгоритма A будет ко-
нечно. После этого в силу теоремы 1 алгоритм сходится к решению задачи (1).
Использование точных штрафных функций позволяет существенно упро-
стить реализацию схем декомпозиции для квазиблочных задач выпуклого про-
граммирования со связывающими переменными вида: найти
,
1
min ( , ) : ( , ) 0, 1,...,
m
i i
i i
x y
i
f f x y h x y i m
∗
=
= ≤ =
∑ , (9)
где ( , ), ( , )i i
i if x y h x y - выпуклые функции i(n k )+ – размерного вектора
( , )ix y , , ikn ix R y R∈ ∈ , принимающие конечные значения при любых , ix y .
Здесь x – связывающие переменные,
iy – переменные i -го блока. Предполага-
ется, что заданы
0
0, ikn i
x R y R∈ ∈ , 1,...,i m= , такие, что
0
0( , ) 0i
ih x y < .
Схема декомпозиции для задачи (9) основана на том, что при фиксирован-
ных значениях связывающих переменных x эта задача распадается на подзада-
чи, каждая из которых есть задача с ограничениями и может решаться незави-
симо [1, 6]. Обозначим ( )i xΦ оптимальное значение i –й подзадачи при задан-
ных значениях переменных x , тогда координирующая задача имеет вид: найти
НЕКОТОРЫЕ ВОПРОСЫ ИСПОЛЬЗОВАНИЯ НЕГЛАДКИХ ШТРАФНЫХ ФУНКЦИЙ
Теорія оптимальних рішень. 2011, № 10 125
1
min ( ) :
m
n
i
i
x x R
=
Φ ∈
∑ . (10)
При решении задачи (10) возникают существенные проблемы, поскольку
функции ( )i xΦ определены не при любых значениях x . В работе [1] для пре-
одоления этих проблем предлагалось делать специальную регуляризацию ис-
ходной задачи.
Пусть заданы штрафные коэффициенты 1 0,..., 0ms s≥ ≥ . Обозначим
( , , ) ( , ) ( , )
i i i
i i i i iS x y s f x y s h x y
+= + . (11)
Поскольку для задачи (9) выполняются условия Слейтера, то существуют
штрафные коэффициенты , 1,...,is i m
∗ = , такие, что при условии ,i is s
∗≥
1,...,i m= следующая задача эквивалента исходной задаче (9): найти
1
,
1
( ,..., ) min ( , , ) : , , 1,...,i
m
ki n i
m i i
x y
i
S s s S x y s x R y R i m
∗
=
= ∈ ∈ =
∑ . (12)
Применение схемы декомпозиции для задачи (12) проще, так как при фик-
сированных связывающих переменных она распадается на подзадачи, которые
являются задачами безусловной минимизации и имеют решение при любых x .
Для применения такого подхода может использоваться рассмотренная процеду-
ра итеративного уточнения штрафных коэффициентов , 1,...,is i m= .
2. Конические продолжения функций. Применение негладких штрафных
функций возможно, если все функции задачи определены при любых значениях
переменных. В случаях, когда функции могут быть не определены вне допусти-
мой области, в [5] предлагалось использовать конические продолжения функ-
ций. Рассмотрим применение конических продолжений в схемах декомпозиции.
Пусть заданы: выпуклая функция : { }nf R R→ ∞U , замкнутое выпуклое
множество
nC R⊂ , domC f⊆ , внутренняя точка
0x множества C ,
0 intx C∈ , и некоторое число E . Для x C∉ обозначим
0( , )C x xπ точку пе-
ресечения отрезка 0[ , ]x x с границей множества C . Положим
0 0 0 0
( , ) ( ; )C CR x x x x x x x= − π − , (13)
0 0( ) ( ( ( , )) ) ( , )E C Cx E f x x E R x xχ = + π − ⋅ . (14)
Определим операцию конического продолжения
0( , , , )f C x EΓ функции f
с множества C на
n
R :
Ю.П. ЛАПТИН
126 Теорія оптимальних рішень. 2011, № 10
0 ( ), если ,
( , , , ) : ( ) ( )
( ), если .
E
E
f x x C
f C x E f x x
x x C
∈
Γ → ψ =
χ ∉
(15)
Функция ( )E xψ – непрерывна и принимает конечные значения при любых x .
Лемма 3 [5]. Пусть функция f липшицева на C . Тогда существует конеч-
ное E
∗
, такое, что для всех
*
E E≤ функция : n
E R Rψ → – выпуклая.
Заметим, что
0( , )CR x x есть функция Минковского [4] для множества C ,
записанная относительно точки
0
x . Функция
0( , )CR x x – выпуклая; если
intx C∈ , то
0( , ) 1CR x x < , если x C∉ , то
0( , ) 1CR x x > , для граничных точек
x множества C имеет место
0( , ) 1CR x x = .
Рассмотрим задачу
{ }0
min ( ) : ( , ) 1E Cx R x x
∗
ψ = ψ ≤ (16)
и негладкую штрафную функцию
0( , ) ( ) ( , ) 1E E CP x u x u R x x
+
= ψ + − . (17)
Нетрудно проверить, что
( , ) ( )E E uP x u x−= ψ . (18)
Рассмотрим квазиблочную задачу (9) выпуклого программирования со свя-
зывающими переменными. Предполагается, что , : { }ikn
i if h R R R× → ∞U –
выпуклые собственные функции, { }( , ) : , , ( , ) 0iki n i i
i iC x y x R y R h x y= ∈ ∈ ≤
– ограниченные и замкнутые множества, int(dom dom )i i iC f h⊆ I , функции
if липшицевы на iC 1,...,i m= . Заданы точки
0
0, ikn i
x R y R∈ ∈ , такие, что
0
0( , ) 0i
ih x y < , 1,...,i m= .
Положим
0
0( , , ) ( , , ( , ), )i i
i i i i ix y E f C x y Eψ = Γ – конические продолжения
функций if с множеств iC на все пространство iknR R× ( iE – параметр),
1,...,i m= . Рассмотрим задачу: найти
1
,
1
( ,..., ) min ( , , ) : , , 1,...,i
m
ki n i
m i i
x y
i
E E x y E x R y R i m
∗
=
ψ = ψ ∈ ∈ =
∑ . (19)
НЕКОТОРЫЕ ВОПРОСЫ ИСПОЛЬЗОВАНИЯ НЕГЛАДКИХ ШТРАФНЫХ ФУНКЦИЙ
Теорія оптимальних рішень. 2011, № 10 127
Теорема 3. Существуют конечные числа iE∗
, такие, что при всех
, 1,...,i iE E i m
∗< = , функции ( , , )i
i ix y Eψ выпуклы, а задачи (9) и (19) экви-
валентны (совпадают их оптимальные значения и оптимальные множества).
Доказательство. Поскольку if липшицевы на iC , то из леммы 3 следует
существование величин iE , таких, что при i iE E< функции ( , , )i
i ix y Eψ вы-
пуклы. Рассмотрим задачу
0
0
,
1
min ( , , ) : (( , ), ( , )) 1, 1,...,
i
m
i i i
i i C
x y
i
x y E R x y x y i m
=
ψ ≤ =
∑ , (20)
где
iCR – функция Минковского для множества iC . Очевидно, задачи (9) и (20)
эквивалентны. Из теоремы о негладких штрафных функциях [1, 3] следует су-
ществование коэффициентов , 1,...,iu i m∗ = , таких, что штрафная функция
{ }0
0
1
( , , ) ( , , ) (( , ), ( , )) 1
i
m
i i i
i i i C
i
S x y u x y E u R x y x y
+
=
= ψ + − ∑ будет точной,
если u u
∗> . Обозначив i i iE E u
∗ ∗= − и учитывая (18), получаем утверждение
теоремы.
Так же как и (12) использование задачи (19) позволяет существенно упро-
стить реализацию схемы декомпозиции. Поскольку задачи (9) и (20) эквива-
лентны, то подход, предложенный в первом разделе, может использоваться для
уточнения штрафных коэффициентов для задачи (20), т.е. для уточнения пара-
метров продолжения iE в функциях ( , , )i
i ix y Eψ .
В заключение необходимо заметить, что значения штрафных коэффициен-
тов, при которых выполняются условия леммы 1, являются завышенными по
сравнению с минимальными значениями, определяемыми теоремами о неглад-
ких штрафных функциях [1–3].
Ю.П. Лаптін
ДЕЯКІ ПИТАННЯ ВИКОРИСТАННЯ НЕГЛАДКИХ ШТРАФНИХ ФУНКЦІЙ
Розгядається підхід, який дозволяє побудувати процедуру автоматичного визначення значень
штрафних коефіцієнтів по ходу роботи оптимізаційного алгоритму. Аналізуються можливості
запропонованого підходу для розробки схем декомпозиції квазіблочних задач оптимізації зі
зв'язуючими змінними.
Ю.П. ЛАПТИН
128 Теорія оптимальних рішень. 2011, № 10
Yu.P.Laptin
SOME QUESTIONS 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. The possibilities of the proposed approach for
the development of decomposition schemes for quasi-block optimization problems with binding
variables are analysed.
1. Shor N. Z. Nondifferentiable Optimization and Polynomial Problems. – London: Kluwer
Academic Publishers, 1998. – 381 p.
2. Пшеничный Б.Н. Метод линеаризации. – М.: Наука, 1983. – 136 с.
3. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программи-
рования .– М.: Наука, 1976. – 191 с.
4. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. – М.: Наука, 1980. –
319 с.
5. Лаптин Ю.П., Лиховид А.П. Использование выпуклых продолжений функций для
решения нелинейных задач оптимизации // Управляющие машины и системы. –
2010. – № 6. – C. 25–31.
6. Лаптин Ю.П., Журбенко Н.Г. Некоторые вопросы решения блочных нелинейных
задач оптимизации со связывающими переменными // Кибернетика и системный
анализ. – 2006. – № 2.– С. 47 – 55.
Получено 25.03.2011
|