Алгоритм решения квадратичной задачи в PNK-методе
Строится вычислительно эффективный алгоритм решения квадратичной подзадачи, решаемой на итерациях PNK-метода. При этом учитывается диагональность квадратичной матрицы, границы переменных, незначительность изменения подзадачи на последовательных итерациях. Приводятся результаты вычислительных экспери...
Saved in:
| Published in: | Теорія оптимальних рішень |
|---|---|
| Date: | 2011 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/46776 |
| 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: | Алгоритм решения квадратичной задачи в PNK-методе / В.Н. Кузьменко, Э.И. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2011. — № 10. — С. 76-83. — Бібліогр.: 13 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859854625765588992 |
|---|---|
| author | Кузьменко, В.Н. Ненахов, Э.И. |
| author_facet | Кузьменко, В.Н. Ненахов, Э.И. |
| citation_txt | Алгоритм решения квадратичной задачи в PNK-методе / В.Н. Кузьменко, Э.И. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2011. — № 10. — С. 76-83. — Бібліогр.: 13 назв. — рос. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | Строится вычислительно эффективный алгоритм решения квадратичной подзадачи, решаемой на итерациях PNK-метода. При этом учитывается диагональность квадратичной матрицы, границы переменных, незначительность изменения подзадачи на последовательных итерациях. Приводятся результаты вычислительных экспериментов.
Будується чисельно ефективний алгоритм розв'язування квадратичної підзадачи, яку треба розв'язувати на ітераціях PNK-методу. При цьому враховується діагональність квадратичної матриці, границі змінних, незначна зміна підзадачі на послідовних ітераціях. Наводяться результати обчислювальних експериментів.
Computationally effective algorithm for solving quadratic subproblem on iteration of PNK-method is built. Diagonal property of quadratic matrix, bounds on variables, small change of subproblem are took into account. Results of computational experiments are given.
|
| first_indexed | 2025-12-07T15:42:51Z |
| format | Article |
| fulltext |
76 Теорія оптимальних рішень. 2011, № 10
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Строится вычислительно эф-
фективный алгоритм решения
квадратичной подзадачи, решае-
мой на итерациях PNK-метода.
При этом учитывается диаго-
нальность квадратичной матри-
цы, границы переменных, незна-
чительность изменения подзада-
чи на последовательных итераци-
ях. Приводятся результаты вы-
числительных экспериментов.
В.Н. Кузьменко, Э.И. Ненахов
2011
ÓÄÊ 519.85
Â.Í. ÊÓÇÜÌÅÍÊÎ, Ý.È. ÍÅÍÀÕÎÂ
ÀËÃÎÐÈÒÌ ÐÅØÅÍÈß ÊÂÀÄÐÀÒÈ×ÍÎÉ
ÇÀÄÀ×È Â PNK-ÌÅÒÎÄÅ
Введение. Ключевым моментом различных
алгоритмов, использующих решение квадра-
тичной подзадачи, есть эффективность реша-
теля этой подзадачи [1–3]. Под решателем
понимается алгоритм, реализующий метод
решения и использующий особенности по-
становки подзадачи и ее данных. Поскольку
практический интерес представляют задачи
большой размерности [2, 3], то решатель
должен обладать такими свойствами: он
должен реализовывать вычислительно эф-
фективный метод, быть приспособленным к
конкретной постановке задачи, компактно
представлять разреженные данные и быстро
с ними оперировать, находить решение под-
задачи с заданной точностью, в том числе
быстро находить приближенные решения.
Методы решения квадратичной задачи в
различных ее постановках разработаны дос-
таточно глубоко [4–10]. Обширная библио-
графия приведена в обзоре [11]. Поэтому в
данной работе речь идет об эффективном ис-
пользовании одного из методов активного
набора в PNK-методе [12, 13]. Возможность
такого использования обусловлена, в частно-
сти, сходством логики работы обоих мето-
дов. Оба метода используют наборы линей-
ных ограничений, разделяя их на активное и
неактивное подмножества, и в этом допол-
няют друг друга. PNK-метод на каждой ите-
рации модифицирует квадратичную задачу и
добавляет новые неактивные, но нарушен-
ные ограничения, а квадратичный метод
строит последовательность точек, сходя-
щуюся к решению задачи.
АЛГОРИТМ РЕШЕНИЯ КВАДРАТИЧНОЙ ЗАДАЧИ В PNK-МЕТОДЕ
Теорія оптимальних рішень. 2011, № 10 77
Подзадача, решаемая на итерации PNK-метода, может быть записана сле-
дующим образом:
}5.0{min 21
2
,, 21
ξ+ξ+−
ξξ
kkkr
x
Nhhxx , (1)
kiiii Xxxxxfxf ∈∀ξ≤−′+ ,)),(()( 1 , (2)
kiiii Xxxxxx ∈∀ξ≤−ϕ′+ϕ ,)),(()( 2 , (3)
xxx ≤≤ξ≤ ,0 2 , (4)
где переменная 1ξ с учетом ограничений (2) аппроксимирует целевую функцию
)(xf ; переменная 2ξ с учетом ограничений (3) – обобщенную функцию огра-
ничений )(xϕ ; kX – текущее (на итерации k) множество точек аппроксимации;
}:)(min{arg kkr XxxFx ∈= – вычисленная точка минимума штрафной функции
)}(;0max{)()( xNxfxF kk ϕ+= на kX ; )(),( xxf ϕ′′ – элементы субдифферен-
циалов )(),( xxf ϕ∂∂ ; kN – штрафной множитель; kh –множитель, выполняю-
щий роль величины шага.
Запишем квадратичную задачу (1)–(4) в более общем виде
}|5.0{min
,
bGAxpxdxx
T
x
≥ξ+ξ++⋅
ξ
. (5)
В постановке (5) ограничения (4) учтены как общие, переменные 1ξ , 2ξ со-
браны в вектор ξ , d и p – вектор-строки, собранные по линейной части (1).
Функция Лагранжа для задачи (5) имеет вид
0),(5.0),,( ≥λξ−−λ+ξ++⋅=λξ GAxbpxdxxxL
T .
Необходимые условия оптимальности Каруша - Куна - Таккера имеют вид
=λ<ξ−−
≥λ=ξ−−
=
λ
∂
0,0
0,0
i
ii
i
i
ii
i
i gxab
gxabL
, { }mIi ...,,1=∈ ,
0)(
0)(
=λ−=∇
=λ−+=∇
ξ
T
T
x
GpL
AdxL
, (6)
где – ii
ga , строки i матриц A и G; m – количество строк ограничений в (5).
Суть метода активного набора можно сформулировать как поиск множества
IIa ⊂∗ ограничений задачи (5), которые в оптимальном решении выполнены
как равенства. Для произвольного активного набора aI переменные ax λξ,, оп-
ределяются решением следующей линейной системы, полученной из (6):
−
−
=
λ
ξ
−
−
a
T
T
T
aaa
T
a
T
a
b
p
dx
GA
G
AE
0
00
0
, (7)
В.Н. КУЗЬМЕНКО, Э.И. НЕНАХОВ
78 Теорія оптимальних рішень. 2011, № 10
где aa GA , – подматрицы матриц A, G, aab λ, – части векторов λ,b , соответст-
вующие подмножеству aI . Остальные переменные iλ полагаются равными 0.
Оптимальность набора aI проверяется по оставшимся условиям из (6).
Необходимым условием разрешимости системы (7) есть наличие в ней хотя
бы одного ограничения, включающего переменные 1ξ , 2ξ , и не более n+2 огра-
ничений из системы (5), где n – длина вектора x.
При поиске оптимального активного набора система (7) должна решаться
многократно прямо и косвенно. Поэтому важно рационально изменять систему
и пересчитывать ее решение, основываясь на предыдущем наборе и решении.
Выполним преобразование пространства переменных x таким образом, чтобы
система активных ограничений приняла вид
aaaaaa bGyLGQyAGxA =ξ+=ξ+=ξ+ )0( ,
где Q – ортогональная матрица преобразования пространства Qyx = ; )0(L –
матрица, состоящая из нижней треугольной L и нулевой подматриц. Такое пре-
образование возможно, если ранг aA равен числу ее строк, т.е. ограничение
2ξ =0 не активно.
В преобразованном пространстве изменяется вид градиентов функции Ла-
гранжа по переменным λ,y , а именно:
ξ−
−=∇λ Gy
S
L
bL
0
,
TT
T
T
y S
L
dQyL λ
−+=∇
0
)( , (8)
где AQ
S
L
=
0
.
В таком представлении вектор y разделяется на компоненты, соответст-
вующие aI и нет, )( Na yyy = . Более того можно установить взаимно-
однозначное соответствие между переменными ay и ограничениями aI .
Система (7) приобретает вид
−
−
−
=
λ
ξ
−
−
a
T
T
N
T
a
T
a
N
a
a
T
a
N
T
a
b
p
dQ
dQ
y
y
GL
G
E
LE
)(
)(
00
000
000
00
, (9)
АЛГОРИТМ РЕШЕНИЯ КВАДРАТИЧНОЙ ЗАДАЧИ В PNK-МЕТОДЕ
Теорія оптимальних рішень. 2011, № 10 79
и решается в следующем порядке: )(1 ξ−= −
aaa GbLy , ))((1 T
aa
TT
a dQyL +=λ − ,
( )T
aaa
TT
a
T
aa
TT
a
T
a
T
a
T dQGbLLGdQyLGGp )()())(( 111 +ξ−=+=λ= −−− . Из последне-
го находим ( ) ( )( )TT
aa
TT
aa
TT
a pdQbLLGGLLG −+=ξ −−−−−
)(
11111 . Далее, подставляя
ξ , находим ay и T
aλ . Ny считается независимо T
NN dQy )(−= . Несмотря на не-
которую громоздкость формул система решается эффективно, так как не ис-
пользуется явное обращение треугольной матрицы L, матрица aGL
1− имеет раз-
мер 2×aI , а матрица ( )a
TT
a GLLG 11 −− – 22× .
Если ограничение 02 =ξ активно, то оно добавляется к системе (9), а также
добавляется столбец соответствующей двойственной переменной
2ξλ , содер-
жащий единственный ненулевой элемент –1 в строке, соответствующей 2ξ .
В этом случае первыми находятся переменные 1ξ и
2ξλ из системы
( ) ( )
λ
+−+=
ξ
ξ
−−−−−
2
0
)(
0
111111 TT
aa
TT
aa
TT
a pdQbLLGGLLG .
Если активный набор не является оптимальным, то алгоритм выполняет его
изменение путем добавления нарушенных ограничений из (5) и вывода ограни-
чений, у которых двойственные переменные отрицательны. Порядок ввода, вы-
вода ограничений и пересчета системы (9) зависит от конкретной реализации
алгоритма. Но при любой реализации необходимо выполнить соответствующее
изменение матриц Q и L. И если матрица L может иметь небольшую размер-
ность, то матрица Q имеет размерность nn× . Поэтому рассмотрим вопрос: как
используя специфику постановки задачи можно уменьшить объем вычислений
при изменении матриц Q и L.
Спецификой в постановке задачи (1)-(4) есть наличие границ на переменные
и единичная квадратичная матрица. Если среди активных ограничений есть гра-
ницы переменных и соответствующие ограничения записаны первыми, то ра-
венство )0(LQAa = более детально представляется в виде
( ) )0(0
0
L
LBP
E
DP
B
P
QA T
T
a =
′
=
= ,
где P – строки ограничений (5), соответствующие границам переменных, B –
строки "обычных" ограничений, D – правая часть столбцов матрицы Q . Каж-
дая строка в P содержит только один ненулевой элемент +1 или –1. Отсюда с
учетом того, что 0=PD , следует, что строки Q , содержащие +1, –1 подматри-
цы TP , не содержат других ненулевых элементов. Следовательно, при соответ-
ствующем ( xΠ ) изменении порядка переменных матрица Q может быть пред-
В.Н. КУЗЬМЕНКО, Э.И. НЕНАХОВ
80 Теорія оптимальних рішень. 2011, № 10
ставлена в виде
′
′
Π=ΠΠ=
Q
E
AQAQA xa
T
xxaa
0
0
, т.е.
′
′
Π=
Q
E
Q x
0
0
, где E′
– диагональная матрица с элементами +1, –1.
При добавлении нового ограничения к системе активных ограничений мат-
рица Q должна преобразоваться для сохранения треугольного вида результата
произведения ( )0
0
11 ++
+
+
+
=
=
=′ LQ
Qa
L
QQ
a
A
QA
a
a , где aA′ –матрица увели-
ченного набора активных ограничений, +a – строка добавленного ограничения,
1Q – соответственно измененная матрица Q , +Q – ортогональное преобразова-
ние, зануляющее "хвост" строки Qa+ .
Если матрица 1+L имеет размер rr × , то необходимо занулить rn − эле-
ментов строки Qa+ , начиная с конца. Зануление каждого элемента выполняется
с помощью преобразования элементарного поворота, а именно, если js – по-
следний ненулевой элемент строки, то преобразование jq , задаваемое матри-
цей, полученной из единичной с подматрицей
−
+ −
−
−
1
1
22
1
1
jj
jj
jj
ss
ss
ss
в строках
и столбцах 1−j , j , даст 0 в позиции j строки Qa+ . Таким образом, матрица
+Q может быть представлена в виде произведения knknnn qqqqQ −+−−+ = 11... .
Другие, используемые в алгоритме повороты, задаются изменением знаков
в подматрице 22× :
−−
−
−
−−
− −
−
−
−
−
−
1
1
1
1
1
1
,,
jj
jj
jj
jj
jj
jj
ss
ss
ss
ss
ss
ss
.
Если 01 =−js , то второй и третий варианты поворота эквивалентны в зави-
симости от знака js перестановке столбцов 1−j и j в матрице Q . Но в этом
случае более рационально найти ближайший к js ненулевой элемент γs строки
Qa+ , такой, что jr <γ< . Если такой γs существует, то преобразование пово-
рота q выполняется для столбцов γ и j . Если нет, то для столбцов r и j .
При удалении ограничения из списка активных матрицу Q также необхо-
димо преобразовать. Если удаляется γ -е ограничение из r активных, то при
r<γ в матрице L′ , получаемой из L после удаления строки γ , получится γ−r
ненулевых элементов справа от диагонали в строках γ ,…, 1−r . Для зануления
этих элементов необходимо применить один оператор поворота для каждой
строки, начиная со строки γ . Соответствующее преобразование матрицы Q за-
дается оператором 11... −+γγ− = rqqqQ , а преобразованная матрица −= QQQ1 .
АЛГОРИТМ РЕШЕНИЯ КВАДРАТИЧНОЙ ЗАДАЧИ В PNK-МЕТОДЕ
Теорія оптимальних рішень. 2011, № 10 81
Так как изначально матрица Q равна единичной и каждое ее преобразова-
ние выражается в виде ряда операторов поворота, то в общем виде на итерации
k матрица Q может быть представлена как ∏
∈
=
kTt
tk qQ , где kT – упорядочен-
ное множество индексов операторов поворотов, задающее порядок операторов
tq в произведении, а операции с ее участием – как последовательное примене-
ние операторов tq . Изменение матрицы Q – как дополнение множества kT .
Опишем схематически алгоритм решения квадратичной задачи.
0. Инициализация: ∅=aI , L – матрица 00 × , ∅=0T ( EQ = ).
1. Start – поиск допустимого двойственного решения.
do; Решить (9). Найти x. }0|{: <λ∈=− iaIiI ,
if ∅≠−I then −= III aa \: . Изменить QL, . Повторить блок. end
end
2. Restart – поиск оптимального решения.
do while ( 0>∆
mi
, }\|max{ a
ii
iim IIigxabagri ∈ξ−−=∆= );
}{: maa iII ∪= , 0=step .
do while ( 1<step ); aa λ=λ 0 , xx =0 .
Изменить LQ, . Решить (9). Найти 0aaa λ−λ=λ∆ , 0xxx −=∆ .
}0},{\|/min{0 <λ∆∈λ∆λ= imaii iIiagri .
if 0i существует then }1;/min{
00 iistep λ∆λ−= else 1=step end
aaa step λ∆⋅+λ=λ 0 , xstepxx ∆⋅+= 0 .
if 1<step then }{\: 0iII aa = end
end
end
Решение квадратичной подзадачи начинается либо с точки 1, либо с точки
2. Точка 1 используется вначале, а также при изменении параметров подзадачи –
штрафного множителя kN , шага – kh , рекорда – rx . Если эти параметры не из-
менились, то решение начинается с точки 2, так как при добавлении новых ог-
раничений линеаризации (2), (3) по точке 1+kx активный набор aI остается
двойственно допустимым, а нарушенными только новые ограничения.
Решение системы (9) в блоке Restart находится существенно проще, чем в
блоке Start. Переменные iy , }{\ ma iIi ∈ не изменяются, выполнение нарушен-
ного ограничения mi достигается за счет изменения одной переменной
mi
y , ко-
торая определяет изменение переменной
mi
λ , что в свою очередь определяет
изменение переменных iλ , }{\ ma iIi ∈ .
В.Н. КУЗЬМЕНКО, Э.И. НЕНАХОВ
82 Теорія оптимальних рішень. 2011, № 10
Еще один важный момент уменьшения вычислительной сложности – обнов-
ление множества kT . Множество kT увеличивается с добавлением и выводом
каждого активного ограничения, с изменением их порядка. Произведение Qa+
требует выполнения kT×4 операций умножения и kT×2 сложения. При зна-
чительном росте kT выполняется перестройка множества kT и пересчет матри-
цы L , а именно: стартуя с L – 00× и ∅=kT имитируется добавление актив-
ных ограничений aI , начиная с границ переменных. При этом отсеиваются все
промежуточные операторы поворота, связанные выводом ограничений из спи-
ска активных и изменением их порядка в этом списке, матрица L становится
более разреженной за счет уменьшения ошибок вычислений.
Результаты вычислительных экспериментов. Вычислительные экспери-
менты проводились с целью демонстрации влияния использования специфики
внутренней квадратичной задачи на общее время решения задачи в зависимости
от общего количества переменных и количества переменных, лежащих на гра-
нице в оптимальном решении. Результаты вычислений приведены в таблице.
Результаты с использованием специфики
квадратичной подзадачи
Результаты без использования специфики
квадратичной подзадачи
Размерность
задачи,
n
Кол-во пере-
менных на
границе
Время
решения, с
Размерность
задачи,
n
Кол-во пере-
менных на
границе
Время
решения, с
10 0 0.5 10 0 0.6
10 5 0.1 10 5 0.5
100 0 3.9 100 0 4.3
100 90 0.9 100 90 4.2
1000 300 22.6 1000 300 62.2
1000 700 10.3 1000 700 68.7
5000 100 198.5 5000 100 328.5
5000 3000 28.5 5000 3000 362.9
Заключение. В результате выполненной работы значительно улучшена эф-
фективность работы PNK-метода. Показано, что учет специфики квадратичной
подзадачи, решаемой на каждой итерации, позволяет значительно уменьшить
объем вычислений на итерациях метода.
В.М. Кузьменко, Е.І. Ненахов
АЛГОРИТМ РОЗВ’ЯЗУВАННЯ КВАДРАТИЧНОЇ ЗАДАЧІ У PNK-МЕТОДІ
Будується чисельно ефективний алгоритм розв’язування квадратичної підзадачи, яку треба
розв’язувати на ітераціях PNK-методу. При цьому враховується діагональність квадратичної
АЛГОРИТМ РЕШЕНИЯ КВАДРАТИЧНОЙ ЗАДАЧИ В PNK-МЕТОДЕ
Теорія оптимальних рішень. 2011, № 10 83
матриці, границі змінних, незначна зміна підзадачі на послідовних ітераціях. Наводяться ре-
зультати обчислювальних експериментів.
V.M. Kuzmenko, E.I.Nenakhov
AN ALGORYTHM FOR SOLVING QUADRATIC PROBLEM IN PNK-METHOD
Computationally effective algorithm for solving quadratic subproblem on iteration of PNK-method
is built. Diagonal property of quadratic matrix, bounds on variables, small change of subproblem
are took into account. Results of computational experiments are given.
1. Murray W., Prieto F.J. A Sequential Quadratic Programming Algorithm Using an Incom-
plete Solution of the Subproblem // SIAM J. Optim. – 1995. – 5, N 3. – P. 590–640.
2. Boggs P.T., Tolle J.W. Sequential quadratic programming for large-scale nonlinear optimi-
zation // J. Computational and Applied Mathematics. – 2000. – N 124. – P. 123–137.
3. Kim S.J., Koh K., Lustig M., Boyd S. An Interior-Point Method for Large-Scale L1-
Regularized Least Squares // J. of selected topics in signal processing. – 2007. – 1, N 4. –
P. 606–617
4. Dax A. The gradient projection method for quadratic programming // Institute of Mathe-
matics Report. – Jerusalem: The Hebrew University of Jerusalem, 1978. – P. 124–149.
5. Gill P.E., Murray W. Numerically Stable Methods for Quadratic Programming // Math.
Progr. – 1978. – 14(3). – P. 349–372.
6. Goldfarb D., Idnani A. A numerically stable dual method for solving strictly convex quad-
ratic programs // Math. Progr. – 1983. – N 27. – P. 1–33.
7. Gill P.E.,Gould N.I.M., Murray W., Saunders M.A., Write M.H. A weighted Gram-Schmidt
method for convex quadratic programming // Math. Progr. – 1984. – 30 (2). – P. 176–195.
8. Powell M.J.D. On the quadratic programming algorithm of Goldfarb and Idnani // Mathe-
matical Programming Studies. – 1985. – N 25. – P. 46–61.
9. Костина Е.А., Костюкова О.И. Алгоритм решения выпуклой квадратичной зада-
чи с линейными равенствами и неравенствами // ЖВМиМФ. – 2001. – № 42. –
С. 1012 – 1026.
10. Schittkowski K. QL: A Fortran code for convex quadratic programming - user's guide //
Report, Department of Mathematics, University of Bayreuth, 2003. – P. 64–71.
11. Gould N. I. M., Toint Ph.L., A Quadratic Programming Bibliography. – 2001. –
http://www.optimization-online.org/DB_HTML/2001/02/2 85.html
12. Пшеничный Б.Н., Ненахов Э.И., Кузьменко В.Н. Комбинированный метод решения
общей задачи выпуклого программирования // Кибернетика и системный анализ. –
1998. – № 4. – С. 121–134.
13. Кузьменко В.Н., Бойко В.В. О применении комбинированного метода выпуклого
программирования // Теорія оптимальних рішень. – К.: Ін-т кібернетики
ім. В.М. Глушкова НАН України, 2003. – С. 19–24.
Получено 14.04.2011
|
| id | nasplib_isofts_kiev_ua-123456789-46776 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-12-07T15:42:51Z |
| publishDate | 2011 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Кузьменко, В.Н. Ненахов, Э.И. 2013-07-06T17:04:11Z 2013-07-06T17:04:11Z 2011 Алгоритм решения квадратичной задачи в PNK-методе / В.Н. Кузьменко, Э.И. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2011. — № 10. — С. 76-83. — Бібліогр.: 13 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/46776 519.85 Строится вычислительно эффективный алгоритм решения квадратичной подзадачи, решаемой на итерациях PNK-метода. При этом учитывается диагональность квадратичной матрицы, границы переменных, незначительность изменения подзадачи на последовательных итерациях. Приводятся результаты вычислительных экспериментов. Будується чисельно ефективний алгоритм розв'язування квадратичної підзадачи, яку треба розв'язувати на ітераціях PNK-методу. При цьому враховується діагональність квадратичної матриці, границі змінних, незначна зміна підзадачі на послідовних ітераціях. Наводяться результати обчислювальних експериментів. Computationally effective algorithm for solving quadratic subproblem on iteration of PNK-method is built. Diagonal property of quadratic matrix, bounds on variables, small change of subproblem are took into account. Results of computational experiments are given. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Алгоритм решения квадратичной задачи в PNK-методе Алгоритм розв'язування квадратичної задачі у PNK-методі An algorithm for solving quadratic problem in PNK-method Article published earlier |
| spellingShingle | Алгоритм решения квадратичной задачи в PNK-методе Кузьменко, В.Н. Ненахов, Э.И. |
| title | Алгоритм решения квадратичной задачи в PNK-методе |
| title_alt | Алгоритм розв'язування квадратичної задачі у PNK-методі An algorithm for solving quadratic problem in PNK-method |
| title_full | Алгоритм решения квадратичной задачи в PNK-методе |
| title_fullStr | Алгоритм решения квадратичной задачи в PNK-методе |
| title_full_unstemmed | Алгоритм решения квадратичной задачи в PNK-методе |
| title_short | Алгоритм решения квадратичной задачи в PNK-методе |
| title_sort | алгоритм решения квадратичной задачи в pnk-методе |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/46776 |
| work_keys_str_mv | AT kuzʹmenkovn algoritmrešeniâkvadratičnoizadačivpnkmetode AT nenahovéi algoritmrešeniâkvadratičnoizadačivpnkmetode AT kuzʹmenkovn algoritmrozvâzuvannâkvadratičnoízadačíupnkmetodí AT nenahovéi algoritmrozvâzuvannâkvadratičnoízadačíupnkmetodí AT kuzʹmenkovn analgorithmforsolvingquadraticprobleminpnkmethod AT nenahovéi analgorithmforsolvingquadraticprobleminpnkmethod |