Документация

Воспользуйтесь преимуществами структурированного гессена

quadprog метод, отражающий область доверия, может решить большие проблемы, когда гессен плотный, но структурированный. Для этих проблем, quadprog не вычисляет H * Y непосредственно с Hessian H, как это происходит для проблем, отражающих область доверия, с разреженным H, потому что формирование H было бы интенсивным для памяти. Вместо этого необходимо предоставитьquadprog с функцией, которая, учитывая матрицу Y и информацию о H, вычисляет W = H * Y.

В этом примере матрица Гессена H имеет структуру H = B + A*A' где B является разреженной 512 на 512 симметричной матрицей, и A представляет собой разреженную матрицу 512 на 10, состоящую из ряда плотных столбцов. Во избежание чрезмерного использования памяти, которое может произойти при работе с H непосредственно потому, что H является плотным, пример предоставляет гессенскую функцию умножения, qpbox4mult. Эта функция при передаче матрицы Y, использует разреженные матрицы A и B для вычисления матричного продукта Гессена W = H*Y = (B + A*A')*Y.

В первой части этого примера матрицы A и B необходимо предоставить гессенскую функцию умножения qpbox4mult. Можно передать одну матрицу в качестве первого аргумента quadprog, которая передается гессенской функции умножения. Для определения значения второй матрицы можно использовать вложенную функцию.

Во второй части примера показано, как затянуть TolPCG допуск для компенсации приблизительного предварительного условия вместо точного H матрица.

Шаг 1: Решите, какую часть H передать квадрогу в качестве первого аргумента.

Также A или B может быть передан в качестве первого аргумента quadprog. Пример выбирает прохождение B в качестве первого аргумента, потому что это приводит к лучшему предварительному кондиционированию (см. Предварительное кондиционирование).

quadprog(B,f,[],[],[],[],l,u,xstart,options)

Шаг 2: Записать функцию для вычисления гессеновых матричных продуктов для H.

Теперь определите функцию runqpbox4 это

Первый аргумент вложенной функции qpbox4mult должен совпадать с первым аргументом, переданным quadprog, которая в данном случае является матрицей B.

Второй аргумент для qpbox4mult - матрица Y из W = H*Y). Поскольку quadprog ожидает Y используется для формирования гессенского матричного продукта, Y всегда является матрицей с n строки, где n - количество измерений в задаче. Количество столбцов в Y может варьироваться. Функция qpbox4mult вложен так, что значение матрицы A происходит от внешней функции. Оптимизация Toolbox™ программное обеспечение включает в себя runqpbox4.m файл.

function [fval, exitflag, output, x] = runqpbox4
%RUNQPBOX4 demonstrates 'HessianMultiplyFcn' option for QUADPROG with bounds.

problem = load('qpbox4'); % Get xstart, u, l, B, A, f
xstart = problem.xstart; u = problem.u; l = problem.l;
B = problem.B; A = problem.A; f = problem.f;
mtxmpy = @qpbox4mult; % function handle to qpbox4mult nested function

% Choose algorithm and the HessianMultiplyFcn option
options = optimoptions(@quadprog,'Algorithm','trust-region-reflective','HessianMultiplyFcn',mtxmpy);

% Pass B to qpbox4mult via the H argument. Also, B will be used in
% computing a preconditioner for PCG.
[x, fval, exitflag, output] = quadprog(B,f,[],[],[],[],l,u,xstart,options);

    function W = qpbox4mult(B,Y)
        %QPBOX4MULT Hessian matrix product with dense structured Hessian.
        %   W = qpbox4mult(B,Y) computes W = (B + A*A')*Y where
        %   INPUT:
        %       B - sparse square matrix (512 by 512)
        %       Y - vector (or matrix) to be multiplied by B + A'*A.
        %   VARIABLES from outer function runqpbox4:
        %       A - sparse matrix with 512 rows and 10 columns.
        %
        %   OUTPUT:
        %       W - The product (B + A*A')*Y.
        %

        % Order multiplies to avoid forming A*A',
        %   which is large and dense
        W = B*Y + A*(A'*Y);
    end

end

Шаг 3: Вызовите подпрограмму квадратичной минимизации с начальной точкой.

Вызов процедуры квадратичной минимизации, содержащейся в runqpbox4, введите

[fval,exitflag,output] = runqpbox4;

для выполнения предыдущего кода. Затем просмотрите значения для fval, exitflag, output.iterations, и output.cgiterations.

fval,exitflag,output.iterations, output.cgiterations

fval =

  -1.0538e+03


exitflag =

     3


ans =

    18


ans =

    30

После 18 итераций с общим количеством 30 итераций PCG значение функции уменьшается до

fval
fval =
 -1.0538e+003

и оптимальность первого порядка

output.firstorderopt
ans =
    0.0043

Предварительное создание условий

Иногда quadprog не может использовать H для вычисления предварительного условия, поскольку H существует только неявно. Вместо этого quadprog использование B, аргумент передан вместо H, чтобы вычислить предварительное условие. B является хорошим выбором, потому что он того же размера, что и H и приближает H до некоторой степени. Если B не были такого же размера, как H, quadprog вычисляет устройство предварительного кондиционирования на основе некоторых матриц диагонального масштабирования, определенных из алгоритма. Обычно это не так хорошо.

Потому что предварительное условие более приблизительное, чем когда H доступен явным образом, настройка TolPCG может потребоваться несколько меньшее значение параметра. Этот пример аналогичен предыдущему, но уменьшает TolPCG от 0,1 до 0,01.

function [fval, exitflag, output, x] = runqpbox4prec
%RUNQPBOX4PREC demonstrates 'HessianMultiplyFcn' option for QUADPROG with bounds.

problem = load('qpbox4'); % Get xstart, u, l, B, A, f
xstart = problem.xstart; u = problem.u; l = problem.l;
B = problem.B; A = problem.A; f = problem.f;
mtxmpy = @qpbox4mult; % function handle to qpbox4mult nested function

% Choose algorithm, the HessianMultiplyFcn option, and override the TolPCG option
options = optimoptions(@quadprog,'Algorithm','trust-region-reflective',...
    'HessianMultiplyFcn',mtxmpy,'TolPCG',0.01);

% Pass B to qpbox4mult via the H argument. Also, B will be used in
% computing a preconditioner for PCG.
% A is passed as an additional argument after 'options'
[x, fval, exitflag, output] = quadprog(B,f,[],[],[],[],l,u,xstart,options);

    function W = qpbox4mult(B,Y)
        %QPBOX4MULT Hessian matrix product with dense structured Hessian.
        %   W = qpbox4mult(B,Y) computes W = (B + A*A')*Y where
        %   INPUT:
        %       B - sparse square matrix (512 by 512)
        %       Y - vector (or matrix) to be multiplied by B + A'*A.
        %   VARIABLES from outer function runqpbox4prec:
        %       A - sparse matrix with 512 rows and 10 columns.
        %
        %   OUTPUT:
        %       W - The product (B + A*A')*Y.
        %

        % Order multiplies to avoid forming A*A',
        %   which is large and dense
        W = B*Y + A*(A'*Y);
    end

end

Теперь введите

[fval,exitflag,output] = runqpbox4prec; 

для выполнения предыдущего кода. После 18 итераций и 50 итераций PCG значение функции имеет то же значение до пяти значащих цифр

fval
fval = 
-1.0538e+003

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

output.firstorderopt
ans =
    0.0043