URSS.ru - Издательская группа URSS. Научная и учебная литература
Об издательстве Интернет-магазин Контакты Оптовикам и библиотекам Вакансии Пишите нам
КНИГИ НА РУССКОМ ЯЗЫКЕ


 
Вернуться в: Каталог  
Обложка Дикин И.И. Метод внутренних точек в линейном и нелинейном программировании
Id: 101578
 
209 руб.

Метод внутренних точек в линейном и нелинейном программировании

URSS. 2010. 120 с. Мягкая обложка. ISBN 978-5-396-00035-3.

 Аннотация

В монографии исследуются методы определения внутренних точек допустимой области и множества решений задач математического программирования. Представлены теоремы сходимости последовательности векторов двойственных оценок для полностью вырожденных линейных систем, изучаются контрпримеры. Рассматриваются две классические проблемы обработки наблюдений, а также задача быстрой корректировки режима электроэнергетической системы. Для решения задач, среди ограничений которых есть нелинейные, предлагается эффективный вариант метода Ньютона. Установлена сходимость последовательных приближений к внутренней допустимой точке нелинейной системы. Исследуются задачи геометрического, полуопределенного программирования, построения области асимптотической устойчивости на плоскости и поиска потокораспределения в гидравлической системе с регуляторами. Для иллюстрации сходимости представленных алгоритмов предлагаются примеры. Проведен анализ непрерывных алгоритмов. Изучается предельное поведение траекторий, используется техника, характерная для прямого метода Ляпунова.

Книга предназначена для математиков и инженеров, а также для всех интересующихся теорией и приложениями методов оптимизации.


 Оглавление

Предисловие
Введение
1. Метод внутренних точек для задачи линейного программирования
 1.1.Прямая и двойственная задачи
 1.2.Улучшение допустимого вектора
 1.3.Нахождение чебышевской точки несовместной системы линейных уравнений
 1.4.Задача быстрой корректировки режима электроэнергетической системы
 1.5.Линейная система специального вида
 1.6.Минимизация суммы модулей линейных функций
 1.7.Определение внутренней точки линейных неравенств
 1.8.Учет двусторонних неравенств
 1.9.Решение общей задачи линейного программирования
 1.10.Исследование сходимости
 1.11.Минимизация линейной формы
 1.12.Контрпримеры
 1.13.Метод Кармаркара
2. Задачи с нелинейными ограничениями
 2.1.Решение системы равенств и неравенств
 2.2.Решение задачи нелинейного программирования
 2.3.Расчет потокораспределения в гидравлической системе с регуляторами
 2.4.Построение области асимптотической устойчивости на плоскости
 2.5.Решение одной задачи геометрического программирования
 2.6.Исследование задачи полуопределенного программирования
3. Непрерывные варианты метод
 3.1.Минимизация гладкой функции
 3.2.Определение минимума позинома
 3.3.Линейная и нелинейная дополнительность
Список литературы

 Предисловие

Данная книга является последней работой математика Ильи Иосифовича Дикина (14.04.1936--28.02.2008).

Илья Иосифович был аспирантом (1963--1966) выдающегося отечественного ученого, лауреата Нобелевской премии, основоположника линейного программирования академика Леонида Витальевича Канторовича. Несомненно, Л.В.Канторович имел глубокие идеи о методах решения задач линейного программирования, но он почти не оставил их четких описаний. В то же время в работе со своими учениками он передавал им некоторые из этих идей, исследуя конкретные задачи. В результате такого взаимодействия в 1967 году в Докладах Академии Наук СССР появилась статья И.И.Дикина "Итеративное решение задач линейного и квадратичного программирования", в которой по существу были заложены основы метода, получившего впоследствии название "метод внутренних точек". При этом задача решалась с помощью специальных вписанных в допустимое множество эллипсоидов. Нужно вспомнить, что 1967 год относился к периоду безраздельного господства симплекс-метода как основного инструмента решения задач линейного программирования, и появление нового метода совсем другого типа не привлекло большого интереса. Ситуация кардинально изменилась в 1984 году, после публикации статьи американского математика Кармаркара. В ней предлагался некий итеративный метод линейного программирования и оценивалась его сложность (количество вычислений, необходимых для достижения заданной точности). Эта сложность оказалась полиномиальной, т.е. полиномиально зависящей от размерности задачи. В то же время для симплекс-метода уже были построены примеры, в которых число итераций оказывалось экспоненциальным. Более того, на многих примерах большой размерности метод Кармаркара продемонстрировал высокую вычислительную эффективность по сравнению с симплекс-методом. В период триумфального шествия алгоритма Кармаркара по миру было выяснено, что он имеет много общего с методом Дикина, который почти на 20 лет старше! Это привлекло большое внимание к работе 1967 года и к дальнейшим исследованиям И.И.Дикина по модификации и обоснованию метода. Его работы получили международное признание; введенные им эллипсоиды получили название "эллипсоидов Дикина". Ныне метод внутренних точек -- наиболее популярный и перспективный инструмент решения задач выпуклой оптимизации; ему посвящены сотни статей и монографий, а его программные реализации включены в основные пакеты по оптимизации.

Сам Илья Иосифович, после окончания аспирантуры Новосибирского университета, работал сначала в этом же городе, а затем в Иркутске, причем с 1971 года -- в Сибирском энергетическом институте СО АН СССР (ныне -- Институт систем энергетики им.Л.А.Мелентьева СО РАН). Он продолжал теоретические исследования методов оптимизации и широко применял их для решения практических задач электроэнергетики. Он привлек многих своих коллег к этой деятельности. В частности, в 1980 году появилась содержательная монография И.И.Дикина и В.И.Зоркальцева "Итеративное решение задач математического программирования: алгоритмы метода внутренних точек"; впоследствии второй автор стал активно самостоятельно работать в этой области.

Предлагаемая читателю книга -- попытка Ильи Иосифовича рассказать о своих последних результатах и опыте их практического использования. Конечно, она не может рассматриваться как учебник, в ней нет систематического описания истории метода внутренних точек, изложения современных результатов других авторов, обширной библиографии. К сожалению, такая библиография в основном содержала бы зарубежные публикации, труднодоступные отечественному читателю. Чтобы облегчить читателю ориентацию в сложном мире методов внутренних точек, редакторы позволили себе несколько расширить список литературы и добавили некоторые замечания в тексте. Нам кажется, что публикуемая книга, содержащая многие идеи пионера метода внутренних точек И.И.Дикина, представляет несомненный интерес. Нужно только иметь в виду, что термин "метод внутренней точки" в современной литературе приобрел несколько иной смысл, чем исходный, заложенный основателем метода -- рассматриваются иные вычислительные схемы, доказываются результаты о сложности метода а не о его сходимости), он применяется для задач выпуклой а не только линейной) оптимизации и т.д. Предложенный же И.И.Дикиным метод получил название "affine scaling method".

Следует отметить серьезную поддержку в издании книги директора Института систем энергетики, члена-корреспондента РАН Николая Ивановича Воропая. Конечно, книга не увидела бы свет без огромной работы вдовы и соавтора Ильи Иосифовича -- Ольги Михайловны Поповой.

Доктор технических наук Б.Т.Поляк,
доктор физико-математических наук Ю.Е.Бояринцев,
доктор физико-математических наук В.Ф.Чистяков

 Введение

Метод внутренних точек предложен автором в 1967 г. [15, 16] и развивался им с соавторами в последующие годы [17--45, 80--91]. В монографии акцентируется внимание на важных прикладных и теоретических аспектах. Описывается опыт успешного решения прикладных задач, для иллюстрации сходимости алгоритмов предлагаются примеры. Представлены теоремы сходимости.

В гл.1 изучаются алгоритмы определения внутренних точек допустимой области и множества решений задачи линейного программирования. Описывается алгоритм улучшения допустимого вектора, при реализации которого допустимой точке ставится в соответствие вектор двойственных переменных. Экспериментально установлено, что при использовании метода внутренних точек двойственные переменные сходятся быстрее к оптимальному решению, чем прямые переменные. Рассматриваются две классические проблемы обработки наблюдений и задача быстрой корректировки режима электроэнергетической системы. При решении исследуемых в этой главе содержательных задач линейного программирования предлагается применить алгоритм улучшения допустимого вектора для решения двойственной задачи.

Отметим, что у метода внутренних точек есть эффективный способ поиска начального приближения. Рассматривается итерационный процесс определения относительно внутренней допустимой точки, при этом учитываются двусторонние неравенства. Представлены теоремы сходимости последовательности векторов двойственных оценок для полностью вырожденных линейных систем, изучаются контрпримеры. Используются потенциальные логарифмические функции. Получены оценки изменения этих зависимостей. Рассматривается метод Кармаркара.

В гл.2 представлен эффективный вариант метода Ньютона. Предполагается, что среди ограничений есть нелинейные. При этом при построении вспомогательной задачи не рассматриваются ограничения в форме неравенств и решается классическая экстремальная проблема. Неравенства учитываются с помощью специального выбора весовых коэффициентов и длины шага. Если все соотношения, определяющие допустимую область, являются линейными, то получаем итерационные процессы, рассматриваемые в первой главе. Исследуется локальная сходимость алгоритма. Установлена сходимость последовательных приближений к относительно внутренней допустимой точке нелинейной системы. Рассматривается применение метода к экстремальным задачам. При реализации предлагаемого подхода процесс оптимизации чередуется с вводом в допустимую область.

Представлена проблема определения потокораспределения в гидравлической системе с регуляторами расхода и давления. Это интересная задача, для решения которой требуется привлекать вычислительные алгоритмы, позволяющие эффективно учитывать ограничения в форме неравенств. Известно, что при описании каждого регулятора требуется рассмотреть два неравенства, удовлетворяющие условиям сопряженности. В работе впервые к этим ограничениям добавляется простое уравнение и предлагается использовать малоизвестную модификацию метода Ньютона. При этом последовательные приближения принадлежат внутренности области, определяемой линейными неравенствами, и сходятся к решению, которое находится на границе. Здесь, в отличие от базового варианта метода, матрица Якоби является квадратной. Доказана локальная сходимость алгоритма.

Метод внутренних точек и компьютерная графика применяются для построения области притяжения динамической системы на плоскости. Используются положения прямого метода Ляпунова. Приведен пример для иллюстрации эффективности исследуемого подхода.

Исследуется глобальная сходимость метода решения задачи геометрического программирования с одним вынужденным ограничением. Предлагаемый алгоритм можно использовать при поиске химического равновесия системы идеальных газов.

Предлагается итеративный алгоритм определения допустимого решения задачи линейного полуопределенного программирования. Устанавливается глобальная сходимость метода решения однородной задачи, имеющей единственное решение. Рассматриваются две стратегии выбора величины шага.

Гл.3 посвящена исследованию сходимости непрерывных процессов метода внутренних точек. Рассматриваются задачи квадратичного программирования, линейной и нелинейной дополнительности. Проведен анализ непрерывных алгоритмов, которые ставятся в соответствие этим проблемам. Изучается предельное поведение траекторий. Используется техника, характерная для прямого метода Ляпунова.

По мнению автора, книга может оказаться полезной как для прикладников, так и для теоретиков.


 Об авторе

Илья Иосифович ДИКИН (1936--2008)

Кандидат физико-математических наук. В 1963--1966 гг. был аспирантом лауреата Нобелевской премии академика Л. В. Канторовича. С 1971 г. работал в Институте систем энергетики им. Л. А. Мелентьева СО РАН. Автор оригинального метода решения задач математического программирования -- метода внутренних точек.

 
© URSS 2016.

Информация о Продавце