Экстремальные задачи с коническими ограничениями
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.
Saved in:
| Published in: | Теорія оптимальних рішень |
|---|---|
| Date: | 2006 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2006
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84964 |
| 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: | Экстремальные задачи с коническими ограничениями / Э.И. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 128-135. — Бібліогр.: 7 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859749873165795328 |
|---|---|
| author | Ненахов, Э.И. |
| author_facet | Ненахов, Э.И. |
| citation_txt | Экстремальные задачи с коническими ограничениями / Э.И. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 128-135. — Бібліогр.: 7 назв. — рос. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| 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.
|
| first_indexed | 2025-12-01T23:35:19Z |
| format | Article |
| 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
|
| id | nasplib_isofts_kiev_ua-123456789-84964 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-12-01T23:35:19Z |
| publishDate | 2006 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Ненахов, Э.И. 2015-07-17T17:10:58Z 2015-07-17T17:10:58Z 2006 Экстремальные задачи с коническими ограничениями / Э.И. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 128-135. — Бібліогр.: 7 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/84964 519.8 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. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Экстремальные задачи с коническими ограничениями Extremal problems with cone constraints Article published earlier |
| spellingShingle | Экстремальные задачи с коническими ограничениями Ненахов, Э.И. |
| title | Экстремальные задачи с коническими ограничениями |
| title_alt | Extremal problems with cone constraints |
| title_full | Экстремальные задачи с коническими ограничениями |
| title_fullStr | Экстремальные задачи с коническими ограничениями |
| title_full_unstemmed | Экстремальные задачи с коническими ограничениями |
| title_short | Экстремальные задачи с коническими ограничениями |
| title_sort | экстремальные задачи с коническими ограничениями |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84964 |
| work_keys_str_mv | AT nenahovéi ékstremalʹnyezadačiskoničeskimiograničeniâmi AT nenahovéi extremalproblemswithconeconstraints |