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.