Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 99
Текст из файла (страница 99)
Конечно, возможны и такие ситуации, когда имеются простые аналитические выражения для производных минимизируемой функции,— в таких случаях, возможно, выгоднее применять методы, использующие градиент нли проиаводные более высокого порядка.
Важными характеристиками метода минимизации являются также область сходнмости метода, устойчивость метода к погрешностям, объем памяти ЭВМ, необходимой для реализации метода, удобство программирования, широта класса задач, к которым применим метод, и т. и. Большое количество разнообразных и отчасти противоречивых характеристик методов, недостаточная разработанность методики оценки упомянутых характеристик затрудняют сравнение методов друг с другом. Иногда для сравнения методов минимизации задают некоторой набор тестовых задач (набор таких задач см., например, в (3141) и лучшим признают тот метод, с помощью которого удается решить указанные тестовые задачи с нужной точностью эа меньшее число итераций, меньшее число вычислений значений функции или ее производных, или за меньшее машинное время.
Несомненно, такие «соревнования» методов полезны, хотя и на их основе нельзя делать окончательные выводы о преимуществах того или иного метода. Здесь следует также заметить, что один и тот же метод, примененный для минимизации одной и той же функции, может привести к различным результатам в зависимости от того, на каком алгоритмическом языке составлена программа, каково качество транслятора (квалификация программиста), на какой ЭВМ решается задача и т. д. Конечно, хотелось бы иметь метод, наилучший во всех отношениях.
Однако такого универсального метода пока нет, и вряд ли такой метод существует. Поэтому для эффективного решения конкретной задачи минимизации, по-видимому, нужно разумно сочетать различные методы с учетом всевозможной априорной информации о решаемой задаче (гладкость исходных данных, выпуклость, физические илн какие-либо иные соображения об области возможного расположения точки минимума и т. д.), ОБЩИЕ ЗАМЕЧАНИЯ З ~з1 417 имеющихся вычислительных средств, ресурсов машинного времени и т. п. В тех случаях, когда нет никакой априорной информации о задаче, которую нужно решить, по-видимому, сначала полезно попробовать применить не очень точные, но простые методы минимизации (например, метод перебора значений функций на сетке с небольшим числом узловых точек, метод покоординатного спуска, метод случайного поиска), а затем на основе накопленной информации при необходимости перейти к более точным методам.
2. Успешное решение различных классов прикладныхэкстремальных задач невозможно без пакета минимизации, состоящего из библиотеки подпрограмм, охватывающей достаточно много методов минимизации, а также управляющих и вспомогательных программ. Пакеты минимизации могут быть использованы в автоматизированном или диалоговом режиме. При работе с пакетом в диалоговом режиме математик — вычислитель, получая сведения о текущих результатах, оперативно вмешивается в процесс минимизации, осуществляет переход ог одного метода к другому, изменяет параметры методов, параметры программ. Диалоговый режим работы с пакетом минимизации позволяет лучшим образом использовать опыт и интуицию математика — вычислителя и предъявляет высокие требования к его профессиональным знаниям в области методов решения экстремальных задач.
В тех случаях, когда пользователь, т. е. специалист, проводящий расчеты, не является компетентным в области методов решения экстремальных задач, желательно иметь пакеты минимизации, работающие в автоматическом режиме. Для работы в этом режиме пакет должен содержать управляющую программу, обеспечивающую автоматический выбор наиболее подходящей последовательности используемых методов, их параметров з зависимости от конкретной решаемой задачи.
Принцип построения пакетов минимизации, примеры таких пакетов описаны в ~8, 151. Заметим, что создание эффективно действующих и достаточно универсальных пакетов минимизации, которые могут быть использованы в различных режимах, представляет собой важную и большую научно-техническую задачу. 3. Следует обратить внимание читателя на то, что первоначальная постановка прикладных задач минимизации зачастуго бывает достаточно грубой, упрощенной и предполагает, что в процессе решения задача будет уточняться.
Это значит, что первоначальный вариант задачи не всегда имеет смысл решать слишком точно. Иногда гораздо выгоднее с помощью простых методов, с небольшой затратой машинного времени получить грубые предварительные результаты и затем проанализировать их вместе с экспертами, с заказчиком. Уже при таком упрощон- 4И МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИИ МНОГИХ ПЕРЕМЕНЕ1ЫХ ~ГЛ.
Ь ном анализе может выясниться, что некоторые параметры и ограничения, ранее казавшиеся несущественными и поэтому не учтенные в первоначальной постановке задачи, должны быть включены в нее, и наоборот, часть прежних параметров и ограничений могут оказаться несущественными и без ущерба для существа задачи могут быть опущены. Заметим, что процесс уточнения постановки задачи весьма удобно проводить с помощью пакета минимизации в диалоговом режиме.
Иногда стремятся учесть многие детали задачи и создать слишком подробную математическую модель исследуемого процесса, а затем пытаются найти наилучшие, оптимальные значения всех параметров процесса. Однако такой подход может привести к задаче минимизации с очень большим числом переменных и численное решение такой задачи моясет встретить непреодолимые трудности.
Но даже в тех случаях, когда удается найти оптимальные значения параметров, нх практическое использование может оказаться невозможным пз-за того, что заказчик, будучи не в состоянии охватить полученную информацию, может не понять разумность выработанных на ее основе рекомендаций и может от них вообще отказаться. Поэтому па первых этапах исследования прикладных задач минимизации желательно пользоваться простымн моделями, учитывающими основные, определяющие параметры.
4. К сожалению, последнему совету удается следовать не всегда. Например, математические модели социально-экономических процессов, достаточно адекватно отражающих основные закономерности, как правило, чрезвычайно сложны, содержат большое число переменных и приводят к так называемым задачам минимизации большой размерности. Численное решение таких задач обычными методами становится невозможным даже при использовании самых мощных современных ЭВЫ.
Некоторые классы задач большой размерности допускают разбиение на ряд слабо связанных между собой подзадач, имеющих сравнительно небольшие размерности, решая которые, иногда удается получить приближенное решение исходной задачи. Следует заметить, что задачи минимизации болыпой размерности к настоящему времени изучены слабо. Некоторые методы решения таких задач см., например, в [111, 117, 194, 203, 242, 302, 320, 3301. 5. В ряде методов минимиаации, описанных выше, предполагалось, что начальная точка и,, принадлежащая множеству У, известна.
Для некоторых множеств, таких, как, например, параллелепипед, шар, гиперплоскость, указать такую точку и, совсем нетрудно. Однако не следует думать, что определение точки и, из любого множества У всегда просто. Например, если У=(и~вЕ": д,.(и)=0, ~=1, ..., г), (1) то для определения точки п,ш У нужно решать систему урав- 4»9 овщпв злмвчания пений (вообще говоря, нелинейных). Чтобы найти какую-либо точку множества У=(и»нЕ": у;(и)<0, »=1, ..., т), (2) придется решать систему неравенств. Определение решения систем линейных или нелинейных уравнений и неравенств представляет собой весьма серьезную задачу, которой посвящена обширная литература; см., например, (4, 8, 13, 20, 22, 39, 42, 45, 54, 73, 76, 93, 106, 111, 112, 117, 119, 162, 200, 209, 221, 237— 239, 277, 282, 296, 298, 301, 321, 324, 3351.
Полезно заметить, что задачу нахождения какой-либо точки и„принадлежащей множеству (1) или (2), можно переформулировать в виде задачи минимизации. А именно, в случае множества (1) введем функцию Р (и) = ~ч", д'; (и), и ~ Е", а в случае множества (2) — функцию Р(и) = ~ (шах[у»(и); 0))г, ион Е", р)0, »=1 и рассмотрим задачу минимизации Р(и) — (п(; и»и Е".
Для решения этой задачи могут быть использованы любые подходящие методы минимизации. Если Уча Я», то условие и» ж У равносильно условию Р(и») = 0 = (п1Р(и) = Ра. Если Р,„) О, к»» то У= ~. Если же Р~ = О, но нижняя грань Р(и) на Е" не достигается, то также (7 = И. Если ЕТ =(и я Е: и ш У„я,(и) ( О, 1 = 1, ..., т, д»(и) = О, »=т+1, ..., т), то для определения какой-либо точки и,»и У можно рассмотреть задачу минимизации »» в Р(и) = ~", (шах(у»(и); 0))г+ ~~ ~д»(и)(з- ш(; иенУ», р)0. »=1 1= »1 Здесь предполагается, что множество У» имеет столь простую структуру, что нахождение точки и, »н У» не вызывает трудностей. Задачу отыскания точки, принадлежащей множеству (2), можно свести к несколько иной задаче минимизации а — ш1; з=(и,о)ш С =(з =(и,а)жЕ"+': я»(и)(а, (=1,...,т). (3) 420 метОды минимизации Функций мнОГих пегеменных ~гл, э Понятно, что если У~ 8, то 1п(О(0.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
