Основные определения

Методы решения нелинейных экстремальных задач

Основные определения

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

Определение 1. Последовательность прибли-

жений называется минимизирующей, если .

Знание какой-либо минимизирующей последовательности позволяет найти с любой точностью значение . Заметим, что минимизирующая последовательность не обязательно сходится к .

Определение 2. Последовательность приближений называется сильно сходящейся (сходящейся по норме), если .

В последнем случае появляется возможность вычисления значения с любой точностью.

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

тельную информацию о ней, удается подобрать нужный критерий.

Определение 3. Последовательность приближений называется релаксационной, если выполняются неравенства

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

, (1)

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

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

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

.

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

одной переменной мы обсудим позже.