Квадратичная минимизация с плотным, структурированным гессианом

Используйте в своих интересах структурированный Гессиан

quadprog отражающий метод доверительной области может решить большие задачи, где Гессиан является плотным, но структурирован. Для этих проблем, quadprog не вычисляет H*Y с Гессианом 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 передать quadprog в качестве первого аргумента.

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

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

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

Теперь задайте функциональный runqpbox4 это

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

    W = qpbox4mult(Hinfo,Y,...)

    Первые два аргумента Hinfo и Y требуются.

  • Загружает проблемные параметры от qpbox4.mat.

  • Использование optimoptions установить HessianMultiplyFcn опция к указателю на функцию, который указывает на qpbox4mult.

  • Вызовы quadprog с B в качестве первого аргумента.

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

Второй аргумент к qpbox4mult матричный Y (  W = H*Y). Поскольку quadprog ожидает Y использоваться, чтобы сформировать матричное произведение Гессиана, Y всегда матрица с n строки, где n количество размерностей в проблеме. Количество столбцов в Y может варьироваться. Функциональный qpbox4mult вкладывается так, чтобы значение матричного A прибывает из внешней функции. Программное обеспечение Optimization 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;

запускать предыдущий код. Затем отобразите значения для fvalexitflag , 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

Примечание

Уменьшение TolPCG слишком много может существенно увеличить число итераций PCG.

Похожие темы

Для просмотра документации необходимо авторизоваться на сайте