Неотрицательная линейная задача для метода наименьших квадратов, основанная на проблеме

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

minxCx-d2.

В этом случае ограничьте решение быть неотрицательными, x0.

Чтобы начаться, загрузите массивы C и d в вашу рабочую область.

load particle

Просмотрите размер каждого массива.

sizec = size(C)
sizec = 1×2

        2000         400

sized = size(d)
sized = 1×2

        2000           1

Создайте переменную x оптимизации из соответствующего размера для умножения C. Наложите нижнюю границу 0 на элементах x.

x = optimvar('x',sizec(2),'LowerBound',0);

Создайте выражение целевой функции.

residual = C*x - d;
obj = sum(residual.^2);

Создайте задачу оптимизации под названием nonneglsq и включайте целевую функцию в проблему.

nonneglsq = optimproblem('Objective',obj);

Найдите решатель по умолчанию для проблемы.

opts = optimoptions(nonneglsq)
opts = 
  lsqlin options:

   Options used by current Algorithm ('interior-point'):
   (Other available algorithms: 'active-set', 'trust-region-reflective')

   Set properties:
     No options set.

   Default properties:
              Algorithm: 'interior-point'
    ConstraintTolerance: 1.0000e-08
                Display: 'final'
           LinearSolver: 'auto'
          MaxIterations: 200
    OptimalityTolerance: 1.0000e-08
          StepTolerance: 1.0000e-12

   Show options not used by current Algorithm ('interior-point')

Решите задачу с помощью решателя по умолчанию.

[sol,fval,exitflag,output] = solve(nonneglsq);
Solving problem using lsqlin.

Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.

Чтобы видеть детали процесса оптимизации, исследуйте структуру output.

disp(output)
            message: '...'
          algorithm: 'interior-point'
      firstorderopt: 9.9673e-07
    constrviolation: 0
         iterations: 9
       linearsolver: 'sparse'
       cgiterations: []
             solver: 'lsqlin'

Структура output показывает что lsqlin решатель использует разреженный внутренний линейный решатель для алгоритма внутренней точки и берет 9 итераций, чтобы прибыть в меру оптимальности первого порядка приблизительно 1e-6.

Измените алгоритм

Доверительная область отражающий алгоритм решает связано ограниченные проблемы. Смотрите, как хорошо это выполняет на этой проблеме.

opts.Algorithm = 'trust-region-reflective';
[sol2,fval2,exitflag2,output2] = solve(nonneglsq,'Options',opts);
Solving problem using lsqlin.

Local minimum possible.

lsqlin stopped because the relative change in function value is less than the function tolerance.
disp(output2)
         iterations: 14
          algorithm: 'trust-region-reflective'
      firstorderopt: 5.2187e-08
       cgiterations: 54
    constrviolation: []
       linearsolver: []
            message: 'Local minimum possible....'
             solver: 'lsqlin'

На этот раз решатель берет больше итераций и находит решение с более низкой (лучшей) мерой оптимальности первого порядка.

Чтобы получить еще лучшую меру оптимальности первого порядка, попытайтесь установить SubproblemAlgorithm опция к 'factorization'.

opts.SubproblemAlgorithm = 'factorization';
[sol3,fval3,exitflag3,output3] = solve(nonneglsq,'Options',opts);
Solving problem using lsqlin.

Optimal solution found.
disp(output3)
         iterations: 11
          algorithm: 'trust-region-reflective'
      firstorderopt: 1.3973e-14
       cgiterations: 0
    constrviolation: []
       linearsolver: []
            message: 'Optimal solution found.'
             solver: 'lsqlin'

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

Измените решатель

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

[sol4,fval4,exitflag4,output4] = solve(nonneglsq,'Solver','lsqnonneg');
Solving problem using lsqnonneg.
disp(output4)
    iterations: 184
     algorithm: 'active-set'
       message: 'Optimization terminated.'
        solver: 'lsqnonneg'

lsqnonneg не сообщает мера оптимальности первого порядка. Вместо этого исследуйте нормы невязки, которые возвращены в fval выходные параметры . Чтобы видеть цифры более низкого значения, вычтите 22.5794 из каждой нормы невязки.

t = table(fval - 22.5794, fval2 - 22.5794, fval3 - 22.5794, fval4 - 22.5794,...
    'VariableNames',{'default','trust-region-reflective','factorization','lsqnonneg'})
t=1×4 table
     default      trust-region-reflective    factorization    lsqnonneg 
    __________    _______________________    _____________    __________

    5.0804e-05          4.9179e-05            4.9179e-05      4.9179e-05

Решатель по умолчанию имеет немного более высокую (худшую) норму невязки, чем другие три, нормы невязки которых неразличимы на этом уровне точности отображения. Чтобы видеть, который является самым низким, вычтите lsqnonneg следуйте из двух результатов.

disp([fval2 - fval4,fval3 - fval4])
   1.0e-12 *

    0.7070    0.6928

lsqnonneg норма невязки является самой маленькой почти незначительной суммой. Однако lsqnonneg берет большинство итераций, чтобы сходиться.

Похожие темы