Main Content

Objetivo lineal o cuadrático con restricciones cuadráticas

Este ejemplo muestra cómo resolver un problema de optimización que tiene un objetivo lineal o cuadrático y restricciones de desigualdad cuadrática. Muestra cómo generar y utilizar el degradado y hessian de las funciones objetivo y restricción.

Problema cuadrático restringido

Supongamos que puede poner su problema en la forma

minx(12xTQx+fTx+c)

sujetas a

12xTHix+kiTx+di0,

Dónde 1 ≤ i ≤ m. Supongamos que al menos una Hi es distinto de cero; de lo contrario, puede usar o resolver este problema.quadproglinprog Con cero Hi, las restricciones son no lineales y los Estados que son el solucionador adecuado.Tabla de decisión de optimizaciónfmincon

El ejemplo asume que las matrices cuadráticas son simétricas. Esto es sin pérdida de generalidad; puede reemplazar una matriz no simétrica (o) con una versión simetralizada equivalenteHQ (H + HT)/2.

Si tiene componentes, entonces y elxNQ Hi son-por-matrices, y elNNf Ki son-por-1 vectores, y y elNc Di son escalares.

Función objetivo

Formule el problema utilizando la sintaxis.fmincon Supongamos que son vectores de columna. (es un vector de columna cuando el vector inicial es.)xfxx0

function [y,grady] = quadobj(x,Q,f,c) y = 1/2*x'*Q*x + f'*x + c; if nargout > 1     grady = Q*x + f; end

Función de restricción

Para la coherencia y la indexación fácil, coloque cada matriz de restricción cuadrática en una matriz de celdas. De forma similar, coloque los términos lineales y constantes en matrices de celdas.

function [y,yeq,grady,gradyeq] = quadconstr(x,H,k,d) jj = length(H); % jj is the number of inequality constraints y = zeros(1,jj); for i = 1:jj     y(i) = 1/2*x'*H{i}*x + k{i}'*x + d{i}; end yeq = [];      if nargout > 2     grady = zeros(length(x),jj);     for i = 1:jj         grady(:,i) = H{i}*x + k{i};     end end gradyeq = [];

Ejemplo numérico

Por ejemplo, suponga que tiene el siguiente problema.

Q = [3,2,1;      2,4,0;      1,0,5]; f = [-24;-48;-130]; c = -2;  rng default % for reproducibility % Two sets of random quadratic constraints: H{1} = gallery('randcorr',3); % random positive definite matrix H{2} = gallery('randcorr',3); k{1} = randn(3,1); k{2} = randn(3,1); d{1} = randn; d{2} = randn;

Hessian

Crear una función de hessian. El Hessiano del Lagrangio es dado por la ecuación

xx2L(x,λ)=2f(x)+λi2ci(x)+λi2ceqi(x).

calcula un conjunto aproximado de multiplicadores de Lagrangefmincon Λi, y los empaqueta en una estructura. Para incluir el hessian, utilice la siguiente función.

function hess = quadhess(x,lambda,Q,H) hess = Q; jj = length(H); % jj is the number of inequality constraints for i = 1:jj     hess = hess + lambda.ineqnonlin(i)*H{i}; end

Solución

Utilice el algoritmo para resolver el problema de manera más eficiente.fminconinterior-point Este algoritmo acepta una función de hessian que usted suministra. Establezca estas opciones.

options = optimoptions(@fmincon,'Algorithm','interior-point',...     'SpecifyObjectiveGradient',true,'SpecifyConstraintGradient',true,...     'HessianFcn',@(x,lambda)quadhess(x,lambda,Q,H));

Llame para resolver el problema.fmincon

fun = @(x)quadobj(x,Q,f,c); nonlconstr = @(x)quadconstr(x,H,k,d); x0 = [0;0;0]; % column vector [x,fval,eflag,output,lambda] = fmincon(fun,x0,...     [],[],[],[],[],[],nonlconstr,options);

Examine los multiplicadores de Lagrange.

lambda.ineqnonlin
ans =     12.8412    39.2337

Ambos multiplicadores de desigualdad no lineales son distintos de cero, por lo que ambas restricciones cuadráticas están activas en la solución.

Eficiencia cuando se proporciona un hessian

El algoritmo de punto interior con gradientes y un hessian es eficiente. Examine el número de evaluaciones de funciones.

output
output =            iterations: 9           funcCount: 10     constrviolation: 0            stepsize: 5.3547e-04           algorithm: 'interior-point'       firstorderopt: 1.5851e-05        cgiterations: 0             message: 'Local minimum found that satisfies the constraints.  Optimization compl...'

utilizado sólo 10 evaluaciones de función para resolver el problema.fmincon

Compare esto con la solución sin el hessian.

options.HessianFcn = []; [x2,fval2,eflag2,output2,lambda2] = fmincon(fun,[0;0;0],...     [],[],[],[],[],[],nonlconstr,options); output2
output2 =            iterations: 17           funcCount: 22     constrviolation: 0            stepsize: 2.8475e-04           algorithm: 'interior-point'       firstorderopt: 1.7680e-05        cgiterations: 0             message: 'Local minimum found that satisfies the constraints.  Optimization compl...'

Esta vez se utilizaron aproximadamente el doble de iteraciones y evaluaciones de funciones.fmincon Las soluciones son las mismas que dentro de las tolerancias.

Extensión a las restricciones de igualdad cuadrática

Si también tiene restricciones de igualdad cuadráticas, puede usar esencialmente la misma técnica. El problema es el mismo, con las restricciones adicionales

12xTJix+piTx+qi=0.

Reformule sus restricciones para usar el Ji, PiY Qi Variables. La estructura tiene los multiplicadores de Lagrange para las restricciones de igualdad.lambda.eqnonlin(i)

Ejemplos relacionados

Más acerca de