Анализ методов полиэдральной аппроксимации выпуклых тел и их применение в задачах многокритериальной оптимизации

• Автор: Ефремов, Роман Владимирович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Москва
• Количество страниц: 112 с. : ил

Содержание
Содержание.
Введение.
Глава 1. Теоретический анализ асимптотической эффективности хаусдорфовых методов полиэдральной аппроксимации
1.1. Некоторые понятия теории методов полиэдральной аппроксимации ВКТ многогранниками.

1.2. Формулировка основных результатов главы

1.3. Доказательство основных результатов3

1.3.1. Метрика второй основной квадратичной формы на

поверхности ВКТ

1.3.2. Вспомогательные утверждения

1.3.3. Доказательство основных теорем.

1.4. Анализ метода Уточнения Оценок.
1.5. Достижимость полученных опенок асимптотической эффективности.
Глава 2. Экспериментальный анализ эффективности методов полиэдральной аппроксимации ВКТ.
2.1. Некоторые определения и результаты теории двойственности методов полиэдральной аппроксимации.
2.2. Метод внешней полиэдральной аппроксимации, двойственный к методу УО
2.2.1. Схема отсечения, реализуемая методом УО.
2.2.2. Реализация метода УО
2.2.3. Оценка асимптотической эффективности метода УО
2.3. Методика проведения эксперимента.
2.3.1. План эксперимента
2.3.2. Формирование совокупности эллипсоидов,
участвующих в эксперименте.
2.3.3. Расчет аппроксимирующих последовательностей
2.3.4. Расчет выборочной эффективности
2.3.5. Методика оценки номера многогранника, с которого
можно изучать асимптотические свойства в аппроксимирующей последовательности.
2.3.6. Методика оценки нижней ассимптотической
эффективности
2.4. Анализ экспериментальных данных
2.4.1. Анализ асимптотической эффективности.
2.4.2. Дополнительные результаты
2.5. Выводы из экспериментального исследования
Глава 3. Использование методов аппроксимации в системе поддержки поиска эффективных стратегий улучшения качества воды
3.1. Проблема поддержки поиска эффективных стратегий улучшения качества воды.
3.1.1. Постановка задачи.
3.1.2. Математическая модель планирования качества воды
3.1.3. Использование Метода Разумных Целей.
3.2. Метод Экономного Описания Аппроксимации
3.2.1. Описание метода.
3.2.2. Экспериментальное исследование метода.
3.3. Система поддержки поиска стратегий улучшения качества воды
3.3.1. Описание системы
3.3.2. Пример использования системы
3.3.3. Результаты экспериментального использования метода
ЭОА в системе.
Заключение
Приложение
Иллюстрации к главе 1
Иллюстрации к главе 2
Иллюстрации к главе 3.
Литература


Под итеративным методом полиэдральной аппроксимации тела С понимают метод, в котором строятся последовательности телесных многогранников Р( Р1,. С, причем на каждой итерации п последующий многогранник Рп строится на основе предыдущего за счет добавления к совокупности его вершин (либо к совокупности его гиперграней) единственной новой вершины (гиперграни). Итеративные методы различаются способом построения последующего многогранника по предыдущему. В данной работе рассматриваются методы, использующие две схемы построения последующего многогранника по предыдущему: схему восполнения и схему отсечения. С и построения нового вписанного в С многогранника Р”'] := сопч{рпиР}. Конкретные методы, основанные на схеме восполнения, можно характеризовать способами решения двух задач: способом выборарпедС и способом построения сопу{рп^Р) в требуемом виде. В схеме отсечения предполагается построенным описанный вокруг тела С многогранник Р! Тогда (я+1)-я итерация состоит из двух шагов: выбора направления и„€У‘] и построения нового описанного вокруг С многогранника рп+ ;= рггЬ(ипу С), где Ь(ип, С) - опорное к С гиперпрострапство, с нормалью ип. Конкретные методы, основанные на схеме отсечения, можно характеризовать способами решения задач выбора направления ип и построения РГ1глЬ(ип, С) в требуемом виде. К^: ||и|| = 1}. Схема восполнения реализуется следующим образом. С. Тогда для некоторого направления ип ео _1 находится такая граничная точка р„, что g{un, С). С многогранника соп{рг^Рп). В случае схемы отсечения считается, что задан многогранник Р,}, описанный вокруг С. Тогда для некоторого направления ипе? С), вместе с ип определяющее полупространство Ь = {у е <и,„у> < g(м,? С)}, которое затем используется для построения нового описанного вокруг С многогранника 7я п I. Х). Наиболее эффективными являются адаптивные методы выбора направлений ипеЗИ направление выбирается на основе информации об аппроксимируемом теле, полученной на предыдущих итерациях. Впервые идеи адаптивной аппроксимации тел были предложены в [] и []. В [] для аппроксимации части границы двумерного выпуклого тела было предложено уточнение вписанного в тело аппроксимирующего многогранника в направлении нормали того ребра, на котором достигается наибольшее отклонение многогранника от аппроксимируемого тела. В [] предложено аппроксимировать проекцию выпуклого компактного множества последовательностью многогранников. Синтез этих двух идей осуществлен в методе Уточнения Оценок (УО) []. ВКТ многогранниками, используемым на практике. Метод У О состоит в следующем. Пусть требуется аппроксимировать тело С. Пусть задана желаемая точность аппроксимации ? На я-й итерации должен быть построен вписанный в тело С многогранник Рп в виде как множества решений системы линейных неравенств, так и списка вершин, для которых указана принадлежность к гиперграням многогранника (так называемое двойное описание). Пусть ЩРп) - множество единичных внешних нормалей гиперграней многогранника Р' которое можно считать заданным системой линейных неравенств, описывающей многогранник Р”. Тогда я+1-я итерация метода УО состоит в следующем. На первом шаге для каждого из неравенств описания многогранника Рп (т. Рп)) рассчитываем опорную функцию тела С на основе решения соответствующей задачи оптимизации (1). Выбираем такое направление иеЩР*), для которого величина g( иу С) - g{ и, Рп) максимальна. Отметим, что в процессе расчета опорной функции для направлений иеи(Рп) находятся и точки р границы тела С, что <г/, /? С). Если величина тах {g{UyC) - g{lly Рп) иеи(Р")} меньше желаемой точности аппроксимации ? В противном случае, строится выпуклая оболочка многогранника Рп и точки рп, соответствующей направлению ип, на котором достигается тах {g(Uy С) -g(u, Рп): пе(/(Р*)}. Сложная операция построения сопу{р„ и Рп) в виде множества решений системы линейных неравенств осуществляется на основе специально разработанного алгоритма, использующего двойное описание многогранника Рп []. Множество сопу{/7„ и РГ)} используется в качестве новой аппроксимации Рпт] множества С.