РАЗВИТИЕ МЕТОДОВ ГЛАДКОЙ ОПТИМИЗАЦИИ В ИНСТИТУТЕ КИБЕРНЕТИКИ

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

Длительное время в области гладкой оптимизации плодотворно работал академик Б.Н. Пшеничный вместе со своими учениками Ю.М. Данилиным и В.М.Паниным. Основные результаты совместных исследований Б.Н. Пшеничного и Ю.М. Данилина были суммированы в 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.