MATLAB.Exponenta
MATLAB и Simulink на русском
Технологии разработки и отладки
		сложных технических систем
Математика\Optimization Toolbox

Список функций Optimization Toolbox

  В оглавление \ К предыдущему разделу

QUADPROG

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

, такую что

где H, A и Aeq есть матрицы, а f, b, beq, lb, ub и x есть векторы.

Синтаксис

x = quadprog(H,f,A,b)
x = quadprog(H,f,A,b,Aeq,beq)
x = quadprog(H,f,A,b,Aeq,beq,lb,ub)
x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)
x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options)
x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options,p1,p2,...)
[x,fval] = quadprog(...)
[x,fval,exitflag] = quadprog(...)
[x,fval,exitflag,output] = quadprog(...)
[x,fval,exitflag,output,lambda] = quadprog(...)

Описание

  • x = quadprog(H,f,A,b) возвращает вектор х, который минимизирует 1/2*x'*H*x + f'*x при условии A*x <= b.
  • x = quadprog(H,f,A,b,Aeq,beq) решает указанную выше задачу с дополнительным выполнением ограничений типа равенства Aeq*x = beq.
  • x = quadprog(H,f,A,b,Aeq,beq,lb,ub) определяет набор нижних и верхних границ для проектируемой переменной х, так что бы решение находилось в диапазоне lb <= x <= ub.
  • x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0) устанавливает стартовую точку как x0.
  • x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options) ) проводит оптимизацию с определенными в структурной опции параметрами оптимизации.
  • x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options,p1,p2,...) передает параметры p1,p2,... в функцию множителей матрицы Гессе, определенную с помощью, если он имеется, параметра HessMult в данной структуре опций.
  • [x,fval] = quadprog(...) возвращает значение целевой функции от х. fval = 0.5*x'*H*x + f'*x.
  • [x,fval,exitflag] = quadprog(...) возвращает значение exitflag, который описывает выходные условия в quadprog.
  • [x,fval,exitflag,output] = quadprog(...) возвращает структурный выход с информацией об оптимизации.
  • [x,fval,exitflag,output,lambda] = quadprog(...) возвращает структурную lambda с полями, содержащими множители Лагранжа в виде решения от х.

Аргументы:

Входные аргументы.
Таблица 4-1, Входные аргументы, содержит общее описание аргументов, передаваемых в quadprog. Options задает функционально-специфические детали для параметров опций.

Выходные аргументы.
Таблица 4-2. “Выходные аргументы” содержат общее описание возвращаемых quadprog аргументов. В этом разделе приводятся общие специфические детали для величин exitflag, lambda и output:

Eitflag

Описывает выходные условия.

  • > 0 Данная функция сходится к решению по х.
  • 0 Максимальное число оценки функции или итераций было превышено
  • < 0 Функция не сходится к некому решению.

Lamda

Структура, которая содержит множители Лагранжа при решении по х (разделенном по типам aсловий). Поле структуры:

  • Lower Нижние границы lb
  • Upper Верхние границы lb
  • Ineqlin Линейные неравенства
  • Eqlin Линейные равенства

Output

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

  • Iterations Число выполненных итераций
  • Algorithm Используемый алгоритм
  • Cgiterations Число PCG итераций (только для крупно-масштабного алгоритма)
  • Firstorderopt Измерение оптимальности первого порядка (только для крупно-масштабного алгоритма). Для крупно-масштабных задач с краевыми ограничениями оптимальностью первого порядка будет бесконечная норма v.*g, где v определяется как Ограничения Бокса и g –градиент. Для крупно масштабных задач с только линейными ограничениями оптимальностью первого порядка будет 2 нормы нормированной невязки (z = M\r) для расчета Редуцированного Сопряженного Градиента с предварительной обработкой данных. Смотри Алгоритм в разделе “Сопряженные Градиенты с предварительной обработкой данных”, а так же Задачи с линейными ограничениями

Options

Параметры оптимизационных опций. Можно использовать optimset для того, чтобы установить или изменить значения данных полей в структуре параметров опций. Часть параметров используется ко всем алгоритмам, некоторые используются только для крупномасштабного алгоритма, а другие применимы только среднемасштабных алгоритмов.

Параметры для установки алгоритмического предпочтения

LargeScale

В случае установки 'on' используется, если это возможно, крупно-масштабный алгоритм. Для использования средне-масштабного алгоритма устанавливается 'off'.

'’on' более предпочтителен. Если в задаче имеются только верхние и нижние границы, т.е. отсутствуют линейные равенства и неравенства, то по умолчанию принимается крупно-масштабный алгоритм. Или, если в задаче для quadprog заданы только линейные равенства, т.е. верхней и нижней границ и не специфицированы линейные неравенства, а число равенств не больше, чем длина х, то по умолчанию данный алгоритм использует крупно-масштабный алгоритм. В противном, используется средне-масштабный алгоритм.

Medium-Scale and Large-Scale Algorithms. Эти параметры используются как для средне-масштабного, так и крупно-масштабного алгоритмов:

Diagnostics

Проводится печать диагностической информации о минимизируемой функции.

Display

Уровень отображения. 'off' отображение не производится, 'iter' отображение проводится на каждой итерации, 'final' (принимается по умолчанию) отображение только конечной информации.

MaxIter

Максимально число допустимых итераций.

Large-Scale Algorithm Only. Эти параметры используются только для крупно-масштабного алгоритма:

HessMult

Указатель функции для функции множителей матрицы Гессе. В случае крупно-масштабной задачи данная функция вычисляет произведение матриц Гессе H*Y без действительного формирования H. Такая функция имеет форму

W = hmfun(Hinfo,Y,p1,p2,...)

где Hinfo и дополнительные параметры p1,p2,... включают в себя используемые для расчета H*Y матрицы. Hinfo должно быть таким же, что и первый аргумент в quadprog, а p1,p2,... есть те же дополнительные параметры, что передаются в quadprog.

quadprog(Hinfo,...,options,...
         p1,p2,...)

Y есть матрица с тем же самым числом строк, что и размерность данной задачи. W = H*Y, хотя H явно не формируется

quadprog использует Hinfo для расчета предварительных данных.

В качестве примера смотри Квадратичную Оптимизацию с Компактной, но Структурированной Матрицей Гессе.

MaxPCGIter

Максимальное число PCG (предварительно сопряженный градиент) итераций (Смотри ниже раздел Алгоритм).

PrecondBandWidth

Верхняя полоса предварительной обработки для PCG. По умолчанию используется диагональная начальная подготовка (верхняя полоса из 0). Для некоторых задач увеличение полосы снижает число итераций PCG.

TolFun

Конечная допустимая точность значения функции. TolFun используется в качестве выходного критерия для задач с простыми верхними и нижними границами (lb, ub).

TolPCG

Конечное допустимое число итераций PCG. TolPCG используется в качестве выходного критерия для задач, когда имеются только ограничения виде равенств (Aeq, beq).

TolX

Конечное допустимое отклонение по значению х.

TypicalX

Типичные значения х.

Примеры:

Найти значения х, которые минимизируют

при условии, что

Сперва отметим, что данная в матичной записи будет как

где

, ,

Введем эти коэффициенты матриц

Далее запустим программу квадратичного программирования.

Что генерирует решение

x = 
     0.6667
     1.3333
fval =
    -8.2222
exitflag =
     1
output = 
       iterations: 3
        algorithm: 'medium-scale: active-set'
    firstorderopt: []
     cgiterations: []
lambda.ineqlin
ans =
    3.1111
    0.4444
         0
lambda.lower
ans =
     0
     0

Ненулевые элементы вектора в полях lambda указывают на активные ограничения в данной задаче. В данном случае, первый и второй ограничения в виде неравенств (lambda.ineqlin) являются активными ограничениями (т.е. решение находится в пределах таких границ). Для данной задачи, все нижние границы являются неактивными.

Примечания:

В общем quadprog определяет локальное решение, хотя задача является строго выпуклой.

Вероятно, более лучшие численные результаты будут, если с помощью Aeq и beq явно специфицировать данные равенства вместо неявного использования lb и ub.

Если компоненты х не имеют верхних (или нижних границ), то quadprog выберет, соответствующие компоненты ub (или lb) будут установлены как Inf (бесконечность) (или -Inf для lb) в отличие от произвольного, но очень большого положительного (или отрицательного в случае нижних границ) числа.

Крупно-масштабная оптимизация. Если х0 не задано или х0 не является строго допустимым, то quadprog выберет новую строго допустимую (центрированную) стартовую точку

Если поставлена задача с ограничениями типа равенств и quadprog выявит отрицательную кривизну, то оптимизация заканчивается потому, что ограничения не достаточно выделяют область. В данном случае, exitflag возвратит значение -1, отобразится сообщение (даже не смотря на то, параметр отображения установлен как 'off'), а возвращаемый х не будет решением, а направлением отрицательной кривизны по отношению к H.

Для задач с просто нижними и верхними границами (lb, ub), quadprog выходит на основе значения TolFun. Для задач только с ограничениями типа равенств (Aeq, beq), то выход на основе TolPCG. Корректировка TolFun и TolPCG влияет на выходные результаты. TolX используется в обоих типах задач.

Алгоритм:

Крупно-масштабная оптимизация. В случае если приведенная в lsqlin имеет только верхние и нижние границы, т.е. не определены линейные неравенства или равенства, то по умолчанию принимается крупно-масштабный алгоритм. Или, если приведенная в quadprog задача имеет только линейные равенства, т.е. не специфицированы ни верхние и нижние границы, ни линейные неравенства, то по умолчанию принимается крупно-масштабный алгоритм.

Данный алгоритм является реализацией метода доверительных подпространств и основан на методе внутренних отражений Ньютона, описанного в [1]. Каждая итерация включает в себя приближенное решение крупной линейной системы с помощью метода предварительно сопряженных градиентов(PCG). Смотри Метод Доверительной Области для Нелинейной Оптимизации и Метода Предварительно Сопряженных Градиентов в разделе “Крупно-Масштабные Алгоритмы”.

Средне-масштабная оптимизация. lsqlin при установке options. quadprog использует метод активной системы, который также является проекционным методом, аналогично тому, что описано в [2]. Этот метод находит начальные решения путем решения задачи линейного программирования. Данный метод так же обсуждается в разделе Стандартные Алгоритмы.

Диагностика:

Крупно-масштабная оптимизация. Коды крупно-масштабного метода не допускают равенства верхней и нижней границ. Например, если lb(2) == ub(2), то lsqlin дает ошибку

Равные верхние и нижние границы не допустимы в данном крупно-масштабном методе.

Взамен этого используются ограничения типа равенств и средне-масштабный метод.

Если имеются только ограничения типа равенств, то еще можно использовать крупно-масштабный метод. Но если совместно есть, как равенства, так и границы, то необходимо использовать средне-масштабный метод.

Средне-масштабная оптимизация. Если решение является недопустимым, то quadprog дает предупреждение

        Предупреждение. Ограничения являются слишком жесткими.
        Нет допустимого решения

В этом случае quadprog проводит минимизацию для ограничения с наибольшим нарушением

Когда ограничения типа равенств являются противоречащими, то quadprog дает предупреждение

        Предупреждение. Ограничения являются слишком жесткими.
        Нет допустимого решения

Решения без ограничений, что может быть когда матрица Гессе является отрицательной полуопределенностью, могут привести к

        Предупреждение. Решение не ограничено и бесконечно
        Ограничения не являются достаточно жесткими.

В данном случае quadprog возвращает значение х, которое удовлетворяет данным ограничениям.

Ограничения:

К настоящему времени имеются только уровни отображения, при использовании опции параметров Отображения, 'off' и 'final'; итерационный вывод с опцией 'iter' отсутствует.

Решение для задач с бесконечностью или отрицательной бесконечностью часто является задачей без ограничений (в данном случае exitflag возвращается с отрицательным значением, что отмечает, что минимум не найден), а когда конечное решение все же существует, то quadprog может давать только локальный минимум, поскольку такая задача может быть невыпуклой.

Крупно-масштабная оптимизация. Линейный равенства могут быть зависимыми (т.е. Aeq должен иметь полный строчный ранг. Отметим, это означает что, Aeq не может иметь строк больше, чем столбцов. Если это все же имеет место, то взамен вызывается средне-мастабный алгоритм. Для большей информации о постановке задач и требуемой информации смотри Таблицу 1-4. Требования и Область Применения Крупно-Масштабных Задач

Литература:

  1. Coleman, T.F. and Y. Li, "A Reflective Newton Method for Minimizing a Quadratic Function Subject to Bounds on some of the Variables," SIAM Journal on Optimization, Vol. 6, Number 4, pp. 1040-1058, 1996.
  2. Gill, P. E. and W. Murray, and M.H. Wright, Practical Optimization, Academic Press, London, UK, 1981.

  В оглавление \ К предыдущему разделу


Поиск по сайту:

Система Orphus

Яндекс.Метрика