Главная > Методы обработки сигналов > Численные методы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 6. Как оптимизировать?

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

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

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

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

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

а) программа эффективно решает задачи минимизации из класса, с которым автор программы обычно имеет дело, или

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

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

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

Существует ряд стандартных программ наилучшего приближения функций отношением многочленов

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

Рис. 7.6.1

Рис. 7.6.2

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

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

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

Рассмотрим пример задачи, где сам факт необходимости ее решения может быть поставлен под сомнение.

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

Предположим, что точка минимума находится путем продвижения в направлении, противоположном градиенту функции , иначе — численным интегрированием системы

Тогда множество начальных условий, исходя из которых мы будем приходить в точку минимума, находится в небольшой окрестности этой точки. Можно говорить, что при рассмотрении окрестности точки минимума в микроскопическом масштабе эта точка оказывается точкой притяжения решения системы (2); при рассмотрении в более крупном масштабе она уже оказывается точкой отталкивания (рис. 7.6.2).

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

Рис. 7.6.3

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

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

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

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

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

Оптимизация функций (моделей) меньшего числа параметров оказывается более легкой по следующим двум причинам: становится проще структура линий уровня минимизируемой функции; вычисление каждого значения функции обычно требует меньшего объема вычислений.

При построении упрощенных моделей в первую очередь следует учитывать наиболее важные параметры задачи.

Что такое важность факторов или параметров? Можно говорить, что важными параметрами являются те, от которых функция сильно зависит. На языке математики это означает, что производные функции по этим параметрам относительно велики. Второстепенными параметрами являются те, от которых рассматриваемая функция зависит слабо, т. е. производные по которым малы. Формально важность параметров можно определить, оценивая производные рассматриваемой функции. Однако для сложных задач такая оценка и особенно математически обоснованный выбор новых параметров весьма трудоемки. Характеристика параметров по более наглядному критерию —их важности — дает возможность руководителю производственной системы подсказать математику первоочередность выбора параметров.

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

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

В другой аналогичной ситуации руководство предприятием не пошло по такому пути. Оно настойчиво требовало от математической группы разработки универсального алгоритма, который по заданным внешним характеристикам конструируемого прибора выдавал бы оптимальный набор внутренних параметров прибора: расположение и размеры деталей конструкции, вес и т. п. Предлагавшиеся математиками алгоритмы оптимизации не оказывались универсальными и в большинстве случаев не приводили к приемлемому решению. Математики предложили подход к решению задачи, имитирующий реальную ситуацию. Конструктор задает компоновку деталей прибора. Компьютер обсчитывает внешние характеристики прибора и выдает их конструктору. На основании полученной информации конструктор вносит изменения в компоновку. Такой диалоговый режим работы позволил бы отказаться от дорогостоящего реального конструирования прибора и его испытаний. Руководство предприятия отказалось от такого подхода к решению проблемы и потратило много времени на бесплодные поиски «более квалифицированных» математиков, способных предложить «универсальный» бездиалоговый алгоритм решения казавшейся ему столь простой задачи. Большие материальные затраты и потеря темпов в разработке новой техники в конце концов привели к пониманию того, что предлагавшийся математиками путь решения задачи на данном этапе понимания проблемы был единственно возможным.

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

Способы нахождения начального приближения и сами итерационные методы часто имеют аналогию с какими-то реальными процессами и в других явлениях. Работа зрительного аппарата и мозга при отыскании какого-либо предмета, по-видимому, организована по следующей схеме. Сначала производится беглый осмотр всего поля зрения в крупном масштабе, на основании полученной информации выбирается участок для дальнейшего просмотра, затем производится просмотр этого участка в крупном масштабе и т.д. Обратим внимание на сходство с методами из § 3.16 и § 4 данной главы.

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

Существует гипотеза (необщепризнаиная), что сходным образом работает мозг при решении какой-либо проблемы: получаемая информация фиксируется не вполне детерминированным образом в различных его участках; в то же время в каждый момент работы над проблемой эта информация извлекается лишь из локализованного участка мозга.

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

Таким образом, в этом случае алгоритмы работают по принципу «кто быстрее».

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

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

Конечно, не следует думать, что непосредственное копирование различных реальных систем всегда позволит наилучшим образом решить рассматриваемую оптимизационную задачу.

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

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

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

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

При однократном решении простых задач иногда проще всего применить простейший итерационный метод, например Ньютона, с выдачей на экран хода итерационного процесса.

Задаваясь различными начальными приближениями, часто удается довольно быстро угадать начальное приближение, лежащее в области сходимости метода.

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

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

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

Литература

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

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

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

4. Крылов В. И., Бобков В. В., Монастырный П. И. Начала теории вычислительных методов. Линейная алгебра и нелинейные уравнения. — Минск: Наука и техника, 1982.

5. Нестеров Ю.Е. Эффективные методы в нелинейном программировании. — М.: Радио и связь, 1989.

6. Ортега Д., Рейнболдт В. Итерационные методы решения систем уравнений со многими неизвестными. — М.: Мир, 1975.

<< Предыдущий параграф Следующий параграф >>
Оглавление