Экстремальные задачи с коническими ограничениями
We consider nonlinear semidefinite problems. First-order optimality conditions are derived. An algorithm for solving convex programming with cone constraints is proposed. The algorithm globally converges. General parametric problem was investigated.
Gespeichert in:
| Datum: | 2006 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2006
|
| Schriftenreihe: | Теорія оптимальних рішень |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/84964 |
| 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: | Экстремальные задачи с коническими ограничениями / Э.И. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 128-135. — Бібліогр.: 7 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-84964 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-849642015-07-18T03:02:00Z Экстремальные задачи с коническими ограничениями Ненахов, Э.И. We consider nonlinear semidefinite problems. First-order optimality conditions are derived. An algorithm for solving convex programming with cone constraints is proposed. The algorithm globally converges. General parametric problem was investigated. 2006 Article Экстремальные задачи с коническими ограничениями / Э.И. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 128-135. — Бібліогр.: 7 назв. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/84964 519.8 ru Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| description |
We consider nonlinear semidefinite problems. First-order optimality conditions are derived. An algorithm for solving convex programming with cone constraints is proposed. The algorithm globally converges. General parametric problem was investigated. |
| format |
Article |
| author |
Ненахов, Э.И. |
| spellingShingle |
Ненахов, Э.И. Экстремальные задачи с коническими ограничениями Теорія оптимальних рішень |
| author_facet |
Ненахов, Э.И. |
| author_sort |
Ненахов, Э.И. |
| title |
Экстремальные задачи с коническими ограничениями |
| title_short |
Экстремальные задачи с коническими ограничениями |
| title_full |
Экстремальные задачи с коническими ограничениями |
| title_fullStr |
Экстремальные задачи с коническими ограничениями |
| title_full_unstemmed |
Экстремальные задачи с коническими ограничениями |
| title_sort |
экстремальные задачи с коническими ограничениями |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2006 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/84964 |
| citation_txt |
Экстремальные задачи с коническими ограничениями / Э.И. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 128-135. — Бібліогр.: 7 назв. — рос. |
| series |
Теорія оптимальних рішень |
| work_keys_str_mv |
AT nenahovéi ékstremalʹnyezadačiskoničeskimiograničeniâmi |
| first_indexed |
2025-07-06T12:05:12Z |
| last_indexed |
2025-07-06T12:05:12Z |
| _version_ |
1836899120433856512 |
| fulltext |
128 Теорія оптимальних рішень. 2006, № 5
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Рассматриваются задачи нели-
нейного полуопределенного про-
граммирования. Построены усло-
вия оптимальности первого по-
рядка. Для выпуклой задачи с ко-
ническим ограничением предло-
жен алгоритм ее решения, кото-
рый является глобально сходя-
щимся. Исследована общая пара-
метрическая задача.
Э.И. Ненахов, 2006
ÓÄÊ 519.8
Ý.È. ÍÅÍÀÕÎÂ
ÝÊÑÒÐÅÌÀËÜÍÛÅ ÇÀÄÀ×È
Ñ ÊÎÍÈ×ÅÑÊÈÌÈ ÎÃÐÀÍÈ×ÅÍÈßÌÈ
Введение. В настоящей работе изучаются
задачи нелинейного программирования, ко-
гда переменные есть матрицы. Они являются
частным случаем общей задачи оптимиза-
ции. Особенности таких задач состоят в том,
что матрицы имеют некоторые численные
характеристики, которые достаточно слож-
ным образом определяются через их пара-
метры. Это требуется учитывать, в частно-
сти, при построении необходимых и доста-
точных условий экстремума.
Рассмотрим пространство n
M всех мат-
риц A размерностью nn × с вещественными
элементами jia , где i − индекс строки, j −
индекс столбца, njni ...,1,...,1 == . В n
M
введем скалярное произведение матриц
∑=∗
ji
jiji baBA
,
и норму =∗= AAA
2
∑=
ji
jia
,
2
.
Пусть теперь nn
MS ⊂ − пространство
симметричных матриц, nn
SS ⊂+ – конус по-
ложительно определенных симметричных
матриц. По определению n
SA +∈ , если
( ) n
RpppA ∈∀≥ 0, , и писать 0≥A . Матри-
ца n
SA +∈ строго положительно определена
( )0>A , если здесь имеет место строгое не-
равенство при 0≠p .
Конус строго положительно определенных
матриц обозначим n
S ++ .
ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ С КОНИЧЕСКИМИ ОГРАНИЧЕНИЯМИ
Теорія оптимальних рішень. 2006, № 5 129
При рассмотрении оптимизационных задач необходимо исследовать конус,
сопряженный к конусу n
S + :
{ }nnn
SABASBS ++ ∈∀≥∗∈= ,0:* .
Теорема 1 [1]. Имеет место равенство nn
SS ++ =* .
Для матрицы n
SA +∈0 введем конус ( ) ( ){ }0,:00 >λ∈−λ= ++
n
SAAAAK .
Теорема 2. Сопряженный конус к конусу ( )0AK есть ( ) =*0AK
{ }0:0 0 =∗≥= BAB .
Доказательство. Пусть матрица ( )*0AKB ∈ , то из определения сопряжен-
ного конуса
( ) 0,,00 >λ∈∀≥−λ∗ ++
n
SAAAB .
Учитывая, что n
S ++ – внутренность конуса n
S + и любая матрица A из n
S + –
предельная для матриц из n
S ++ , получаем
n
SABABA +∈∗≥∗ ,0 . (1)
Покажем, что 0,0 ≥∀≥∗ ABA . Пусть это не выполняется, т. е. для некото-
рой матрицы 01 ≥A будет 01 <∗ BA . Тогда для любого ( ) 00 1 <∗λ>λ BA , и
при ( ) ∞−→∗λ∞+→λ BA1 . Но 01 ≥λ A для 0>λ , так, что приходим в проти-
воречие с (1). Таким образом, по теореме 1 0≥B .
Далее, полагая в (1) 0=A получаем, что 00 ≤∗ BA . Так как n
SA +∈0 , то в
соответствии с теоремой 1 00 ≥∗ BA . Значит, 00 =∗ BA , что и требовалось до-
казать.
Рассмотрим функции от матриц. Пусть ( )ASA
n ϕ∈ , − некоторая функция
от ее элементов jia ji ≤, . Вначале предположим, что она дифференцируема и
обозначим ji
a ji
ji ≤
∂
ϕ∂
=ϕ′ , . Для произвольного приращения n
SP ∈
выполняется
( ) ( ) ( ) ( ) ( ) ( ) +ϕ′+ϕ=+ϕ′+ϕ=+ϕ ∑∑
=≤
n
i
iiii
ji
jiji pAAPOpAAPA
1
( ) ( ) ( ) ( ) ( ) ( )POPAAPOpApA
ji
jiji
ji
jiji +∗ϕ′+ϕ=+ϕ′+ϕ′+ ∑∑
>< 2
1
2
1
,
где матрица ( )Aϕ′ имеет элементы jiϕ′ на диагонали и jiji ≠ϕ′ ,
2
1
.
Э.И. НЕНАХОВ
130 Теорія оптимальних рішень. 2006, № 5
Пусть теперь ( )Aϕ − выпуклая функция. Тогда существует ее субградиент
{ }
jiji ≤
ϕ′ [2], для приращения n
SP ∈ выполняется
( ) ( ) ( ) ( ) ( ) PAApAAPA
ji
jiji ∗ϕ′+ϕ=ϕ′+ϕ≥+ϕ ∑
≤
,
так, что матрица ( )Aϕ′ − субградиент функции ( )Aϕ в пространстве n
S .
В качестве примера выпуклой функции рассмотрим наибольшее собствен-
ное значение матрицы A
( ) ( )zzAA
Bz
,max
∈
=λ , где { }1: == zzB .
Производная по направлению P от этой функции в точке A [3] есть
( )
( )
( )
( )
( ) PzzzzPPA
T
ABzABz
∗==λ′
∈∈
max,max, ,
где ( ) ( ) ( ){ }zzAABzAB ,: =λ∈= .
Следовательно, субдифференциал функции ( )Aλ [2, 3] есть
( ) ( ){ }ABzzzocA
T ∈=λ∂ : ,
так, что субградиент функции ( )Aλ имеет вид
( ) ( )ABzzzA k
m
k
kk
m
k
T
kkk ∈=γ≥γγ=λ′ ∑∑
== 11
,1,0, .
Заметим, что каждый kz – собственный вектор матрицы A , соответствую-
щий ее максимальному собственному значению. Кроме того, для множества
матриц ранга 1 { } nT
SzzzR +⊂== 1: выполняется
( ) ( ) ( )AWCAzzAA R
RC
T
Bz
=∗=∗=λ
∈∈
maxmax ,
где ( )AWR − опорная функция к множеству R в точке A [3]. Так как R − ком-
пакт, то его выпуклая оболочка { }1:0 =≥== CSCRocQ p замкнута ( CS p −
след матрицы C ). Следовательно,
( ) ( )AWCAA Q
QC
=∗=λ
∈
max ,
а экстремальные точки множества Q есть матрицы из множества R .
Рассмотрим следующую задачу:
( ) ( ){ }n
k SAlkAA +∈=≤ϕϕ ,,...,1,0min 0 , (2)
где функции ( ) ,,...,1,0, lkAk =ϕ – выпуклые, 0A − ее решение. Пусть выполня-
ется условие Слейтера: существует такая матрица n
SA +∈ , что
( ) lkAk ,...,1,0 =<ϕ .
ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ С КОНИЧЕСКИМИ ОГРАНИЧЕНИЯМИ
Теорія оптимальних рішень. 2006, № 5 131
Для построения необходимых и достаточных условий минимума задачи (2)
воспользуемся леммой 4.2 [4]. В качестве выпуклого конуса MK , требуемого
для выполнения условий этой леммы, можно взять конус возможных направле-
ний в точке 0A к множеству n
S + , а в качестве функций ( )Ph k − производные по
направлению P в точке ( ) lkPAA k ,...,1,0,,00 =ϕ′ .
Далее, строим функцию Лагранжа ( ) ( )∑
=
ϕ=
l
k
kk AuuAL
0
, и матрицу
( ) ( )∑
=
ϕ′=′
l
k
kk AuuAL
0
, , где ( )Akϕ′ − некоторый субградиент функции ( )Akϕ .
Тогда согласно упомянутой лемме найдутся такие числа ku , не все равные ну-
лю, что
( ) ( )*, 00 AKuAL ∈′ , (3)
( ) lkulkAu kkk ,...,1,0,0;,...,1,00 =≥==ϕ . (4)
В силу теоремы 2 из включения (3) следует, что
( ) ( ) 0,,0, 000 =∗′≥′ AuALuAL . (5)
Поскольку выполняется условие Слейтера, то множитель 10 =u .
Теорема 3. Для того, чтобы матрица 0A была решением задачи (2) необхо-
димо и достаточно, чтобы выполнялись условия (4), (5).
Исследуем общую параметрическую задачу. Предположим, что элементы
матрицы A зависят от вектора ( ) ( ){ } ,,...,1,,...,1, njnixaxARx ji
q ===∈
( ) ( )xaxa ijji = . Пусть jia − непрерывно дифференцируемые функции x ,
jia′ − вектор с компонентами qk
x
a
k
ji
,...,1, =
∂
∂
. Обозначим
,
∂
′∂
=
∂
∂
k
ji
k x
a
x
A
njni ,...,1,,...,1 == . Теперь для q
Rp ∈ определим
( ) ( ) ( ) ( )( ){ }
jiji
t
pxa
t
xAptxA
pxA
,0
,lim, ′=
−+
=′
+→
.
Тогда для функции ( ) ( )( )zzxAx
Bz
,max
∈
=ϕ производная по направлению p в точ-
ке x будет
Э.И. НЕНАХОВ
132 Теорія оптимальних рішень. 2006, № 5
( ) ( ) ( )
( )( )
( )( ) ( )( )
=
−+
=
ϕ−+ϕ
=ϕ′
+→∈+→ t
zzxAzzptxA
t
xptx
px
txABzt
,,
limmaxlim,
00
( )( )
( )( )
( )( )
( ) ( )pxAzzzzpxA
T
xABzxABz
,max,,max ′∗=′=
∈∈
,
где ( )( ) ( ) ( )( ){ }zzxAxBzxAB ,: =ϕ∈= .
Общая параметрическая задача имеет следующий вид:
( ) ( ) ( ) ( ){ }qn
kk RxSxAlkxmkxx ∈∈=≤ϕ−−==ϕϕ + ;;,...,1,0;1,...,,0min 0 . (6)
Пусть для ( )xk kϕ< 0 − гладкая функция, ( ) ( )pxpxh kk ,, ϕ′= . Для 0≥k
в решении x задачи (6)
( )( ) ( )
( )pxh
t
xtoptx
k
kk
t
,lim
0
≤
ϕ−++ϕ
+→
,
где ( )pxh k , − непрерывная, выпуклая и положительно однородная функция по
( ) 0/, →ttop при 0+→t .
Кроме того, обозначим ( )xkϕ∂ субдифференциал выпуклой по p функции
( )pxh k , при ( ) ( ){ }( )xxp kk ϕ′=ϕ∂= 0 , ,0<k а вектор q
k
R
x
A
U
x
A
U ∈
∂
∂
∗=
∂
∂
∗ .
Тогда справедлив следующий результат.
Теорема 4. Для того, чтобы точка x была решением задачи (6), необходи-
мо, чтобы нашлись такие не все равные нулю числа lmku k ,...,, −= и матрица
n
SU +∈ , что
( ) ;0,0;0,0 ≥≥>=ϕ kukxu kkk
( ) ( )∑
−= ∂
∂
∗=ϕ′=∗
l
mk
kk
x
A
UxuxAU ;0 ,
где ( ) ( )xx kk ϕ∂∈ϕ′ .
В линейном случае ( ) ( ) ( ) ∑
=
+==ϕ
q
k
kk AxAxAxcx
1
00 ,, точка *x удовлетво-
ряет условию оптимальности, если найдется такое n
SU +∈ , что
( ) 0;...,1,
1
0 =∗+∗=∗= ∑
=
∗
k
q
k
kkk AUxAUqkAUс .
ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ С КОНИЧЕСКИМИ ОГРАНИЧЕНИЯМИ
Теорія оптимальних рішень. 2006, № 5 133
Замечание 1. Пусть в задаче (6) отсутствуют функциональные ограничения,
а ( )xA − положительное полуопределенное выпуклое ( )xevnocdsp − отобра-
жение, т.е.
( ) ( ) ( ) ( )( ) [ ]1,0,,,11 ∈∈∀∈−+−−+ + tRyxSytxtAyAtxAt
qn .
Для случая, когда целевая функция и ( )xA достаточно гладкие на q
R необ-
ходимые условия минимума первого и второго порядка построены в [5]. При
этом условия первого порядка вытекают из теоремы 4.
Для решения задачи (2) построим алгоритм, основанный на комбинации
метода линеаризации и метода отсекающих гиперплоскостей. Для этого опреде-
лим выпуклую функцию ( ) ( )AA k
lk
ϕ=ϕ
≤≤1
max . Тогда задача (2) эквивалентна
задаче
( ) ( ){ }n
SAAA +∈≤ϕϕ ,0min 0 .
Введем теперь штрафную функцию ( ) ( ) ( ){ }xAA ϕα+ϕ=Φα ,0max0 и рассмот-
рим экстремальную задачу
( ){ } ( ) ( ){ }nn
SAAASAA ++α ∈≥ξξ≤ϕξ≤ϕξα+ξ=∈Φ ,0,,minmin 221021 . (7)
Пусть, по прежнему, 0A − решение задачи (2), ku − ее множитель Лагранжа.
Лемма 1. Если число α достаточно велико
>α ∑
=
l
k
ku
1
, то решение задачи
(7) есть ( ) 0,, 20010 =ξϕ=ξ AA .
Рассмотрим вспомогательную задачу. Исходная матрица n
SA +∈1 и число
1α заданы. Начальное множество 1X состоит из этой единственной матрицы.
Пусть на j –й итерации алгоритма построено множество { }jsAX sj ,...,1, == ,
число jj A,α − точка минимума ( )AαΦ на jX . Следующее множество 1+jX и
число 1+α j строятся по такому правилу. Решаем вспомогательную задачу
21
2
2
1
min ξα+ξ+− jjAA ,
( ) ( ) ( ) jsAAAA sss ,...,1,100 =ξ≤−∗ϕ′+ϕ ,
( ) ( ) ( ) jsAAAA sss ,...,1,2 =ξ≤−∗ϕ′+ϕ ,
n
SA +∈≥ξ ,02 . (8)
Пусть
1
2
1
11 ,,
++
+ ξξ jj
jA − решение задачи (8), полагаем множество
{ } jjjjj AXX α=α= +++ 2, 111 U при ,0
1
2 >ξ +j
иначе jj α=α + 1 .
Э.И. НЕНАХОВ
134 Теорія оптимальних рішень. 2006, № 5
Лемма 2. Начиная с некоторого достаточно большого j индуцируемая ал-
горитмом jα будет константой α .
В силу выпуклости функций 0ϕ и ϕ при ( ) =ξϕ=ξ= 201 ,, jj AAA
( ){ }jAϕ= ,0max все неравенства в (8) выполняются, поэтому для матрицы
jjj AAP −= ++ 11 имеет место оценка
( ) ( )j
j
j
jj AP
j 21
2
1
2
1
ξα+ξ−Φ≤ α+ .
Отсюда, согласно лемме 2 для достаточно больших j
( ) ( )jj
jj AP
j 21
2
1
2
1
ξα+ξ−Φ≤ α+ .
Но правая часть этого неравенства при ∞→j (как и
j
2ξ ) стремится к нулю.
Следовательно, 0lim =
∞→
j
j
P . Используя данное равенство, аналогично схеме до-
казательства [6], можно показать, что последовательность { }jA сходится к ре-
шению задачи (2).
Замечание 2. Для случая, когда в задаче (2) функции непрерывно диффе-
ренцируемые в [7] построен алгоритм, близкий к вышеописанному.
Заключение. В работе исследованы экстремальные задачи, в которых пе-
ременными являются симметричные матрицы. Условие положительной опреде-
ленности существенно усложняет получение необходимых (и достаточных) ус-
ловий экстремума. Дальнейшее развитие данной работы будет направлено на
построение необходимых условий экстремума второго порядка.
Е.І. Ненахов
ЕКСТРЕМАЛЬНІ ЗАДАЧІ З КОНІЧНИМИ ОБМЕЖЕННЯМИ
Розглядаються задачі нелінійного напіввизначеного програмування. Побудовані умови опти-
мальності першого порядку. Для опуклої задачі з конічним обмеженням запропоновано алго-
ритм її розв′язку, який є глобально збіжним. Досліджена загальна параметрична задача.
E.I. Nenakhov
EXTREMAL PROBLEMS WITH CONE CONSTRAINTS
We consider nonlinear semidefinite problems. First-order optimality conditions are derived. An al-
gorithm for solving convex programming with cone constraints is proposed. The algorithm globally
converges. General parametric problem was investigated.
1. Fletcher R. Semidefinite matrix constraints in optimization // SIAM J. Control Optim. −
1985. − 23. − P. 493–513.
ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ С КОНИЧЕСКИМИ ОГРАНИЧЕНИЯМИ
Теорія оптимальних рішень. 2006, № 5 135
2. Шор Н.З. Методы минимизации недифференцируемых функций и их применение. −
Киев: Наук. думка, 1979. − 199 с.
3. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. − М.: Наука, 1980. −
319 с.
4. Пшеничный Б.Н. Необходимые условия экстремума. − М.: Наука, 1969. − 151 с.
5. Shapiro A. First and second order analysis of nonlinear semidefinite programs // Math.
progr. − 1997. − 77. − P. 301 − 320.
6. Пшеничный Б.Н., Ненахов Э.И., Кузьменко В.Н. Комбинированный метод решения
общей задачи выпуклого программирования // Кибернетика и системный анализ. −
1998. − № 4. − С. 121 − 133.
7. Kanzow C., Nagel C., Kato H., Fukushima M. Successive linearization methods for nonlinear
semidefinite programs // Computational Optim. And Appl. − 2005. − 31. − P. 251 − 273.
Получено 31.05.2006
|