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

Недокументированный вывод

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