Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

full_book

.pdf
Скачиваний:
53
Добавлен:
27.03.2015
Размер:
6 Мб
Скачать
☆

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

номера следует добавить в множества Ja или Jb, соответственно, дополнительно применив правила их коррекции (7.73), (7.74) для k=k+1.

Если же перемещение точки должно быть выполнено с фиксированным коэффициентом длины шага (как это происходит, например, в методе Ньютона), то, в случае выхода точки за пределы изменения переменных, коэффициент x длины шага уменьшается таким образом, чтобы точка y k+1=y k+xkd k оказалась на границе области D. Далее выполняется описанная выше коррекция множеств

Ja и Jb.

Осталось рассмотреть случай, когда одномерное перемещение в пространстве переменных yw не приводит к выходу точки y k+1 на новые фрагменты границы. В этом случае необходимо проверить условия возврата к многообразию или пространству более высокой размерности, который может быть выполнен за счет исключения из множеств Ja или Jb номеров части переменных. Правила исключения следующие:

Ja := Ja \{i Ja: ∂ f(y k)/∂yi<0 }

(7.75)

Jb := Jb \ {i Jb: ∂ f(y k)/∂yi>0 }.

(7.76)

Условия исключения переменной в (7.75), (7.76) определяются тем, что в текущей точке поиска становится положительной проекция антиградиента функции f на внутреннюю (по отношению к области D ) нормаль к гиперплоскости y i = a i. При выполнении этого условия существует направление смещения с этой гиперплоскости внутрь области, при котором функция f будет локально убывать. Таким образом, если в результате коррекции (7.75), (7.76) хотя бы одно из множеств Ja или Jb изменится, необходимо перейти к поиску в многообразии более высокой размерности, выполнив в нем рестарт метода из последней точки предшествующего поиска, аналогично тому, как это было описано выше.

7.8.3.2.Учет двусторонних ограничений в методах прямого поиска

Вметодах прямого поиска способ учета двусторонних ограничений уникален для каждого из этих методов. Более того, некоторые из них не имеют точных модификаций для задач с двусторонними ограничениями. Типичным примером является метод Нелдера–Мида. Некоторые же методы, например метод Хука–Дживса, напротив, легко обобщаются на такие задачи.

Рассмотрим принципы модификации для метода Хука–Дживса. В нем выполняются действия только двух типов: шаг по образцу и построение конфигурации.

С учетом ограничений, шаг по образцу выполняется таким образом, что при выходе рабочей точки за границы области D величина последнего смещения корректируется так, чтобы точка оказалась на границе D. При построении конфигурации в обычном методе координатные перемещения выполняются с шагом h. В модифицированном методе величины координатных перемещений не превосходят h, а в случае, если эти перемещения выводят из области D, заменяются на перемещения до границ этой области.

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

Городецкий С.Ю.

Лекция 2.19–2.22

51

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

книге Ф. Гилла и У. Мюррея [13]. Кроме того, учет двусторонних ограничений на переменные в этом методе можно выполнить с использованием общего метода внешнего штрафа, который был рассмотрен в разделе 3.2.

Заключение

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

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

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

52

Лекция 2.19–2.22

Городецкий С.Ю.

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

Лист регистрации изменений

Дата

Автор

Комментарии

08.11.01

Городецкий С.Ю.

Создание документа и раздела 7.7

15.08.01

Городецкий С.Ю.

Создание раздела 7.2

28.08.01

Городецкий С.Ю.

Создание раздела 7.3

24.07.02

Городецкий С.Ю.

Создание раздела 7.1

24.07.02

Городецкий С.Ю.

Внесение изменений в раздел 7.1

25.07.02

Городецкий С.Ю.

Внесение изменений в раздел 7.2

26.07.02

Городецкий С.Ю.

Внесение изменений в раздел 7.3

27.07.02

Городецкий С.Ю.

Внесение изменений в разделы

 

 

7.4–7.7

28.07.02

Городецкий С.Ю.

Внесение изменений в раздел 7.8

29.07.02

Городецкий С.Ю.

Внесение изменений в раздел 7.8

19.11.03

Городецкий С.Ю.

Добавление и оптимизация

–

 

рисунков в разделах 7.1–7.6,

22.11.03

 

корректура этих разделов

23.11.03

Городецкий С.Ю.

Корректура разделов 7.7–7.8

–

 

 

26.11.03

 

 

Городецкий С.Ю.

Лекция 2.19–2.22

53

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации».

Часть 2. Нелинейное программирование и многоэкстремальная оптимизация. Литература

Литература

Основная литература

10.Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. – М.: Мир,

1982.

11.Бертсекас Д. Условная оптимизация и методы множителей Лагранжа.– М.: Радио и

связь, 1987

12.Васильев Ф.П. Численные методы решения экстремальных задач. – М.:Наука, 1982.

13.Гилл Ф., Мюррей У.,Райт М. Практическая оптимизация.– М.: Мир, 1985.

14.Карманов В.Г. Математическое программирование. – М.:Наука, 1986.

15.Подиновский В.В, Ногин В.Д. Парето–оптимальные решения многокритериальных задач.– М.: Наука, 1982

16.Стронгин Р.Г. Численные методы многоэкстремальной оптимизации (информационно– статистические алгоритмы) – М.:Наука, 1978.

17.Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. – М.:Наука,1986.

18.Strongin R.G.,Sergeev Ya.D. Global Optimization with Non–Convex Constraints. Sequential and Parallel Algorithms.– Dordrecht: Kluver Academic Publishers. The Netherlands, 2000.

Дополнительная литература

19.Аоки М. Введение в методы оптимизации.– М.:Наука, 1977.

20.Батищев Д.И. Поисковые методы оптимального проектирования. М.: Советское радио,

1975.

21.Гермейер Ю.Б. Введение в теорию исследования операций. М.: Наука, 1971.

22.Гилл, у, Мюррей Численные методы условной оптимизации. — М.:Мир, 1977, п.7.13.

23.Городецкий С.Ю., Неймарк Ю.И. О поисковых характеристиках алгоритма глобальной оптимизации с адаптивной стохастической моделью. // Проблемы случайного поиска./ Под ред. Л.А. Растригина. Рига: Зинатне, 1981. Вып.9 стр. 83-105.

24.Городецкий С.Ю. Сходимость и асимптотические оценки поведения для одного класса методов поиска. // Динамика систем. Динамика и управление. Горький: ГГУ, 1984.

25.Городецкий С.Ю. Метод поиска условного глобального минимума, основанный на простых вероятностных моделях минимизируемой функции и функций ограничений. //Динамика систем. Управление и оптимизация. Горький: ГГУ, 1987.

26.Городецкий С.Ю. Процедура решения задач многокритериальной оптимизации, основанная на простых адаптивных вероятностных моделях критериев. //Непараметрические и робастные методы в кибернетике и информатике. Материалы VII Всесоюзного семинара. Томск:

изд-во ТГУ, 1990. Часть 1, с.156–159.

27.Городецкий С.Ю. Методы поиска множества решений многокритериальных задач на основе простых вероятностных моделей критериев. ННГУ, Н.Новгород, 1992. — Деп. в ВИНИТИ

25.03.92, № 1024–В92, 18 с.

28.Городецкий С.Ю. Многоэкстремальная оптимизация на основе триангуляции области.// Математическое моделирование и оптимальное управление. Вестник Нижегородского государственного университета. Вып. 2(21). Н.Новгород: изд-во ННГУ, 1999, с.249–269.

29.Городецкий С.Ю. Методы многоэкстремальной оптимизации на основе триангуляции области поиска. //В кн.: Первая всероссийская научно-практическая конференция по вопросам решения научно-практических задач в промышленности ОПТИМ–2001. Сборник докладов. — С-

Пб.: ЦНИИТС, 2001, с.191–196.

30.Гришагин В.А. Об условиях сходимости для одного класса алгоритмов глобального поиска. – В сб.: Тезисы докл. III Всес. семинара "Численные методы нелинейного программирования". Харьков:ХГУ, 1979, с. 82-84.

Городецкий С.Ю., Гришагин В.А. Литература

стр.1

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации».

Часть 2. Нелинейное программирование и многоэкстремальная оптимизация. Литература

31.Гришагин В.А., Стронгин Р.Г. Оптимизация многоэкстремальных функций при монотонно унимодальных ограничениях. //Изв. АН СССР. Техническая кибернетика, 1984, №4, с. 203-208.

32.Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. –М.:Наука, 1982.

33.Евтушенко Ю.Г., Потапов М.А. Методы численного решения многокритериальных задач. //ДАН, 1986, т.28, № 11.

34.Евтушенко Ю.Г., Потапов М.А. Численные методы решения многокритериальных задач. //В кн.: Кибернетика и вычислительная техника. Вып.3. — М.: Наука, 1987, с.209–218.

35.Евтушенко Ю.Г., Ратькин В.А. Метод половинных делений для глобальной оптимизации функций многих переменных. //Техническая кибернетика. 1987, №1, с.119–127.

36.Жиглявский А.А., Жилинскас А.Г. Методы поиска глобального экстремума.–М.: Наука,

1991

37.Жилинскас А.Г. Одношаговый байесовский метод поиска экстремума функций одной переменной. // Кибернетика 1975, № 1 с. 139–144.

38.Лузин Н.Н. Теория функций действительного переменного. — М.: Учпедгиз,1948.

39.Маркин Д.Л., Стронгин Р.Г. О равномерной оценке множества слабоэффективных точек

вмногоэкстремальных многокритериальных задачах оптимизации. //ЖВМиМФ. 1993,т.33,N 2.

40.Методы поиска глобального экстремума. Методические указания./ Сост. Городецкий С.Ю.– Горький:, ГГУ, 1990.

41.Моцкус Й.Б. О байесовских методах поиска экстремума. //Автоматика и вычислительная техника, 1972, № 3, с.53–62.

42.Моцкус Й.Б. Исследование простого байесого алгоритма для решения многоэскстремальных задач. ИМиК АН ЛССР, Вильнюс, 1979. — Деп. В ВИНИТИ 1979, № 4291– 79, 8с.

43.Неймарк Ю.И. Динамические системы и управляемые процессы.— М.: Наука, 1978.

44.Неймарк Ю.И., Стронгин Р.Г. Информационный подход к задаче поиска экстремума функций. //Известия АН СССР. Техническая кибернетика, 1966, №1, с.17-26.

45.Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации.

– М.: Наука, 1979.

46.Пиявский С.А. Алгоритмы отыскания абсолютного минимума функций. //В кн.: Теория оптимальных решений. Вып.2. Киев, 1967, с.13-24.

47.Пиявский С.А. Один алгоритм отыскания абсолютного минимума функции. //ЖВМ и МФ, №4, 1972, с.888-896.

48.Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах.– М.:

Наука, 1975.

49.Сергеев Я.Д., Квасов Д.Е. Адаптивные диагональные кривые и их программная реализация. // Вестник ННГУ. Мат. Моделирование и оптимальное управление. Вып. 2(24), 2001,

с.300–317.

50.Соболь И.М., Статников Р.Б. Выбор оптимальных параметров в задачах со многими критериями. — М.: Наука, 1981.

51.Стронгин Р.Г. Поиск глобального оптимума. –М.:Знание,1990.

52.Стронгин Р.Г., Гергель В.П., Городецкий С.Ю., Гришагин В.А., Маркина М.В. Современные методы принятия оптимальных решений. — Н. Новгород: Изд-во ННГУ, 2002.

53.Стронгин Р.Г., Маркин Д.Л. Минимизация многоэкстремальных функций при невыпуклых ограничениях.// Кибернетика №4, 1986, с.64-69.

54.Сухарев А.Г. Оптимальный поиск экстремума. – М.: Изд МГУ, 1975.

55.Уайлд Д.Дж. Методы поиска экстремума. 1967.

56.Химмельблау Д. Прикладное нелинейное программирование. –М.:Мир, 1975.

57.Черноусько Ф.Л., Меликян. Игровые задачи управления и поиска.–М.: Наука, 1978

Городецкий С.Ю., Гришагин В.А. Литература

стр.2

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации».

Часть 2. Нелинейное программирование и многоэкстремальная оптимизация. Литература

58.Шор Н.З. О скорости сходимости метода обобщенного градиентного спуска с растяжением пространства. //Кибернетика, № 2, 1970.

59.Kushner H.J. A versatile Stochastic model of a function of unknown and tire-varing form. //J. Math. anal and appl. v5, №1, 1962, pp.150-167.

60.Kushner H. A New Method of Locating the Maximum Point of an Arbitrary Multipeak Curve in the Presence of Noise. //Transactions ASME, Ser. D, J. Basic Eng., 1964, vol.86, №.1, p.97-106.

61.Pinter J. Global optimization in Action. –Dordrecht: Kluwer Academic Publishers. The Netherlands, 1996.

62.Strongin R.G., Sergeyev Ya.D., Grishagin V.A. Parallel Characteristical Algorithms for Solving Problems of Global Optimization // Journal of Global Optimization,10, 1997, pp. 185-206.

63.Sergeyev Ya.D. On Convergence of "Divide the Best" Global Optimization Algorithms. //Optimization, Vol.44, 1998, pp.303-325.

64.Sergeyev Ya.D. An efficient strategy for adaptive partition of N–dimentional intervals in the framework of diagonal algoritms. // Journal of Optimization Theory and Applications, vol.107, №.1, 2000, pp. 145–168.

65.Sergeyev Ya.D., Grishagin V.A. А Parallel Method for Finding the Global Minimum of Univariate Functions. // Journal of Optimization Theory and Applications, vol.80, №.3, 1994.

Это будет указано в сносках

Митягин Б.С.Два неравенства для объемов выпуклых тел. – Мат. заметки, 1969, т.5, вып.1.

Белоглазов И.Н., Джанджагава Г.И., Чигин Г.П. Основы навигации по геофизическим полям /Под ред.А.А.Красовского.— М.: Наука, 1985.

Городецкий С.Ю., Гришагин В.А. Литература

стр.3

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации».

Часть 2. Нелинейное программирование и многоэкстремальная оптимизация. Литература

Городецкий С.Ю., Гришагин В.А. Литература

стр.4

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]