Алгоритм проектирования на политоп
Предложен алгоритм определения кратчайшего вектора выпуклой оболочки конечного множества точек евклидового пространства. Алгоритм основан на решении задачи минимизации квадратичной функции в положительном ортанте. Алгоритм предназначен для использования в численных методах оптимизации. Запропоновано...
Gespeichert in:
| Datum: | 2008 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2008
|
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/12708 |
| 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: | Алгоритм проектирования на политоп / Н.Г. Журбенко // Теорія оптимальних рішень: Зб. наук. пр. — 2008. — № 7. — С. 125-131. — Бібліогр.: 2 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860131654923714560 |
|---|---|
| author | Журбенко, Н.Г. |
| author_facet | Журбенко, Н.Г. |
| citation_txt | Алгоритм проектирования на политоп / Н.Г. Журбенко // Теорія оптимальних рішень: Зб. наук. пр. — 2008. — № 7. — С. 125-131. — Бібліогр.: 2 назв. — рос. |
| collection | DSpace DC |
| description | Предложен алгоритм определения кратчайшего вектора выпуклой оболочки конечного множества точек евклидового пространства. Алгоритм основан на решении задачи минимизации квадратичной функции в положительном ортанте. Алгоритм предназначен для использования в численных методах оптимизации.
Запропоновано алгоритм визначення найкоротшого вектора випуклої оболонки кінцевої множини точок евклідового простору. Алгоритм базується на розв’язанні задачі мінімізації квадратичної функції у позитивному ортанті і призначений для використання в числових методах оптимізації.
The algorithm for determining of the nearest vector belonging to a convex hull of finite set in the Euclidean space is suggested. The algrithm is based on solving quadtratic minimization problem in a positive orthant. The algorithm is designed for use in numerical optimization methods.
|
| first_indexed | 2025-12-07T17:45:34Z |
| format | Article |
| fulltext |
Теорія оптимальних рішень. 2008, № 7 125
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Предложен алгоритм определения
кратчайшего вектора выпуклой
оболочки конечного множества
точек евклидового пространства.
Алгоритм основан на решении
задачи минимизации квадратич-
ной функции в положительном
ортанте. Алгоритм предназначен
для использования в численных
методах оптимизации.
Н.Г. Журбенко, 2008
ÓÄÊ 519.8
Í.Ã. ÆÓÐÁÅÍÊÎ
ÀËÃÎÐÈÒÌ ÏÐÎÅÊÒÈÐÎÂÀÍÈß
ÍÀ ÏÎËÈÒÎÏ
1
Задано множество }1,=,{= mkgG k векто-
ров n
kg E∈ в n-мерном евклидовом про-
странстве .nE −}{GCo выпуклая оболочка
множества :G
=1
{ } = { | = ,
m
n
k k
k
Co G x E x g∈ λ∑
=1
=1, 0, =1, }
m
k k
k
k mλ λ ≥∑ .
Задача состоит в определении наименьшего
по норме (евклидовой) вектора ,}{*
GCop ∈
для которого принято обозначение }.{GNr
Определение этого вектора обычно предста-
вляется следующей простейшей задачей ква-
дратичного программирования:
2
*
=1
= arg min
m
k k
k
p g
λ
∑ (1)
,1=
1=
k
m
k
λ∑ (2)
.1,=0, mkk ≥λ (3)
Необходимость в решении задачи определе-
ния вектора { }Nr G возникает во многих ал-
горитмах оптимизации. При этом алгоритм
должен удовлетворять следующим требова-
ниям: учитывать специфические особенности
задачи квадратичного программирования (1)–
(3); быть эффективным и численно устойчи-
вым; определять представление вектора *
p в
виде выпуклой комбинации минимального
1
Работа выполнена при частичной финансо-
вой поддержке CRDF (Фонда гражданских иссле-
дований и развития США, проект UKM2-2812-
KV-06).
Н.Г. ЖУРБЕНКО
126 Теорія оптимальних рішень. 2008, № 7
числа векторов из множества G ; учитывать необходимость решения серии за-
дач с последовательным включением в множество G новых векторов. Известно
несколько программных реализаций алгоритмов с такими свойствами
(например, [1]). Однако опыт их использования показывает недостаточную чис-
ленную устойчивость этих реализаций для задач больших размерностей в си-
туации когда }{0 GCo∈ (или 0* ≈p ). Далее приводится алгоритм, который
(как показал опыт его численного использования) существенно устраняет ука-
занный недостаток.
Рассмотрим следующую задачу:
21
min ,
2
x (4)
,1,=;),( mktgx k ≥ (5)
где ( , )⋅ ⋅ − скалярное произведение в ;n
E 0>t – (произвольное) положительное
число. Двойственная к (4)–(5) задача будет состоять в следующем:
2
=1 =1
1
max min , | | 0 ,
2
m m
n
k k k
xu
k k
x u g x t u x E u
− + ∈ ≥
∑ ∑ (6)
где m
Eu ∈ – двойственные переменные задачи (4)–(5) относително ограничений
(5). Решение задачи минимизации по переменным x в (6) очевидно:
.=
1=
kk
m
k
gux ∑ (7)
Отсюда следует, что (6) состоит в следующем (заменяем операцию min на
max и изменяем знак целевой функции на противоположный):
k
m
k
kk
m
k
utgu ∑∑ −
1=
2
1=2
1
min . (8)
0.≥u (9)
Пусть },,,{= 21 mgggG K – матрица ;mn × ,m
Re∈ .,1)(1,1,= Te K Здесь и
далее
T)(K – операция транспонирования. Тогда задача (8)–(9) представляется
в следующей компактной форме:
,),(),(
2
1
min uetuGuG
T − (10)
0.≥u (11)
Утверждение 1 . Cистема ограничений (5) совместна тогда и только тогда,
когда *
= 0.p /
Если система ограничений (5) совместна, то
АЛГОРИТМ ПРОЕКТИРОВАНИЯ НА ПОЛИТОП
Теорія оптимальних рішень. 2008, № 7 127
,/=
*
1=
*
1=
*
k
m
k
kk
m
k
ugup ∑∑ (12)
где *
u – решение двойственной задачи (8)–(9) (или, что то же, задачи (6)).
Доказательство. Пусть система ограничений (5) совместна. Тогда исходная
(4)–(5) и двойственная (6) задачи разрешимы. Их решения обозначим
*
x и
*
u
соответственно. В силу (7) имеем
.=
*
1=
*
kk
m
k
gux ∑ (13)
Так как 0,>t то 0=x не является допустимой точкой системы (5). Поэто-
му 0.* ≠x Отсюда, учитывая (13) и (9), 0.>*
1=
k
m
k
u∑ Пусть
* *
=1 =1
= / =
m m
k k k
k k
p u g u∑ ∑
* *
=1
= / .
m
k
k
x u∑ Из определения p следут, что }.{GCop ∈
Докажем, что .= *pp Для произвольного 1,l m∈ рассмотрим величину
2
* * * * * * * 2 *
=1 =1 =1 =1
( , ) / , / , / ( ) /
m m m m
l l l k k l k k
k k k k
d g p p g x u x u g x u x u
= − = − = −
∑ ∑ ∑ ∑ . В силу
условия (5) .),( * txgl ≥ Поэтому ./)(/
2
*
1=
2**
1=
−
≥ ∑∑ k
m
k
k
m
k
l uxutd
Условие равенства значений функционалов прямой и двойственной задач
для оптимальных значений переменных состоит в следующем:
* 2 * 2 *
=1
1 1
( ) = ( ) .
2 2
m
k
k
x x t u
− −
∑
Отсюда следует:
* 2 *
=1
( ) = .
m
k
k
x t u∑ Используя полученное выражение для * 2
( ) ,x
получаем справедливость следующей системы неравенств:
.1,=0,),(= mlppgd ll ∀≥− (14)
Однако справедливоть (14) означает, что p является вектором наименьшей
длины из выпуклой оболочки множества векторов ,G а из единственности тако-
го вектора следует: .=
*
pp
Пусть 0.* ≠p Докажем, что система (5) совместна. Так как },{=* GNrp то
,1,=0,),(
**
mkppgk ≥− или ,1,=,)(),(
2**
mkppgk ≥ Пусть * 2 *
= /( ) .x t p p%
Тогда * 2 *
( , ) = /( ) ( , ) , = 1, .k kg x t p g p t k m≥% Таким образом x% удовлетворяет сис-
теме (5). Следовательно, система (5) совместна. Утверждение 1 доказано.
Н.Г. ЖУРБЕНКО
128 Теорія оптимальних рішень. 2008, № 7
Из утверждения 1 следует, что решение задачи поиска наименьшего по но-
рме вектора из выпуклой оболочки системы векторов сводится к решению зада-
чи (8)–(9). Причем, если целевая функция задачи (8)–(9) не ограничена снизу, то
}.{0 GCo∈
Задача (8)–(9) является простейшей задачей квадратичного программирова-
ния. Для ее решения предлагается использовать известный алгоритм, основан-
ный на методе сопряженных градиентов в сочетании с операцией проектирова-
ния на область допустимых значений переменных: 0}|{= ≥+
uuR (подробное
описание алгоритма содержится, например, в [2]). За конечное число шагов этот
алгоритм определяет решение задачи (8)–(9) *u или устанавливает факт неогра-
ниченности целевой функции (8). Во втором случае (когда }{0 GCo∈ ) определя-
ется некоторая точка 0u ≥% и вектор ,0η0, ** ≠≥η такие, что на луче
}0,η~|{ * ≥+== hhuuuL целевая функция неограничено убывает.
Часто для задачи (1)–(3) необходимо не только найти ее решение ,
*
p но и
определить представление этого решения в виде выпуклой комбинации векто-
ров из множества G . Если },{0 GCo∉ такое представление определяется, оче-
видно, формулой (12). В следующем утверждении это представление определяе-
тся и для случая 0 { }.Co G∈
Утверждение 2. Пусть на луче }0,~|{ * ≥η+== hhuuuL , где 0,u ≥%
0* ≥η и 0* ≠η , целевая функция (10) неограничено убывает. Тогда
.}{0 GCo∈ При этом
./=0
*
1=
*
1=
k
m
k
kk
m
k
g ηη ∑∑ (15)
Доказательство. Так как целевая функция исходной задачи (4)–(5) очевид-
но ограничена снизу, а целевая функция двойственной задачи (10)–(11) неогра-
ничена снизу, то система ограничений исходной задачи (5) несовместна. Поэто-
му (см. утверждение 1) 0 { }.Co G∈
На луче L целевая функция (10) неограничено убывает, поэтому для 0>h∀
,0)),~((
** <ηη+ hug где teGuGug
T −=)( – градиент этой функции. Тогда
,0||),~( 2** <η+η− GhteuGGT для 0.>h∀ Отсюда следует равенство 0.=*ηG
Поделив это равенство на положительное число ,*
1=
k
m
k
η∑ получаем (15).
Опишем алгоритм представления вектора *
p (решение задачи) в виде выпу-
клой комбинации минимального числа векторов из множества G .
Пусть .0* ≠p Тогда определен вектор *
u и справедлива формула (12). Ну-
АЛГОРИТМ ПРОЕКТИРОВАНИЯ НА ПОЛИТОП
Теорія оптимальних рішень. 2008, № 7 129
левые значения компонент вектора *
u фиксируем. Это можно интерпретировать
как исключение из множества G всех векторов ,kg для которых .0* =ku Поэто-
му, не ограничивая общности, будем считать, что .,2,1,0*
mkuk K=> Так как
−*
u решение задачи (10)–(11), то градиент ее целевой функции в точке *
u равен
нулю: * *( ) 0.T
g u G Gu te= − = Рассмотрим систему линейных уравнений
( m уравнений, n неизвестных):
0.=ηG (16)
Пусть существует ненулевое решение системы (16) .η Заметим, что если
,nm > ненулевое решение, очевидно, существует. Рассмотрим прямую
}.|{ * η+== huuuL Для ,Lu ∈ .0)()( * =η+= GhGugug T Прямая ,L очевидно,
пересекает границу положительного ортанта 0≥u хотя бы в одной точке. При-
чем определение такой точки *~u элементарно просто (поэтому соответствующий
алгоритм не приводится). Заметим, что ,0~* ≥u при этом хотя бы одна компо-
нента вектора *~u равна нулю. Так как ,0)~( * =ug то *~u – решение задачи. Таким
образом, мы уменьшили (по крайней мере, на единицу) число векторов в пред-
ставлении решения задачи .*
p Описанная процедура применяется до тех пор,
пока существует ненулевое решение соответствующей системы (16). Число век-
торов в представлении решения задачи гарантировано не превышает .n
Пусть .0* =p Тогда, как указывалось выше, определен вектор 0* ≥η ,
0* ≠η . 0* =ηG и справедлива формула (15). Нулевые значения компонент век-
тора
*η фиксируем. Аналогично вышерассмотренному случаю это можно ин-
терпретировать как исключение из множества G всех векторов ,kg для кото-
рых .0* =ηk Поэтому, не ограничивая общности, будем считать, что
.,2,1,0*
mkk K=>η Так как −*
u решение задачи (10)–(11), то градиент ее целе-
вой функции .0)( ** =−= teGuGug
T Рассмотрим систему линейных уравнений
( 1+m уравнений, n неизвестных):
,0=ηG (17)
.0),( * =ηη (18)
Пусть существует ненулевое решение системы (16) .η Заметим, что если
,1 nm >+ то ненулевое решение, очевидно, существует. Рассмотрим прямую
}.|{ * η+η== huuL Для ,Lu ∈ .0=ηG Прямая ,L очевидно, пересекает грани-
цу положительного ортанта 0≥u в двух точках. Причем определение этих то-
чек элементарно просто (поэтому соответствующий алгоритм не приводится).
Н.Г. ЖУРБЕНКО
130 Теорія оптимальних рішень. 2008, № 7
Выберем одну из этих точек .0~* ≥η Заметим, что ,0~,0~ ** ≠η≥η при этом хотя
бы одна компонента вектора *~η равна нулю. Так как ,0* =ηG то для решения
задачи справедливо представление (15). Таким образом, мы уменьшили (по
крайней мере, на единицу) число векторов в представлении решения задачи в
виде выпуклой комбинации. Описанная процедура применяется до тех пор, пока
существует ненулевое решение соответствующей системы (17)–(18). Число век-
торов в представлении решения задачи гарантировано не превышает 1.n +
Заметим, что гарантированное минимальное число векторов в представле-
нии решения задачи в виде их выпуклой комбинации соответствует, разумеется,
известной теореме Каратеодори (для случая 0* ≠p с учетом того, что точка *
p
принадлежит границе множества }{GCo ).
Переходим к схеме использования описанного алгоритма в режиме решения
серии задач с последовательным включением в множество G новых векторов.
Пусть .
~
1+∪= mgGG Для множества G предполагаются известными вектор
0}{ ≠= GNrp и −∈ m
Ru
* решение двойственной задачи (10)–(11). Необхо-
димо решить задачу (10)–(11), соответствующую множеству .
~
G Обычно при
решении этой задачи в качестве начальной точки используют точку
.)0,(~ 1*0 +∈= mTT
Ruu Как показал опыт, эффективность алгоритма несколько
выше, если начальную точку выбирать следующим образом. Пусть
,)1(},{~
11 ++ µ−+µ== mm gpgpNrp где 10 <µ< (представляют интерес обычно
именно такие значения µ ). Тогда определим начальную точку для алгоритма
решения задачи (10)–(11) по формуле
).,)(1/1(,(~ **0
euuu
T
−µ= (19)
Легко проверить, что при этом выполняется равенство
.~/~=~ 0
1
1=
0
1
1=
k
m
k
kk
m
k
ugup ∑∑
++
(20)
Сравнение формулы (20) с (12) поясняет смысл такого выбора начальной
точки.
Формулу (19) целесообразно использовать для выбора значения парамет-
ра t , который можно рассматривать как параметр нормировки задачи (10)–(11).
Его целесообразно выбирать в соответствии со следующим равенством:
1|~||~~~
| 0 +== mtetuGG
T ,
где .)1,1,1(~ 1+∈= mT
Re K Такой выбор соответствует требованию равенства норм
квадратичной и линейной составляющих градиента целевой функции задачи
(10)–(11) в точке .~0
u
АЛГОРИТМ ПРОЕКТИРОВАНИЯ НА ПОЛИТОП
Теорія оптимальних рішень. 2008, № 7 131
В заключение отметим, что разработана программная реализация изложен-
ного алгоритма в форме класса .
++
C
Н.Г. Журбенко
АЛГОРИТМ ПРОЕКТУВАННЯ НА ПОЛІТОП
Запропоновано алгоритм визначення найкоротшого вектора випуклої оболонки кінцевої
множини точок евклідового простору. Алгоритм базується на розв’язанні задачі мінімізації
квадратичної функції у позитивному ортанті і призначений для використання в числових
методах оптимізації.
N.G. Zhurbenko
THE ALGORITHM OF PROJECTING ON A POLYTOPE
The algorithm for determining of the nearest vector belonging to a convex hull of finite set in the
Euclidean space is suggested. The algrithm is based on solving quadtratic minimization problem in
a positive orthant. The algorithm is designed for use in numerical optimization methods.
1. Wolfe P. Finding the nearest point in a polytope // Math. Program. – 1976. – 11, N 2. –
P. 128–149.
2. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах. – М.:
Наука, 1975. – 376 с.
Получено 11.04.2008
|
| id | nasplib_isofts_kiev_ua-123456789-12708 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-12-07T17:45:34Z |
| publishDate | 2008 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Журбенко, Н.Г. 2010-10-20T10:40:33Z 2010-10-20T10:40:33Z 2008 Алгоритм проектирования на политоп / Н.Г. Журбенко // Теорія оптимальних рішень: Зб. наук. пр. — 2008. — № 7. — С. 125-131. — Бібліогр.: 2 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/12708 519.8 Предложен алгоритм определения кратчайшего вектора выпуклой оболочки конечного множества точек евклидового пространства. Алгоритм основан на решении задачи минимизации квадратичной функции в положительном ортанте. Алгоритм предназначен для использования в численных методах оптимизации. Запропоновано алгоритм визначення найкоротшого вектора випуклої оболонки кінцевої множини точок евклідового простору. Алгоритм базується на розв’язанні задачі мінімізації квадратичної функції у позитивному ортанті і призначений для використання в числових методах оптимізації. The algorithm for determining of the nearest vector belonging to a convex hull of finite set in the Euclidean space is suggested. The algrithm is based on solving quadtratic minimization problem in a positive orthant. The algorithm is designed for use in numerical optimization methods. ru Інститут кібернетики ім. В.М. Глушкова НАН України Алгоритм проектирования на политоп Алгоритм проектування на політоп The algorithm of projecting on a polytope Article published earlier |
| spellingShingle | Алгоритм проектирования на политоп Журбенко, Н.Г. |
| title | Алгоритм проектирования на политоп |
| title_alt | Алгоритм проектування на політоп The algorithm of projecting on a polytope |
| title_full | Алгоритм проектирования на политоп |
| title_fullStr | Алгоритм проектирования на политоп |
| title_full_unstemmed | Алгоритм проектирования на политоп |
| title_short | Алгоритм проектирования на политоп |
| title_sort | алгоритм проектирования на политоп |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/12708 |
| work_keys_str_mv | AT žurbenkong algoritmproektirovaniânapolitop AT žurbenkong algoritmproektuvannânapolítop AT žurbenkong thealgorithmofprojectingonapolytope |