Пусть функция
также непрерывна, дифференцируема и выпукла во множестве
.
Суть метода линейной аппроксимации.
где
.
В изложенном виде метод может привести к выходу точки
за пределы допустимой области (см. прим. 1).
Пример 1
Рассмотрим следующую двумерную
задачу условной оптимизации с тремя ограничениями типа неравенств (первое ограничение – нелинейное, второе и третье ограничения — линейные):
где
Пример иллюстрирует рис. 1, на котором линии уровня
целевой функции 
получены с помощью следующей MATLAB-программы:
x = -2 : 0.1 : 6;
y = x;
[X, Y] = meshgrid(x);
Z = X.^2 + (Y - 6.).^2 - 12;
V = [-10, -5, 0, 5, 10, 20, 40, 80];
[C, h] = contour(X, Y, Z, V);
clabel(C, h);
Рис. 1. Точка Xr+1 лежит вне области допустимых значений D.
Примечание 1
Прямая
представляет собой след от пересечения плоскости, которая является касательной к поверхности
в точке
, с плоскостью 0x
1x
2. Эта прямая не обязательно является касательной к линии
— прямая
может пересекать кривую
, быть касательной к ней или не иметь с ней общих точек. Аналогично, линия уровня
функции
представляет собой след от пересечения плоскости, которая является касательной к поверхности
в точке
, с плоскостью
.
Чтобы избежать выхода текущей точки за границы
области допустимых значений, следующее приближение
к точке минимума
функции
из множества
находится по формуле
 | (6) |
Величина шага
в формуле (6) в разных вариантах
метода линейной аппроксимации может определяться разными способами. Приведем два из множества возможных способов.
2-й способ выбора величины шага 
. Полагаем
и по формуле (6) находим вектор
. Вычисляем значение
целевой функции в полученной точке. Если условие
 | (8) |
не выполнено, то уменьшаем величину шага
(например, в два раза) и повторно проверяем выполнение условия (8). Дробление шага
и вычисление
производим до выполнения условия (8).
Схема метода линейной аппроксимации.
Рассмотрим вариант метода, в котором используется 1-й способ выбора величины шага
.
- Задаем начальную точку
и полагаем счетчик числа итераций 
.
- Вычисляем градиенты функций
в точке 
.
- Решаем задачу линейного программирования (5) – находим точку
.
- Решаем одномерную задачу минимизации (7) – находим величину шага
и вектор 
.
- Проверяем условие окончания поиска (см. ниже). Если условие окончания поиска выполнено, то полагаем
и завершаем итерации. Иначе – полагаем 
и переходим к п.2
или условие
где
— константа, определяющая требуемую точность решения по градиенту функции
.
- Если функция
имеет высокую степень нелинейности, то на основе решения вспомогательной задачи минимизации (5) направление поиска может быть выбрано слишком неточно (см. рис. 2), что приводит к медленной сходимости метода.
- Метод требует, чтобы точка
принадлежала множеству допустимых значений 
. Если это требование не выполнено, то прежде приходится использовать какой-либо метод поиска точки, принадлежащей множеству допустимых значений.
Рис. 2. Направление поиска (Xr+1-Xr), которое обеспечивает метод на основе линейной аппроксимации, далеко от оптимального направления (X*-Xr).
