ММвЭ- лекции

3.3 Сепарабельное программирование

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

Определение.

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

Кусочно-линейная аппроксимация для сепарабельной непрерывной функции f(x) строится следующим образом. Интервал значений каждой переменной x_i разбивается при помощи сетки с K_iузлами. Таким образом, на интервале x_i^(L) Ј x_i Ј x_i^(R) рассматривается следующая последовательность точек:

x_i⁽^L⁾ = x_i⁽¹⁾ < x_i⁽¹⁾ <...< x_i⁽^K_i⁾ = x_i⁽^R⁾

Введём обозначение f_i^(k) = f_i(x_i^(k)). Тогда аппроксимирующая функция примет вид:

причём при всех i=1,...,N выполняется:

Последнее условие выражает тот факт, что не более двух переменных l⁽ⁱ⁾ должны быть положительными.

Таким образом, нелинейная функция f(x) заменяется кусочно-линейной . Для построения хорошего приближения число узлов сетки должно быть большим, то есть линейность достигается за счёт роста размерности задачи, то есть решение задачи НЛП сводится к решению задачи ЛП большой размерности с переменными l_i^(k). Полученная задача ЛП может быть решена с помощью симплекс-метода, дополненного правилом ограниченного ввода в базис, учитывающего условие (*).

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

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

Содержание