Esta página aún no se ha traducido para esta versión. Puede ver la versión más reciente de esta página en inglés.

Optimización de la cartera de programación cuadrática de enteros mixtos: basada en Solver

En este ejemplo se muestra cómo resolver un problema de optimización de la cartera de programación cuadrática de enteros mixtos (MIQP) mediante el solucionador de programación lineal de enteros mixtos (MILP).intlinprog La idea es resolver iterativamente una secuencia de problemas de MILP que localmente aproximan el problema de MIQP. Para el enfoque basado en problemas, vea.Optimización de la cartera de programación cuadrática de enteros mixtos: basada en problemas

Problema contorno

Como mostró Markowitz ("selección de portafolio", J. Finance volumen 7, número 1, PP. 77-91, marzo 1952), puede expresar muchos problemas de optimización de la cartera como problemas de programación cuadrática. Supongamos que tiene un conjunto de activos y desea elegir una cartera, conN

<math display="block">
<mrow>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo stretchy="false">)</mo>
</mrow>
</math>
ser la fracción de su inversión que está en activo
<math display="block">
<mrow>
<mi>i</mi>
</mrow>
</math>
. Si conoce el vector
<math display="block">
<mrow>
<mi>r</mi>
</mrow>
</math>
de retornos de valor de cada activo y la matriz de covarianzas
<math display="block">
<mrow>
<mi>Q</mi>
</mrow>
</math>
de los retornos, entonces para un determinado nivel de riesgo-aversión
<math display="block">
<mrow>
<mi>λ</mi>
</mrow>
</math>
maximiza la rentabilidad esperada ajustada al riesgo:

<math display="block">
<mrow>
<munder>
<mrow>
<mi mathvariant="normal">max</mi>
</mrow>
<mrow>
<mi>x</mi>
</mrow>
</munder>
<mo stretchy="false">(</mo>
<msup>
<mrow>
<mi>r</mi>
</mrow>
<mrow>
<mi>T</mi>
</mrow>
</msup>
<mi>x</mi>
<mo>-</mo>
<mi>λ</mi>
<msup>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mi>T</mi>
</mrow>
</msup>
<mi>Q</mi>
<mi>x</mi>
<mo stretchy="false">)</mo>
<mo>.</mo>
</mrow>
</math>

El solucionador aborda este problema de programación cuadrática.quadprog Sin embargo, además del problema de programación cuadrática simple, es posible que desee restringir una cartera de varias maneras, como:

  • No tener más que activos en la cartera, donde.MM <= N

  • Tener al menos activos en la cartera, donde.m0 < m <= M

  • Tener restricciones, lo que significasemicontinuous

    <math display="block">
    <mrow>
    <mi>x</mi>
    <mo stretchy="false">(</mo>
    <mi>i</mi>
    <mo stretchy="false">)</mo>
    <mo>=</mo>
    <mn>0</mn>
    </mrow>
    </math>
    O
    <math display="block">
    <mrow>
    <mi>f</mi>
    <mrow>
    <mstyle mathvariant="normal">
    <mrow>
    <mi>m</mi>
    <mi>i</mi>
    <mi>n</mi>
    </mrow>
    </mstyle>
    </mrow>
    <mo></mo>
    <mi>x</mi>
    <mo stretchy="false">(</mo>
    <mi>i</mi>
    <mo stretchy="false">)</mo>
    <mo></mo>
    <mi>f</mi>
    <mrow>
    <mstyle mathvariant="normal">
    <mrow>
    <mi>m</mi>
    <mi>a</mi>
    <mi>x</mi>
    </mrow>
    </mstyle>
    </mrow>
    </mrow>
    </math>
    para algunas fracciones fijas
    <math display="block">
    <mrow>
    <mi>f</mi>
    <mrow>
    <mstyle mathvariant="normal">
    <mrow>
    <mi>m</mi>
    <mi>i</mi>
    <mi>n</mi>
    </mrow>
    </mstyle>
    </mrow>
    <mo>></mo>
    <mn>0</mn>
    </mrow>
    </math>
    Y
    <math display="block">
    <mrow>
    <mi>f</mi>
    <mrow>
    <mstyle mathvariant="normal">
    <mrow>
    <mi>m</mi>
    <mi>a</mi>
    <mi>x</mi>
    </mrow>
    </mstyle>
    </mrow>
    <mo></mo>
    <mi>f</mi>
    <mrow>
    <mstyle mathvariant="normal">
    <mrow>
    <mi>m</mi>
    <mi>i</mi>
    <mi>n</mi>
    </mrow>
    </mstyle>
    </mrow>
    </mrow>
    </math>
    .

No puede incluir estas restricciones en.quadprog La dificultad es la naturaleza discreta de las restricciones. Además, aunque el solucionador de programación lineal de enteros mixtos no controla las restricciones discretas, no aborda las funciones de objetivo cuadrático.intlinprog

Este ejemplo construye una secuencia de problemas MILP que satisfacen las restricciones, y que cada vez más aproximan la función cuadrática del objetivo. Aunque esta técnica funciona en este ejemplo, es posible que no se aplique a diferentes tipos de problemas o restricciones.

Empiece por modelar las restricciones.

Modelado de restricciones discretas

<math display="block">
<mrow>
<mi>x</mi>
</mrow>
</math>
es el vector de las fracciones de asignación de activos, con
<math display="block">
<mrow>
<mn>0</mn>
<mo></mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo stretchy="false">)</mo>
<mo></mo>
<mn>1</mn>
</mrow>
</math>
para cada
<math display="block">
<mrow>
<mi>i</mi>
</mrow>
</math>
. Para modelar el número de activos en la cartera, necesita variables indicadoras
<math display="block">
<mrow>
<mi>v</mi>
</mrow>
</math>
tal que
<math display="block">
<mrow>
<mi>v</mi>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mn>0</mn>
</mrow>
</math>
Cuando
<math display="block">
<mrow>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mn>0</mn>
</mrow>
</math>
Y
<math display="block">
<mrow>
<mi>v</mi>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mn>1</mn>
</mrow>
</math>
Cuando
<math display="block">
<mrow>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo stretchy="false">)</mo>
<mo>></mo>
<mn>0</mn>
</mrow>
</math>
. Para obtener las variables que satisfacen esta restricción, establezca el
<math display="block">
<mrow>
<mi>v</mi>
</mrow>
</math>
Vector sea una variable binaria e imponer las restricciones lineales

<math display="block">
<mrow>
<mi>v</mi>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo stretchy="false">)</mo>
<mi>f</mi>
<mrow>
<mstyle mathvariant="normal">
<mrow>
<mi>m</mi>
<mi>i</mi>
<mi>n</mi>
</mrow>
</mstyle>
</mrow>
<mo></mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo stretchy="false">)</mo>
<mo></mo>
<mi>v</mi>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo stretchy="false">)</mo>
<mi>f</mi>
<mrow>
<mstyle mathvariant="normal">
<mrow>
<mi>m</mi>
<mi>a</mi>
<mi>x</mi>
</mrow>
</mstyle>
</mrow>
<mo>.</mo>
</mrow>
</math>

Estas desigualdades exigen que

<math display="block">
<mrow>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo stretchy="false">)</mo>
</mrow>
</math>
Y
<math display="block">
<mrow>
<mi>v</mi>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo stretchy="false">)</mo>
</mrow>
</math>
son cero exactamente al mismo tiempo, y también hacen cumplir que
<math display="block">
<mrow>
<mi>f</mi>
<mrow>
<mstyle mathvariant="normal">
<mrow>
<mi>m</mi>
<mi>i</mi>
<mi>n</mi>
</mrow>
</mstyle>
</mrow>
<mo></mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo stretchy="false">)</mo>
<mo></mo>
<mi>f</mi>
<mrow>
<mstyle mathvariant="normal">
<mrow>
<mi>m</mi>
<mi>a</mi>
<mi>x</mi>
</mrow>
</mstyle>
</mrow>
</mrow>
</math>
Cuando
<math display="block">
<mrow>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo stretchy="false">)</mo>
<mo>></mo>
<mn>0</mn>
</mrow>
</math>
.

Además, para imponer las restricciones en el número de activos de la cartera, imponga las restricciones lineales

<math display="block">
<mrow>
<mi>m</mi>
<mo></mo>
<munder>
<mrow>
<mo></mo>
</mrow>
<mrow>
<mi>i</mi>
</mrow>
</munder>
<mi>v</mi>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo stretchy="false">)</mo>
<mo></mo>
<mi>M</mi>
<mo>.</mo>
</mrow>
</math>

Las aproximaciones lineales objetivas y sucesivas

Como se formuló primero, se intenta maximizar la función objetiva. Sin embargo, todos los solucionadores de Optimization Toolbox™ se minimizan. Así que formule el problema minimizando el negativo del objetivo:

<math display="block">
<mrow>
<munder>
<mrow>
<mi mathvariant="normal">min</mi>
</mrow>
<mrow>
<mi>x</mi>
</mrow>
</munder>
<mi>λ</mi>
<msup>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mi>T</mi>
</mrow>
</msup>
<mi>Q</mi>
<mi>x</mi>
<mo>-</mo>
<msup>
<mrow>
<mi>r</mi>
</mrow>
<mrow>
<mi>T</mi>
</mrow>
</msup>
<mi>x</mi>
<mo>.</mo>
</mrow>
</math>

Esta función objetiva no es lineal. El solucionador MILP requiere una función objetiva lineal.intlinprog Hay una técnica estándar para reformular este problema en uno con objetivos lineales y restricciones no lineales. Introducir una variable de holgura

<math display="block">
<mrow>
<mi>z</mi>
</mrow>
</math>
para representar el término cuadrático.

<math display="block">
<mrow>
<munder>
<mrow>
<mi mathvariant="normal">min</mi>
</mrow>
<mrow>
<mi>x</mi>
<mo>,</mo>
<mi>z</mi>
</mrow>
</munder>
<mi>λ</mi>
<mi>z</mi>
<mo>-</mo>
<msup>
<mrow>
<mi>r</mi>
</mrow>
<mrow>
<mi>T</mi>
</mrow>
</msup>
<mi>x</mi>
<mrow>
<mtext> such that </mtext>
</mrow>
<msup>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mi>T</mi>
</mrow>
</msup>
<mi>Q</mi>
<mi>x</mi>
<mo>-</mo>
<mi>z</mi>
<mo></mo>
<mn>0</mn>
<mo>,</mo>
<mspace width="0.5em"></mspace>
<mi>z</mi>
<mo></mo>
<mn>0</mn>
<mo>.</mo>
</mrow>
</math>

Al resolver iterativamente las aproximaciones de MILP, se incluyen nuevas restricciones lineales, cada una de las cuales se aproxima a la restricción no lineal localmente cerca del punto actual. En particular, para

<math display="block">
<mrow>
<mi>x</mi>
<mo>=</mo>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mn>0</mn>
</mrow>
</msub>
<mo>+</mo>
<mi>δ</mi>
</mrow>
</math>
Dónde
<math display="block">
<mrow>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mn>0</mn>
</mrow>
</msub>
</mrow>
</math>
es un vector constante y
<math display="block">
<mrow>
<mi>δ</mi>
</mrow>
</math>
es un vector variable, la aproximación de primer orden de Taylor a la restricción es

<math display="block">
<mrow>
<msup>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mi>T</mi>
</mrow>
</msup>
<mi>Q</mi>
<mi>x</mi>
<mo>-</mo>
<mi>z</mi>
<mo>=</mo>
<msubsup>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mn>0</mn>
</mrow>
<mrow>
<mi>T</mi>
</mrow>
</msubsup>
<mi>Q</mi>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mn>0</mn>
</mrow>
</msub>
<mo>+</mo>
<mn>2</mn>
<msubsup>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mn>0</mn>
</mrow>
<mrow>
<mi>T</mi>
</mrow>
</msubsup>
<mi>Q</mi>
<mi>δ</mi>
<mo>-</mo>
<mi>z</mi>
<mo>+</mo>
<mi>O</mi>
<mo stretchy="false">(</mo>
<mo>|</mo>
<mi>δ</mi>
<msup>
<mrow>
<mo>|</mo>
</mrow>
<mrow>
<mn>2</mn>
</mrow>
</msup>
<mo stretchy="false">)</mo>
<mo>.</mo>
</mrow>
</math>

Reemplazar

<math display="block">
<mrow>
<mi>δ</mi>
</mrow>
</math>
Por
<math display="block">
<mrow>
<mi>x</mi>
<mo>-</mo>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mn>0</mn>
</mrow>
</msub>
</mrow>
</math>
Da

<math display="block">
<mrow>
<msup>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mi>T</mi>
</mrow>
</msup>
<mi>Q</mi>
<mi>x</mi>
<mo>-</mo>
<mi>z</mi>
<mo>=</mo>
<mo>-</mo>
<msubsup>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mn>0</mn>
</mrow>
<mrow>
<mi>T</mi>
</mrow>
</msubsup>
<mi>Q</mi>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mn>0</mn>
</mrow>
</msub>
<mo>+</mo>
<mn>2</mn>
<msubsup>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mn>0</mn>
</mrow>
<mrow>
<mi>T</mi>
</mrow>
</msubsup>
<mi>Q</mi>
<mi>x</mi>
<mo>-</mo>
<mi>z</mi>
<mo>+</mo>
<mi>O</mi>
<mo stretchy="false">(</mo>
<mo>|</mo>
<mi>x</mi>
<mo>-</mo>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mn>0</mn>
</mrow>
</msub>
<msup>
<mrow>
<mo>|</mo>
</mrow>
<mrow>
<mn>2</mn>
</mrow>
</msup>
<mo stretchy="false">)</mo>
<mo>.</mo>
</mrow>
</math>

Para cada solución intermedia

<math display="block">
<mrow>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mi>k</mi>
</mrow>
</msub>
</mrow>
</math>
introduce una nueva restricción lineal en
<math display="block">
<mrow>
<mi>x</mi>
</mrow>
</math>
Y
<math display="block">
<mrow>
<mi>z</mi>
</mrow>
</math>
como la parte lineal de la expresión anterior:

<math display="block">
<mrow>
<mo>-</mo>
<msubsup>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mi>k</mi>
</mrow>
<mrow>
<mi>T</mi>
</mrow>
</msubsup>
<mi>Q</mi>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mi>k</mi>
</mrow>
</msub>
<mo>+</mo>
<mn>2</mn>
<msubsup>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mi>k</mi>
</mrow>
<mrow>
<mi>T</mi>
</mrow>
</msubsup>
<mi>Q</mi>
<mi>x</mi>
<mo>-</mo>
<mi>z</mi>
<mo></mo>
<mn>0</mn>
<mo>.</mo>
</mrow>
</math>

Esto tiene la forma

<math display="block">
<mrow>
<mi>A</mi>
<mi>x</mi>
<mo></mo>
<mi>b</mi>
</mrow>
</math>
Dónde
<math display="block">
<mrow>
<mi>A</mi>
<mo>=</mo>
<mn>2</mn>
<msubsup>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mi>k</mi>
</mrow>
<mrow>
<mi>T</mi>
</mrow>
</msubsup>
<mi>Q</mi>
</mrow>
</math>
, hay un
<math display="block">
<mrow>
<mo>-</mo>
<mn>1</mn>
</mrow>
</math>
multiplicador para el
<math display="block">
<mrow>
<mi>z</mi>
</mrow>
</math>
plazo, y
<math display="block">
<mrow>
<mi>b</mi>
<mo>=</mo>
<msubsup>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mi>k</mi>
</mrow>
<mrow>
<mi>T</mi>
</mrow>
</msubsup>
<mi>Q</mi>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mi>k</mi>
</mrow>
</msub>
</mrow>
</math>
.

Este método de agregar nuevas restricciones lineales al problema se denomina método de plano de corte. Para más detalles, véase j. e. Kelley, Jr. "El método de plano de corte para la resolución de programas convexo." J. soc. Indust. Appl. Matemática. Vol. 8, no. 4, PP. 703-712, diciembre, 1960.

MATLAB® formulación problemática

Para expresar los problemas del solucionador, debe hacer lo siguiente:intlinprog

  • Decida qué representan sus variables

  • Exprese los límites inferior y superior en términos de estas variables

  • Dar matrices de igualdad y desigualdad lineales

Tenga la primera

<math display="block">
<mrow>
<mi>N</mi>
</mrow>
</math>
variables representan el
<math display="block">
<mrow>
<mi>x</mi>
</mrow>
</math>
Vector, el siguiente
<math display="block">
<mrow>
<mi>N</mi>
</mrow>
</math>
variables representan el binario
<math display="block">
<mrow>
<mi>v</mi>
</mrow>
</math>
Vector, y la variable final representa el
<math display="block">
<mrow>
<mi>z</mi>
</mrow>
</math>
variable de Slack. Hay
<math display="block">
<mrow>
<mn>2</mn>
<mi>N</mi>
<mo>+</mo>
<mn>1</mn>
</mrow>
</math>
variables en el problema.

Cargue los datos para el problema. Estos datos tienen 225 retornos esperados en el vector y la covarianza de los retornos en la matriz 225-by-225.rQ Los datos son los mismos que en el ejemplo uso de programación cuadrática en problemas de optimización de carteras.

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

Establezca el número de activos como.N

N = length(r);

Establezca índices para las variables

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

Los límites inferiores de todas las variables en el problema son cero.2N+1 Los límites superiores de las primeras variables son uno, y la última variable no tiene ningún límite superior.2N

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

Establezca el número de activos en la solución entre 100 y 150. Incorporar esta restricción en el problema de la forma, es decir,

<math display="block">
<mrow>
<mi>m</mi>
<mo></mo>
<munder>
<mrow>
<mo></mo>
</mrow>
<mrow>
<mi>i</mi>
</mrow>
</munder>
<mi>v</mi>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo stretchy="false">)</mo>
<mo></mo>
<mi>M</mi>
<mo>,</mo>
</mrow>
</math>

escribiendo dos restricciones lineales de la forma

<math display="block">
<mrow>
<mi>A</mi>
<mi>x</mi>
<mo></mo>
<mi>b</mi>
</mrow>
</math>
:

<math display="block">
<mrow>
<munder>
<mrow>
<mo></mo>
</mrow>
<mrow>
<mi>i</mi>
</mrow>
</munder>
<mi>v</mi>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo stretchy="false">)</mo>
<mo></mo>
<mi>M</mi>
</mrow>
</math>

<math display="block">
<mrow>
<munder>
<mrow>
<mo></mo>
</mrow>
<mrow>
<mi>i</mi>
</mrow>
</munder>
<mo>-</mo>
<mi>v</mi>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo stretchy="false">)</mo>
<mo></mo>
<mo>-</mo>
<mi>m</mi>
<mo>.</mo>
</mrow>
</math>

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;

Incluya restricciones semicontinuas. Tome la fracción mínima distinta de cero de los activos para cada tipo de activo y la fracción máxima a ser.0.0010.05

fmin = 0.001; fmax = 0.05;

Incluya las desigualdades

<math display="block">
<mrow>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo stretchy="false">)</mo>
<mo></mo>
<mi>f</mi>
<mrow>
<mstyle mathvariant="normal">
<mrow>
<mi>m</mi>
<mi>a</mi>
<mi>x</mi>
</mrow>
</mstyle>
</mrow>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo stretchy="false">)</mo>
<mo>*</mo>
<mi>v</mi>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo stretchy="false">)</mo>
</mrow>
</math>
Y
<math display="block">
<mrow>
<mi>f</mi>
<mrow>
<mstyle mathvariant="normal">
<mrow>
<mi>m</mi>
<mi>i</mi>
<mi>n</mi>
</mrow>
</mstyle>
</mrow>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo stretchy="false">)</mo>
<mo>*</mo>
<mi>v</mi>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo stretchy="false">)</mo>
<mo></mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo stretchy="false">)</mo>
</mrow>
</math>
como desigualdades lineales.

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)];

Incluir la restricción de que la cartera es 100% invertido, lo que significa

<math display="block">
<mrow>
<mo></mo>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mi>i</mi>
</mrow>
</msub>
<mo>=</mo>
<mn>1</mn>
</mrow>
</math>
.

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

Establezca el coeficiente de aversión de riesgo

<math display="block">
<mrow>
<mi>λ</mi>
</mrow>
</math>
Para.100

lambda = 100;

Defina la función objetiva

<math display="block">
<mrow>
<mi>λ</mi>
<mi>z</mi>
<mo>-</mo>
<msup>
<mrow>
<mi>r</mi>
</mrow>
<mrow>
<mi>T</mi>
</mrow>
</msup>
<mi>x</mi>
</mrow>
</math>
como vector. Incluya ceros para los multiplicadores del
<math display="block">
<mrow>
<mi>v</mi>
</mrow>
</math>
Variables.

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

Resolver el problema

Para resolver el problema de forma iterativa, empiece resolviendo el problema con las restricciones actuales, que aún no reflejan ninguna linearización. Las restricciones de enteros están en el vector.vvars

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

Prepare una condición de detención para las iteraciones: deténgase cuando la variable de holgura

<math display="block">
<mrow>
<mi>z</mi>
</mrow>
</math>
se encuentra dentro del 0,01% del verdadero valor cuadrático. Establezca tolerancias más estrictas que las predeterminadas para ayudar a garantizar que el problema sigue siendo estrictamente factible a medida que se acumulan las restricciones.

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

Mantenga un historial de las variables verdaderas cuadráticas y de holgura calculadas para el trazado.

history = [truequadratic,zslack];

Calcule los valores cuadráticos y de holgura. Si difieren, a continuación, añadir otra restricción lineal y resolver de nuevo.

En la sintaxis de Toolbox, cada nueva restricción lineal

<math display="block">
<mrow>
<mi>A</mi>
<mi>x</mi>
<mo></mo>
<mi>b</mi>
</mrow>
</math>
proviene de la aproximación lineal

<math display="block">
<mrow>
<mo>-</mo>
<msubsup>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mi>k</mi>
</mrow>
<mrow>
<mi>T</mi>
</mrow>
</msubsup>
<mi>Q</mi>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mi>k</mi>
</mrow>
</msub>
<mo>+</mo>
<mn>2</mn>
<msubsup>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mi>k</mi>
</mrow>
<mrow>
<mi>T</mi>
</mrow>
</msubsup>
<mi>Q</mi>
<mi>x</mi>
<mo>-</mo>
<mi>z</mi>
<mo></mo>
<mn>0</mn>
<mo>.</mo>
</mrow>
</math>

Usted ve que la nueva fila de

<math display="block">
<mrow>
<mi>A</mi>
<mo>=</mo>
<mn>2</mn>
<msubsup>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mi>k</mi>
</mrow>
<mrow>
<mi>T</mi>
</mrow>
</msubsup>
<mi>Q</mi>
</mrow>
</math>
y el nuevo elemento en
<math display="block">
<mrow>
<mi>b</mi>
<mo>=</mo>
<msubsup>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mi>k</mi>
</mrow>
<mrow>
<mi>T</mi>
</mrow>
</msubsup>
<mi>Q</mi>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mi>k</mi>
</mrow>
</msub>
</mrow>
</math>
, con el
<math display="block">
<mrow>
<mi>z</mi>
</mrow>
</math>
término representado por el coeficiente a-1 en
<math display="block">
<mrow>
<mi>A</mi>
</mrow>
</math>
.

Después de encontrar una nueva solución, utilice una restricción lineal a medio camino entre las soluciones antiguas y las nuevas. Esta forma heurística de incluir restricciones lineales puede ser más rápida que simplemente tomar la nueva solución. Para usar la solución en lugar de la heurística a mitad de camino, comente la línea "Midway" a continuación y quite el comentario de la siguiente.

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

Examine la solución y la tasa de convergencia

Graficar el historial de la variable de Slack y la parte cuadrática de la función objetivo para ver cómo convergieron.

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

¿Cuál es la calidad de la solución MILP? La estructura contiene esa información.output Examine la brecha absoluta entre los límites calculados internamente en el objetivo de la solución.

disp(output.absolutegap)
     0 

La brecha absoluta es cero, lo que indica que la solución MILP es precisa.

Trazar la asignación óptima. Utilice, no, porque no puede satisfacer las restricciones cuando se utiliza la actualización a mitad de camino.xLinInt(xvars)assetsassets

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

Puede ver fácilmente que todas las asignaciones de activos distintos de cero se encuentran entre los límites semicontinuos

<math display="block">
<mrow>
<mi>f</mi>
<mrow>
<mstyle mathvariant="normal">
<mrow>
<mi>m</mi>
<mi>i</mi>
<mi>n</mi>
</mrow>
</mstyle>
</mrow>
<mo>=</mo>
<mn>0</mn>
<mo>.</mo>
<mn>0</mn>
<mn>0</mn>
<mn>1</mn>
</mrow>
</math>
Y
<math display="block">
<mrow>
<mi>f</mi>
<mrow>
<mstyle mathvariant="normal">
<mrow>
<mi>m</mi>
<mi>a</mi>
<mi>x</mi>
</mrow>
</mstyle>
</mrow>
<mo>=</mo>
<mn>0</mn>
<mo>.</mo>
<mn>0</mn>
<mn>5</mn>
</mrow>
</math>
.

¿Cuántos activos distintos de cero hay? La restricción es que hay entre 100 y 150 activos distintos de cero.

sum(xLinInt(vvars))
ans = 100 

¿Cuál es la rentabilidad esperada para esta asignación y el valor de la rentabilidad ajustada al riesgo?

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. 

Los análisis más elaborados son posibles mediante el uso de características diseñadas específicamente para la optimización de carteras en Financial Toolbox™. Para obtener un ejemplo que muestra cómo utilizar la clase portfolio para controlar directamente las restricciones de cardinalidad y semicontinuas, consultePortfolio Optimization with Semicontinuous and Cardinality Constraints (Financial Toolbox).

Temas relacionados