Main Content

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

이 예제에서는 문제 기반 접근법을 사용하여 혼합 정수 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에는 이러한 제약 조건을 포함시킬 수 없습니다. 이 경우의 어려운 점은 제약 조건의 특성이 이산적이라는 것입니다. 뿐만 아니라, 혼합 정수 선형 계획법 솔버는 이산 제약 조건은 처리하지만 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.

이 목적 함수는 비선형적입니다. 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® 문제 정식화

최적화 문제를 표현하려면 다음을 수행하십시오.

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

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

  • 선형 등식과 선형 부등식의 표현식 지정

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

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

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

N = length(r);

문제 변수, 제약 조건, 목적 함수 만들기

자산 할당 비율을 나타내는 연속 변수 xvars, 연관된 xvars가 0 또는 순양수인지 여부를 나타내는 이진 변수 vvars, 양의 스칼라인 z 변수를 나타내는 zvar을 만듭니다.

xvars = optimvar('xvars',N,1,'LowerBound',0,'UpperBound',1);
vvars = optimvar('vvars',N,1,'Type','integer','LowerBound',0,'UpperBound',1);
zvar = optimvar('zvar',1,'LowerBound',0);

문제에서 모든 2N+1개 변수의 하한은 0입니다. xvars 변수와 yvars 변수의 상한은 1이고 zvar에는 상한이 없습니다.

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

miv(i)M,

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

iv(i)M

iv(i)m.

M = 150;
m = 100;
qpprob = optimproblem('ObjectiveSense','maximize');
qpprob.Constraints.mconstr = sum(vvars) <= M;
qpprob.Constraints.mconstr2 = sum(vvars) >= m;

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

fmin = 0.001;
fmax = 0.05;

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

qpprob.Constraints.fmaxconstr = xvars <= fmax*vvars;
qpprob.Constraints.fminconstr = fmin*vvars <= xvars;

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

qpprob.Constraints.allin = sum(xvars) == 1;

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

lambda = 100;

목적 함수 rTx-λz를 정의하여 문제에 포함시킵니다.

qpprob.Objective = r'*xvars - lambda*zvar;

문제 풀기

문제를 반복적으로 풀려면 먼저 어떤 선형화도 아직 반영하지 않는 현재 제약 조건으로 문제를 풀어보십시오.

options = optimoptions(@intlinprog,'Display','off'); % Suppress iterative display
[xLinInt,fval,exitFlagInt,output] = solve(qpprob,'options',options);

반복의 중지 조건을 준비합니다. 여유 변수 z가 실제 2차 값의 0.01% 내에 있을 때 중지합니다.

thediff = 1e-4;
iter = 1; % iteration counter
assets = xLinInt.xvars;
truequadratic = assets'*Q*assets;
zslack = xLinInt.zvar;

플로팅을 위해 계산된 실제 2차 변수와 여유 변수의 내역을 유지합니다. 디폴트 값보다 더 엄격한 허용오차를 설정하여 반복이 올바른 해로 수렴하도록 합니다.

history = [truequadratic,zslack];

options = optimoptions(options,'LPOptimalityTolerance',1e-10,'RelativeGapTolerance',1e-8,...
                      'ConstraintTolerance',1e-9,'IntegerTolerance',1e-6);

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

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

-xkTQxk+2xkTQx-z0.

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

while abs((zslack - truequadratic)/truequadratic) > thediff % relative error
    constr = 2*assets'*Q*xvars - zvar <= assets'*Q*assets;
    newname = ['iteration',num2str(iter)];
    qpprob.Constraints.(newname) = constr;
    % Solve the problem with the new constraints
    [xLinInt,fval,exitFlagInt,output] = solve(qpprob,'options',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)')

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')

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) 항목을 참조하십시오.

관련 항목