Некоторые задачи построения описанных эллипсоидов

Некоторые задачи построения описанных эллипсоидов

Some modifications of circumscribed ellipsoid methods are discussed. There are considered the problems which are important for such modifications – the problem of selecting the most essential cutting planes from a set of ones which were accumulated during previous iterations and the problem of circu...

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2006
Автор: Лаптин, Ю.П.
Формат: Стаття
Мова:Russian
Опубліковано: Інститут кібернетики ім. В.М. Глушкова НАН України 2006
Назва видання:Теорія оптимальних рішень
Онлайн доступ:http://dspace.nbuv.gov.ua/handle/123456789/84956
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Некоторые задачи построения описанных эллипсоидов / Ю.П. Лаптин // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 68-76. — Бібліогр.: 9 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-84956
record_format dspace
spelling irk-123456789-849562015-07-18T03:01:38Z Некоторые задачи построения описанных эллипсоидов Лаптин, Ю.П. Some modifications of circumscribed ellipsoid methods are discussed. There are considered the problems which are important for such modifications – the problem of selecting the most essential cutting planes from a set of ones which were accumulated during previous iterations and the problem of circumscribed ellipsoid construction for intersection of sphere and simplex. 2006 Article Некоторые задачи построения описанных эллипсоидов / Ю.П. Лаптин // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 68-76. — Бібліогр.: 9 назв. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/84956 519.8 ru Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Russian
description Some modifications of circumscribed ellipsoid methods are discussed. There are considered the problems which are important for such modifications – the problem of selecting the most essential cutting planes from a set of ones which were accumulated during previous iterations and the problem of circumscribed ellipsoid construction for intersection of sphere and simplex.
format Article
author Лаптин, Ю.П.
spellingShingle Лаптин, Ю.П.
Некоторые задачи построения описанных эллипсоидов
Теорія оптимальних рішень
author_facet Лаптин, Ю.П.
author_sort Лаптин, Ю.П.
title Некоторые задачи построения описанных эллипсоидов
title_short Некоторые задачи построения описанных эллипсоидов
title_full Некоторые задачи построения описанных эллипсоидов
title_fullStr Некоторые задачи построения описанных эллипсоидов
title_full_unstemmed Некоторые задачи построения описанных эллипсоидов
title_sort некоторые задачи построения описанных эллипсоидов
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate 2006
url http://dspace.nbuv.gov.ua/handle/123456789/84956
citation_txt Некоторые задачи построения описанных эллипсоидов / Ю.П. Лаптин // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 68-76. — Бібліогр.: 9 назв. — рос.
series Теорія оптимальних рішень
work_keys_str_mv AT laptinûp nekotoryezadačipostroeniâopisannyhéllipsoidov
first_indexed 2025-07-06T12:04:44Z
last_indexed 2025-07-06T12:04:44Z
_version_ 1836899091111477248
fulltext 68 Теорія оптимальних рішень. 2006, № 5 ÒÅÎÐ²ß ÎÏÒÈÌÀËÜÍÈÕ Ð²ØÅÍÜ Рассматриваются задачи, возни- кающие при разработке некото- рых модификаций методов опи- санных эллипсоидов – задача ра- ционального выбора наиболее су- щественных отсечений из сово- купности накопленных на преды- дущих итерациях и задача по- строения описанного эллипсоида вокруг пересечения шара и сим- плекса  Ю.П. Лаптин, 2006 ÓÄÊ 519.8 Þ.Ï. ËÀÏÒÈÍ ÍÅÊÎÒÎÐÛÅ ÇÀÄÀ×È ÏÎÑÒÐÎÅÍÈß ÎÏÈÑÀÍÍÛÕ ÝËËÈÏÑÎÈÄΠМетод описанных эллипсоидов [1, 2] обеспе- чивает геометрическую скорость сходимости и является основой многих важных теорети- ческих результатов (см., например [3]). Од- нако показатель скорости сходимости с рос- том размерности решаемых задач стремится к единице, что объясняет практическую не- эффективность этого метода. Для повышения эффективности в работах [4–6] предлагается использовать вместо одного несколько отсе- чений. Как правило, используются (выбира- ются) две отсекающие плоскости, генери- руемые специальным образом, так чтобы угол между ними был меньше 2 π . В настоящей работе рассматриваются за- дачи, возникающие при использовании n отсекающих плоскостей, где n – число пе- ременных. Предлагаются алгоритмы при- ближенного решения этих задач. Модифицированные методы описан- ных эллипсоидов. Рассматривается задача безусловной минимизации выпуклой функ- ции ),(xf n Ex ∈ . В каждой точке n Ex∈ могут быть вычислены значение функции )(xf и некоторый субградиент )(xg . Пред- полагается, что оптимальная точка ∗ x нахо- дится в шаре радиусом 0R с центром в точ- ке 0x . Модифицированными методами описан- ных эллипсоидов будем называть методы, в которых на каждой итерации ,...1,0, =kk считаются заданными НЕКОТОРЫЕ ЗАДАЧИ ПОСТРОЕНИЯ ОПИСАННЫХ ЭЛЛИПСОИДОВ Теорія оптимальних рішень. 2006, № 5 69 � матрица преобразования пространства xAyA kk =, ; � шар { }kkk RyyyS ≤−= : в преобразованном пространстве, в котором со- держится оптимальная точка ∗∗ = xAy k ; � совокупность отсекающих плоскостей (полупространств), накопленных на предыдущих итерациях, { } kikikii IixffxAygyH ∈−≤−= ∗ ,)(),(: , где ki Iix ∈, – точки в исходном пространстве, в которых вычислялись значения функций и субградиенты; ∗ kf – значение рекорда на текущей итерации; ig – субградиент в преобразованном пространстве, соответствующий точке ix , 1),( −∗ == kkiki ABxgBg . На каждой итерации выполняются следующие действия (шаги): 1) некоторым способом генерируются совокупность точек kkj JjSx ∈∈ , и соответствующие отсекающие плоскости (полупространства); 2) выделяется множество отсекающих плоскостей (полупространств), kkk JIT U⊆ ; 3) вокруг пересечения         ∈ II kTi ik HS некоторым образом строится описан- ный эллипсоид kE (очевидно, что эллипсоид kE содержит оптимальную точку ∗ x ); 4) формируется преобразование A , переводящее эллипсоид kE в шар 1+kS ; 5) полагается kk AAA ×=+1 ; 6) формируется множество отсекающих плоскостей (полупространств), kkk JII U⊆+1 . Различные методы отличаются реализацией шагов 1) - 3), 6). В первоначальной версии метода описанных эллипсоидов [1, 2] на каждой итерации генерируется одна точка – центр шара kS (шаг 1), используется одно отсечение, проходящее через центр шара kS (шаг 2), вокруг полушара строится описанный эллипсоид минимального объема (шаг 3), информация о построен- ных ранее отсекающих плоскостях не используется, 01 =+kI (шаг 6). Такой Ю.П. ЛАПТИН 70 Теорія оптимальних рішень. 2006, № 5 алгоритм сходится по объему области локализации с геометрической скоростью с показателем ) 1 ( 2 1 1 2 n O n q +−= . Для оптимального (по числу итераций) метода центров тяжести [7] показа- тель скорости сходимости en n q n 1 1 1 1 −→      + −= , при ∞→n , однако этот метод нереализуем из-за чрезмерной трудоемкости вычислений на каждой ите- рации. Одним из направлений повышения эффективности метода описанных эллип- соидов является использование нескольких субградиентов (отсекающих гипер- плоскостей) при определении области локализации решений задачи на каждой итерации [4, 5, 6]. На шаге 1 по некоторому правилу генерируются вспомога- тельные точки kj Jjx ∈, . На шаге 2, как правило, используются несколько (чаще всего две) отсекающих гиперплоскостей, построенных во вспомогатель- ных точках kj Jjx ∈, . При этом отбираются гиперплоскости, углы между ко- торыми (попарно) меньше 2 π . На шаге 6 при формировании множества отсекающих плоскостей 1+kI для следующей итерации в некоторых реализациях используются операции агреги- рования [6]. Важное значение при реализации таких методов имеют алгоритмы построе- ния описанного эллипсоида kE на шаге 3, которые предложены для относи- тельно простых фигур. В работе [4] рассматриваются три типа фигур: сегмент – часть шара, отсеченная от него плоскостью; слой – часть шара, заключенная между двумя параллельными плоскостями; )(ms -пирамида – часть шара kS , ограниченная совокупностью из m плос- костей, nm ≤ , попарно расположенных под нетупыми углами и проходящими через некоторую внутреннюю точку этого шара (вершину пирамиды). При этом соответствующая совокупность нормалей m ggg ,...,, 21 к плоскостям состав- ляет систему линейно независимых векторов. Предполагается, что все фигуры принадлежат некоторому полушару ша- ра kS . Приведены соотношения, определяющие оптимальные эллипсоиды для сегмента и слоя, исследуются свойства )(ms -пирамид. Вводится понятие c -пирамиды – пересечение )(ms -пирамиды с подпространством mL , порож- денным нормалями m ggg ,...,, 21 . Вершина c -пирамиды принадлежит внут- НЕКОТОРЫЕ ЗАДАЧИ ПОСТРОЕНИЯ ОПИСАННЫХ ЭЛЛИПСОИДОВ Теорія оптимальних рішень. 2006, № 5 71 ренности шара kS , основание лежит на сферической поверхности шара. С c -пирамидой естественным образом связан некоторый симплекс M , натяну- тый на ее ребра. Для случая, когда длина ребер c -пирамиды не превышает по длине радиуса шара kS , приводится алгоритм построения оптимального эллипсоида E , опи- санного вокруг )(ms -пирамиды, с центром в ее вершине. Обозначим { }mip i ,...,1, = набор m -мерных векторов, являющихся реб- рами c -пирамиды, P - матрица векторов столбцов i p . Тогда отношение объе- ма эллипсоида E к объему шара kS будет равно (предполагается, что 1=R ) Pq mn det1 2 −      −= ρ , (1) где ρ - расстояние между центром шара и вершиной c -пирамиды. Поскольку Pdet численно равен объему m -мерного параллелепипеда, натянутого на ребра { }mip i ,...,1, = , то хороший выигрыш по объему получа- ется в случае, когда ребра mip i ,...,1, = лежат под углами, заметно меньшими 2 π . В случае 2=m получаем ϕsin≤q , где ϕ - угол между 1 p и 2 p . Рассматривается также задача построения оптимального эллипсоида, центр которого не совпадает с вершиной )(ms - пирамиды При практической реализации алгоритма использовались сегменты, слои и )2(s -пирамиды, порождаемые двумя отсекающими плоскостями, центр эллип- соида всегда совпадал с вершиной s -пирамиды. На шаге 1 для генерирования точек kj Jjx ∈, используется одномерный поиск вдоль направления, определяемого субградиентом в центре шара kS . Вы- деление подходящих отсекающих плоскостей (пары плоскостей с малым углом между ними) осуществляется перебором и сравнением генерируемых отсечений. Предложенные процедуры позволяют ускорить метод описанных эллипсои- дов при практическом решении задач, однако гарантировать существенное уменьшение объема локализации на каждой итерации не позволяют. В работах [5, 6] на шаге 3 также используются сегменты, слои и )2(s -пирамиды, рассматриваются оптимальные эллипсоиды с центром в вер- шине )2(s -пирамиды. В работе [5] на шаге 1 используются специальные алго- ритмы для генерирования точек kj Jjx ∈, , которые в предельном случае мож- но интерпретировать как ε -субградиентные алгоритмы решения исходной зада- Ю.П. ЛАПТИН 72 Теорія оптимальних рішень. 2006, № 5 чи. В целом в работе предпринимаются усилия для того, чтобы трудоемкость итерации метода эллипсоидов не превышала )( 2 nO . Гарантировать существен- ное уменьшение объема локализации на каждой итерации также не удается. В работе [6] рассматривается алгоритм определения ε -оптимального реше- ния. Для построения отсечений используются ε -субградиенты целевой функ- ции. Предлагается специальная процедура, которая обеспечивает за конечное число шагов построение двух отсекающих плоскостей, угол между которыми не превышает любого заданного значения 0>α . В целом для обеспечения суще- ственного уменьшения объема локализации на итерации ( 7.0≈ ) достаточно применения )( 2 nO процедур приближенной одномерной минимизации. Заметим, что в рассмотренных работах на каждой итерации формируется значительное количество отсечений, а используется только одно или два. Выделение существенных отсечений. Существующие алгоритмы [3, 8] по- зволяют строить описанные (субоптимальные) эллипсоиды вокруг произвольно- го конечного множества точек. Такие алгоритмы обладают полиномиальной трудоемкостью от числа точек. При построении описанного эллипсоида вокруг многогранника { }bAxxM ≤= : , где nmA ×− матрица, должны использоваться вершины этого многогранника. Для того чтобы алгоритмы построения описанных эллип- соидов были реализуемы, число вершин многогранника M должно быть не слишком велико. Простейшим многогранником в пространстве n R является симплекс, число вершин которого равно 1+n . При увеличении числа граней многогранника число вершин растет экспоненциально. В ходе решения оптимизационной задачи число отсекающих плоскостей на- капливается и может достигать больших значений. При построении описанного эллипсоида должны использоваться наиболее существенные отсечения. Пусть многогранник M определяется накопленными отсекающими плоско- стями, { }rxxB ≤= : - текущая локализация множества оптимальных реше- ний (в преобразованном пространстве). Построим вписанный в BM I шар ∗S максимального объема. Отсекающие плоскости, касающиеся шара ∗S , будем использовать как множество ∗ I наибо- лее существенных ограничений. Обозначим iA i -ю строку матрицы A . Без ограничения общности можно считать, что miAi ,...,1,1 == . Будем также предполагать, что nm > . Задача построения вписанного шара максимального объема может быть сформулирована следующим образом: найти НЕКОТОРЫЕ ЗАДАЧИ ПОСТРОЕНИЯ ОПИСАННЫХ ЭЛЛИПСОИДОВ Теорія оптимальних рішень. 2006, № 5 73 zmax (2) при ограничениях mixAbz ii ,...,1, =−≤ , (3) zrx −≤ . (4) Пусть ),( ∗∗ xz - решение задачи (2)-(4), тогда ∗ x - центр вписанного шара, ∗ z - радиус шара. Множество активных в оптимальной точке ограничений вида (3) определяет искомое множество ∗ I . В невырожденном случае nI =∗ , если ограничение (4) активно, в противном случае 1+=∗ nI . Пусть nI =∗ , множество { }rxIibxAxS iie ≤∈≤= ∗,,: (множество { }∗∈≤= IibxAxS iie ,: , если 1+=∗ nI ) будем называть e -пирамидой ( e -симплексом), если каждое ребро { }JibxAxJX ii ∈== ,:)( , ,∗⊂ IJ 1−= nJ , пересекает шар B (текущую локализацию множества оптимальных решений). Построение описанного эллипсоида вокруг пересечения шара и e -симплекса. Пусть определен e - симплекс { }∗∈≤= IibxAxS iie ,: . Рассмот- рим задачу построения «хорошего» описанного эллипсоида вокруг множества BSe I . Обозначим V множество вершин симплекса eS , BVV I=0 , 01 \ VVV = . Пусть задана точка BSx e I∈0 (например, центр вписанного шара ∗ x ). Для каждой точки 1 Vv ∈ обозначим )(vz точку, лежащую на пересечении от- резка ],[ 0 vx с границей шара B . Положим { }11 ),(: VvvzzzV ∈== . Обозначим { }1))(,(: 00 ≤−−= axQaxxE эллипсоид минимального объ- ема, описанный вокруг множества точек 10 VV U . Выпуклая оболочка множест- ва 10 VV U определяет некоторый симплекс «полной размерности». Можно по- казать, что алгоритм построения описанного эллипсоида минимального объема вокруг такого симплекса имеет трудоемкость )( 3 nO операций. Ю.П. ЛАПТИН 74 Теорія оптимальних рішень. 2006, № 5 Обозначим W множество точек пересечения ребер )(JX симплекса eS с границей шара B . Заметим, что точки из множества W могут не принадлежать эллипсоиду 0 E . Для произвольного 0>ρ обозначим { }ρρ ≤−−= ))(,(:),( axQaxxQE . Понятно, что )1,( 00 QEE = . Будем увеличивать эллипсоид ),(0 ρQEE → , изменяя матрицу 0 Q и зна- чение ρ при фиксированном центре a так, чтобы выполнилось ),( ρQEBSe ⊆I . Без ограничения общности можно считать, что матрица 0 Q приведена к диа- гональному виду. Задача увеличения полуосей эллипсоида (уменьшения собст- венных значений матрицы 0 Q ) так, что ),( ρQEW ⊆ , может быть представле- на в виде: найти ∑ = n i i q q 1 lnmax (5) при ограничениях Wwawq n i iii ∈∀≤−∑ = ,1)( 1 2 , (6) niqq ii ,...,1,0 =≤ . (7) При малых изменениях собственных значений niqi ,...,1, = , целевую функ- цию можно линеаризовать. Пусть матрица Q получена в результате решения задачи (5)–(7). Рассмотрим задачу: найти ))(,max( axQax −−=∗ρ (8) при ограничениях ∗∈≤ IibxA ii , , (9) rx ≤ . (10) Очевидно, что для любого ∗≥ ρρ имеет место ),( ρQEBSe ⊆I . При вычислении верхних границ для ∗ρ могут использоваться двойствен- ные квадратичные оценки [9]. НЕКОТОРЫЕ ЗАДАЧИ ПОСТРОЕНИЯ ОПИСАННЫХ ЭЛЛИПСОИДОВ Теорія оптимальних рішень. 2006, № 5 75 Рассмотрим частный случай, когда вне шара B находится только одна вер- шина v′ симплекса eS , т.е. 1|| 1 =V . Множество W в этом случае состоит из n точек. Обозначим { }dpvxxvL =′−=′ ),(:)( – гиперплоскость, проходящая че- рез совокупность точек W , 0>d , { }dpvxxvP ≥′−=′ ),(:)( . Нетрудно ви- деть, что )(vPv ′∉′ и имеет место неравенство { } 1)'(:))(,(max ≤∈−− vPBSxaxQax e II . (11) Поэтому вместо (8)- (10) можно рассматривать задачу: найти ))(,max( axQax −−=ρ , (12) ∗∈≤ IibxA ii , , (13) rx ≤ , (14) dpvx ≤′− ),( . (15) С учетом (11) получаем )1,max(ρρ ≤∗ . Ограничение (15) позволяет существенно сузить множество допустимых то- чек при определении оценки для величины ∗ρ . Обозначим { }1))'(','(:)1,'(' ≤−−= axQaxxQE эллипсоид минималь- ного объема, описанный вокруг сегмента { }rxdpvxx ≤≤′− ,),(: . Очевид- но, что ограничение 1))'(','( ≤−− axQax (16) является избыточным для задачи (12)–(15). Это ограничение может использо- ваться при формировании квадратичной двойственной оценки. Рассмотрим случай, когда вне шара B находится несколько вершин сим- плекса eS , т.е. 1|| 1 >V . Задачи вида (12)–(15) формулируются отдельно для каждой вершины 1 Vv ∈ , ∗ρ равно максимальному из полученных значений. Заключение. Рассмотренные задачи имеют трудоемкость приближенного решения не меньше )( 3 nO , при этом позволяют существенно улучшить показа- тель скорости сходимости модифицированного метода эллипсоидов. Использо- вание таких методов оправдано в задачах, имеющих большую трудоемкость вы- числения значений функций и субградиентов, что характерно для применения схем декомпозиции в математическом программировании. Ю.П. ЛАПТИН 76 Теорія оптимальних рішень. 2006, № 5 Ю.П. Лаптін ДЕЯКІ ЗАДАЧІ ФОРМУВАННЯ ОПИСАНИХ ЕЛІПСОЇДІВ Розглядаються задачі, які виникають при розробці деяких модифікацій методів описаних еліпсоїдів – задача раціонального вибору найбільш суттєвих відсічень із сукупності, що на- копичена на попередніх ітераціях, і задача формування описаного еліпсоїда навколо перети- ну кулі і симплекса. Yu.P.Laptin SOME PROBLEMS OF CIRCUMSCRIBED ELLIPSOID CONSTRUCTION Some modifications of circumscribed ellipsoid methods are discussed. There are considered the problems which are important for such modifications – the problem of selecting the most essential cutting planes from a set of ones which were accumulated during previous iterations and the problem of circumscribed ellipsoid construction for intersection of sphere and simplex. 1. Шор Н.З. Метод отсечения с растяжением пространства для решения задач выпук- лого программирования // Кибернетика. – 1977.– № 1.– С. 94–95. 2. Юдин Д.Б., Немировский А.С. Информационная сложность и эффективные методы решения выпуклых экстремальных задач // Экономика и математические методы. – 1976. – Т. 12, вып.2. – С. 357–369. 3. Shor N. Z. Nondifferentiable Optimization and Polynomial Problems. – London: Kluwer Academic Publishers, 1998. – 381 p. 4. Шор Н.З., Гершович В.И. Об одном семействе алгоритмов для решения задач выпук- лого программирования // Кибернетика. – 1979.– № 4.– С. 62 – 67. 5. Стецюк П.И. Метод центров тяжести простых тел // Кибернетика и системный ана- лиз. – 1996. – № 5. – С.117–138. 6. Журбенко Н.Г. Об одном ε -субградиентном алгоритме минимизации // Теорія оп- тимальних рішень. – 2002. – № 1. – С. 111–118. 7. Левин А.Ю. Об одном алгоритме минимизации выпуклых функций // Докл. Акаде- мии наук СССР. – 1965. – Т. 160.– С. 1244–1247 8. Шор Н.З., Березовский О . А . Построение эллипсоида максимального объема, впи- санного в многогранник, с использованием последовательного растяжения про- странства // Кибернетика и вычислительная техника. – Киев: Наук. думка, 1992.– Вып.93. – С. 1 – 6. 9. Шор Н.З., Стеценко С.И. Квадратичные экстремальные задачи и недифференци- руемая оптимизация. – Киев: Наук. думка, 1989. – 208 с. Получено 14.06.2006

Схожі ресурси