25.3 Нелинейное программирование

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

: [x, obj, info, iter, nf, lambda] = sqp (x0, phi) ¶

: […] = sqp (x0, phi, g) ¶

: […] = sqp (x0, phi, g, h) ¶

: […] = sqp (x0, phi, g, h, lb, ub) ¶

: […] = sqp (x0, phi, g, h, lb, ub, maxiter) ¶

: […] = sqp (x0, phi, g, h, lb, ub, maxiter, tolerance) ¶

Минимизация целевой функции с использованием метода последовательного квадратичного программирования (SQP).

Решить нелинейную задачу

min phi (x)
 x

при ограничениях

g(x)  = 0
h(x) >= 0
lb <= x <= ub

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

Первый аргумент — начальное приближение для вектора x0.

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

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

При указании, функция градиента phi{2} должна принимать один векторный аргумент и возвращать вектор. При указании, функция гессиана phi{3} должна принимать один векторный аргумент и возвращать матрицу.

Третий и четвертый аргументы g и h — обработчики функций, указывающие на функции, вычисляющие ограничения равенства и неравенства соответственно. Если в задаче нет ограничений равенства (или неравенства), используйте пустую матрицу ([]) для g (или h). При указании, эти функции ограничений равенства и неравенства должны принимать один векторный аргумент и возвращать вектор.

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

[ d f(x)   d f(x)        d f(x) ]
transpose ( [ ------   -----   ...   ------ ] )
            [  dx_1     dx_2          dx_N  ]

Пятый и шестой аргументы, lb и ub, содержат нижние и верхние границы для x. Они должны быть согласованы с ограничениями равенства и неравенства g и h. Если аргументы являются векторами, то x(i) ограничено lb(i) и ub(i). Граница также может быть скаляром, в этом случае все элементы x будут иметь одинаковую границу. Если задан только один предел (lb, ub), другой будет по умолчанию равен (-realmax, +realmax).

Седьмой аргумент maxiter определяет максимальное количество итераций. Значение по умолчанию равно 100.

Восьмой аргумент tolerance определяет толерантность для критериев остановки. Значение по умолчанию равно sqrt (eps).

Возвращаемое значение в info может быть одним из следующих:

101

Алгоритм завершился нормально. Все ограничения соответствуют заданной толерантности.

102

Обновление BFGS завершилось ошибкой.

103

Было достигнуто максимальное число итераций.

104

Шаг стал слишком маленьким, т.е., дельта x, меньше, чем tol * norm (x).

Пример вызова sqp:

function r = g (x)
  r = [ sumsq(x)-10;
        x(2)*x(3)-5*x(4)*x(5);
        x(1)^3+x(2)^3+1 ];
endfunction

function obj = phi (x)
  obj = exp (prod (x)) - 0.5*(x(1)^3+x(2)^3+1)^2;
endfunction

x0 = [-1.8; 1.7; 1.9; -0.8; -0.8];

[x, obj, info, iter, nf, lambda] = sqp (x0, @phi, @g, [])

x =

  -1.71714
   1.59571
   1.82725
  -0.76364
  -0.76364

obj = 0.053950
info = 101
iter = 8
nf = 10
lambda =

  -0.0401627
   0.0379578
  -0.0052227

См. также: qp.