25.2 Квадратичное программирование ¶

Octave также может решать задачи квадратичного программирования, это

min 0.5 x'*H*x + x'*q

при условии

A*x = b
     lb <= x <= ub
     A_lb <= A_in*x <= A_ub

: [x, obj, info, lambda] = qp (x0, H) ¶

: [x, obj, info, lambda] = qp (x0, H, q) ¶

: [x, obj, info, lambda] = qp (x0, H, q, A, b) ¶

: [x, obj, info, lambda] = qp (x0, H, q, A, b, lb, ub) ¶

: [x, obj, info, lambda] = qp (x0, H, q, A, b, lb, ub, A_lb, A_in, A_ub) ¶

: [x, obj, info, lambda] = qp (…, options) ¶

Решить задачу квадратичного программирования (QP).

Решить задачу квадратичного программирования, определённую

min 0.5 x'*H*x + x'*q
 x

при условии

A*x = b
lb <= x <= ub
A_lb <= A_in*x <= A_ub

с помощью метода активного множества нулевого пространства.

Любое ограничение (A, b, lb, ub, A_in, A_lb, A_ub) может быть установлено в пустую матрицу ([]) если она отсутствует. Ограничения A и A_in — матрицы, при этом каждая строка представляет собой одно ограничение. Другие ограничения — скаляры или векторы в зависимости от количества ограничений. Алгоритм быстрее, если начальное предположение выполнимо.

options — структура, определяющая дополнительные параметры, которые контролируют алгоритм. В настоящее время qp распознаёт эти параметры: "MaxIter", "TolX".

"MaxIter" предписывает максимальное количество итераций алгоритма до остановки оптимизации. Значение по умолчанию равно 200. Значение должно быть положительным целым числом.

"TolX" определяет порог завершения для неизвестных переменных x. Значение по умолчанию равно sqrt (eps) или приблизительно 1e-8.

При возврате x — местоположение минимума, а fval содержит значение целевой функции в x.

info

Структура, содержащая информацию о работе алгоритма во время выполнения. Определены следующие поля:

solveiter

Количество итераций, необходимых для нахождения решения.

info

Целое число, указывающее статус решения.

0

Задача выполнима и выпуклая. Найдено глобальное решение.

1

Задача не выпуклая. Найдено локальное решение.

2

Задача не выпуклая и неограниченная.

3

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

6

Задача невыполнима.

См. также: sqp.

: x = pqpnonneg (c, d) ¶

: x = pqpnonneg (c, d, x0) ¶

: x = pqpnonneg (c, d, x0, options) ¶

: [x, minval] = pqpnonneg (…) ¶

: [x, minval, exitflag] = pqpnonneg (…) ¶

: [x, minval, exitflag, output] = pqpnonneg (…) ¶

: [x, minval, exitflag, output, lambda] = pqpnonneg (…) ¶

Минимизировать (1/2 * x' * c * x + d' * x) при условии x >= 0.

c и d должны быть вещественными матрицами, а c должна быть симметрической и положительно определённой.

x0 — необязательное начальное приближение для решения x.

options — структура параметров для изменения поведения алгоритма (см. optimset). pqpnonneg распознаёт один параметр: "MaxIter".

Результаты:

x

Матрица решения

minval

Минимальное достигнутое значение модели, 1/2*xmin'*c*xmin + d'*xmin

exitflag

Индикатор сходимости. 0 указывает на превышение количества итераций, а значит, сходимость не достигнута; >0 указывает на сходимость алгоритма. (Алгоритм стабилен и сойдётся при достаточном количестве итераций.)

output

Структура с двумя полями:

• "algorithm": Использованный алгоритм ("nnls")
• "iterations": Количество итераций.

lambda

Умножители Лагранжа. Если они не равны нулю, соответствующие значения x должны быть равны нулю, что указывает на то, что решение прижато к координатной плоскости. Величина показывает, насколько улучшится остаток, если ограничения x >= 0 будут ослаблены в этом направлении.

См. также: lsqnonneg, qp, optimset.