Main Content

이 번역 페이지는 최신 내용을 담고 있지 않습니다. 최신 내용을 영문으로 보려면 여기를 클릭하십시오.

혼합 정수 2차 계획법 포트폴리오 최적화: 솔버 기반

이 예제에서는 intlinprog 혼합 정수 선형 계획법(MILP) 솔버를 사용하여 혼합 정수 2차 계획법(MIQP) 포트폴리오 최적화 문제를 푸는 방법을 보여줍니다. 이 문제의 요점은 국소적으로 MIQP 문제의 근삿값을 구하는 일련의 MILP 문제를 반복적으로 푸는 것입니다. 문제 기반 접근법에 대해서는 혼합 정수 2차 계획법 포트폴리오 최적화: 문제 기반 항목을 참조하십시오.

문제 개요

Markowitz가 증명한 바와 같이("Portfolio Selection," J. Finance Volume 7, Issue 1, pp. 77-91, March 1952), 많은 포트폴리오 최적화 문제를 2차 계획법 문제로 표현할 수 있습니다. N개의 자산으로 구성된 집합이 있고 x(i)가 자산 i에 대한 투자를 나타내는 포트폴리오를 선택하려 한다고 가정해 보겠습니다. 각 자산의 평균 수익으로 구성된 벡터 r과 수익의 공분산 행렬 Q를 아는 경우, 지정된 위험 회피 수준 λ에 대해 위험 조정 후 예상 수익을 극대화합니다.

maxx(rTx-λxTQx).

quadprog 솔버는 이 2차 계획법 문제를 해결합니다. 하지만 일반 2차 계획법 문제 외에도, 다음과 같이 다양한 방법으로 포트폴리오를 제한하려 할 수 있습니다.

  • 포트폴리오에 포함된 자산이 M개를 넘지 않으며, M <= N임.

  • 포트폴리오에 포함된 자산이 최소 m개이며, 0 < m <= M임.

  • 반연속 제약 조건 포함(즉, x(i)=0이거나 일부 고정된 비율 fmin>0fmaxfmin에 대해 fminx(i)fmax임).

quadprog에는 이러한 제약 조건을 포함시킬 수 없습니다. 이 경우의 어려운 점은 제약 조건의 특성이 이산적이라는 것입니다. 뿐만 아니라, 혼합 정수 선형 계획법 솔버 intlinprog는 이산 제약 조건은 처리하지만 2차 목적 함수를 처리하지는 않습니다.

이 예제에서는 제약 조건을 충족하고 2차 목적 함수를 점점 근사화하는 일련의 MILP 문제를 생성합니다. 이 기법은 이 예제에서는 효과가 있지만, 다른 문제 또는 제약 조건 유형에는 적용되지 않을 수 있습니다.

제약 조건을 모델링하는 것으로 시작합니다.

이산 제약 조건 모델링하기

x는 자산 할당 비율로 구성된 벡터로, 각 i에 대해 0x(i)1입니다. 포트폴리오에서 자산의 개수를 모델링하려면 x(i)=0일 때 v(i)=0이고 x(i)>0일 때 v(i)=1이 되는 표시 변수 v가 필요합니다. 이 제한을 충족하는 변수를 가져오려면 v 벡터를 이진 변수로 설정하고 다음 선형 제약 조건을 적용하십시오.

v(i)fminx(i)v(i)fmax.

이 부등식은 모두 x(i)v(i)가 동시에 정확히 0이 되도록 하고, 또한 x(i)>0일 때마다 fminx(i)fmax가 되도록 합니다.

또한 포트폴리오에 있는 자산의 개수에 제약 조건를 적용하려면 다음 선형 제약 조건을 적용하십시오.

miv(i)M.

목적 함수 및 연속 선형 근사

처음 정식화할 때는 목적 함수 값을 최대화하려고 시도할 수 있습니다. 그러나 모든 Optimization Toolbox™ 솔버는 목적 함수를 최소화합니다. 따라서 다음과 같이 음을 취한 목적 함수의 최소화 문제로 정식화하십시오.

minxλxTQx-rTx.

이 목적 함수는 비선형적입니다. intlinprog MILP 솔버를 사용하려면 선형 목적 함수가 필요합니다. 이 문제를 선형 목적 함수와 비선형 제약 조건이 있는 문제로 다시 정식화하기 위한 표준 기법이 있습니다. 2차 항을 나타내기 위해 여유 변수 z를 사용합니다.

minx,zλz-rTx such that xTQx-z0,z0.

MILP 근삿값을 반복적으로 구할 때 새로운 선형 제약 조건을 포함시킵니다. 이러한 조건 각각은 현재 점 근처에 국소적으로 비선형 제약 조건을 근사화합니다. 특히 x=x0+δ의 경우(여기서 x0은 상수 벡터이고 δ는 변수 벡터임), 제약 조건에 대한 1차 테일러 근사는 다음과 같습니다.

xTQx-z=x0TQx0+2x0TQδ-z+O(|δ|2).

δx-x0으로 바꾸면 다음과 같은 식이 됩니다.

xTQx-z=-x0TQx0+2x0TQx-z+O(|x-x0|2).

각각의 중간 해 xk에 대해 xz에서 새로운 선형 제약 조건을 다음과 같이 위 표현식의 선형 부분으로 추가합니다.

-xkTQxk+2xkTQx-z0.

이는 Axb 형식을 가지며, 여기서 A=2xkTQ이고 z 항의 승수는 -1이며 b=xkTQxk입니다.

문제에 새로운 선형 제약 조건을 추가하는 이 방법을 평면 절단 방법이라고 합니다. 자세한 내용은 J. E. Kelley, Jr. "The Cutting-Plane Method for Solving Convex Programs." J. Soc. Indust. Appl. Math. Vol. 8, No. 4, pp. 703-712, December, 1960을 참조하십시오.

MATLAB® 문제 정식화

intlinprog 솔버에 사용할 문제에는 다음이 표현되어야 합니다.

  • 변수가 나타내는 대상 결정

  • 이러한 변수로 하한과 상한 표현

  • 선형 등식과 선형 부등식의 행렬 지정

처음 N개의 변수는 x 벡터를, 다음 N개의 변수는 이진 v 벡터를, 마지막 변수는 z 여유 변수를 나타내도록 합니다. 이 문제에는 2N+1개의 변수가 있습니다.

문제에 대한 데이터를 불러옵니다. 이 데이터에는 벡터 r에 225개의 예상 수익과 225×225 행렬 Q에 수익의 공분산이 포함되어 있습니다. 이 데이터는 포트폴리오 최적화를 위한 2차 계획법 예제에 있는 데이터와 동일합니다.

load port5
r = mean_return;
Q = Correlation .* (stdDev_return * stdDev_return');

자산 개수를 N으로 설정합니다.

N = length(r);

변수에 인덱스를 설정합니다.

xvars = 1:N;
vvars = N+1:2*N;
zvar = 2*N+1;

문제에서 모든 2N+1개 변수의 하한은 0입니다. 처음 2N개 변수의 상한은 1이고, 마지막 변수에는 상한이 없습니다.

lb = zeros(2*N+1,1);
ub = ones(2*N+1,1);
ub(zvar) = Inf;

해의 자산 개수가 100에서 150 사이의 값이 되도록 설정합니다. 이 제약 조건을 다음과 같은 형식으로 문제에 포함시킵니다.

miv(i)M,

이때 다음과 같이 Axb 형식의 두 선형 제약 조건을 작성합니다.

iv(i)M

i-v(i)-m.

M = 150;
m = 100;
A = zeros(1,2*N+1); % Allocate A matrix
A(vvars) = 1; % A*x represents the sum of the v(i)
A = [A;-A];
b = zeros(2,1); % Allocate b vector
b(1) = M;
b(2) = -m;

반연속 제약 조건을 포함시킵니다. 자산에서 0이 아닌 최소 비율은 각 자산 유형에 대해 0.001이고, 최대 비율은 0.05라고 가정하겠습니다.

fmin = 0.001;
fmax = 0.05;

부등식 x(i)fmax(i)*v(i)fmin(i)*v(i)x(i)를 선형 부등식으로 포함시킵니다.

Atemp = eye(N);
Amax = horzcat(Atemp,-Atemp*fmax,zeros(N,1));
A = [A;Amax];
b = [b;zeros(N,1)];
Amin = horzcat(-Atemp,Atemp*fmin,zeros(N,1));
A = [A;Amin];
b = [b;zeros(N,1)];

포트폴리오가 100% 투자되는 제약 조건을 포함시킵니다. 즉, xi=1입니다.

Aeq = zeros(1,2*N+1); % Allocate Aeq matrix
Aeq(xvars) = 1;
beq = 1;

위험 회피 계수 λ100으로 설정합니다.

lambda = 100;

목적 함수 λz-rTx를 벡터로 정의합니다. v 변수의 승수에 0을 포함시킵니다.

f = [-r;zeros(N,1);lambda];

문제 풀기

문제를 반복적으로 풀려면 먼저 어떤 선형화도 아직 반영하지 않는 현재 제약 조건으로 문제를 풀어보십시오. vvars 벡터에 정수 제약 조건이 있습니다.

options = optimoptions(@intlinprog,'Display','off'); % Suppress iterative display
[xLinInt,fval,exitFlagInt,output] = intlinprog(f,vvars,A,b,Aeq,beq,lb,ub,options);

반복의 중지 조건을 준비합니다. 여유 변수 z가 실제 2차 값의 0.01% 내에 있을 때 중지합니다. 제약 조건이 누적됨에 따라 문제가 엄밀히 실현 가능한 상태로 유지되도록 디폴트 값보다 더 엄격한 허용오차를 설정합니다.

thediff = 1e-4;
iter = 1; % iteration counter
assets = xLinInt(xvars); % the x variables
truequadratic = assets'*Q*assets;
zslack = xLinInt(zvar); % slack variable value
options = optimoptions(options,'LPOptimalityTolerance',1e-10,'RelativeGapTolerance',1e-8,...
                      'ConstraintTolerance',1e-9,'IntegerTolerance',1e-6);

플로팅을 위해 계산된 실제 2차 변수와 여유 변수의 내역을 유지합니다.

history = [truequadratic,zslack];

2차 값과 여유 값을 계산합니다. 두 값이 다르면 다른 선형 제약 조건을 추가하고 다시 풉니다.

툴박스 구문에서 각각의 새로운 선형 제약 조건 Axb는 다음 선형 근사에서 제공됩니다.

-xkTQxk+2xkTQx-z0.

A=2xkTQ의 새 행과 b=xkTQxk의 새 요소가 표시되고 A에 a -1 계수로 표현된 z 항이 있습니다.

새로운 해를 구한 후 이전 해와 새로운 해의 중간에 해당하는 선형 제약 조건을 사용합니다. 선형 제약 조건을 포함하는 이 발견적 방법이 단순히 새로운 해를 선택하는 것보다 빠를 수 있습니다. 발견적으로 중간 해를 사용하는 대신 이 해를 사용하려면 아래에서 "Midway" 라인을 주석 처리하고 그 뒤에 오는 라인을 주석 해제하십시오.

while abs((zslack - truequadratic)/truequadratic) > thediff % relative error
    newArow = horzcat(2*assets'*Q,zeros(1,N),-1); % Linearized constraint
    rhs = assets'*Q*assets;                       % right hand side of the linearized constraint
    A = [A;newArow];
    b = [b;rhs];
    % Solve the problem with the new constraints
    [xLinInt,fval,exitFlagInt,output] = intlinprog(f,vvars,A,b,Aeq,beq,lb,ub,options);
    assets = (assets+xLinInt(xvars))/2; % Midway from the previous to the current
%     assets = xLinInt(xvars); % Use the previous line or this one
    truequadratic = xLinInt(xvars)'*Q* xLinInt(xvars);
    zslack = xLinInt(zvar);
    history = [history;truequadratic,zslack];
    iter = iter + 1;
end

해와 수렴 속도 검토하기

여유 변수와 목적 함수 중 2차 부분의 내역을 플로팅하여 이들의 수렴 방식을 확인합니다.

plot(history)
legend('Quadratic','Slack')
xlabel('Iteration number')
title('Quadratic and linear approximation (slack)')

Figure contains an axes object. The axes object with title Quadratic and linear approximation (slack), xlabel Iteration number contains 2 objects of type line. These objects represent Quadratic, Slack.

MILP 해의 품질은 어떻습니까? output 구조체에 그 정보가 포함되어 있습니다. 해에서 목적 함수에 관해 내부적으로 계산된 범위 사이의 절대 간격을 검토합니다.

disp(output.absolutegap)
     0

절대 간격이 0이며, 이는 MILP 해가 정확함을 나타냅니다.

최적의 할당을 플로팅합니다. 중간 업데이트를 사용할 때 assets가 제약 조건을 충족하지 않을 수 있으므로 assets가 아니라 xLinInt(xvars)를 사용합니다.

bar(xLinInt(xvars))
grid on
xlabel('Asset index')
ylabel('Proportion of investment')
title('Optimal Asset Allocation')

Figure contains an axes object. The axes object with title Optimal Asset Allocation, xlabel Asset index, ylabel Proportion of investment contains an object of type bar.

0이 아닌 자산 할당이 모두 반연속 범위 fmin=0.001fmax=0.05 사이에 있음을 쉽게 알 수 있습니다.

0이 아닌 자산이 얼마나 많습니까? 제약 조건은 100개 ~ 150개 사이의 0이 아닌 자산이 있다는 것입니다.

sum(xLinInt(vvars))
ans = 100

이 할당에 대한 예상 수익과 위험 조정 후 수익 값은 어떻게 될까요?

fprintf('The expected return is %g, and the risk-adjusted return is %g.\n',...
    r'*xLinInt(xvars),-fval)
The expected return is 0.000595107, and the risk-adjusted return is -0.0360382.

Financial Toolbox™에서 포트폴리오 최적화를 위해 특별히 설계된 기능을 사용하면 더욱 정교한 분석이 가능합니다. 반연속 제약 조건과 구성종목수(cardinality) 제약 조건을 직접 다루기 위해 Portfolio 클래스를 사용하는 방법을 보여주는 예제는 Portfolio Optimization with Semicontinuous and Cardinality Constraints (Financial Toolbox) 항목을 참조하십시오.

관련 항목