Использование PNK–метода для решения невыпуклых задач оптимизации
Рассматривается возможность решения невыпуклых задач оптимизации PNK-методом, использующим переменную кусочно-линейную аппроксимацию функций и подбирающим точный штрафной множитель при наличии ограничений. Изучаются условия сходимости метода к локальному оптимуму в случае невыпуклости. Приводятся ре...
Saved in:
| Published in: | Теорія оптимальних рішень |
|---|---|
| Date: | 2012 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/85015 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Использование PNK–метода для решения невыпуклых задач оптимизации / В.Н. Кузьменко, В.В. Бойко // Теорія оптимальних рішень: Зб. наук. пр. — 2012. — № 11. — С. 47-52. — Бібліогр.: 9 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859672424276033536 |
|---|---|
| author | Кузьменко, В.Н. Бойко, В.В. |
| author_facet | Кузьменко, В.Н. Бойко, В.В. |
| citation_txt | Использование PNK–метода для решения невыпуклых задач оптимизации / В.Н. Кузьменко, В.В. Бойко // Теорія оптимальних рішень: Зб. наук. пр. — 2012. — № 11. — С. 47-52. — Бібліогр.: 9 назв. — рос. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | Рассматривается возможность решения невыпуклых задач оптимизации PNK-методом, использующим переменную кусочно-линейную аппроксимацию функций и подбирающим точный штрафной множитель при наличии ограничений. Изучаются условия сходимости метода к локальному оптимуму в случае невыпуклости. Приводятся результаты вычислительных экспериментов.
Розглядається можливість розв’язання неопуклих задач оптимізації PNK-методом, яких використовує змінну частково-лінійну апроксимацію функцій та знаходить точний штрафний множник у разі наявності обмежень. Вивчаються умови збіжності метода до локального оптимуму у випадку, що розглядається. Наводяться результати обчислювальних експериментів.
An opportunity for solving nonconvex optimization problems by PNK-method is considered. This method uses variable piecewise linear approximation for functions and finds exact penalty multiplier for constraints. Convergence conditions to local optimum are studied. Results of computational experiments are added
|
| first_indexed | 2025-11-30T14:03:36Z |
| format | Article |
| fulltext |
Теорія оптимальних рішень. 2012 47
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Рассматривается возможность
решения невыпуклых задач опти-
мизации PNK-методом, исполь-
зующим переменную кусочно-
линейную аппроксимацию функ-
ций и подбирающим точный
штрафной множитель при нали-
чии ограничений. Изучаются ус-
ловия сходимости метода к ло-
кальному оптимуму в случае не-
выпуклости. Приводятся резуль-
таты вычислительных экспери-
ментов.
В.Н. Кузьменко, В.В. Бойко
2012
ÓÄÊ 519.85
Â.Í. ÊÓÇÜÌÅÍÊÎ, Â.Â. ÁÎÉÊÎ
ÈÑÏÎËÜÇÎÂÀÍÈÅ PNK-ÌÅÒÎÄÀ ÄËß
ÐÅØÅÍÈß ÍÅÂÛÏÓÊËÛÕ ÇÀÄÀ×
ÎÏÒÈÌÈÇÀÖÈÈ
Введение. В настоящей работе описываются
особенности применения PNK-метода (ком-
бинированного метода выпуклого програм-
мирования) [1, 2] к задачам с невыпуклыми
функциями. Метод основан на использова-
нии информации в окрестности текущей точ-
ки в виде набора отсекающих плоскостей, а
также на подборе точного штрафного мно-
жителя для задач с ограничениями. Опыт
применение PNK-метода для решения при-
кладных задач показал вычислительную эф-
фективность и надежность данного метода
[1, 3]. Разработана модификация метода, ге-
нерирующая последовательность точек, схо-
дящуюся к решению, по допустимой области
исходной задачи [2], а также модификация,
позволяющая для гладких задач учитывать
информацию об окрестности текущей точки
в виде квадратичной регуляризирующей до-
бавки [4].
В научной литературе методы, основанные
на аналогичных идеях, носят название "bun-
dle method" или "bundle proximal methods".
Рассматриваются в основном методы для
решения задач без ограничений [5–8]. Для
поиска решений невыпуклых задач исполь-
зуются разные подходы. Так в [8] использу-
ется локальная динамическая коррекция за-
дачи, которая делает ее выпуклой в некото-
рой окрестности текущей рекордной точки.
В отличие от названных работ PNK-метод
находит локальные минимумы задач мини-
мизации с ограничениями, используя изме-
няющуюся выпуклую аппроксимацию целе-
вой функции и ограничений.
В.Н. КУЗЬМЕНКО, В.В. БОЙКО
48 Теорія оптимальних рішень. 2012
Изначально PNK-метод разработан для решения задач выпуклого програм-
мирования
},1,0)(:)({min Mxmjxfxf j
x
∈≤≤≤ , (1)
где j
n
ffRx ,;∈ – выпуклые непрерывные функции, принимающие конечные
значения на выпуклом многограннике M .
Поиск решения основан на следующей итерационной процедуре.
Пусть сделано 1−k итераций. В результате получено множество точек kX ,
состоящее из начальной точки Mx ∈1 и 1−k точек kiMxi ,...,2, =∈ – резуль-
татов итераций.
Очередная k-я итерация заключается в решения квадратичной задачи, в ко-
торой минимизируется кусочно-линейная аппроксимация, построенная по точ-
кам множества kX , штрафной функции исходной задачи с учетом регуляризи-
рущей квадратичной добавки, а именно:
}
2
1
{min 21
2
,, 21
ξ+ξ+−
ξξ
kr
kx
Nxx
h
, (2)
kiiii Xxxxxfxf ∈∀ξ≤−′+ ,)),(()( 1 , (3)
kiiii Xxxxxx ∈∀ξ≤−ϕ′+ϕ ,)),(()( 2 , (4)
Mx ∈ξ≤ ,0 2 , (5)
где }:)(min{arg kkr XxxFx ∈= – точка минимума штрафной функции
)}(;0max{)()( xNxfxF kk ϕ+= на kX ; r – индекс этой точки;
}1:)({max)( mjxfx j
j
≤≤=ϕ – обобщенное ограничение; )(),( xxf ϕ′′ – эле-
менты субдифференциалов )(),( xxf ϕ∂∂ ; kN – значение штрафного множителя
на итерации k; kh – параметр, выполняющий роль шагового множителя; пере-
менные 1ξ и 2ξ аппроксимируют соответственно целевую функцию f и функ-
цию ограничений φ с помощью систем неравенств (3) и (4).
Точка 1+kx , найденная в результате решения задачи (2)–(4), добавляется к
множеству точек аппроксимации }{ 11 ++ ∪= kkk xXX .
Штрафной множитель kN увеличивается, если найденное в результате ре-
шения задачи 0*
2 >ξ .
Регулировка шагового множителя kh является наиболее сложной процеду-
рой метода, поскольку этот множитель отвечает за скорость сходимости метода
и точность аппроксимации исходной задачи.
Рассмотрим теперь общий случай, когда среди функций jff , , mj ,...,1=
есть невыпуклые, то есть задача в целом невыпукла.
ИСПОЛЬЗОВАНИЕ PNK-МЕТОДА ДЛЯ РЕШЕНИЯ НЕВЫПУКЛЫХ ЗАДАЧ ОПТИМИЗАЦИИ
Теорія оптимальних рішень. 2012 49
Определение 1. Кусочно-линейная аппроксимация некоторой функции
)(xφ в заданной точке rx на множестве X является корректной, если для лю-
бой точки Xx ∈ )()),(()( rr xxxxx φ≤−φ′+φ .
Определение 2. Кусочно-линейная аппроксимация (2)–(5) задачи (1) на
итерации k есть корректной, если корректной есть аппроксимация функции
)(xFk , а именно: если для }:)(min{arg kkr XxxFx ∈= и для любой точки
kXx ∈ )()),()(()()( rkrkk xFxxxNxfxNxf ≤−ϕ′+′+ϕ+ при 0)( >ϕ x , и при
0)( ≤ϕ x )()),(()( rkr xFxxxfxf ≤−′+ .
Из определения 1 следует, что корректность аппроксимации рассматривает-
ся только по отношению к текущей рекордной точке. При изменении рекордной
точки корректность аппроксимации может нарушиться, что требует изменения
аппроксимации задачи.
В случае невыпуклой задачи для функций f и ϕ будем использовать раз-
личные множества для аппроксимации f
kX и ϕ
kX , причем количество элемен-
тов в каждом множестве может быть меньше, чем итерация k, т.е.
kXkX k
f
k ≤≤ ϕ
, .
Рассмотрим возможные результаты добавления новой точки аппроксима-
ции после итерации метода и изменении параметров работы метода. Пусть те-
кущая аппроксимация задачи (1) есть корректной и в результате решения задачи
(2)–(5) найдена новая точка 1+kx . Включим ее в множества f
kX и ϕ
kX .
Возможны следующие варианты:
1) Новая аппроксимация (2)–(5) задачи есть корректной;
2) Новая аппроксимация не есть корректной;
a) рекордная точка изменилась (новым рекордом может быть 1+kx или
рекордом стала другая точка после увеличения штрафа 1+kN ). В этом
случае есть точки, неверно аппроксимирующие f или ϕ в точке rx .
Например, для f это означает, что )()),(()( rr xfxxxfxf >−′+ .
b) рекордная точка не изменилась. Это означает, что точка 1+kx и(или)
другие точки неверно аппроксимирует f и(или) ϕ в точке rx .
В случае 1) процесс продолжается без удаления точек из f
kX ,
ϕ
kX .
В случае 2) продолжение работы алгоритма может быть построено не-
сколькими способами.
Способ первый. В случай 2a) точки, неверно аппроксимирующие новый ре-
корд, выбрасываются из множеств f
kX и(или) ϕ
kX . В случае 2b) точка 1+kx вы-
брасывается из f
kX и(или) ϕ
kX , а шаговый множитель kh уменьшается.
В.Н. КУЗЬМЕНКО, В.В. БОЙКО
50 Теорія оптимальних рішень. 2012
Такой способ является более простым, но при его реализации вместе с уст-
ранением некорректной аппроксимации теряется информация о значениях
функций в ранее пройденных точках.
Второй способ позволяет исправить некорректность аппроксимации и со-
хранить информацию о значениях функций.
Пусть в точке x для некоторой функции φ выполнено неравенство
)()),(()( rr xxxxx φ>−φ′+φ . Изменим аппроксимацию в точке x таким образом,
чтобы она стала корректной для rx . Для этого найдем минимальный по модулю
вектор g такой, что ∆−φ≤−+φ′+φ )(),)(()( rr xxxgxx , где 0>∆ – параметр,
существенно превосходящий критерий 0>ε точности поиска решения по зна-
чению функции. Получаем ∆−−φ′−φ−φ≤− )),(()()(),( xxxxxxxg rrr . Наи-
меньший по модулю вектор g колинеарен разности xxr − , т.е. )( xxtg r −= ,
где t – искомый параметр. Обозначив правую часть последнего неравенства
0<∆φ
x и найдя t , получим 2)(/)( xxxxg rxr −∆⋅−= φ .
Для обоих предложенных способов построения корректной аппроксимации
невыпуклой задачи возможно нахождение "ложного" минимума, если использо-
вать теже критерии остановки алгоритма, что и для выпуклого случая. Имеется
ввиду следующее.
Среди критериев остановки в PNK-методе есть достижение минимальной
величины смещения на итерации δ≤− +1kr xx и точности аппроксимации ре-
корда ε≤ξ+ξ− )()( *
2
*
1 krk NxF , где 0, >δε – малые параметры.
В случае невыпуклой задачи выполнение этих критериев не гарантирует
приближения к локальному минимуму. (Нетрудно построить примеры, показы-
вающие это). Кусочно-линейная аппроксимация, для которой выполнение кри-
териев остановки означает нахождение локального минимума, должна строиться
на точка, лежащих в окрестности этого минимума.
Поэтому при выполнении указанных критериев изменяется аппроксимация
задачи с целью проверки рекордной точки. А именно: каждое из множеств f
kX
и ϕ
kX изменяется так { }krrk XxxxxX ∈∀−+=′ |)(5.0 , т.е. рекордная точка ос-
тается, а все остальные приближаются к рекордной. В результате либо итераци-
онный процесс может быть продолжен, либо множество точек аппроксимации
снова приближается к рекордной. Локальный минимум считается найденным,
если выполнены критерии останова и точки аппроксимации лежат в некоторой
заданной окрестности рекорда γ≤−
∈∀
r
Xx
xx
k
max для обоих множеств f
kX и ϕ
kX .
ИСПОЛЬЗОВАНИЕ PNK-МЕТОДА ДЛЯ РЕШЕНИЯ НЕВЫПУКЛЫХ ЗАДАЧ ОПТИМИЗАЦИИ
Теорія оптимальних рішень. 2012 51
Результаты вычислительных экспериментов. Вычислительные экспери-
менты проводились с целью демонстрации возможностей PNK-метода при по-
иске минимумов невыпуклых задач оптимизации. В качестве тестовых примеров
были взяты невыпуклые задачи, которые можно найти на сайте программного
продукта AMPL [9]. Результаты вычислений приведены в таблице.
Название
файла задачи
Размерность
задачи,
n
Кол-во пере-
менных
Полученное
решение
Время
решения, с
blend.mod 10 10 16483.87 0.5
cut.mod 10 15 5463.893 0.1
econmin.mod 100 65 67.12048 3.9
iocol2.mod 100 90 478.3789 7.9
net3.mod 1000 300 0.476892 22.6
steel4.mod 1000 700 32901.98 10.3
transp11.mod 5000 100 8.734901 198.5
prod0.mod 5000 3000 3789214. 28.5
Заключение. В результате выполненной работы построен алгоритм нахож-
дения локальных минимумов невыпуклой задачи, основанный на PNK-методе.
Предложены варианты реализации алгоритма. Дальнейшее развитие работы бу-
дет направлено на улучшение эффективности поиска локальных минимумов за-
дач, а также на построение оценок при поиске глобального минимума.
В.М. Кузьменко, В.В. Бойко
РОЗВ’ЯЗАННЯ НЕОПУКЛИХ ЗАДАЧ ОПТИМІЗАЦІЇ PNK-МЕТОДОМ
Розглядається можливість розв’язання неопуклих задач оптимізації PNK-методом, яких вико-
ристовує змінну частково-лінійну апроксимацію функцій та знаходить точний штрафний
множник у разі наявності обмежень. Вивчаються умови збіжності метода до локального оп-
тимуму у випадку, що розглядається. Наводяться результати обчислювальних експериментів.
V.M. Kuzmenko, V.V. Boyko
SOLVING NONCONVEX OPTIMIZATION PROBLEMS BY PNK-METHOD
An opportunity for solving nonconvex optimization problems by PNK-method is considered. This
method uses variable piecewise linear approximation for functions and finds exact penalty multip-
lier for constraints. Convergence conditions to local optimum are studied. Results of computational
experiments are added.
1. Пшеничный Б.Н., Ненахов Э.И., Кузьменко В.Н. Комбинированный метод решения
общей задачи выпуклого программирования // Кибернетика и системный анализ. –
1998. – № 4. – С. 121–134.
В.Н. КУЗЬМЕНКО, В.В. БОЙКО
52 Теорія оптимальних рішень. 2012
2. Кузьменко В.Н., Бойко В.В. О применении комбинированного метода выпуклого
программирования // Теорія оптимальних рішень. – К.: Ін-т кібернетики
ім. В.М. Глушкова НАН України, 2003. – С. 19–24.
3. Бойко В.В., Кузьменко В.Н. Применение комбинированного метода выпуклого про-
граммирования в задачах финансовой математики // Теорія оптимальних рішень. –
К.: Ін-т кібернетики ім. В.М. Глушкова НАН України, 2008. – С. 146–152.
4. Бойко В.В., Кузьменко В.Н. Использование квадратичного приближения функций в
PNK-методе // Теорія оптимальних рішень. – К.: Ін-т кібернетики ім. В.М. Глушкова
НАН України, 2010. – С. 120–125.
5. Fuduli A., Gaudioso M., Giallombardo G. A DC piecewise affine model and a bundling
technique in nonconvex nonsmooth minimization // Optim. Methods Softw. – 19 (1).–
2004. – P. 89–102.
6. Noll D., Prot O., Rondepierre A. A proximity control algorithm to minimize nonsmooth
and nonconvex functions // Pac. J. Optim. – 4 (4). – 2008. – P. 569–602.
7. Hare W., Sagastizabal C. Computing proximal points of nonconvex functions // Math.
Program. – 116 (1-2, Ser. B). – 2009. – P. 221–258.
8. Hare W., Sagastizabal C. A redistributed proximal bundle method for nonconvex optimiza-
tion // SIAM J. Optim. – 20. – 2010. – P. 2442-2473.
9. AMPL Examples – http://www.ampl.com/EXAMPLES/index.html
Получено 13.04.2012
|
| id | nasplib_isofts_kiev_ua-123456789-85015 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-11-30T14:03:36Z |
| publishDate | 2012 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Кузьменко, В.Н. Бойко, В.В. 2015-07-18T12:32:39Z 2015-07-18T12:32:39Z 2012 Использование PNK–метода для решения невыпуклых задач оптимизации / В.Н. Кузьменко, В.В. Бойко // Теорія оптимальних рішень: Зб. наук. пр. — 2012. — № 11. — С. 47-52. — Бібліогр.: 9 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/85015 519.85 Рассматривается возможность решения невыпуклых задач оптимизации PNK-методом, использующим переменную кусочно-линейную аппроксимацию функций и подбирающим точный штрафной множитель при наличии ограничений. Изучаются условия сходимости метода к локальному оптимуму в случае невыпуклости. Приводятся результаты вычислительных экспериментов. Розглядається можливість розв’язання неопуклих задач оптимізації PNK-методом, яких використовує змінну частково-лінійну апроксимацію функцій та знаходить точний штрафний множник у разі наявності обмежень. Вивчаються умови збіжності метода до локального оптимуму у випадку, що розглядається. Наводяться результати обчислювальних експериментів. An opportunity for solving nonconvex optimization problems by PNK-method is considered. This method uses variable piecewise linear approximation for functions and finds exact penalty multiplier for constraints. Convergence conditions to local optimum are studied. Results of computational experiments are added ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Использование PNK–метода для решения невыпуклых задач оптимизации Розв’язання неопуклих задач оптимізації PNK-методом Solving nonconvex optimization problems by PNK-method Article published earlier |
| spellingShingle | Использование PNK–метода для решения невыпуклых задач оптимизации Кузьменко, В.Н. Бойко, В.В. |
| title | Использование PNK–метода для решения невыпуклых задач оптимизации |
| title_alt | Розв’язання неопуклих задач оптимізації PNK-методом Solving nonconvex optimization problems by PNK-method |
| title_full | Использование PNK–метода для решения невыпуклых задач оптимизации |
| title_fullStr | Использование PNK–метода для решения невыпуклых задач оптимизации |
| title_full_unstemmed | Использование PNK–метода для решения невыпуклых задач оптимизации |
| title_short | Использование PNK–метода для решения невыпуклых задач оптимизации |
| title_sort | использование pnk–метода для решения невыпуклых задач оптимизации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/85015 |
| work_keys_str_mv | AT kuzʹmenkovn ispolʹzovaniepnkmetodadlârešeniânevypuklyhzadačoptimizacii AT boikovv ispolʹzovaniepnkmetodadlârešeniânevypuklyhzadačoptimizacii AT kuzʹmenkovn rozvâzannâneopuklihzadačoptimízacíípnkmetodom AT boikovv rozvâzannâneopuklihzadačoptimízacíípnkmetodom AT kuzʹmenkovn solvingnonconvexoptimizationproblemsbypnkmethod AT boikovv solvingnonconvexoptimizationproblemsbypnkmethod |