Гарантирующие и оптимистические решения задач целочисленной оптимизации с выпуклыми квадратичными функциями ограничений
The paper studies complex integer optimization problems with inexact coefficients of linear objective function and convex quadratic function of constraints. Exact and approximate decomposition methods are developed and proved for search of guaranteeing and optimistic solutions to such problems. The...
Saved in:
| Published in: | Теорія оптимальних рішень |
|---|---|
| Date: | 2006 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2006
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84952 |
| 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. — С. 39-47. — Бібліогр.: 9 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860200779498913792 |
|---|---|
| author | Семенова, Н.В. |
| author_facet | Семенова, Н.В. |
| citation_txt | Гарантирующие и оптимистические решения задач целочисленной оптимизации с выпуклыми квадратичными функциями ограничений / Н.В. Семенова // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 39-47. — Бібліогр.: 9 назв. — рос. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | The paper studies complex integer optimization problems with inexact coefficients of linear objective function and convex quadratic function of constraints. Exact and approximate decomposition methods are developed and proved for search of guaranteeing and optimistic solutions to such problems. The paper proposes some classes of uncertainty sets that describe input data of such problems.
|
| first_indexed | 2025-12-07T18:10:19Z |
| format | Article |
| fulltext |
Теорія оптимальних рішень. 2006, № 5 39
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Исследованы сложные задачи це-
лочисленной оптимизации с не-
точно заданными коэффициен-
тами линейной целевой функции и
выпуклых квадратичных функций
ограничений. Построены и обос-
нованы точные и приближенные
декомпозиционные методы поис-
ка гарантирующих и оптими-
стических решений таких задач.
Рассмотрены некоторые классы
множеств неопределенности, опи
сывающих исходные данные этих
задач.
Н.В. Семенова, 2006
ÓÄÊ 519.8
Í.Â. ÑÅÌÅÍÎÂÀ
ÃÀÐÀÍÒÈÐÓÞÙÈÅ
È ÎÏÒÈÌÈÑÒÈ×ÅÑÊÈÅ ÐÅØÅÍÈß
ÇÀÄÀ× ÖÅËÎ×ÈÑËÅÍÍÎÉ
ÎÏÒÈÌÈÇÀÖÈÈ Ñ ÂÛÏÓÊËÛÌÈ
ÊÂÀÄÐÀÒÈ×ÍÛÌÈ ÔÓÍÊÖÈßÌÈ
ÎÃÐÀÍÈ×ÅÍÈÉ
Введение. При решении ряда оптимиза-
ционных задач, которые возникают на прак-
тике, приходится учитывать различные фак-
торы неопределенности и случайности: не-
точность входной информации, неадеква-
тность математических моделей реальным
процессам, ошибки округления, погрешность
вычислений и др. Современная теория и
практика оптимизации строятся на основе
классической постановки оптимизационных
задач, которая предполагает, что все данные
заданы точно. Но для большого числа диск-
ретных оптимизационных задач, возникаю-
щих, например, в статистике (анализ данных
и надежность), биологии (молекулярная био-
логия, генетика, анализ ДНК), физике (физи-
ка высоких энергий, рентгеновская кристал-
лография), криптографии (конструирование
помехозащищенных кодов), математике, по-
литике, социальных науках (управление сис-
темами медицинского обслуживания, обра-
зования, социальной защиты), такая поста-
новка является неудовлетворительной. Ис-
ходные данные: целевая функция и допусти-
мая область могут изменяться в процессе оп-
тимизации. Более того, по словам академика
В.М. Глушкова [1], в их целенаправленном
изменении заключается основная содержа-
тельная сущность процесса оптимизации для
рассматриваемого класса задач.
Продолжая исследования, представленные в
работах [2–6], в этой статье изучаются цело-
Н.В. СЕМЕНОВА
40 Теорія оптимальних рішень. 2006, № 5
численные оптимизационные задачи с линейной целевой функцией и выпуклы-
ми квадратичными функциями ограничений в условиях неопределенности дан-
ных. Разработаны и обоснованы точные и приближенные декомпозиционные
методы нахождения гарантирующих и оптимистических решений этих задач.
Рассмотрены некоторые классы множеств неопределенности, описывающих ис-
ходные данные указанных задач.
1. Постановка задачи. Задача целочисленной оптимизации с выпуклыми
квадратичными ограничениями имеет следующий вид:
{ }{ }max , | ( ) , , 0, 1,...,i i i i mc x f x D x x q x b i N m= + + ≤ ∈ = , (1)
где вектор решений n
x Z∈ ; n
Z – множество n–мерных целочисленных векторов
из Rn
; параметры с∈R
n
, b∈R
m
, ,n n n
i iq R D R
×∈ ∈ ; 0iD f (то есть являются сим-
метричными неотрицательно определенными матрицами) для всех i∈Nm.
Формулировка (1) допускает, что данные о векторе c и квадратичных
функциях ограничений ( ), ,i mf x i N∈ известны точно. Однако на практике эти
параметры оцениваются с помощью данных, которые содержат результаты по-
мех, возмущений, ошибок измерений и различные виды неопределенностей.
О них известны лишь множества возможных значений, а статистические харак-
теристики отсутствуют. Поскольку задачи целочисленной оптимизации, как
правило, чувствительны к возмущениям параметров, ошибки входных данных
имеют тенденцию влиять на решения этих задач и часто приводят к результатам,
далеким от оптимальных.
Целочисленную оптимизационную задачу поиска гарантирующих решений
с выпуклыми квадратичными функциями ограничений в условиях неточно за-
данных данных можно представить в виде
max{min{ ,c x | c ∈C}| x∈ 1X }, (2)
соответственно задачу поиска оптимистических решений с управляемыми дан-
ными представим в виде
max{max{ ,c x | c ∈C}| x∈ 2X }, (3)
где 1X = {x∈Z
n
| fi(x) ≤ 0 ∀ fi∈Fi, i∈Nm }; 2X = {x∈Z
n
| ∃ fi∈Fi fi(x) ≤ 0, i∈Nm },
c∈R
n
; C – выпуклое замкнутое множество из Rn
; ( ) , ,i i if x D x x q x= + +
0;ib+ ≤ Fi – множество выпуклых квадратичных функций в R
n
, mi N∈ .
Оптимальным решением задачи (2) (соответственно задачи (3)) является па-
ра ( ,с x ) (( xc , ) задачи (3)), элементы которой c ∈C, x ∈ 1X ( c ∈C, x ∈ 2X )
удовлетворяют условию
〈 c,x 〉 min{ , | } min{ , | }c x c C c x c C= 〈 〉 ∈ ≥ 〈 〉 ∈ , (4)
( , c x〈 〉 mах{ , | } mах{ , | }c x c C c x c C= 〈 〉 ∈ ≥ 〈 〉 ∈ ) (5)
для всех (c,x), таких, что x∈ )(, 21 XxX ∈ .
ГАРАНТИРУЮЩИЕ И ОПТИМИСТИЧЕСКИЕ РЕШЕНИЯ ЗАДАЧ ЦЕЛОЧИСЛЕННОЙ …
Теорія оптимальних рішень. 2006, № 5 41
Если решение ( ,c x ) задачи (2) (соответственно ( xc , ) задачи (3)) существу-
ет, то оно является гарантирующим (оптимистическим) в том понимании, что
, , 0i i iD x x q x b+ + ≤ ∀ ( ), , ,i i i i mD q b S i N∈ ∈ ,( ∃ ( ), , :i i i iD q b S∈
, , 0i i iD x x q x b+ + ≤ , mNi∈ ) и ∀x∈ 1 2( )X x X∈ выполняется условие (4) − (5).
Задание множеств неопределенности С и Fi существенно влияет на степень
сложности сопутствующих задач оптимизации при построении оптимального
решения. Следует отметить, что для некоторых классов множеств неопределен-
ности задачи целочисленного линейного, квадратичного и полуопределенного
программирования легко сводятся к стандартным оптимизационным задачам с
точно заданными данными.
Опишем некоторые классы множеств неопределенности, для которых зада-
чи (2) и (3) могут быть сведены к оптимизационным задачам с точно заданными
данными. Рассмотрим случай, когда множество С задано таким образом:
0{ : , 0}C c c c ε ε= − ≤ > , где 0c и ε - соответственно заданные вектор и число.
Тогда { }min , : ( )c x c C f xc∈ = − − , { } )(:,max xfCcxc C=∈ , где ( )Cf x –
опорный функционал выпуклого множества С. Поскольку ( )Cf x для С в этом
случае вычисляется аналитически [7, с.132], то целевая функция задачи (2) при-
нимает вид ( )0max ,c x xε− , а задачи (3) соответственно { }xxc ε+,max 0 .
Покажем, что при некоторых ограничениях на множества неопределенности
C и Si = ( ){ }, , ,i i i mD q b i N∈ , решение задачи (2) и задачи (3) может быть найдено
однократным решением задачи целочисленной оптимизации вида (1).
Будем говорить, что множество W при заданном X имеет максимальный
элемент w
*
W∈ (минимальный элемент w* W∈ ), если ( , *) ( , )f x w f x w≥
(
*
( , *) ( , )) ,f x w f x w x X w W≤ ∀ ∈ ∀ ∈ . Если )
*
* (w w существует, то является
решением * arg maxw
w W
∈
∈
min ( , )f x w
x X∈
( * arg minw
w W
∈
∈
max ( , )f x w
x X∈
).
Приведем примеры множеств, имеющих максимальные (минимальные)
элементы, в предположении, что Si ={ },i mD i N∈ .
1. Пусть для некоторых mi N∈ , 0
iD – известные симметричные неотрица-
тельно определенные матрицы; Si – замкнутые сферы с центром в 0
iD радиусом
ρi > 0: 0{ : , ρ }
T
S D D D D D
i i i i i i is
= = − ≤ , где { }max , : 1
i i
D D y y y
s
= = –
спектральная норма матрицы Di. Тогда при 00 λ
mini i
i
D ≤ ρ ≤ , где [ ]λ
min
i
A –
мини-мальное собственное значение матрицы A; Si является выпуклым компак-
том симметричных неотрицательно определенных матриц. Нетрудно проверить,
Н.В. СЕМЕНОВА
42 Теорія оптимальних рішень. 2006, № 5
что для * 0
i i iD D E= + ρ и 0
*i i iD D E= − ρ , где E – единичная матрица, справедливо
*
( , ) ( , )i i i if x D f x D≥ , *( , ) ( , )i i ii
f x D f x D≤ при любых n
x Z∈ и D Si i∈ , поэтому
*
Di – максимальный, а *iD – минимальный элементы при любом n
X Z⊆ , mi N∈ .
2. Пусть Si , mi N∈ , заданы поэлементными ограничениями на матрицы Di
{{ }: , , }nD d d d d k j Ni kj kj kj kj= ≤ ≤ ∈ , где матрицы { }iD d
kj
= и { }iD d
kj
=
известны и неотрицательно определены i iD S∀ ∈ . Если X содержит только неот-
рицательные элементы, то ( , , )i i iD q b – максимальный, а ( , , )i i iD q b – минималь-
ный элементы, так как при любом 0x ≥ ) , ,,() , ,,( iiiiii bqDxfbqDxf ≥ и
) , ,,() , ,,( iiiiiiii bqDxfbqDxf ≤ ( , , )i i i iD q b S∀ ∈ .
Заметим, что множества S
i
, определенные таким образом, возникают, на-
пример, при оценивании элементов неизвестной ковариационной матрицы 0D
по эмпирическим данным с помощью доверительных интервалов.
Поскольку каждая матрица 0iD f , i∈Nm, неотрицательно определена, то
для решения задачи (2) можно применить предложенные в [2] декомпозицион-
ные методы, согласно которым решение этой задачи сводится к последователь-
ному решению задач целочисленной оптимизации с линейными ограничениями,
а также задач линейного программирования. В этой работе данный подход раз-
вивается для решения задачи (3), допустимая область которой представляет со-
бой бъединение выпуклых множеств и, следовательно, может быть невыпуклой.
Для некоторого
j
x ,...,2,1, =∈ jZ
n рассмотрим задачу МР следующего
вида:
max x0, (6)
при условиях
x0≤ max
kj N∈
,jc x , с
j∈С, k = 1, 2,…, (7)
( , , )
min max
i i i i lD q b S j N∈ ∈
(
j
if (x
j
) + ( ) jjj
i xxxf −∇ , )≤0,
j
if ∈Fi, i∈I⊂Nm, l = 1,2,…, (8)
x∈Z
n
, (9)
где ( )jj
i xf∇ – градиент функции ( )j
if x в точке
j
x .
Определим множества Qi = {x∈R
n
|∃(Di, qi, bi)∈Si : 〈Di x, x〉 + 〈qi , x〉 +bi≤0},
i ∈Nm. X2 = I
mNi
iQ
∈
. Будем предполагать, что множество 2X ограниченное.
Назовём величину ri(x) = min{〈Di x, x〉 + 〈qi ,x〉 + bi ≤ 0 |(Di,qi,bi)∈Si}, i∈Nm, от-
клонением точки x∈Z
n
от границы множества Qi, а величину r(x) = max{ri(x)|i∈I}
ГАРАНТИРУЮЩИЕ И ОПТИМИСТИЧЕСКИЕ РЕШЕНИЯ ЗАДАЧ ЦЕЛОЧИСЛЕННОЙ …
Теорія оптимальних рішень. 2006, № 5 43
– отклонением точки x∈Z
n
от границы множества 2X . Множества, описываемые
ограничениями вида (7), (8), представим соответственно в виде множеств S
k
и P
l
.
Теорема 1. Допустимое (оптимальное) решение ),( 0 xx задачи МР является
допустимым (оптимальным) решением задачи (3 ), где 0x – значение целевой
функции, x – решение этой задачи, тогда и только тогда, когда 0)( ≤xr и
( }:,max{0 Ccxcx ∈≤ ) }.:,max{0 Ccxcx ∈=
Доказательство. Допустимое решение задачи МР является допустимым
решением задачи (3) тогда и только тогда, когда 0)( ≤xr и }.:,max{0 Ccxcx ∈≤
Необходимость этого утверждения очевидна. Достаточность следует из построе-
ния задачи МР и определения )(xr . Учитывая, что задача МР при выполнении
условий теоремы 1 эквивалентна задаче (3), доказывается справедливость этого
утверждения относительно оптимального решения.
Следуя работе [2] и используя предложенные автором декомпозиционные
методы, задача (3) сводится к последовательному решению задач частично це-
лочисленной оптимизации вида МР с линеаризованными ограничениями, а так-
же задач линейного программирования вида { }max , |j
c x c C∈ .
Основная идея предложенного алгоритма cостоит в следующем. Если ре-
шение ),( 0 xx является недопустимым в задаче (3), т.е. 0)( >xr , то оно исключа-
ется из последующего рассмотрения добавлением линейного ограничения к ог-
раничениям задачи МР. Это ограничение обладает таким свойством, что отсека-
ет недопустимое решение, а также часть недопустимой области задачи (3) из
всех последующих рассмотрений. Все добавленные ограничения являются пра-
вильными отсекающими плоскостями, т.е. такими, которые не отсекают ника-
кую часть допустимой области нелинейной задачи (3). Если согласно теореме 1
решение ),( 0 xx оптимально для задачи МР и 0)( ≤xr , }:,max{0 Ccxcx ∈= , то
найденное решение оптимально и для задачи (3).
Алгоритм
1. Выбираем с
1∈С, пусть k, l = 1, P
1
= {x∈ n
Z }, S
1
= {x0,x}|x0 ≤ с
1
x, x0∈R
1
,
x∈ n
Z }.
2. Решаем частично целочисленную оптимизационную задачу МР. Если
она недопустима, то на основании того, что ограничения (8) являются релакса-
цией ограничений ∃(Di, qi, bi)∈Si : 〈Di x, x〉 + 〈qi , x〉 + bi≤0, i ∈Nm, задачи (3) дела-
ем вывод, что задача (3) также недопустима. Этот случай возможен лишь для
k=1. Иначе получаем допустимое (оптимальное) решение (
l
x0 , x
l
) или информа-
цию о том, что целевая функция не ограничена на допустимом множестве. Тогда
в качестве координат вектора x
l
выбираем достаточно большие числа.
Н.В. СЕМЕНОВА
44 Теорія оптимальних рішень. 2006, № 5
3. Находим отклонение r(x
l
) от границы множества 2X . Если r(x
l
) ≤ 0, то со-
гласно теореме 1 (
l
x0 , x
l
) – допустимое (оптимальное) решение задачи (3). Пере-
ходим к п. 4, полагая (
k
x0 , x
k
) = (
l
x0 , x
l
). В противном случае находим элемент
l
if ∈U
Ii
iF
∈
, для которого r(x
l
) > 0, и включаем его в образование множества
IiP
l
i ∈+ ,1 , по формуле (8). Заменяя l на l +1, переходим к п. 2.
4. Решаем задачу линейного программирования вида max {〈c,x
k〉 | c ∈C }.
Пусть c
k+1
– найденное оптимальное решение.
5. Если 〈сk+1
,x
k〉 ≥
k
x0 (〈сk+1
,x
k〉 =
k
x0 ), то алгоритм заканчивается. В соответ-
ствии с теоремой 1 заключаем, что (с
k+1
, x
k
) – приближенное (оптимальное) ре-
шение задачи (3) со значением
k
x0 её целевой функции. Иначе, заменяя k на
k + 1, переходим к п. 2.
Замечание. При использовании этого алгоритма для получения оптималь-
ного решения задачи (3) требование к оптимальности решения задачи МР можно
ослабить. Оптимальность требуется лишь на завершающем шаге. Промежуточ-
ные решения для построения новых отсекающих плоскостей должны быть толь-
ко допустимыми решениями МР и недопустимыми в задаче (3), т.е. не принад-
лежать допустимой области 2X .
Теорема 2. Описанный алгоритм сходится к приближенному (оптимально-
му) решению за конечное число шагов, либо заканчивается на первом шаге с
выводом о том, что задача (3) недопустима.
Далее даются критерии проверки решений на допустимость в задачах (2) и
(3) при некоторых множествах неопределенности, описывающих данные задачи.
2. Задание множеств неопределенности. Простейшим типом такого мно-
жества является дискретное множество, заданное следующим образом:
Sa = {(D,q,b)|(D,q,b) = (Dj,qj,bj), Djf 0, j = 1,…,k}.
Гарантирующее ограничение , , 0Dx x q x b+ + ≤ , для всех (D,q,b)∈Sa эк-
вивалентно k выпуклым квадратичным ограничениям
, , 0, 1,...,j j jD x x q x b j k+ + ≤ = . (10)
Множество, описываемое ограничением вида
0,,:),,( ≤++∈∃ bxqxDxSbqD a (11)
в задаче (3), эквивалентно объединению множеств, описываемых этим ограни-
чением при каждом aSbqD ∈),,( : 0,,
1
≤++
=U
k
j jjj bxqxxD , что равносиль-
но выполнению неравенства
{ } 0),,(:,,min ≤∈++ ajjjjjj SbqDbxqxxD . (12)
ГАРАНТИРУЮЩИЕ И ОПТИМИСТИЧЕСКИЕ РЕШЕНИЯ ЗАДАЧ ЦЕЛОЧИСЛЕННОЙ …
Теорія оптимальних рішень. 2006, № 5 45
Дискретные множества неопределенности, как правило, используются, если
возникает необходимость принимать решение, устойчивое (в задаче (2)) и опти-
мистическое (в задаче (3)) относительно нескольких сценариев – каждое значе-
ние (Dj,qj,bj) соответствует определенному сценарию.
Выпуклая оболочка дискретного множества неопределенности задается та-
ким образом: Sa′ ={(D,q,b) | (D,q,b) =
1
k
j=
∑ λj(Dj,qj,bj), Dj f 0, λj ≥ 0,∀ j ∈ Nk,
1
λ 1}.
k
j
j=
=∑
Ограничение , , 0Dx x q x b+ + ≤ ∀(D,q,b)∈Sa′ эквивалентно следующему:
λ
1
k
jj
∑
=
, , 0,j j jD x x q x b+ + ≤ ∀ λj ≥ 0, ,kj N∈
1
λ 1
k
j
j=
=∑ , что в свою очередь
эквивалентно множеству ограничений (10). Ограничения вида (11) в случае
множества неопределенности Sa′ эквивалентны ограничениям (12).
Множества неопределенности Sa и Sa′ могут быть в дальнейшем расширены
на следующее многогранное множество неопределенности:
Sb = {(D,q,b)|(D,q,b) = ∑
=
k
j 1
λj(Dj,qj,bj), Dj f 0,∀ j∈Nk, Aλ = d, λ ≥ 0},
где {λ∈R
k|Aλ = d, λ ≥ 0}≠∅. Введем в рассмотрение вектор
),,...,(, 1 k
k
gggRg =∈
gj= , , ,j j jD x x q x b+ + j∈ .kN
Утверждение 1. Вектор х∈Z
n
удовлетворяет ограничению 〈Dx, x〉 + 〈q,
x〉+b≤0 для всех (D,q,b)∈Sb, если и только если существует вектор u∈R
k
, такой,
что удовлетворяет соотношениям А
Т
u≥g, 0, ≤ud .
Доказательство. Зафиксируем х. Тогда ограничение , , 0 Dx x q x b+ + ≤
для всех (D,q,b)∈Sb эквивалентно ограничениям ,λ 0g ≤ ∀λ≥0 такого, что Аλ=
d.
Согласно теории двойственности линейного программирования, последнее со-
отношения эквивалентно следующим: ∃ u такой, что А
Т
u ≥ g, 0, ≤ud .
Утверждение 2. Вектор х∈Z
n
удовлетворяет ограничению :),,( bSbqD ∈∃
0,, ≤++ bxqxDx для всех (D, q, b)∈Sb, если и только если
0, ≤ud ∀ u ≥ 0: А
Т
u ≤ g. (13)
Доказательство. Ограничение 0,,:),,( ≤++∈∃ bxqxDxSbqD b при дан-
ном х∈Z
n
эквивалентно следующему: ∃ λ ≥ 0, λ∈R
k
такой, что удовлетворяет
Н.В. СЕМЕНОВА
46 Теорія оптимальних рішень. 2006, № 5
условиям Аλ= d, ,λ 0g ≤ . В соответствии с теорией двойственности линейного
программирования эти соотношения эквивалентны соотношениям (13).
Некоторые множества неопределенности, описывающие исходные данные
для задач вида (2) с непрерывными переменными, представлены в [9].
Заключение. Исследованы сложные задачи целочисленной оптимизации с
неточно заданными коэффициентами линейной целевой функции и квадратич-
ных функций ограничений. Рассмотрены некоторые классы множеств неопреде-
ленности, для которых такие задачи могут быть записаны как задачи с точно за-
данными данными. Построены и обоснованы точные и приближенные деком-
позиционные методы нахождения гарантирующих и оптимистических решений
указанных задач в условиях неопределенности в данных, основанные на конст-
руктивных аппроксимациях их задачами более простой структуры.
Н.В. Семенова
ГАРАНТУЮЧІ ТА ОПТИМІСТИЧНІ РOЗВ’ЯЗКИ ЗАДАЧ ЦІЛОЧИСЛОВОЇ ОПТИМІЗАЦІЇ
З ОПУКЛИМИ КВАДРАТИЧНИМИ ФУНКЦІЯМИ ОБМЕЖЕНЬ
Досліджено складні задачі цілочислової оптимізації з неточно заданими коефіцієнтами лі-
нійної цільової функції й опуклих квадратичних функцій обмежень. Побудовано та обґрун-
товано точні і наближені декомпозиційні методи знаходження гарантуючих і оптимістичних
розв’язків таких задач. Розглянуто деякі класи множини невизначеності, що описують вхідні
дані цих задач.
N.V. Semenova
GUARANTEEING AND OPTIMISTIC SOLUTIONS TO INTEGER OPTIMIZATION
PROBLEMS WITH CONVEX QUADRATIC FUNCTIONS OF CONSTRAINTS
The paper studies complex integer optimization problems with inexact coefficients of linear objec-
tive function and convex quadratic function of constraints. Exact and approximate decomposition
methods are developed and proved for search of guaranteeing and optimistic solutions to such prob-
lems. The paper proposes some classes of uncertainty sets that describe input data of such problems.
1. Глушков В.М. О системной оптимизации // Кибернетика.– 1980.– № 5.– С. 89 -− 90.
2. Семенова Н.В. О решении задач целочисленной оптимизации на выпуклых множе-
ствах в условиях неопределенности данных // Теориія оптимальних рішень. – К.: Ін-т
кибернетики ім. В.М.Глушкова НАН України, 2005. – № 4.– С. 107–112.
3. Сергієнко І.В., Рощин В.О., Семенова Н.В. Розв’язування задач неточного цілочисе-
льного програмування // Доп. АН УРСР. Сер. А. – 1988.– № 12.– С. 61– 64.
4. Рощин В.А., Семенова Н.В., Сергиенко И.В. Вопросы решения и исследования одно-
го класса задач неточного целочисленного программирования // Кибернетика.–
1989.–№ 2.–С. 42–46, 64.
5. Рощин В.А., Семенова Н.В., Сергиенко И.В. Декомпозиционный подход к решению
некоторых задач целочисленного программирования с неточными данными // Журн.
вычисл. математики и мат. физики. – 1990. – 29, № 5. – С. 786 – 791.
ГАРАНТИРУЮЩИЕ И ОПТИМИСТИЧЕСКИЕ РЕШЕНИЯ ЗАДАЧ ЦЕЛОЧИСЛЕННОЙ …
Теорія оптимальних рішень. 2006, № 5 47
6. Сергиенко И.В., Рощин В.А., Семенова Н.В. Некоторые задачи целочисленного про-
граммирования с неоднозначно заданными данными и их решение // Проблемы
управления и информатики. – 1998. – № 6. – С. 116–123.
7. Рокафеллар Р. Выпуклый анализ. – М.: Мир, 1973. – 471с.
8. Kelley J. The cutting plane method for solving convex program //SIAM J.–1960.– 8, №4.–
P.703–712.
9. Goldfarb D., Iyengar G. Robust convex quadratically constrained programs // Math.
Program.– 2003.– N 3.– Р. 135–141.
Получено 15 .06.2006
|
| id | nasplib_isofts_kiev_ua-123456789-84952 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-12-07T18:10:19Z |
| publishDate | 2006 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Семенова, Н.В. 2015-07-17T16:42:14Z 2015-07-17T16:42:14Z 2006 Гарантирующие и оптимистические решения задач целочисленной оптимизации с выпуклыми квадратичными функциями ограничений / Н.В. Семенова // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 39-47. — Бібліогр.: 9 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/84952 519.8 The paper studies complex integer optimization problems with inexact coefficients of linear objective function and convex quadratic function of constraints. Exact and approximate decomposition methods are developed and proved for search of guaranteeing and optimistic solutions to such problems. The paper proposes some classes of uncertainty sets that describe input data of such problems. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Гарантирующие и оптимистические решения задач целочисленной оптимизации с выпуклыми квадратичными функциями ограничений Guaranteeing and optimistic solutions to integer optimization problems with convex quadratic functions of constraints Article published earlier |
| spellingShingle | Гарантирующие и оптимистические решения задач целочисленной оптимизации с выпуклыми квадратичными функциями ограничений Семенова, Н.В. |
| title | Гарантирующие и оптимистические решения задач целочисленной оптимизации с выпуклыми квадратичными функциями ограничений |
| title_alt | Guaranteeing and optimistic solutions to integer optimization problems with convex quadratic functions of constraints |
| title_full | Гарантирующие и оптимистические решения задач целочисленной оптимизации с выпуклыми квадратичными функциями ограничений |
| title_fullStr | Гарантирующие и оптимистические решения задач целочисленной оптимизации с выпуклыми квадратичными функциями ограничений |
| title_full_unstemmed | Гарантирующие и оптимистические решения задач целочисленной оптимизации с выпуклыми квадратичными функциями ограничений |
| title_short | Гарантирующие и оптимистические решения задач целочисленной оптимизации с выпуклыми квадратичными функциями ограничений |
| title_sort | гарантирующие и оптимистические решения задач целочисленной оптимизации с выпуклыми квадратичными функциями ограничений |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84952 |
| work_keys_str_mv | AT semenovanv garantiruûŝieioptimističeskierešeniâzadačceločislennoioptimizaciisvypuklymikvadratičnymifunkciâmiograničenii AT semenovanv guaranteeingandoptimisticsolutionstointegeroptimizationproblemswithconvexquadraticfunctionsofconstraints |