О применении комбинированного метода выпуклого программирования
При решении практических задач оптимизации может быть неизвестно выполняется ли условие Слейтера и есть ли допустимое решение. Предлагаются дополнительные процедуры и настройки комбинированного метода [1], которые делают его поведение предсказуемым в указанных случаях. При выполнении условия Слейтер...
Збережено в:
| Опубліковано в: : | Теорія оптимальних рішень |
|---|---|
| Дата: | 2003 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2003
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84850 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | О применении комбинированного метода выпуклого программирования / В.Н. Кузьменко, В.В. Бойко // Теорія оптимальних рішень: Зб. наук. пр. — 2003. — № 2. — С. 19-24. — Бібліогр.: 8 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859824684499992576 |
|---|---|
| author | Кузьменко, В.Н. Бойко, В.В. |
| author_facet | Кузьменко, В.Н. Бойко, В.В. |
| citation_txt | О применении комбинированного метода выпуклого программирования / В.Н. Кузьменко, В.В. Бойко // Теорія оптимальних рішень: Зб. наук. пр. — 2003. — № 2. — С. 19-24. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | При решении практических задач оптимизации может быть неизвестно выполняется ли условие Слейтера и есть ли допустимое решение. Предлагаются дополнительные процедуры и настройки комбинированного метода [1], которые делают его поведение предсказуемым в указанных случаях. При выполнении условия Слейтера они позволяют генерировать последовательность точек, сходящуюся к решению по допустимой области. Результаты обосновываются.
При розв'язуванні практичних задач оптимізації може бути невідомо чи виконується умова Слейтера і чи існує припустимий розв'язок. Пропонуються додаткові процедури та настройки комбінованого метода [1], які роблять його поведінку передбачуваною для зазначених випадків. При виконанні умови Слейтера вони дозволяють генерувати послідовність точок, що збігається до розв'язку по допустимій області. Результати обґрунтовуються.
In a process of practical optimization problem solving it may be not known is the Slater condition true and does a feasible solution exist. Additional procedures and settings of combination method are proposed to make its behavior predictable in the cases mentioned above. When the Slater condition is true these procedures allow to generate a sequence of points that converges to solution throughout feasible region. The results are proved.
|
| first_indexed | 2025-12-07T15:27:58Z |
| format | Article |
| fulltext |
Теорія оптимальних рішень. 2003, № 2 19
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
При решении практических задач
оптимизации может быть неиз-
вестно выполняется ли условие
Слейтера и есть ли допустимое
решение. Предлагаются дополни-
тельные процедуры и настройки
комбинированного метода [1],
которые делают его поведение
предсказуемым в указанных слу-
чаях. При выполнении условия
Слейтера они позволяют генери-
ровать последовательность то-
чек, сходящуюся к решению по
допустимой области. Результа-
ты обосновываются.
В.Н. Кузьменко, В.В. Бойко,
2003
ÓÄÊ 519.8
Â.Í. ÊÓÇÜÌÅÍÊÎ, Â.Â. ÁÎÉÊÎ
Î ÏÐÈÌÅÍÅÍÈÈ
ÊÎÌÁÈÍÈÐÎÂÀÍÍÎÃÎ ÌÅÒÎÄÀ
ÂÛÏÓÊËÎÃÎ ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈß
В работе [1] описан и обоснован комбиниро-
ванный метод решения общей задачи выпук-
лого программирования. Этот метод исполь-
зует идеи разработанных ранее методов ли-
неаризации [2], отсекающих плоскостей [3],
точных штрафных функций [4] и отличается
простотой в реализации и надежностью в
работе.
Комбинированный метод разработан для
задач с ограничениями, но он также приме-
ним к задачам без ограничений при соответ-
ствующей формулировке последних и в этом
случае совпадает с модифицированным ме-
тодом отсечения [5].
Особенностью комбинированного метода
является то, что последовательность точек,
которая сходится к решению, лежит, как
правило, вне допустимой области задачи.
Однако при решении практических задач
[6] пользователя может интересовать пове-
дение целевой функции в допустимой облас-
ти, тем более что вне допустимой области
целевая функция может быть не определена.
Возможна ситуация, когда в задаче нет до-
пустимого решения. Тогда пользователя ин-
тересует информация, позволяющая "пра-
вильно" скорректировать задачу. Такие зада-
чи возникают, например, при оптимизации
комплексных систем в энергетике.
Ниже предлагается некоторый подход к
использованию комбинированного метода,
который позволяет расширить его примени-
мость и увеличить "полезность" выходной
информации.
В.Н. КУЗЬМЕНКО, В.В. БОЙКО
20 Теорія оптимальних рішень. 2003, № 2
Итак, решается задача
},1,0)(:)({min Mxmjxfxf j
x
∈≤≤≤ , (1)
где j
n
ffRx ,,∈ - выпуклые непрерывные функции, принимающие конечные
значения на M . M заданно системой линейных неравенств и ограничено.
Положим }1:)({max)( mjxfx j
j
≤≤=ϕ .
Пусть в задаче (1) выполнены условия Слейтера: ,0и~ >γ∈∃ Mx т.ч.
γ−≤ϕ )~(x .
Выберем Mx ∈1 , зададим 01 >N , положим }{,2/ 111 xX =γ=ε .
Точка 1+kx , множество 1+kX и значения 11, ++ εkkN определяются на k-м ша-
ге по результату решения задачи
}~{min 21
2
,, 21
ξ+ξ+−
ξξ
kk
x
Nxx ,
kiiii Xxxxxfxf ∈∀ξ≤−′+ ,)),(()( 1 ,
kiiii Xxxxxx ∈∀ξ≤−ϕ′+ϕ ,)),(()( 2 ,
Mxk ∈ε−≥ξ ,2 , (2)
где }:)(min{arg~
kkk XxxFx ∈= – точка минимума штрафной функции
)}(;max{)()( xNxfxF kkk ϕε−+= на kX ; )(),( xxf ϕ′′ – элементы субдиффе-
ренциалов ).(),( xxf ϕ∂∂
Пусть kk
kx 211 ,, ξξ+ – решение задачи (2). Выполним регулировку 1:
}{ 11 ++ ∪= kkk xXX ;
kk NN 21 =+ , если k
k ε−>ξ2 , иначе kk NN =+1 ;
2/1 kk ε=ε + , если 0)( 1 <ϕ +kx , иначе kk ε=ε +1 .
Лемма 1. Описанный процесс при 01 >ε порождает подпоследовательность
точек ...,2,1,)( =jx jp , такую что 0)( )( <ϕ jpx .
Доказательство. Для любого из вышерассматриваемых kε задача (2) соот-
ветствует исходной задаче
},1,)(:)({min Mxmjxfxf kj
x
∈≤≤ε−≤ ,
для которой выполнены условия сходимости комбинированного метода [1].
Следовательно при условии kk ε=ε +1 за конечное число шагов после изменения
ε будет сгенерирована некоторая точка +
εk
x , такая что mjxf
kj ≤≤<+
ε 1,0)( .
Такие точки и образуют указанную подпоследовательность ...,2,1,)( =jx jp .
Лемма доказана.
О ПРИМЕНЕНИИ КОМБИНИРОВАННОГО МЕТОДА ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ
Теорія оптимальних рішень. 2003, № 2 21
Лемма 2. Последовательность kx , ...,2,1=k и подпоследовательность
...,2,1,)( =jx jp , в частности, сходятся к решению задачи (1).
Доказательство. Доказательство проводится аналогично доказательству
сходимости комбинированного метода с учетом того, что 0→εk при ∞→k , а
при 01 =ε предложенный алгоритм совпадает с комбинированным методом.
При решении практических задач может быть неизвестно есть ли у задачи
допустимое решение, а тем более с какой константой выполняется условие
Слейтера. Поэтому вопрос о поведении метода в вырожденных случаях и при
отсутствии допустимого решения, а также разработка алгоритма, который учи-
тывает возможность таких данных, является важным [7].
Положим )}(;max{)( xx ϕε−=ψε и рассмотрим задачу
}:)({min Mxx
x
∈ψε . (3)
Пусть }:)(min{Arg MxxQ ∈ψ= εε , ε∈Qx
* , )( *
xt εε ψ= .
εQ – выпуклое компактное множество решений задачи (3), MQ ⊆ε .
Далее рассмотрим задачу
}:)({min 0Qxxf
x
∈ . (4)
Если 00 =t , то задачи (1) и (4) эквивалентны. Если 00 >t , то задача (1) не
имеет допустимого решения, в то время как задача (4) имеет решение. Поэтому
для решения практических задач предпочтительно применение метода, который
решает задачу (4), оперируя исходной информацией (1).
Возможность применения к задаче (4) тех или иных методов оптимизации
зависит от свойств множества 0Q и поведения функции )(0 xψ в окрестности
множества 0Q . Теория и практика показывает, что наименее зависимым от ука-
занных свойств есть метод штрафных функций, его сходимость доказывается
при наиболее общих предположениях о свойствах задач [8]. Одновременно от-
мечается, что при неограниченном росте множителя kN задача (2) может стать
плохо обусловленной, поэтому желательно использовать "точные" штрафы.
Если задача (1) обладает вышеперечисленными "хорошими" свойствами, то
рост kN ограничен [1]. Если условие Слейтера не выполнено, то независимо от
того существует допустимое решения или нет, может оказаться, что алгоритма
(2) при 01 =ε и без изменения kN сходится при достаточно большом 1N .
Ниже предлагается регулировка элементов 1+kX , 11, ++ εkkN алгоритма (2),
которая используется при условии, что мы не знаем выполняется ли для задачи
(1) условие Слейтера, и позволяет по возможности ограничить рост kN .
Итак, пусть заданы Mx ∈1 ( 0)( 1 >ϕ x ), числа 01 >N , 01 >ε , }{ 11 xX = и
решена задача (2).
На k-м шаге алгоритма выполняется регулировка 2.
В.Н. КУЗЬМЕНКО, В.В. БОЙКО
22 Теорія оптимальних рішень. 2003, № 2
1. Положим }{ 11 ++ ∪= kkk xXX .
2. Если, 0)( 1 <ϕ +kx , то положим 2/)( 11 ++ ϕ−=ε kk x , kk NN =+1 . Условие Слей-
тера выполнено и далее используем регулировку 1.
3. Если k
k ε−>ξ2 , то:
3.1. Решим задачу 2
, 2
min ξ
ξx
,
kiiii Xxxxxx ∈∀ξ≤−ϕ′+ϕ ,)),(()( 2 ,
Mxk ∈ε−≥ξ ,2 . (5)
Пусть k
kx 2,1 ξ+ – ее решение. Положим )}),(()({max 11 ikii
Xx
k
xxxfxf
ki
−′+=ξ +
∈
.
3.2. Если kk
22 ξ<ξ , то положим kk NN 21 =+ , иначе kk NN =+1 .
3.3. Если k
k ε−>ξ2 , то положим }2/;0max{ 21
k
k ξ−=ε + , иначе kk ε=ε +1 .
3.4. Положим }{ 111 +++ ∪= kkk xXX .
4. Если k
k ε−=ξ2 , то положим, kk ε=ε +1 .
Лемма 3. Если для задачи (1) выполняется условие Слейтера, то при регули-
ровке 2 для некоторого 0k будет выполнено 0)( 10
<ϕ +kx .
Доказательство. 1. Пусть 01 ≥ε таково, что 1)(min ε−<ϕ
∈
x
Mx
. Тогда
kk
k ∀ε−=ε−=ξ 12 , выполнено условие Слейтера, регулировка 2 совпадает с ре-
гулировкой 1 следовательно справедлива лемма 1, то есть будет найдена точка
10+kx такая, что 0)( 10
<ϕ +kx .
2. Пусть 01 >ε таково, что 1)(min ε−≥ϕ
∈
x
Mx
. Предположим, что в этом случае
лемма не верна. Тогда регулировка 2 порождает бесконечную последователь-
ность.
Предположим, что начиная с некоторого k ′ kε не изменяется, то есть
kkkk
′≥∀>ε=ε ′ 0 . (Если 1)(min ε−=ϕ
∈
x
Mx
, то 1=′k ). Тогда либо k
k
′ε−=ξ2 , либо
k
k
′ε−=ξ2 kk ′≥∀ , а соответствующие точки 1,1 ++ kk xx являются решением зада-
чи (5) и образуют последовательность, соответствующую методу отсекающих
плоскостей [3], минимизирующую непрерывную функцию )(x
k ′εψ и сходящую-
ся к множеству
k
Q
′ε . Но тогда k
Mx
x
k ′ε
∈
ε−=ψ
′
)(min и найдется точка 10+kx такая,
что 4k .
Для случая 1)(min ε−=ϕ
∈
x
Mx
это противоречие доказывает лемму.
О ПРИМЕНЕНИИ КОМБИНИРОВАННОГО МЕТОДА ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ
Теорія оптимальних рішень. 2003, № 2 23
Для случая 1)(min ε−>ϕ
∈
x
Mx
это противоречит тому, что регулировка 2 исполь-
зуется бесконечно. Следовательно 1+kx и найдется 1k такое, что
1
)(min k
Mx
x ε−≤ϕ
∈
.
Но для такого случая лемма уже доказана.
Полученное противоречие доказывает лемму в целом.
Лемма 4. Если для задачи (1) условие Слейтера не выполнено и в описанном
процессе kN стабилизируется, то есть k ′∃ такое, что kkNN kk
′≥∀= ′ , то по-
следовательность точек kx сходится к решению *
x задачи (4).
Доказательство. Если условие Слейтера не выполнено, то 0→εk , так как
иначе по аналогии с доказательством леммы 3 получим, что 0)(min <ϕ
∈
x
Mx
. Так
как kN стабилизируется, то kk
kk ′≥∀ξ=ξ 22 и точки 1+kx образуют последова-
тельность сходящуюся к множеству 0Q , соответствующую методу отсекающих
плоскостей для функции )(xϕ . Тогда *
22 )(min ξ=ϕ→ξ
∈
x
Mx
k .
Так как выполнено *
22,0 ξ→ξ→ε k
k , kN стабилизировано, то дальнейшее
доказательство проводится аналогично доказательству сходимости комбиниро-
ванного метода [1]. Лемма доказана.
Лемма 5. Если для задачи (1) условие Слейтера не выполнено и в описанном
процессе ∞→kN , то 0→εk , )(min2 x
Mx
k ϕ→ξ
∈
, 01 Qxk →+ .
Доказательство. 0→εk согласно лемме 4. Точки 1+kx образуют последо-
вательность, сходящуюся к множеству 0Q , а *
22 )(min ξ=ϕ→ξ
∈
x
Mx
k . Так как
∞→kN , то значения k
2ξ такие, что kk
22 ξ>ξ , образуют последовательность, для
которой справедливо
k
k
k
kk
k
k
k
kk
k
k
k
kk NxxNxxNxx 21
2
121
2
121
2
1
~~~ ξ+ξ+−≤ξ+ξ+−<ξ+ξ+− +++ .
Так как множество M ограничено, а f непрерывна и конечна на M, то суще-
ствую константы A, B, L такие, что MxxAxx ∈∀<− 21
2
21 , , Bxf
Mx
<
∈
)(max ,
Lxf
Mx
<′
∈
)(max . Тогда k
kkk
NALBA /)2(222 +++ξ<ξ<ξ и следовательно
*
22 ξ→ξk , а последовательность точек 1,1 ++ kk xx сходится к множеству 0Q .
Лемма доказана.
Полученные результаты показывают, что возможно построение алгоритмов
решения оптимизационных задач, которые не предъявляют каких-либо специ-
альных требований к условиям задачи и в тоже время генерируют варианты ре-
В.Н. КУЗЬМЕНКО, В.В. БОЙКО
24 Теорія оптимальних рішень. 2003, № 2
шения, дающие пользователю существенную информацию для анализа задачи.
Именно такие алгоритмы необходимы при создании интеллектуальных инфор-
мационных систем.
Развитие данной работы будет направлено на доказательство сходимости ал-
горитма при использовании в качестве задачи (5) более совершенного модифи-
цированного метода отсечения и проверку гипотезы о сходимости алгоритма (2)
для задач, в которых условие Слейтера не выполнено. Будет исследована эффек-
тивность алгоритмов при решении конкретных практических задачах.
В.М. Кузьменко, В.В. Бойко
ПРО ЗАСТОСУВАННЯ КОМБІНОВАНОГО МЕТОДУ ОПУКЛОГО ПРОГРАМУВАННЯ
При розв'язуванні практичних задач оптимізації може бути невідомо чи виконується умова
Слейтера і чи існує припустимий розв'язок. Пропонуються додаткові процедури та настройки
комбінованого метода [1], які роблять його поведінку передбачуваною для зазначених
випадків. При виконанні умови Слейтера вони дозволяють генерувати послідовність точок,
що збігається до розв'язку по допустимій області. Результати обґрунтовуються.
V.N. Kuzmenko, V.V. Boyko
USING OF CONVEX PROGRAMMING COMBINATION METHOD
In a process of practical optimization problem solving it may be not known is the Slater condition
true and does a feasible solution exist. Additional procedures and settings of combination method
are proposed to make its behavior predictable in the cases mentioned above. When the Slater condi-
tion is true these procedures allow to generate a sequence of points that converges to solution
throughout feasible region. The results are proved.
1. Пшеничный Б.Н., Ненахов Э.И., Кузьменко В.Н. Комбинированный метод решения общей
задачи выпуклого программирования // Кибернетика и системный анализ. – 1998. – № 4. –
С. 121-134.
2. Пшеничный Б.Н. Метод линеаризации. – М.: Наука, 1983. – 136.
3. Kelley J. Tne cutting plane method for solving convex program // SIAM J. – 1960. – 8. – N 4. –
P. 703-712.
4. Бертсекас Д.П. Условная оптимизация и методы множителей Лагранжа. – М.: Радио и
связь, 1987. – 399 с.
5. Пшеничный Б.Н., Ненахов Э.И., Кузьменко В.Н. Модифицированный метод отсечения
для минимизации выпуклой функции // Кибернетика и системный анализ. – 1997. – № 6.–
С. 142-149.
6. Лаптин Ю.П., Журбенко Н.Г. Разработка программных средств оптимизации сложных
технических объектов // Теорія оптимальних рішень. – К.: Ін-т кібернетики ім.
В.М.Глушкова, 2002. – С. 3-12.
7. Поляк Б.Т. Введение в оптимизацию. – М.: Наука,1983. – 384 с.
8. Мину М. Математическое программирование. Теория и алгоритмы. – М.: Наука, 1990. –
488 с.
Получено 09.09.2003
|
| id | nasplib_isofts_kiev_ua-123456789-84850 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-12-07T15:27:58Z |
| publishDate | 2003 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Кузьменко, В.Н. Бойко, В.В. 2015-07-16T14:55:18Z 2015-07-16T14:55:18Z 2003 О применении комбинированного метода выпуклого программирования / В.Н. Кузьменко, В.В. Бойко // Теорія оптимальних рішень: Зб. наук. пр. — 2003. — № 2. — С. 19-24. — Бібліогр.: 8 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/84850 519.8 При решении практических задач оптимизации может быть неизвестно выполняется ли условие Слейтера и есть ли допустимое решение. Предлагаются дополнительные процедуры и настройки комбинированного метода [1], которые делают его поведение предсказуемым в указанных случаях. При выполнении условия Слейтера они позволяют генерировать последовательность точек, сходящуюся к решению по допустимой области. Результаты обосновываются. При розв'язуванні практичних задач оптимізації може бути невідомо чи виконується умова Слейтера і чи існує припустимий розв'язок. Пропонуються додаткові процедури та настройки комбінованого метода [1], які роблять його поведінку передбачуваною для зазначених випадків. При виконанні умови Слейтера вони дозволяють генерувати послідовність точок, що збігається до розв'язку по допустимій області. Результати обґрунтовуються. In a process of practical optimization problem solving it may be not known is the Slater condition true and does a feasible solution exist. Additional procedures and settings of combination method are proposed to make its behavior predictable in the cases mentioned above. When the Slater condition is true these procedures allow to generate a sequence of points that converges to solution throughout feasible region. The results are proved. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень О применении комбинированного метода выпуклого программирования Про застосування комбінованого методу опуклого програмування Using of convex programming combination method Article published earlier |
| spellingShingle | О применении комбинированного метода выпуклого программирования Кузьменко, В.Н. Бойко, В.В. |
| title | О применении комбинированного метода выпуклого программирования |
| title_alt | Про застосування комбінованого методу опуклого програмування Using of convex programming combination method |
| title_full | О применении комбинированного метода выпуклого программирования |
| title_fullStr | О применении комбинированного метода выпуклого программирования |
| title_full_unstemmed | О применении комбинированного метода выпуклого программирования |
| title_short | О применении комбинированного метода выпуклого программирования |
| title_sort | о применении комбинированного метода выпуклого программирования |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84850 |
| work_keys_str_mv | AT kuzʹmenkovn oprimeneniikombinirovannogometodavypuklogoprogrammirovaniâ AT boikovv oprimeneniikombinirovannogometodavypuklogoprogrammirovaniâ AT kuzʹmenkovn prozastosuvannâkombínovanogometoduopuklogoprogramuvannâ AT boikovv prozastosuvannâkombínovanogometoduopuklogoprogramuvannâ AT kuzʹmenkovn usingofconvexprogrammingcombinationmethod AT boikovv usingofconvexprogrammingcombinationmethod |