Достаточное условие точности двойственных лагранжевых оценок для квадратичных экстремальных задач
Рассматривается общая задача минимизации квадратичной функции на квадратичных ограничениях. Приведено достаточное условие точности двойственной лагранжевой оценки, предложенной Н.З. Шором, для данной задачи....
Збережено в:
| Дата: | 2011 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Назва видання: | Теорія оптимальних рішень |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/46769 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Достаточное условие точности двойственных лагранжевых оценок для квадратичных экстремальных задач / О.А. Березовский // Теорія оптимальних рішень: Зб. наук. пр. — 2011. — № 10. — С. 26-30. — Бібліогр.: 3 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-46769 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-467692013-07-07T03:03:46Z Достаточное условие точности двойственных лагранжевых оценок для квадратичных экстремальных задач Березовский, О.А. Рассматривается общая задача минимизации квадратичной функции на квадратичных ограничениях. Приведено достаточное условие точности двойственной лагранжевой оценки, предложенной Н.З. Шором, для данной задачи. Розглядається загальна задача мінімізації квадратичної функції на квадратичних обмеженнях. Наведено достатню умову точності двоїстої лагранжевої оцінки запропонованої Н.З. Шором. для даної задачі. The general problem of minimizing a quadratic function with quadratic constraints is considered. One proved the sufficient condition for the accuracy of dual Lagrange bound, which proposed by N.Z Shor, for this problem. 2011 Article Достаточное условие точности двойственных лагранжевых оценок для квадратичных экстремальных задач / О.А. Березовский // Теорія оптимальних рішень: Зб. наук. пр. — 2011. — № 10. — С. 26-30. — Бібліогр.: 3 назв. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/46769 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 |
2011 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/46769 |
| citation_txt |
Достаточное условие точности двойственных лагранжевых оценок для квадратичных экстремальных задач / О.А. Березовский // Теорія оптимальних рішень: Зб. наук. пр. — 2011. — № 10. — С. 26-30. — Бібліогр.: 3 назв. — рос. |
| series |
Теорія оптимальних рішень |
| work_keys_str_mv |
AT berezovskijoa dostatočnoeuslovietočnostidvojstvennyhlagranževyhocenokdlâkvadratičnyhékstremalʹnyhzadač |
| first_indexed |
2025-07-04T06:13:42Z |
| last_indexed |
2025-07-04T06:13:42Z |
| _version_ |
1836695814021316608 |
| fulltext |
26 Теорія оптимальних рішень. 2011, № 10
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Рассматривается общая задача
минимизации квадратичной функ-
ции на квадратичных ограничени-
ях. Приведено достаточное усло-
вие точности двойственной ла-
гранжевой оценки, предложенной
Н.З. Шором, для данной задачи.
О.А. Березовский, 2011
ÓÄÊ 519.8
Î.À. ÁÅÐÅÇÎÂÑÊÈÉ
ÄÎÑÒÀÒÎ×ÍÎÅ ÓÑËÎÂÈÅ ÒÎ×ÍÎÑÒÈ
ÄÂÎÉÑÒÂÅÍÍÛÕ ËÀÃÐÀÍÆÅÂÛÕ
ÎÖÅÍÎÊ ÄËß ÊÂÀÄÐÀÒÈ×ÍÛÕ
ÝÊÑÒÐÅÌÀËÜÍÛÕ ÇÀÄÀ×
Рассмотрим общую постановку квадратич-
ной задачи оптимизации:
*
0min ( )f f x= (1)
при ограничениях
( ) 0if x ≤ ,
LE
i I∈ , ( ) 0if x = ,
EQ
i I∈ , (2)
где ( ) , {0}T T LE EQ
i i i if x x K x b x c i I I= + + ∈ ∪ ∪ –
произвольные квадратичные функции в про-
странстве nℜ . С учетом того, что в общем
случае задача (1)–(2) многоэкстремальна и
относится к классу NP-трудных задач, ста-
новится актуальным нахождение оценок для
данной задачи за "приемлемое" (полино-
миальное) время и исследование их точно-
сти. В частности, для получения нижних
оценок *ψ оптимального значения целевой
функции *f задачи (1)–(2) ( * *
fψ ≤ ) акаде-
миком Н.З. Шором был предложен двойст-
венный подход [1, 2], основанный на исполь-
зовании функции Лагранжа:
* *sup ( )
u D U
u f
+∈ ∩
ψ = ψ ≤ ,
где
( ) inf ( , )
nx R
u L x u
∈
ψ = ; (3)
( , ) ( ) ( ) ( )T T
L x u x K u x b u x c u= + + – функция
Лагранжа для задачи (1)–(2), в которой
0
1
( )
m
i i
i
K u K u K
=
= +∑ , 0
1
( )
m
i i
i
b u b u b
=
= +∑ ,
0
1
( )
m
i i
i
c u c u c
=
= +∑ , | | | |LE EQ
m I I= + ;
U
+ – область определения вектора мно-
ДОСТАТОЧНОЕ УСЛОВИЕ ТОЧНОСТИ ДВОЙСТВЕННЫХ ЛАГРАНЖЕВЫХ ОЦЕНОК…
Теорія оптимальних рішень. 2011, № 10 27
жителей Лагранжа mu ∈ℜ , учитывающая наличие ограничений в виде нера-
венств: { : 0, }LE
iU u u i I
+ = ≥ ∈ ;
D – множество переменных mu ∈ℜ , при которых матрица ( )K u положи-
тельно определена.
При u D∈ задача (3) строго выпукла (матрица ( )K u положительно опреде-
лена, и, соответственно, невырождена), т.е. решив систему ' ( , ) 0xL x u = , откуда
1( ) ( ) ( ) / 2x u K u b u
−= − (единственное решение не вырожденной системы), можно
записать
11
( ) ( ) ( ) ( ) ( )
4
T
u b u K u b u c u
−ψ = + =
1
0 0 0 0
1 1 1 1
1
4
T
m m m m
i i i i i i i i
i i i i
b u b K u K b u b c u c
−
= = = =
= + + + + +
∑ ∑ ∑ ∑ . (4)
Функция ( )uψ вогнутая и непрерывно дифференцируемая в области D , а
значит и в области определения D U
+
I (ее градиент вычисляется по формулам
' ( ( )), 1,
iu if x u i mψ = = ).
Исследуем маргинальную функцию ( )uψ , предварительно переписав ее в
следующем виде:
2
0 0
1 1 1
1
( ) ( )( ) / ( )
4
n m m
T
j i i j i i
j i i
u u b u b u c u c
= = =
ψ = − ξ + λ + +
∑ ∑ ∑ , (5)
где
0
1 1
( ) ( ) ( )
m n
T
i i j j j
i j
K u K u u u
= =
+ = λ ξ ξ∑ ∑ – представление квадратичной матрицы
функции Лагранжа с помощью собственных чисел ( )j uλ и собственных векто-
ров ( )j uξ ( 1,j n= ).
Понятно, что оценка * sup ( )
u D U
u
+∈ ∩
ψ = ψ может достигаться либо внутри
множества D , либо когда u стремится к границе положительной
определенности D D∩ . Определим для каждого u D U
+∈ ∩ ( D U
+∩ –
замыкание области определения двойственных переменных) множество
1,
( ) { {1,..., }: ( ) min ( ) 0}j j
j n
J u j n u u
=
= ∈ λ = λ = – множество индексов прямых пере-
менных задачи, которые соответствуют граничным точкам множества D (т.е.
индексы дробных членов в выражении (5), знаменатели которых при данном
u D U +∈ ∩ обращаются в ноль). Причем это множество может быть как пусто
(если u D∈ ), так и состоять из одного или более членов (при \u D D∈ и в зави-
симости от числа кратности min
1,
( ) min ( ) 0
j
j n
u u
=
λ = λ = ).
О.А. БЕРЕЗОВСКИЙ
28 Теорія оптимальних рішень. 2011, № 10
Рассмотрим возможные случаи, которые могут возникать в зависимости от
свойств области определения двойственных переменных.
Случай 1. u D U +∀ ∈ ∩ ( )j J u∃ ∈ такое, что 0
1
( )( ) 0
m
T
j i i
i
u b u b
=
ξ + ≠∑ .
В этом случае при стремлении к нулю знаменателей дробных членов в
выражении (5) хотя бы один соответствующий числитель не стремится к нулю.
Тогда ( )uψ → −∞ при u u→ % для всех \u D D U
+∈ ∩% (для тех u% , у которых
( ) { }J u ≠ ∅% ), либо ( )uψ принимает конечные значения при u D∈ (для u , у ко-
торых ( ) { }J u = ∅ ). То есть для вогнутой задачи * sup ( )
u D U
u
+∈ ∩
ψ = ψ достигается во
внутренней точке области положительной определенности (так как в гранич-
ных точках области положительной определенности функция ( )uψ стремится
к −∞ ). Но для данного случая справедлива следующая лемма.
Лемма 1 [1]. Если * sup ( )
u D U
u
+∈ ∩
ψ = ψ достигается на множестве D , то
* *
fψ = .
Таким образом, в случае 1 оценка является точной ( * *
fψ = ).
Случай 2. u D U
+∃ ∈ ∩ ( )j J u∀ ∈
0
1
( )( ) 0
m
T
j i i
i
u b u b
=
ξ + =∑ .
В данном случае для всех дробных членов в выражении (5) при стремлении
к нулю знаменателей соответствующие числители также стремятся к нулю.
Пусть существуют такие вектор n
p∈ℜ и положительное число 0ε >% , что
для любого (0, )ε∈ ε%
u D U +∀ ∈ ∩ ( )j J u∃ ∈ такое, что 0
1
( )( ) 0
m
T
j i i
i
u b u b p
=
ξ + + ε ≠∑ . (6)
Рассмотрим вспомогательную задачу, которая соответствует исходной с
возмущенной целевой функцией
*
0min( ( ) ( , ))f f x p xε = + ε (7)
при ограничениях
( ) 0if x ≤ , LE
i I∈ , ( ) 0if x = , EQ
i I∈ , (8)
Для этой задачи маргинальная функция будет иметь вид
2
0 0
1 1 1
1
( ) ( )( ) / ( )
4
n m m
T
j i i j i i
j i i
u u b p u b u c u cε
= = =
ψ = − ξ + ε + λ + +
∑ ∑ ∑ .
Тогда в силу условия (6) имеем случай 1, т.е. * *
fε εψ = . Но * * * *
f fε ε≥ ψ ≥ ψ = ,
поскольку при u D∈
( )
2
1
1
( ) ( ) ( ) / ( ) ( )
4
n
T
j j
j
u u u p u uε
=
ψ = ψ − εξ λ ≤ ψ∑ .
ДОСТАТОЧНОЕ УСЛОВИЕ ТОЧНОСТИ ДВОЙСТВЕННЫХ ЛАГРАНЖЕВЫХ ОЦЕНОК…
Теорія оптимальних рішень. 2011, № 10 29
Поскольку * * * * * *( ) ( ) ( , ) ( , )f f x f x p x f p xε ε ε ε ε ε= = + ε ≥ + ε , где *
xε – решение
возмущенной задачи, то * * * * *
( , )p x f f fε εε ≥ − ≥ − ψ , т.е. при 0ε → получаем
* *
fψ = .
Таким образом доказано, что при { }D ≠ ∅ условие (6) является достаточ-
ным для того, чтобы * *
fψ = (в случае 1 вектор p равен, например, нулевому
вектору).
Лемма 2. Если существуют такие вектор p и положительное число 0ε >% ,
что для любого (0, )ε∈ ε%
u D U
+∀ ∈ ∩ ( )j J u∃ ∈ 0
1
( )( ) 0
m
T
j i i
i
u b u b p
=
ξ + + ε ≠∑ ,
то * *
fψ = .
Приведем пример возможного практического применения леммы 2 на сле-
дующей задаче:
* max min( )T T
f x x x x= = − − (9)
при ограничениях
0T T
i ix x b x c+ + ≤ , 1,i m= . (10)
В данном случае
1) известны все собственные векторы матрицы функции Лагранжа – на-
правлены по координатным осям и не зависят от двойственных переменных;
2) собственные числа равны между собой:
1
1
m
j i
i
u
=
λ = − +∑ , 1,j n= .
Для рассматриваемой задачи условие леммы 2 примет следующий вид:
0
1 1
( )( ) ( ) 0
m m
T
j i i i i j
i i
u b u b p u b p
= =
ξ + + ε = + ε ≠∑ ∑ , 1,j n= ,
т.е. все координаты вектора
1
m
i i
i
u b p
=
+ ε∑ не могут одновременно обращаться в
ноль при
1
\ { : 1 0, 0}
m
i
i
u D D U u u u
+
=
∈ ∩ = − + = ≥∑ .
Очевидно, что когда
0 int( { , 1,..., })ico b i m∉ = , (11)
то при p , направленном внутрь области { , 1,..., }ico b i m= , ( \ )u D D U
+∀ ∈ ∩ ус-
ловие леммы 2 выполняется и, следовательно, оценка точная. Отметим, что ко-
гда 0 { , 1,..., }ico b i m∉ = , то условие справедливо даже при 0p = .
В противном случае, когда 0 int( { , 1,..., })ico b i m∈ = , это не всегда так.
О.А. БЕРЕЗОВСКИЙ
30 Теорія оптимальних рішень. 2011, № 10
Например, в задаче
* 2min( )f x= −
при ограничениях
2( 2) 25x + ≤ ,
2( 5) 9x − ≤ ,
оценка * 10.42ψ = − (достигается при * (0.7143,0.2857)u = , *
2.8289x = ) и
* * 9fψ ≠ = − .
Заметим, что полученный результат для задачи (9)–(10) перекликается с
теоремой из работы [3], где данная задача сводилась к задаче
{ }* arg max min{ , 1,..., } | 0, 1,...,T T T
i i i i
i
x b x c i m x x b x c i m= − − = + + ≤ = . (12)
Теорема [3]. Для того, чтобы вектор *x (решение задачи (12)) был решени-
ем задачи (9)–(10), необходимо и достаточно, чтобы 0 { , 1,..., }ico b i m∉ = .
Подобным образом лемму 2 можно применить и для исследования других
случаев.
О.А. Березовський
ДОСТАТНЯ УМОВА ТОЧНОСТІ ДВОЇСТИХ ЛАГРАНЖЕВИХ ОЦІНОК
ДЛЯ КВАДРАТИЧНИХ ЕКСТРЕМАЛЬНИХ ЗАДАЧ
Розглядається загальна задача мінімізації квадратичної функції на квадратичних обмеженнях.
Наведено достатню умову точності двоїстої лагранжевої оцінки, запропонованої Н.З. Шором,
для даної задачі.
O.A. Berezovskyi
THE SUFFICIENT CONDITION FOR THE ACCURACY OF DUAL LAGRANGE BOUNDS IN
QUADRATIC EXTREMAL PROBLEMS
The general problem of minimizing a quadratic function with quadratic constraints is considered.
One proved the sufficient condition for the accuracy of dual Lagrange bound, which proposed by
N.Z Shor, for this problem.
1. Шор Н.З., Стеценко С.И. Квадратичные экстремальные задачи и недифференцируе-
мая оптимизация. – Киев: Наук. думка, 1989. – 208 с.
2. Shor N.Z. Nondifferentiable Optimization and Polynomial Problems. – Dordrecht, Kluwer,
1998. – 394 p.
3. Ненахов Э.И. Решение некоторых оптимизационных задач с квадратичными ограни-
чениями // Теорія оптимальних рішень. – Київ: Ін-т кібернетики ім. В.М. Глушкова
НАН України, 2008. – №7. – С.80–87.
Получено 28.03.2011
|