РАЗВИТИЕ МЕТОДОВ ГЛАДКОЙ ОПТИМИЗАЦИИ В ИНСТИТУТЕ
КИБЕРНЕТИКИ
Одним из ярких направлений научной деятельности академика
В.М.Глушкова, его последователей и учеников были численные методы
оптимизации. Это стало естественным продолжением исследований, связанных
с поиском оптимальных решений и изучением условий экстремумов.
Длительное время в области гладкой оптимизации плодотворно
работал академик Б.Н. Пшеничный вместе со своими учениками Ю.М.
Данилиным и В.М.Паниным. Основные результаты совместных исследований
Б.Н. Пшеничного и Ю.М. Данилина были суммированы в 1975 году в их
монографии "Численные методы в экстремальных задачах"
[1], переведенной на многие языки мира и являющейся одной из лучших
книг в области численных методов оптимизации.
Эти результаты отвечали требованиям, которые предъявлялись
к численным методам в 70-е годы прошлого столетия в связи с усложнением
решаемых задач и развитием теории численных методов. Интерес стали
представлять алгоритмы, более эффективные по сравнению с существовавшими
на то время (в основном это были градиентные методы и метод Ньютона).
Выдвигаемые требования были таковы: методы по трудоемкости итерации
должны приближаться к градиентным (эта трудоемкость сравнительно
невелика), а по скорости сходимости - к методу Ньютона.
Изучались также методы, основанные на идеях, использования
переменной метрики с помощью построения сопряженных векторов. Такие
алгоритмы обладают в сравнительном плане определенными преимуществами:
они не требуют точного вычисления минимума функции в направлении
движения (что достаточно трудоемко), их скорость сходимости выше.
Описанные в [1] методы используют для своей реализации только вычисления
значений функции. Свойства их аналогичны методам, в которых используются
вычисления производных функции.
К концу 60-х годов сформировалась основная группа методов
условной оптимизации - возможных направлений, условного градиента,
проекции градиента, демпфированный метод Ньютона, методы штрафов,
методы множителей и модифицированных функций Лагранжа. В случае
линейных ограничений они, как правило, сохраняли высокие свойства
алгоритмов безусловной оптимизации градиентного и ньютоновского
типов - нелокальную сходимость, эффективность реализации, соответствующие
локальные оценки скорости сходимости ([2, 3] и другие). Однако,
если ограничения нелинейны, то эти методы теряют указанные качества,
поскольку без линейной аппроксимации ограничений ни одна их итерация
не может быть точно реализована за конечное и равномерно ограниченное
число вычислений. Несоответствие между методами безусловной и условной
оптимизации при нелинейных ограничениях было устранено в работах
киевской школы оптимизации в Институте кибернетики, возглавляемым
В.М.Глушковым.
Проведенные исследования открыли путь новому подходу
к решению многих задач о размещении объектов в пространстве , которые
до сих пор рассматривались и решались только аналитическими методами
классической математики. Формулировка проблемы в виде общей оптимизационной
задачи и использование численного метода для ее решения позволили
снять ряд ограничений на формы и размеры объектов, которые требуются
в традиционных методах решения этих задач. Численно были решены
трудные и практически важные задачи кодирования, оптимальной упаковки
шаров в параллелепипед с минимальной суммой сторон и в шар минимального
радиуса, задачи оптимальной укладки мерных параллелепипедов в контейнер.
При этом кроме задач в классической постановке (когда рассматриваемые
шары одинакового радиуса, параллелепипеды - одного размера и ориентации)
впервые были рассмотрены и численно решены задачи упаковки шаров
с различными радиусами и задачи укладки параллелепипедов различной
ориентации и неодинаковых размеров [17].
В.Н.Кузьменко, Э.И.Ненахов, В.М.Панин
Литература
1. Пшеничный Б.Н., Данилин Ю.М. Численные методы
в экстремальных задачах. - М.: Наука, 1975. -320с.
2. Васильев Ф.П. Численные методы решения экстремальных задач. -
М.: Наука, 1983. -518с.
3. Поляк Б.Т. Введение в оптимизацию.- М.: Наука, 1983. -384с.
4. Пшеничный Б.Н. Алгоритм для общей задачи математического программирования
// Кибернетика. -1970. - №5. - С. 120-125.
5. Данилин Ю.М. Методы минимизации, основанные на аппроксимации
исходного функционала выпуклым // Журн. вычисл. математики и матем.
физики. -1970. - 10, №5. - С. 1067-1080.
6. Пшеничный Б.Н. Метод линеаризации. - М.: Наука, 1983. -136с.
7. Панин В. М. Методы конечных штрафов с линейной аппроксимацией
ограничений. I // Кибернетика. -1984. - №2. - С. 44-50; II // Там
же. - №4. - С. 73-81.
8. Панин В. М. Оценки сходимости двух методов линеаризации. // Докл.
АН УССР, Сер. А, -1984. - №5. - С. 77-79.
9. Панин В.М., Соболенко Л.А. Сходимость одного метода линеаризации.
// Методы решения сложных задач математического программирования,
Киев: Ин-т кибернетики им В.М. Глушкова, 1985, С.11-16.
10. Панин В. М. Линейный метод конечных штрафов с регулируемым вектором
спуска. // Кибернетика и системный анализ. -1988. - №5. - С. 50-55.
11. Панин В. М., Пшеничный Б.Н., Лаврина Т.В. Методы аппроксимирующего
программирования в условной оптимизации // Журнал обчислювальної
та прикладної математики. - 2001, №1 (86). - С.61-70.
12. Pang G.S. A B-differentiable equation - based, globally and
locally quadratically convergent algorithm for nonlinear programs,
complementarity and variational inequality problems // Math. Progr.
- 1991. -51, №1. - P. 101-131.
13. Панин В.М., Скопецкий В.В. Нелокальный метод Ньютона для задач
выпуклой оптимизации и монотонных вариационных неравенств // Кибернетика
и системный анализ. -2002. - №5. - С. 43-64.
14. Пшеничный Б.Н., Калжанов М.У. Метод решения вариационных неравенств
// Там же. -1992. - №6. - С. 48-55.
15. Панин В.М., Лаврина Т.В. Проекционные методы решения нелинейных
вариационных неравенств // Системні дослідження та інформаційні
технології. -2002. - №2. - С. 103-117.
16. Панин В.М., Скопецкий В.В., Лаврина Т.В. Модели и методы конечномерных
вариационных неравенств. // Кибернетика и системный анализ. -2000.
- №6. - С. 47-64.
17. Пшеничный Б.Н., Соболенко Л.А. Метод обратно-выпуклого программирования
и укладка параллелепипедов // Кибернетика и системный анализ. -1996.
- №3. - С. 16-26.
|