Глава II. Численные методы нелинейного программирования

Общие положения

Постановка проблемы

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

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

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

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

Общие принципы.

Подавляющее большинство численных методов оптимизации относится к итерационным. Суть итерационных методов заключается в том, что задаётся некоторая начальная точка X₀ в Rⁿ и строится последовательность {X_k} точек в Rⁿ, причём очередная X_k+1 строится по предыдущим, как правило, по X_k.

Для определённости рассмотрим задачу безусловного локального минимума:

f(X^*)= . (1.2.1)

Численное решение задачи (1.2.1) заключается в построении последовательности {X_k}, обладающей свойством

f(X_k+1)<f(X_k), k=0, 1, …, (1.2.2)

В общем виде итерационная последовательность по формулам

X_k+1=X_k+h_kD_k, (1.2.3)

где D_k - направление перехода из точки X_k в точку X_k+1, обеспечивающее выполнение условия (1.2.2). Оно называется направлением спуска, h_k - величина шага.

Начальная точка X₀ задаётся, исходя из некоторых соображений применительно к конкретному методу.

Направление спуска D_k должно удовлетворять условию

(Ñf(X_k), D_k)<0, k=0, 1, …, (1.2.4)

которое обеспечивает убывание функции. Например, в качестве D_k можно взять антиградиент -Ñf(X_k).

Величина шага h_k>0 выбирается либо из условия (1.2.2), либо из условия

f(X_k+h_kD_k)® . (1.2.5)

обеспечивающего наискорейший спуск в направлении D_k.

Последовательность {X_k} называется минимизирующей, если = . Сходимость последовательности {X_k} при выборе приемлемого направления D_k и величины шага h_k из условия (1.2.2) или (1.2.5) зависит от характера функции f(X) и от выбора начальной точки X₀.

В зависимости от наивысшего порядка (частных) производных функции f(X), используемых для формирования D_k и h_k, численные методы задачи безусловной оптимизации делятся на три группы:

1. Методы нулевого порядка, использующие только информацию о значении функции f(X).

2. Методы первого порядка, использующие информацию о первых производных функции f(X).

3. Методы второго порядка, использующие информацию о вторых производных функции f(X).

Наше рассмотрение мы и начнём с методов нулевого, первого и второго порядков безусловной оптимизации.