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 и, если заданы, должны быть векторами того же размера, что и вектор x0. Границы должны быть согласованы с ограничениями-равенствами и ограничениями-неравенствами g и h.

Седьмой аргумент 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.