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, tol)

Минимизирует целевую функцию с помощью метода последовательного квадратичного программирования (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.

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

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

101

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

102

Обновление BFGS не удалось.

103

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

104

Шаг стал слишком маленьким, т.е., delta 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.