Main Content

범위 제약 조건을 사용한 2차 최소화

라이브 스크립트 열기

이 예제에서는 몇 가지 옵션 설정이, 희소 형식이면서 범위 제약 조건이 있는 양의 정부호 2차 문제에 미치는 영향을 보여줍니다.

2차 행렬 H를 주대각선에 요소 +4와 비대각선에 요소 –2가 있는 400×400 크기의 삼중대각 대칭 행렬로 만듭니다.

Bin = -2*ones(399,1);
H = spdiags(Bin,-1,400,400);
H = H + H';
H = H + 4*speye(400);

400번째를 제외한 각 성분에 [0,0.9]의 범위를 설정합니다. 400번째 성분은 비유계가 되도록 허용합니다.

lb = zeros(400,1);
lb(400) = -inf;
ub = 0.9*ones(400,1);
ub(400) = inf;

f(400) = –2를 제외하고 선형 벡터 f를 0으로 설정합니다.

f = zeros(400,1);
f(400) = -2;

Trust-Region-Reflective 풀이

'trust-region-reflective' 알고리즘을 사용하여 2차 계획법을 풉니다.

options = optimoptions('quadprog','Algorithm',"trust-region-reflective");
tic
[x1,fval1,exitflag1,output1] = ... 
        quadprog(H,f,[],[],[],[],lb,ub,[],options);
Local minimum possible.

quadprog stopped because the relative change in function value is less than the function tolerance.

time1 = toc
time1 = 0.1044

해를 검토합니다.

fval1,exitflag1,output1.iterations,output1.cgiterations
fval1 = -0.9930

exitflag1 = 3

ans = 18

ans = 1682

이 알고리즘은 비교적 적은 반복 횟수로 수렴되지만 CG(켤레 기울기) 반복을 1000번 넘게 행합니다. 이러한 CG 반복 횟수를 피하려면, 직접적인 솔버를 사용하도록 옵션을 설정합니다.

options = optimoptions(options,'SubproblemAlgorithm','factorization');
tic
[x2,fval2,exitflag2,output2] = ... 
        quadprog(H,f,[],[],[],[],lb,ub,[],options);
Local minimum possible.

quadprog stopped because the relative change in function value is less than the function tolerance.

time2 = toc
time2 = 0.0185

fval2,exitflag2,output2.iterations,output2.cgiterations
fval2 = -0.9930

exitflag2 = 3

ans = 10

ans = 0

이번에는 알고리즘의 반복 횟수가 더 적으며 CG 반복 횟수가 없습니다. 비교적 시간이 많이 소요되는 직접적인 분해 단계에도 불구하고 솔버가 많은 CG 단계를 피하기 때문에 풀이 시간이 상당히 단축됩니다.

Interior-Point 풀이

디폴트 'interior-point-convex' 알고리즘은 다음 문제를 풀 수 있습니다.

tic
[x3,fval3,exitflag3,output3] = ... 
    quadprog(H,f,[],[],[],[],lb,ub); % No options means use the default algorithm
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.

<stopping criteria details>

time3 = toc
time3 = 0.0402

fval3,exitflag3,output3.iterations
fval3 = -0.9930

exitflag3 = 1

ans = 8

결과 비교

모든 알고리즘은 정밀도를 표시하기 위해 동일한 목적 함수 값 0.9930을 지정합니다.

'interior-point-convex' 알고리즘의 경우 반복 횟수가 가장 적습니다. 한편, 직접적인 하위 문제 솔버가 있는 'trust-region-reflective' 알고리즘이 가장 빠르게 해에 도달합니다.

tt = table([time1;time2;time3],[output1.iterations;output2.iterations;output3.iterations],...
    'VariableNames',["Time" "Iterations"],'RowNames',["TRR" "TRR Direct" "IP"])
tt=3×2 table
                    Time      Iterations
                  ________    __________

    TRR            0.10443        18    
    TRR Direct    0.018544        10    
    IP            0.040204         8