2차 제약 조건이 있는 선형 목적 함수 또는 2차 목적 함수

이 예제에서는 선형 목적 함수 또는 2차 목적 함수와 2차 부등식 제약 조건을 갖는 최적화 문제를 푸는 방법을 보여줍니다. 그리고 목적 함수와 제약 조건 함수의 기울기와 헤세 행렬을 생성하고 사용합니다.

2차 제약 조건이 있는 문제
목적 함수
제약 조건 함수
수치 예제
헤세 행렬
해(Solution)
헤세 행렬을 제공할 때의 효율성
2차 등식 제약 조건으로 확장

2차 제약 조건이 있는 문제

다음과 같은 형식의 문제라고 가정하겠습니다.

$\min_{x} (\frac{1}{2} x^{T} Q x + f^{T} x + c)$

여기에는 다음 조건이 적용됩니다.

$\frac{1}{2} x^{T} H_{i} x + k_{i}^{T} x + d_{i} \leq 0,$

여기서 1 ≤ i ≤ m입니다. 적어도 하나의 H_i가 0이 아니라고 가정합니다. 그렇지 않을 경우 quadprog 또는 linprog를 사용하여 이 문제를 풀 수 있습니다. H_i가 0이 아니면 제약 조건이 비선형이며, 최적화 의사 결정표에 따르면 fmincon이 적절한 솔버입니다.

이 예제에서는 2차 행렬이 대칭 행렬이라고 가정하며, 이러한 가정은 일반성을 잃지 않습니다. 비대칭 행렬 H(또는 Q)를 이에 상응하는 대칭화된 버전 (H + H^T)/2로 바꿀 수 있습니다.

x에 N개의 성분이 있으면 Q와 H_i가 N×N 행렬이고, f와 k_i는 N×1 벡터이며, c와 d_i는 스칼라입니다.

목적 함수

fmincon 구문을 사용하여 문제를 정식화합니다. x와 f가 열 벡터라고 가정합니다(초기 벡터 x0이 열 벡터이면 x도 열 벡터임).

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

제약 조건 함수

일관성을 유지하고 쉽게 인덱싱할 수 있도록 모든 2차 제약 조건 행렬을 하나의 셀형 배열에 추가합니다. 마찬가지로, 일차항과 상수항도 셀형 배열에 추가합니다.

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 = [];

수치 예제

다음 문제가 있다고 가정합니다.

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;

헤세 행렬

헤세 행렬 함수를 만듭니다. 라그랑주의 헤세 행렬은 다음 방정식으로 주어집니다.

$\nabla_{x x}^{2} L (x, λ) = \nabla^{2} f (x) + \sum λ_{i} \nabla^{2} c_{i} (x) + \sum λ_{i} \nabla^{2} c e q_{i} (x) .$

fmincon은 라그랑주 승수 λ_i의 근사 세트를 계산한 후 이를 구조체에 패키징합니다. 헤세 행렬을 포함시키려면 다음 함수를 사용하십시오.

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

해(Solution)

fmincon의 interior-point 알고리즘을 사용하면 문제를 더 효율적으로 풀 수 있습니다. 이 알고리즘은 사용자가 제공하는 헤세 행렬 함수를 받습니다. 다음과 같이 옵션을 설정합니다.

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

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

라그랑주 승수를 검토합니다.

lambda.ineqnonlin

ans =

   12.8412
   39.2337

두 비선형 부등식 승수가 모두 0이 아니므로, 두 2차 제약 조건도 모두 해에서 활성 상태입니다.

헤세 행렬을 제공할 때의 효율성

기울기와 헤세 행렬을 사용하는 interior-point 알고리즘은 효율적입니다. 함수 실행 횟수를 확인합니다.

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

fmincon은 이 문제를 푸는 데 함수를 10회만 실행합니다.

이 결과를 헤세 행렬을 사용하지 않는 경우의 풀이와 비교해 보겠습니다.

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

이 경우, fmincon이 반복 횟수와 함수 실행 횟수가 2배 정도 많습니다. 해는 동일하게 허용오차 내에 있습니다.

2차 등식 제약 조건으로 확장

2차 등식 제약 조건도 있는 경우 기본적으로 동일한 기법을 사용할 수 있습니다. 문제는 동일하되, 다음 추가 제약 조건을 가집니다.

$\frac{1}{2} x^{T} J_{i} x + p_{i}^{T} x + q_{i} = 0.$

J_i, p_i, q_i 변수를 사용하도록 제약 조건을 다시 정식화하십시오. lambda.eqnonlin(i) 구조체는 등식 제약 조건에 대한 라그랑주 승수를 포함합니다.