Комбинированная штрафная функция для построения различных методов решения нелинейных задач условной оптимизации
Для численного решения гладких задач условной оптимизации с нелинейными ограничениями в форме неравенств разработана общая схема аппроксимирующих методов последовательного квадратичного программирования на основе релаксации штрафной функции, содержащей гладкие и негладкие штрафы. С помощью этой схем...
Збережено в:
| Дата: | 2013 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Назва видання: | Теорія оптимальних рішень |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/85040 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Комбинированная штрафная функция для построения различных методов решения нелинейных задач условной оптимизации / Л.А. Соболенко, С.Г. Ненахова, И.А. Шубенкова // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 42-49. — Бібліогр.: 6 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-85040 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-850402015-07-19T03:02:02Z Комбинированная штрафная функция для построения различных методов решения нелинейных задач условной оптимизации Соболенко, Л.А. Ненахова, С.Г. Шубенкова, И.А. Для численного решения гладких задач условной оптимизации с нелинейными ограничениями в форме неравенств разработана общая схема аппроксимирующих методов последовательного квадратичного программирования на основе релаксации штрафной функции, содержащей гладкие и негладкие штрафы. С помощью этой схемы описаны методы негладких штрафов. Для чисельного розв’язання гладких задач умовної оптимізації з нелінійними обмеженнями у формі нерівностей розроблено загальну схему апроксимуючих методів послідовного квадратичного програмування на основі релаксації штрафної функції, що містить гладкі та негладкі штрафи. За допомогою цієї схеми описано методи негладких штрафів. For the numerical solution of smooth problems of the constrained optimization with nonlinear restrictions in inequalities form the general scheme of approximating methods of sequential square programming is worked out on the basis of relaxation of penalty function containing smooth and nonsmooth penalties. By means of this scheme the methods of nonsmooth penalties are described. 2013 Article Комбинированная штрафная функция для построения различных методов решения нелинейных задач условной оптимизации / Л.А. Соболенко, С.Г. Ненахова, И.А. Шубенкова // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 42-49. — Бібліогр.: 6 назв. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/85040 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 |
2013 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/85040 |
| citation_txt |
Комбинированная штрафная функция для построения различных методов решения нелинейных задач условной оптимизации / Л.А. Соболенко, С.Г. Ненахова, И.А. Шубенкова // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 42-49. — Бібліогр.: 6 назв. — рос. |
| series |
Теорія оптимальних рішень |
| work_keys_str_mv |
AT sobolenkola kombinirovannaâštrafnaâfunkciâdlâpostroeniârazličnyhmetodovrešeniânelinejnyhzadačuslovnojoptimizacii AT nenahovasg kombinirovannaâštrafnaâfunkciâdlâpostroeniârazličnyhmetodovrešeniânelinejnyhzadačuslovnojoptimizacii AT šubenkovaia kombinirovannaâštrafnaâfunkciâdlâpostroeniârazličnyhmetodovrešeniânelinejnyhzadačuslovnojoptimizacii |
| first_indexed |
2025-07-06T12:12:14Z |
| last_indexed |
2025-07-06T12:12:14Z |
| _version_ |
1836899562744184832 |
| fulltext |
42 Теорія оптимальних рішень. 2013
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Для численного решения гладких
задач условной оптимизации с не-
линейными ограничениями в фор-
ме неравенств разработана об-
щая схема аппроксимирующих
методов последовательного квад-
ратичного программирования на
основе релаксации штрафной
функции, содержащей гладкие и
негладкие штрафы. С помощью
этой схемы описаны методы не-
гладких штрафов.
© Л.А. Соболенко, С.Г. Ненахова,
И.А. Шубенкова, 2013
ÓÄÊ 519.8
Ë.À. ÑÎÁÎËÅÍÊÎ, Ñ.Ã. ÍÅÍÀÕÎÂÀ, È.À. ØÓÁÅÍÊÎÂÀ
ÊÎÌÁÈÍÈÐÎÂÀÍÍÀß ØÒÐÀÔÍÀß
ÔÓÍÊÖÈß ÄËß ÏÎÑÒÐÎÅÍÈß
ÐÀÇËÈ×ÍÛÕ ÌÅÒÎÄΠÐÅØÅÍÈß
ÍÅËÈÍÅÉÍÛÕ ÇÀÄÀ× ÓÑËÎÂÍÎÉ
ÎÏÒÈÌÈÇÀÖÈÈ
Введение. В 1970 г. в работе [1] академик
Б.Н. Пшеничный предложил итерационный
метод решения общей задачи математиче-
ского программирования, состоящий в ми-
нимизации некоторой нелинейной целевой
функции ( )f x с нелинейными ограниче-
ниями типа неравенств 1( ) 0, 1, ...,
i
g x i m≤ =
и нелинейными ограничениями равенств
( ) 0,ih x = 1 1,...,i m m= + .
Метод оказался очень эффективным, при
весьма слабых предположениях относитель-
но функций задачи. Он нелокально сходится,
а в случае, когда экстремальная точка ле-
жит в вершине криволинейного многогран-
ника, описываемого ограничениями задачи,
он сходится квадратично. В работе [2] полу-
чены оценки скорости сходимости, полно-
стью соответствующие оценкам классиче-
ского градиентного спуска в безусловной оп-
тимизации. Предложенный метод [1] полу-
чил название метода линеаризации. Он отно-
сится к известным аппроксимирующим ме-
тодам последовательного квадратичного
программирования (к. п.). Суть этих методов
состоит в том, что на каждой итерации целе-
вая функция аппроксимируется некоторой
квадратичной функцией, а ограничения ап-
проксимируются линейными функциями.
КОМБИНИРОВАННАЯ ШТРАФНАЯ ФУНКЦИЯ ДЛЯ ПОСТРОЕНИЯ РАЗЛИЧНЫХ МЕТОДОВ ...
Теорія оптимальних рішень. 2013 43
Решения возникшей задачи к. п. в итерационном процессе 1k k k k
x x pα+ = + ,
0,1,...k = определяет направление спуска
k
p , а величина сдвига в этом направ-
лении
k
α определяется из релаксации (убывания) некоторой штрафной функции
( ) ( ) ( )N k k kx f x NF xΦ = + , где N – коэффициент штрафа, а
( ) ( ) ( ) ( ) ( )( )
11 1max 0, ,..., , ,...,k k m k m k m kF x g x g x h x h x+= . При сделанных в [1]
предположениях при k → ∞ ( ) ( ) ( )*min minN x f x f xΦ = = .
В методе линеаризации [1] при аппроксимации ( )f x квадратичной функ-
цией ( ) ( )
1
, ,
2
k k k k
f x x x A x x x x′ − + − − , где ( )f x′ означает градиент ( )f x ,
,x y – скалярное произведение векторов x и y , рассматриваемых как вектор-
столбцы, полагается T
k k
A A E= = , где E – единичная матрица, T – знак транс-
понирования. Однако, когда ( )* *,T
k kA A L x= → λ , где ( )* *,L x λ – функция Ла-
гранжа исходной задачи математического программирования, λ – вектор мно-
жителей Лагранжа исходной задачи, получаем методы типа Ньютона.
Эти методы являются локальными, т. е. сходятся сверхлинейно (квадратич-
но) лишь в некоторой локальной окрестности точки *x с 1.
k
α = Но при 1
k
α =
релаксация ( )N kxΦ не гарантируется (эффект Маратоса) [3] и тем самым сверх-
линейная скорость не достигается. В работе [4] этот момент обходится путем
переключения алгоритма первого порядка вдали от *x на метод Ньютона вблизи
решения. В локальном алгоритме полагают 1,
k
α = а вектор
k
p определяется из
решения системы уравнений, составляющей необходимые и достаточные усло-
вия экстремума, возникающей на каждой итерации задачи к. п. На практике ме-
тод хорошо себя зарекомендовал, однако бывают случаи, когда условия пере-
ключения не всегда точно обеспечивают попадание в локальную область сходи-
мости метода Ньютона. Возможен возврат на метод первого порядка и повтор-
ное переключение на локальный алгоритм.
В данной работе предлагается для выбора
k
α использовать комбинирован-
ную штрафную функцию. Эта штрафная функция обладает достоинствами
функции ( )N xΦ при использовании ее в нелокальных методах и гарантирует
1
k
α = в локальных методах типа Ньютона.
Постановка задачи: найти
{ }min ( ); | ( ) 0, 1,..., ,n
i
x
f f x x R g x i l∗
∈Ω
= Ω = ∈ ≤ = (1)
где ( ),f x ( ),ig x 1,...,i l= – произвольные нелинейные дифференцируемые
функции. Задача рассматривается при следующих предположениях.
1. Градиенты ( )f x′ , ( )ig x′ , 1,...,i l= удовлетворяют условию Липшица.
Л.А. СОБОЛЕНКО, С.Г. НЕНАХОВА, И.А. ШУБЕНКОВА
44 Теорія оптимальних рішень. 2013
2. В любой точке генерируемой последовательности { }kx , которая предпо-
лагается ограниченной, разрешима вспомогательная задача к. п.
( ) ( )
1
min , , ,
2
k k k kf x x x A x x x x
′ − + − −
( ) ( ) , 0i k i k kg x g x x x′+ − ≤ , 1,...,i l= , (2)
где
k
A – симметричная, сильно положительно определенная матрица
2 2
,ka x A x x a x≤ ≤ , 0a > , n
x R∀ ∈ . (3)
Cуществуют такая константа N и множители Лагранжа
k
λ , что
1
1
.
l
k k
k
N
=
λ = λ <∑ (4)
При выполнении этих условий гарантирована нелокальная сходимость
*k
x X→ метода линеаризации, *X – множество точек *x .
Предполагается, что необходимые условия для задачи (1) выполнены в ре-
гулярной форме
( ) ( )* * *
1
0,
l
i
i
f x g x
=
′ ′ ′+ λ =∑
( )* * 0,i
ig xλ = * 0,iλ ≥ 1,..., .i l= (5)
Под решением задачи(1) подразумевается отыскание стационарных точек,
удовлетворяющих (5).
Условия экстремума (необходимые и достаточные) задачи к. п. (2) в ее ре-
шении
k
x имеют вид.
( ) ( )
1
0,
l
i
k k k k i k
i
f x A p g x
=
′ ′+ + λ =∑ ,
k k k
p x x= −
( ) ( ), 0,i
k i k i k k
g x g x p ′λ + = 0,i
k
λ ≥ 1,..., .i l= (6)
Из сравнения (5) и (6) вытекает ряд утверждений, хорошо известных в оп-
тимизации [1 – 5].
Утверждение 1. Равенство 0
k
p = необходимо и достаточно для того, чтобы
*,k
x x= *.k
λ = λ
Утверждение 2. Если выполнены предположения 1, 2 задачи (1), то { }kx и
{ }kp ограниченные последовательности.
Утверждение 3. Если выполнены условия (2) задачи (1), то 0
k
p → тогда и
только тогда, когда *k
x X→ .
Из 0
k
p → , ( *k
x X→ ) вытекает *.k
λ → Λ . ( *Λ – множество множителей *,
iλ
1,...,i l= ).
КОМБИНИРОВАННАЯ ШТРАФНАЯ ФУНКЦИЯ ДЛЯ ПОСТРОЕНИЯ РАЗЛИЧНЫХ МЕТОДОВ ...
Теорія оптимальних рішень. 2013 45
Смешанная штрафная функция имеет вид:
( ) ( ) ( ) ( ) ( )( )
2
1 1
,
2
l l
i
i i
i i
F z f x g x g x
+ +
µγ
= =
γ
= + µ + λ +∑ ∑ ,+λ ∈ Λ
или, что то же самое,
( ) ( ) ( ) ( )
( )
2
1
, ,
2
g x
F z f x g x g x
+
+ +
µγ = + λ + µ + γ (7)
где z – вектор с компонентами x , ,λ ⋅ – эвклидова норма вектора, знак «+»
означает неотрицательность, а ( )g x
+ и ( )g x
− – векторы с компонентами соот-
ветсвенно ( ) ( ){ }max 0; ig x g x
+ = , ( ) ( ){ }min 0; ,ig x g x
− = , 1,..., ,i l= 0,µ ≥ 0γ ≥ –
коэффициенты штрафа. Будем называть µ – недифференцируемым коэффици-
ентом штрафа, γ – дифференцируемым. В точках z +∈Ω × Λ , ( ) ( ),F z f xµγ =
тогда
( ) ( ) *min min .
xz
F z f x f
+ µγ
∈Ω∈Ω×Λ
= =
Из условия (7) следует, что функция ( )F zµγ линейна по ,λ непрерывна по
z , но по z недифференцируема. При этом она дифференцируема по любому
направлению в .n l
R
+
Обозначим
k
z∆ – вектор-столбец с компонентами
k
p и
k k
∆ λ = λ − λ . Всю-
ду предполагается .
k
+λ ∈ Λ
Применяя правило дифференцирования функции максимума [6] и используя
условия дополняющей нежесткости из (7), можно показать, что в любой точке
n
z R
+∈ × Λ функция ( )F zµγ имеет производную по направлению
k
z∆ , опреде-
ляемую выражением
( )
( )
( ) ( )
, ,
k i i
k k k k i k k
k kk
F z
A p p g x
z
µγ
− +
∂
= − + λ + τ
∂∆
∑ ∑
( )( ) ( ) ( ), ,i i i
k i k k i k k k i k
g x g x p g x′τ = µ + γ − ∆λ + ∆λ (8)
где ( ) ( ){ }1,..., 0
i k
k i l g x+ = ∈ ≥ , а ( ) ( ){ }1,..., 0
i k
k i l g x− = ∈ < .
Формула (8) позволяет сформулировать требования к коэффициентам µ и
,γ при которых ( ) 0k kF z zµγ∂ ∂∆ < и гарантируется релаксация по 0α > функ-
ции ( )k kF z zµγ + α∆ вблизи точки
k
z . Критерием релаксации является, например,
неравенство
( )
1 , ,
k
k k k
k
F z
A p p
z
µγ∂
= −ε
∂∆
10 1.< ε < (9)
Л.А. СОБОЛЕНКО, С.Г. НЕНАХОВА, И.А. ШУБЕНКОВА
46 Теорія оптимальних рішень. 2013
Согласно ограничениям задачи (2) имеем
( )( ) ( ) ( )( ) ( ), ,i k i k k i k i kg x g x p g x g x′µ + γ ≤ − µ + γ ( ).i k∈ +
Поскольку ,
k
+λ ∈ Λ то из условий дополняющей нежесткости в (6) следует
( ) ( ), ,
i i
k i k k k i kg x p g x′−∆λ ≤ ∆λ 1,..., ,i l= из (8) для i
k
τ
,i i
k k
bτ ≤ ( )( ) ( )2 ,i i
k i k k i k
b g x g x= −µ − γ + ∆λ ( )i k∈ + (10)
и
( )
( ), , ,
k
k k k k k k
k
F z
A p p g x b
z
µγ −
∂
≤ − + λ +
∂∆
( )
.i
k k
k
b b
+
= ∑
Можно ввести более сильные критерии релаксации функции ( )F zµγ в виде
лемм.
Лемма 1. Пусть выполнены условия 2 задачи (1), { }k
+λ ∈ Λ – ограниченная
последовательность, 1ε и 2ε – произвольные константы из (0; 1), 0γ > произво-
льно. Тогда найдется «пороговое» 0−µ > такое, что при любом −µ ≥ µ для всех
точек
k
z имеет место
( ) ( )1 2 11 ,
k k k k k
b A p p g xε ε µ +≤ − − . (11)
И выполняется неравенство
( )
( ) ( )1 2 1
, , .
k
k k k k k k
k
F z
A p p g x g x
z
µγ + −
∂
≤ −ε − ε µ + λ
∂∆
В отличие от метода линеаризации [1], в котором условие (4) гарантирует
спуск по вектору
k
p прямых переменных, условие (11) обеспечивает релаксацию
функции ( )F zµγ по вектору n l
k
z R
+∆ ∈ прямых и двойственных переменных.
Введем обозначение € € €: ,
k k k k
∆λ ∆λ = λ − λ в котором €
k
+λ ∈ Λ может быть за-
дано разным способом. Рассмотрим { }€ € ,i
k kλ = λ , { }€ min , ,i i i
k k k
λ = λ λ 1,..., ,i l= где
€
k
+λ ∈ Λ – текущая точка итерационного процесса. Очевидно, что €
k
+λ ∈ Λ и
( )€ € .
k k k
+
+∆λ = λ − λ ∈ Λ
Другим способом задания €
k
λ является € .
k k
λ = λ Ясно, что в этом случае
€ 0.
k
∆λ =
Сформулируем аналог леммы 1.
Лемма 2. Пусть выполнены условия 2 задачи (1). Последовательность
{ }k
+λ ∈ Λ произвольна и 0γ ≥ постоянно. Тогда найдется пороговое 0−µ > та-
кое, что при любом −µ ≥ µ для всех точек €
k
z имеет место
( ) ( )1 1 1
€ 1 , ,
k k k k k
b A p p g x
+≤ − ε − ε µ
КОМБИНИРОВАННАЯ ШТРАФНАЯ ФУНКЦИЯ ДЛЯ ПОСТРОЕНИЯ РАЗЛИЧНЫХ МЕТОДОВ ...
Теорія оптимальних рішень. 2013 47
( )
( ) ( )1 1
€
, , ,
€
k
k k k k k k
k
F z
A p p g x g x
z
µγ + −
∂
≤ −ε + µ + λ
∂∆
(12)
где
k
b имеет вид (10).
Ограниченность { }€kλ и { }€k∆λ следует из определения €
k
λ и условия (4).
Неравенство (12) можно назвать правилом выбора коэффициентов µ и ,γ
которые обеспечивают релаксацию ( )F zµγ в точке
k
z по направлению € .
k
z∆
Методы негладкого штрафа
Рассмотрим методы со вспомогательной задачей к.п. (2), (3) и штрафной
функцией ( ) ,F zµγ основанные на изменении только коэффициента штрафа µ
при произвольном постоянном 0.γ ≥ Далее γ не указываем в обозначениях
( )F zµ и других. Опишем k -ю итерацию алгоритма в точке
k
z ( *,
k
x x≠ 0
k
p ≠ ),
0,1,...k = .
Примем ε и 1ε любыми константами из (0; 1), 0 0,µ > 0
n
x R∈ – произволь-
ны, 0γ > – любое фиксированное число.
Шаг 1 (определение
k
p и
k
λ ). Задать матрицу
k k
A A= , удовлетворяющую
(3), найти ,
k
x
k
λ из решения задачи (2), .
k k k
p x x= −
Шаг 2 (спуск по λ и сохранение штрафа 1k k −µ = µ ).
Вычислить { }€ min , ,i i i
k k k
λ = λ λ 1,..., ,i l= и найти { }€€ , ,k k kz x= λ €
k
∆λ =
( )€ ,
k k
+
= λ − λ полагая 0 0
€λ = λ при 0k = . В случае € 0
k
∆λ = принять 1k k −µ = µ и
перейти к шагу 4. В случае € 0
k
∆λ ≠ проверить неравенство (12) для 1k −µ = µ
или, что то же самое, неравенство
( ) ( ) ( ) ( )
2
1 1 1
€2 , 1 , .
k k k k k k k k
g x A p p g x g x
+ + +
−
∆λ ≤ − ε + µ + γ
(13)
Если оно имеет место, то принять 1k k −µ = µ и перейти к шагу 4, при наруше-
нии (13) к шагу 3.
Шаг 3 (вычисление нового
k
µ , переопределение
k
z ,
k
z∆ ). Найти
k
µ как наи-
меньшее из значений 1 2 ,s
k −µ = µ ⋅ 1,...s = , для которого впервые выполняется (12).
В качестве €
k
λ принять
k
λ и соответственно принять новые { }€ , ,
k k k
z x= λ 0.
k
∆λ =
Шаг 4 (определение
k
α ). Найти
k
α как наименьшее из значений 2 ,s−α =
0,1,...s = , для которого впервые выполняется неравенство ( )€ €
k kF z zµ + α∆ ≤
( ) €€ ,k kF z≤ + εαψ 0 1,< ε < (правило Армийо), где µ означает
k
µ и
( ) ( )1
1
€€ , , ,
2
k k k k k k k k
A p p g x g x
+ −ε ψ ≤ − + µ + λ
10 1.< ε <
Вычислить 1
€ € ;
k k k k
z z z+ = + α ∆ 1.k k= + Конец итерации.
Л.А. СОБОЛЕНКО, С.Г. НЕНАХОВА, И.А. ШУБЕНКОВА
48 Теорія оптимальних рішень. 2013
Замечание 1. Шаг 3 возможен только при
k k
λ ≠ λ и после его выполнения
осуществляется переход в точку { },
k k
x λ по прежнему, обозначаемую ˆ
k
z . Это,
однако, не должно вызывать недоразумений, поскольку, во-первых, после завер-
шения шага 3 вычисленные на шаге 2 значения € ,
k
λ ( )€
k k k
+
∆λ = λ − λ больше не
используются на итерации, во-вторых, точек
k
x с растущим
k
µ конечное число.
Замечание 2. Если €
k k
λ = λ (в частности, при 0k = или в точках ˆ
k
z после
завершения шага 3), то € 0
k
∆λ = и неравенство (12) выполняется для любых
0.µ > Поэтому релаксация ( )F zµ в точке { },
k k
x λ гарантирована, спуск в этом
случае осуществляется только вдоль вектора
k
p , а из 1
€ €
k k k k
z z z+ = + α ∆ вытекает
1 .
k k+λ = λ
Нелокальную сходимость алгоритма устанавливает теорема 1.
Теорема 1. Если выполнены условия 1, 2 задачи (1), то при 0k k≥ коэффи-
циент штрафа 0
k
µ = µ > является постоянным, 0
k
α ≥ α > для всех 0,1,...,k =
( 0α > – константа) и 0,
k
p → ( ) 0,kg x
+ → , *,
k
x x→ *.k
λ → Λ
Локальные оценки скорости сходимости дает теорема 2. Они устанавлива-
ются в зависимости от выполнения следующих условий, являющихся вместе с
2 [6] достаточными условиями минимума задачи (1).
Условия А.
А1. Функции ( ),f x ( ) ,g x ( )*i I x∈ выпуклы в окрестности множеств
,Ω которое содержит внутреннюю точку :x ( ) 0ig x < , 1,...,i l= , ( )*I x =
( ){ }1,..., 0 .
i
i l g x= = =
А2. Функции ( ),f x ( ),ig x ( )* ,i I x∈ дважды непрерывно дифференцируе-
мы в окрестности *,x градиенты ( )* ,ig x′ ( )* ,i I x∈ линейно независимы для
всех 0y ≠ таких, что ( )* , 0,ig x y′ = ( ) ( ){ }* * 0i I x i I x
+∀ ∈ = ∈ λ > выполняется
( )* , 0.xxL z x x >
А3. Градиенты ( )* ,ig x′ ( )*I x = ( )* ,i I x∈ линейно независимы и * 0iλ > для
всех ( )* .i I x∈
Теорема 2. Пусть выполнены условия 1, 2 задачи (1). Тогда
1) если имеет место условие А1, то ( ) ( )1
* ,
k k
F z f o k
−∆ = − = % ;k → ∞
2) если *k
x x→ и в точке *x выполнено условие А2, то *,
k
λ → λ *
€ ,
k
→λ λ
€ 0
k
∆λ → и при 0k k≥ справедливы оценки 1 ,
k k
q+∆ ≤ ∆ ,k
k
Cq∆ ≤
* 1 1
k
kx x C q→ ≤ , где ( )0,1q ∈ – константа 1 2
1 1;q q= <
КОМБИНИРОВАННАЯ ШТРАФНАЯ ФУНКЦИЯ ДЛЯ ПОСТРОЕНИЯ РАЗЛИЧНЫХ МЕТОДОВ ...
Теорія оптимальних рішень. 2013 49
3) если *k
x x→ и в точке *x выполнено условие А3, то *,
k
λ → λ *
€ ,λ → λ
€ 0
k
∆λ → и имеет место 1,
k
α =
2
1 * * ,k kx x C x x+ → ≤ → 0.C >
Заключение. Дальнейшее развитие исследований будет направлено на пос-
троение алгоритмов для численного решения нелинейных задач условной опти-
мизации с использованием штрафной функций Fµγ при постоянном µ и изменя-
емом γ (гладкий штраф), а так же при изменении обоих штрафов µ и γ . Кроме
того будут сформулированы и обоснованы теоремы о нелокальной сходимости
алгоритмов и локальных оценках их скорости сходимости.
Л.О. Соболенко, С.Г. Ненахова, І.А. Шубенкова
КОМБІНОВАНА ШТРАФНА ФУНКЦІЯ ДЛЯ ПОБУДОВИ РІЗНИХ МЕТОДІВ
РОЗВ’ЯЗАННЯ НЕЛІНІЙНИХ ЗАДАЧ УМОВНОЇ ОПТИМІЗАЦІЇ
Для чисельного розв’язання гладких задач умовної оптимізації з нелінійними обмеженнями у
формі нерівностей розроблено загальну схему апроксимуючих методів послідовного квадра-
тичного програмування на основі релаксації штрафної функції, що містить гладкі та негладкі
штрафи. За допомогою цієї схеми описано методи негладких штрафів.
L.A. Sobolenko, S.G. Nenakhova, I.A. Shubenkova
COMBINED PENALTY FUNCTION FOR CONSTRUCTION OF DIFFERENT METHODS
FOR SOLVING OF NONLINEAR PROBLEMS OF THE CONSTRAINED OPTIMIZATION
For the numerical solution of smooth problems of the constrained optimization with nonlinear re-
strictions in inequalities form the general scheme of approximating methods of sequential square
programming is worked out on the basis of relaxation of penalty function containing smooth and
nonsmooth penalties. By means of this scheme the methods of nonsmooth penalties are described.
1. Пшеничный Б.Н. Алгоритм для общей задачи математического программирования //
Кибернетика. – 1970. – № 5. – С. 120 – 125.
2. Панин В.М. Методы конечных штрафов с линейной аппроксимацией ограничений. I //
Кибернетика. – 1984. – № 2. – С. 44 – 50. II // Кибернетика. – 1984. – № 4. – С. 73 – 81.
3. Бертсекас Д. Условная оптимизация и методы множителей Лагранжа. – М.: Радио
и связь, 1987. – 399 с.
4. Пшеничный Б.Н., Соболенко Л.А. // Журнал вычислительной математики и математиче-
ской физики. – 1980. – Т. 20, № 3. – С. 605 – 614.
5. Панин В.М., Скопецкий В.В. Нелокальный метод Ньютона для задач выпуклой оптимиза-
ции и монотонных вариационных неравенств // Кибернетика и системный анализ. – 2002.
– № 5. – С. 43 – 64.
6. Поляк Б.Т. Введение в оптимизацию. – М.: Наука, 1983. – 384 с.
Получено 20.03.2013
|