Решение некоторых оптимизационных задач с квадратичными ограничениями
Рассматриваются две оптимизационные задачи на пересечении конечного числа шаров в пространстве Rⁿ. Получены достаточные условия сведения первой задачи к специальной задаче выпуклого программирования. Приводится случай, когда достаточные условия не выполняются. Вторая задача сводится к минимизации кв...
Збережено в:
| Дата: | 2008 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2008
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/12702 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Решение некоторых оптимизационных задач с квадратичными ограничениями / Э.И. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2008. — № 7. — С. 80-87. — Бібліогр.: 5 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860063255720886272 |
|---|---|
| author | Ненахов, Э.И. |
| author_facet | Ненахов, Э.И. |
| citation_txt | Решение некоторых оптимизационных задач с квадратичными ограничениями / Э.И. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2008. — № 7. — С. 80-87. — Бібліогр.: 5 назв. — рос. |
| collection | DSpace DC |
| description | Рассматриваются две оптимизационные задачи на пересечении конечного числа шаров в пространстве Rⁿ. Получены достаточные условия сведения первой задачи к специальной задаче выпуклого программирования. Приводится случай, когда достаточные условия не выполняются. Вторая задача сводится к минимизации квадратичной выпуклой функции на единичном симплексе.
Розглянуто дві оптимізаційні задачі на перетині кінцевого числа куль в Rⁿ. Отримані достатні умови зведення першої задачі до спеціальної задачі опуклого програмування. Описано випадок, коли достатні умови не виконуються. Друга задача зводиться до мінімізації квадратичної опуклої функції на одиничному симплексі.
The two optimization problems on a set, determined by the intersection of a finite collection of balls in Rⁿ is considered. Sufficient conditions of reducing a first problem to special convex programming problem are formulated. A case with violation of the sufficient conditions is proposed. A second problem can be reduced to minimizing a convex quadratic function over the unit simplex.
|
| first_indexed | 2025-12-07T17:05:47Z |
| format | Article |
| fulltext |
80 Теорія оптимальних рішень. 2008, № 7
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Рассматриваются две оптимиза-
ционные задачи на пересечении
конечного числа шаров в про-
странстве
nR . Получены дос-
таточные условия сведения пер-
вой задачи к специальной задаче
выпуклого программирования.
Приводится случай, когда доста-
точные условия не выполняются.
Вторая задача сводится к мини-
мизации квадратичной выпуклой
функции на единичном симплексе.
Э.И. Ненахов, 2008
ÓÄÊ 519.8
Ý.È. ÍÅÍÀÕÎÂ
ÐÅØÅÍÈÅ ÍÅÊÎÒÎÐÛÕ
ÎÏÒÈÌÈÇÀÖÈÎÍÍÛÕ ÇÀÄÀ×
Ñ ÊÂÀÄÐÀÒÈ×ÍÛÌÈ
ÎÃÐÀÍÈ×ÅÍÈßÌÈ
Общая задача вогнутого программирования
может иметь локальные экстремумы на гра-
нице допустимого множества и весьма слож-
но найти ее глобальный экстремум [1]. Это
обстоятельство не дает возможности приме-
нять эффективные алгоритмы, созданные для
решения задач выпуклого программирова-
ния. Исследуемая первая оптимизационная
задача дает возможность ее применения к
так называемой задаче максимальной лока-
лизации [2].
Рассмотрим следующую задачу в про-
странстве nR :
( ) ( ) ( ){ }==≤+ mibxaxxxx ii ,...,1,,,,max
( ) ( ){ },,max bDxxx ∈= (1)
где вектор ( )mbbb ,...,1= , а допустимая об-
ласть ( ) ≠bD ∅.
Определим вогнутую функцию ( ) =ϕ x
( )( )xab ii
mi
,min
1
−=
≤≤
и рассмотрим задачу вы-
пуклого программирования:
( ) ( ) ( ){ }.maxarg bDxxbx ∈ϕ= (2)
Покажем, что задача (1) тесно связана со
следующей задачей вогнутого программиро-
вания:
( ) ( ){ }.,...,1,,,maxarg mibxaxxv ii =≤= (3)
Рассмотрим задачу (1) в более общей фор-
ме (относительно параметра p ):
( ) ( ) ( ){ += xxxxpu ,,maxarg
( ) }mipbxa ii ,...,1,, =+≤+ . (4)
РЕШЕНИЕ НЕКОТОРЫХ ОПТИМИЗАЦИОННЫХ ЗАДАЧ С КВАДРАТИЧНЫМИ…
Теорія оптимальних рішень. 2008, № 7 81
Пусть 2
vp = , поскольку v – допустимый вектор для задачи (4), то
( ) ( )( ) 222
, vvuvu ≥ . (5)
Из определения ( )pu следует, что
( ) ( )( ) ( )( ) ,,...,1,,,
2222
mivbvuavuvu ii =+≤+
или ввиду (5)
( )( ) ( ) ( )( ) mibvuvuvbvua iii ,...,1,,,
2222
=≤−+≤ .
Итак, ( )2
vu – допустимый вектор задачи (3), а значит выполняется
( ) ( )( ) 222
, vvuvu ≤
. (6)
Объединяя неравенства (5) и (6), получаем равенство ( ) ( )( )=
22
, vuvu
2
v= , т. е. оптимальные значения целевых функций задач (3) и (4) совпадают.
Таким образом, относительно параметра p существует решение p уравнения
( ) ( )( ) ppupu =, , причем вектор ( )pu – решение задачи вогнутого квадратич-
ного программирования.
Лемма. Для того, чтобы вектор ( )bx был решением задачи (1), необходимо
и достаточно, чтобы ( )bx принадлежал границе множества ( )bD .
Теорема 1. Для того, чтобы вектор ( )bx был решением задачи (1), необхо-
димо и достаточно, чтобы { }miacoC i ,...,1,0 ==∈ .
Доказательство. Пусть множество индексов ( ) ( ) ( ){ }xxabixI ii ϕ=−= ,: ,
множество векторов ( )
( ) ( )
( )
∈≥λ=λλ−== ∑∑
∈∈
xIiaggxM i
xIi
i
xIi
ii ,0,1,: . Если
при некотором ( )bxb – внутренняя точка ( )bD , то из определения ( )bx следует,
что ( )( )bxM∈0 [3]. Отсюда C∈0 .
Далее, пусть C∈0 . В качестве b возьмем вектор с положительными ком-
понентами ( )1,...,1=b . Так как ( )bDint0∈ , то сопряженный конус к конусу воз-
можных направлений в точке 0=x к множеству ( )bD содержит единственный
нулевой вектор. Однако C∈0 , тогда ( )00 M∈ и, следовательно, ( )bx=0 . Для
данного ( ) ( )bDbxb int∈ и согласно лемме ( )bx не является решением исходной
задачи. Таким образом, ( ) ( )bDbx int∈ , если и только если C∈0 , что доказывает
теорему.
Следствие. Если C∈0 , то задача (1) имеет единственное решение.
Э.И. НЕНАХОВ
82 Теорія оптимальних рішень. 2008, № 7
Теорема 2. Если существует вектор 0≠a , такой, что ( ) =≥ iaa i ,0,
m,...,1= , то найдется решение задачи (2), являющееся решением задачи (1).
Доказательство. Если ( )bx принадлежит границе ( )bD , то утверждение
теоремы очевидно. Пусть ( ) ( )bDbx int∈ . Определим значение параметра 0λ :
( )( ) ( ){ }bDabx ∈λ−λ=λ max0 .
Покажем, что ( )( )abx 0λ− – искомое решение задачи (2). Действительно,
данный вектор принадлежит границе строго выпуклого множества ( )bD и
( )( ) ( )( ) ( )( ) ( )( )bxaabxababx iii
mi
ϕ≥λ+−=λ−ϕ
≤≤
,,min 0
1
0 . Тогда, согласно лемме
( )( )abx 0λ− – искомый вектор.
Далее, рассмотрим преобразование T из nR в ( ) 0,,/: === yxxxxTyRn
при 0=x . Обозначим { } { }0:,0: >=≤= +− ii biGbiG . Поскольку ( ) ( ) 1,, =⋅ yyxx ,
то применение преобразования T к задаче (1) приводит к следующей задаче:
( ) ( ) ( ){ }miyybyayy ii ,...,1,,,1,min =≤+ . (7)
Если решение задачи (7) ненулевое, то оно определяет и решение исходной
задачи. Если ∅=+G , то задача (7) выпуклого программирования. В этом случае
нет необходимости исследовать задачу (7), так как она сводится к предыдущим
результатам. Действительно, можно предположить, что существует
( ) 0, ≠∈ xbDx . Ибо, если ( ) { }0=bD , то можно формально утверждать, что ре-
шение задачи (2) дает решение задачи (1). Ввиду 0≤b для ненулевого x вы-
полняются неравенства ( ) ( ) mixaxx i ,...,1,0,, =≤+ . Докажем, что C∈0 . Если
это не так, то найдутся 1,,...,1,0
1
=λ=≥λ ∑
=
m
i
ii mi , такие, что 0
1
=λ∑
=
m
i
iia . Умно-
жая каждое предыдущее неравенство на iλ и складывая результаты, получаем
( ) 0, ≤xx . Но 0≠x , тогда C∈0 . По теореме 1 любое решение задачи (2) есть
решение задачи (1).
Предположим теперь, что ≠+G ∅. Определим выпуклую функцию
( ) ( )( ) ii
Gi
byay /,1max +=Ψ
+∈
и выпуклое множество
( ) ( ){ }−∈≤+= Giyybyayy ii ,,,1: .
Рассмотрим следующую задачу выпуклого программирования:
( ) ( ){ }Yyyby ∈Ψ= minarg .
Будем считать, что эта задача имеет единственное решение.
Теорема 3. Если ( ) ( )( ) ( )( )bybyby Ψ≥, , то ненулевой вектор
РЕШЕНИЕ НЕКОТОРЫХ ОПТИМИЗАЦИОННЫХ ЗАДАЧ С КВАДРАТИЧНЫМИ…
Теорія оптимальних рішень. 2008, № 7 83
( ) ( ){ }{ }Yyyyyy ∈Ψ= ,,maxminarg* (8)
и вектор ( )**,/** yyyx = являются решением задачи (7) и (1) соответственно.
Доказательство. Из единственности ( )by и условия теоремы вытекает, что
( ) ( )***, yyy Ψ≥ . Тогда ( ) ( )( ) +∈+≥ Gibyayy ii ,/*,1**, , и учитывая Yy ∈* , то
*y – допустимое решение задачи (7). Покажем, что *y – оптимальное реше-
ние. Предположим, что это не так, т. е. для некоторого допустимого решения y
выполняется ( ) ( )**,, yyyy < . Тогда для +∈Gi имеем
( )( ) ( ) ( )**,,/,1 yyyybya ii <≤+ и, следовательно,
( ) ( ){ } ( ) ( ) ( ){ }*,**,max**,,,max yyyyyyyy Ψ=<Ψ .
Данное строгое неравенство противоречит определению *y . Итак, *y –
решение задачи (7). Очевидно, что ( )**,/** yyyx = – решение задачи (1).
Ясно, что для достаточно больших +∈Gibi , , условие теоремы 3 выполняет-
ся. Поэтому для таких ib решение задачи (1) может быть получено в результате
решения задачи выпуклого программирования (8).
Итак, множество векторов b , при которых выполняется условие теоремы 3,
не пусто. Случай, когда вектор b таков, что не выполняется условие теоремы 3
и C∈0 (т. е. не выполняется условие теоремы 1), требует дальнейшего иссле-
дования.
Рассмотрим случай, когда 1+= nm и векторы 111 ,..., ++ −− nnn aaaa – ли-
нейно независимы. Предположим, что нарушено условие теоремы 1 C∈0 , так
что существуют 1,1,...,1,0
1
1
=λ+=≥λ ∑
+
=
n
i
ii ni , такие, что 0
1
1
=λ∑
+
=
n
i
iia .
Введем дополнительные компоненты 1,...,1,0 +=≥ζ nii . Тогда исходную
задачу запишем так:
( ) ( ) ( ){ }0,1,...,1,,,,max ≥ζ+==ζ++ iiii nibxaxxxx . (9)
Умножив каждое полученное равенство в (9) на iλ и сложив результаты,
получим
( ) ∑∑
+
=
+
=
λ+ζλ−=
1
1
1
1
,
n
i
ii
n
i
ii bxx .
Теперь в качестве целевой функции задачи (9) можно взять ∑
+
=
ζλ−
1
1
n
i
ii . Из
каждых n первых ограничений в (9) вычтем последнее ограничение и получим
эквивалентную систему ограничений. Тогда задача (9) преобразуется в следую-
щую эквивалентную форму:
Э.И. НЕНАХОВ
84 Теорія оптимальних рішень. 2008, № 7
( )
=−=ζ−ζ+−ζλ +++
+
=
∑ ,,...,1,,min 111
1
1
nibbxaa ninini
n
i
ii
( ) ( ) }1,...,1,0,,, 111 +=≥ζ=ζ++ +++ nibxaxx innn .
Так как система векторов { }niaa ni ,...,1,1 =− + – линейно независима, то
вектор x разрешим относительно ( )11 ,..., +ζζ= nz , т. е. zGgx += , где g –
вектор, G – невырожденная матрица. Последнюю экстремальную задачу запи-
шем так:
( ) ( )
≥=ζ+++++ζλ +++
+
=
∑ 0,,,min 111
1
1
zbzGgazGgzGg nnn
n
i
ii . (10)
Если ( ) ( ) 11,, ++ =+ nn bgagg , то 0=z – решение задачи (10). Если
( ) ( ) 11,, ++ >+ nn bgagg , то 0=z – не допустимый вектор этой задачи.
Решение задачи выпуклого программирования
( ) ( )
≥≤ζ+++++ζλ +++
+
=
∑ 0,,,min 111
1
1
zbzGgazGgzGg nnn
n
i
i
также будет решением задачи (10).
Наконец, если ( ) ( ) 11,, ++ <+ nn bgagg , то необходимо найти конечное множе-
ство неотрицательных векторов M , полученных как пересечение координатных
осей в пространстве 1+nR векторов z с эллипсоидом
( ) ( ){ }111,,: +++ ≤ζ+++++= nnn bzGgazGgzGgzE .
Вектор z , для которого выполняется
∈ζλ= ∑
+
=
1
1
minarg
n
i
ii Mzz , будет
решением задачи (10), а вектор zGgx += – решением исходной задачи.
Известен способ сведения задачи линейного программирования к задаче
строго вогнутого программирования, для решения которой разработаны различ-
ные эффективные методы [4]. Укажем возможность сведения задачи вогнутого
программирования к задаче строго вогнутого программирования.
В качестве целевой функции задачи вогнутого программирования в nR все-
гда можно брать линейную функцию:
( ) ( ) ( ){ } ( ){ }Dxxcmibxaxxc ii ∈==≤≥ϕ ,max,...,1,,,0,max , (11)
где ( )xϕ – вогнутая функция, множество ( ){ }mibxaRxM ii
n ,...,1,,: =≤∈= – ог-
раниченное.
РЕШЕНИЕ НЕКОТОРЫХ ОПТИМИЗАЦИОННЫХ ЗАДАЧ С КВАДРАТИЧНЫМИ…
Теорія оптимальних рішень. 2008, № 7 85
Обозначим *D множество решений задачи (11) и пусть выполняется усло-
вие Слейтера.
Определение. Задача вогнутого программирования удовлетворяет условию
U , если существует 0* >ε , такое, что для всех *0, ε≤ε<ε , справедливо ра-
венство
( ) ( ){ } ( ){ }*,maxarg,,maxarg* DxxxDxxxxcx ∈−=∈ε−= . (12)
Теорема 4. Для того, чтобы задача вогнутого программирования удовле-
творяла условию U , необходимо и достаточно, чтобы функция Лагранжа задачи
строго вогнутого программирования
( ) ( ) ( ) ( ){ } ( ){ }*,max,0,*,,,max DxxxMxxxcxcxx ∈−=∈≥ϕ≥− (13)
обладала седловой точкой на множестве 2
+× RM .
Доказательство. Необходимость. Пусть справедливо условие U . Для зада-
чи ( ) ( ){ } *0,,,max ε≤ε<∈ε− Dxxxxc , выполнены условия теоремы Куна–
Таккера [4]. Тогда существует число 0>λ , такое, что
( ) ( ) ( ) ( ) ( ) Mxxxxxcxxxc ∈∀λϕ+ε−≥ε− ,,,**,*, ,
или
( ) ( ) ( ) ( )( ) ( ) Mxxxcxcxxxx ∈∀ϕ
ε
λ
+−
ε
+−≥− ,*,,
1
,**, .
Это означает, что существует седловая точка функции Лагранжа задачи (13) [4].
Достаточность. Пусть ( )λ*,x – седловая точка функции Лагранжа задачи
(11), ** Dx ∈ (в силу условия Слейтера):
( ) ( ) ( ) 0,,,*, >λ∈∀λϕ+≥ Mxxxcxc . (14)
Однако по условию теоремы существует седловая точка функции Лагранжа
задачи (13) ( ) 0,0,,*, 1010 ≥λ≥λλλx :
( ) ( ) ( ) ( )( ) ( ) Mxxxcxcxxxx ∈∀ϕλ+−λ+−≥− ,*,,,**, 10 . (15)
В случае 00 =λ из (15) следует ( ){ }Dxxxx ∈−= ,maxarg* и для любого
0>ε выполняется условие ( ) ( ) Dxxxxx ∈∀ε−≥ε− ,,**, . Складывая это нера-
венство с неравенством (14) и учитывая (13), получаем выполнение (12) для
всех 0>ε .
В случае 00 >λ , из (15) следует
( ) ( ) ( ) ( ) ( ) Mxxxxxcxxxc ∈∀ϕλ+ε−≥ε− ,,*,**,**, 2 , (16)
где 0/,/1*0 0120 ≥λλ=λλ=ε< . Пусть 10 ≤< p , умножим (14) на ( )p−1 , а
(16) – на p , сложим полученные неравенства. Тогда для *ε=ε p
( ) ( ) ( ) ( ) ( )( ) ( ) Mxxppxxxcxxxc ∈∀ϕλ−+λ+ε−≥ε− ,1,,**,*, 2 ,
из которого вновь следует (12).
Э.И. НЕНАХОВ
86 Теорія оптимальних рішень. 2008, № 7
Заметим, что общая задача линейного программирования удовлетворяет усло-
вию U [4].
В заключение, рассмотрим задачу поиска центра шара наименьшим радиу-
сом, описанным вокруг пересечения конечного числа шаров в nR . Существова-
ние решения этой задачи обеспечивает
Теорема 5 [3]. Для того, чтобы точка 0x была центром шара наименьшего
радиуса, описанного вокруг компакта A , необходимо и достаточно найти такие
точки niAyi ,...,1,0, =∈ , лежащие на поверхности шара, что 0x принадлежит
симплексу, натянутому на эти точки.
Пусть ( ) ≠
=
I
m
i
ii raB
1
,int ∅, где шар ( )ii raB , задается так:
mirax ii ,...,1,22
=≤− . (17)
Требуется решить оптимизационную задачу относительно переменных ,y r :
rmin
( ) ( )I
m
i
ii ryBraB
1
,,
=
⊆ ,
1, RrRy n ∈∈ . (18)
Умножив каждое неравенство в (17) на ∑
=
=λ=≥λ
m
i
ii mi
1
1,,...,1,0 , и сложив
их получим после некоторых преобразований, что любая точка x , удовлетво-
ряющая системе (17), также удовлетворяет неравенству
( ) ( )λ=−λ−λ≤λ− ∑∑∑
===
222
1
2
1
2
1
rraaax ii
m
i
i
m
i
ii
m
i
ii .
Итак, ( ) ( ) ( )( )I
m
i
ii reBraB
1
,,
=
λλ⊆ , где центр описанного шара
( ) ∑
=
λ=λ
m
i
ii ae
1
, радиус шара – ( )λr , а вектор ( )mλλ=λ ,...,1 принадлежит
единичному симплексу S . Матрица квадратичной функции ( )λ2
r задает опре-
делитель Грама, построенный на векторах miai ,...,1, = . Из линейной незави-
симости этих векторов следует строгая положительность данного определителя.
Естественно, в общем случае решение задачи выпуклого квадратичного
программирования ( ) ( )*min 22 λ=λ
∈λ
rr
S
может не давать точного решения задачи
РЕШЕНИЕ НЕКОТОРЫХ ОПТИМИЗАЦИОННЫХ ЗАДАЧ С КВАДРАТИЧНЫМИ…
Теорія оптимальних рішень. 2008, № 7 87
(18), а будет некоторым его приближением. Если множество ( )ii
m
i
raB ,
1
I
=
окажет-
ся строго внутри построенного шара ( ) ( )( )*,* λλ reB , то необходимо уменьшить
радиус шара ( )*λr , не меняя положение его центра. Для решения задачи (18) в
[5] предложен другой подход, основанный на свойствах квадратичных выпук-
лых отображений. Для случая 1−≤ nm доказано, что шар ( ) ( )( )*,* λλ reB дает
точное решение исходной задачи, т. е. фактически он удовлетворяет требовани-
ям теоремы 5.
Е.І. Ненахов
РОЗВ'ЯЗУВАННЯ ДЕЯКИХ ОПТИМІЗАЦІЙНИХ ЗАДАЧ З КВАДРАТИЧНИМИ
ОБМЕЖЕННЯМИ
Розглянуто дві оптимізаційні задачі на перетині кінцевого числа куль в
nR . Отримані доста-
тні умови зведення першої задачі до спеціальної задачі опуклого програмування. Описано ви-
падок, коли достатні умови не виконуються. Друга задача зводиться до мінімізації квадратич-
ної опуклої функції на одиничному симплексі.
E.I. Nenakhov
SOLUTION OF SOME OPTIMIZATION PROBLEMS WITH QUADRATIC CONSTRAINTS
The two optimization problems on a set, determined by the intersection of a finite collection of
balls in
nR is considered. Sufficient conditions of reducing a first problem to special convex pro-
gramming problem are formulated. A case with violation of the sufficient conditions is proposed. A
second problem can be reduced to minimizing a convex quadratic function over the unit simplex.
1. Horst R., Tuy H. Global optimization (Deterministic approaches). – Berlin: Springer – Verlag,
1990. – 696 p.
2. Dasarthy B., White L. A maximin location problem // Oper. Res. – 1980. – 28, N 6. – P. 1385 –
1401.
3. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. – М.: Наука, 1980. – 319 с.
4. Эрроу К., Гурвиц Л., Удзава Х. Исследования по линейному и нелинейному программи-
рованию. – М.: Изд-во иностр. лит., 1962. – 333 с.
5. Beck A. On the convexity of a class of quadratic mappings and its application to the problemof
finding the smallest ball enclosing a given intersection of balls // J. Glob. Optim. – 2007. –
39, N 1. – P. 113 – 126.
Получено 02. 04. 2008
|
| id | nasplib_isofts_kiev_ua-123456789-12702 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-12-07T17:05:47Z |
| publishDate | 2008 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Ненахов, Э.И. 2010-10-20T10:01:44Z 2010-10-20T10:01:44Z 2008 Решение некоторых оптимизационных задач с квадратичными ограничениями / Э.И. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2008. — № 7. — С. 80-87. — Бібліогр.: 5 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/12702 519.8 Рассматриваются две оптимизационные задачи на пересечении конечного числа шаров в пространстве Rⁿ. Получены достаточные условия сведения первой задачи к специальной задаче выпуклого программирования. Приводится случай, когда достаточные условия не выполняются. Вторая задача сводится к минимизации квадратичной выпуклой функции на единичном симплексе. Розглянуто дві оптимізаційні задачі на перетині кінцевого числа куль в Rⁿ. Отримані достатні умови зведення першої задачі до спеціальної задачі опуклого програмування. Описано випадок, коли достатні умови не виконуються. Друга задача зводиться до мінімізації квадратичної опуклої функції на одиничному симплексі. The two optimization problems on a set, determined by the intersection of a finite collection of balls in Rⁿ is considered. Sufficient conditions of reducing a first problem to special convex programming problem are formulated. A case with violation of the sufficient conditions is proposed. A second problem can be reduced to minimizing a convex quadratic function over the unit simplex. ru Інститут кібернетики ім. В.М. Глушкова НАН України Решение некоторых оптимизационных задач с квадратичными ограничениями Розв'язування деяких оптимізаційних задач з квадратичними обмеженнями Solution of some optimization problems with quadratic constraints Article published earlier |
| spellingShingle | Решение некоторых оптимизационных задач с квадратичными ограничениями Ненахов, Э.И. |
| title | Решение некоторых оптимизационных задач с квадратичными ограничениями |
| title_alt | Розв'язування деяких оптимізаційних задач з квадратичними обмеженнями Solution of some optimization problems with quadratic constraints |
| title_full | Решение некоторых оптимизационных задач с квадратичными ограничениями |
| title_fullStr | Решение некоторых оптимизационных задач с квадратичными ограничениями |
| title_full_unstemmed | Решение некоторых оптимизационных задач с квадратичными ограничениями |
| title_short | Решение некоторых оптимизационных задач с квадратичными ограничениями |
| title_sort | решение некоторых оптимизационных задач с квадратичными ограничениями |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/12702 |
| work_keys_str_mv | AT nenahovéi rešenienekotoryhoptimizacionnyhzadačskvadratičnymiograničeniâmi AT nenahovéi rozvâzuvannâdeâkihoptimízacíinihzadačzkvadratičnimiobmežennâmi AT nenahovéi solutionofsomeoptimizationproblemswithquadraticconstraints |