Main Content

이 페이지의 최신 내용은 아직 번역되지 않았습니다. 최신 내용은 영문으로 볼 수 있습니다.

2차 계획법 알고리즘

2차 계획법 정의

2차 계획법은 다음과 같이 2차 함수를 최소화하는 벡터 x를 구하는 문제이며, 선형 제약 조건이 적용될 수 있습니다.

minx12xTHx+cTx(1)

적용되는 조건은 A·x ≤ b, Aeq·x = beq, l ≤ x ≤ u입니다.

quadproginterior-point-convex 알고리즘

interior-point-convex 알고리즘은 다음 단계를 수행합니다.

참고

이 알고리즘에는 두 개의 코드 경로가 있습니다. 하나는 헤세 행렬 H가 double형으로 구성된 일반(비희소) 행렬인 경우 실행하고, 다른 하나는 H가 희소 행렬인 경우 실행합니다. 희소 데이터형에 대한 자세한 내용은 희소 행렬 항목을 참조하십시오. 일반적으로, 이 알고리즘은 H를 sparse로 지정하는 경우 0이 아닌 항이 상대적으로 적은 큰 문제에서 더 빠릅니다. 이와 유사하게, 이 알고리즘은 H를 full로 지정하는 경우 상대적으로 조밀한 문제 또는 작은 문제에서 더 빠릅니다.

풀이 전처리/풀이 후처리

이 알고리즘은 먼저 중복 항목을 제거하고 제약 조건을 단순화함으로써 문제를 단순화하려고 합니다. 풀이 전처리 단계 중 수행되는 작업에는 다음이 포함될 수 있습니다.

  • 상한과 하한이 동일한 변수가 있는지 확인합니다. 그럴 경우, 실현가능성을 검사한 후 변수를 수정하고 제거합니다.

  • 하나의 변수만 포함하는 선형 부등식 제약 조건이 있는지 확인합니다. 그럴 경우, 실현가능성을 검사한 다음 선형 제약 조건을 범위로 변경합니다.

  • 하나의 변수만 포함하는 선형 등식 제약 조건이 있는지 확인합니다. 그럴 경우, 실현가능성을 검사한 후 변수를 수정하고 제거합니다.

  • 0으로 이루어진 행을 갖는 선형 제약 조건 행렬이 있는지 확인합니다. 그럴 경우, 실현가능성을 검사한 다음 행을 삭제합니다.

  • 범위와 선형 제약 조건이 일치하는지 확인합니다.

  • 목적 함수의 일차항으로만 표시되고 선형 제약 조건에는 표시되지 않는 변수가 있는지 확인합니다. 그럴 경우, 실현가능성과 유계성(Boundedness)을 검사한 다음 적합한 범위에서 변수를 수정합니다.

  • 여유 변수를 추가하여 선형 부등식 제약 조건을 선형 등식 제약 조건으로 변경합니다.

알고리즘이 실현불가능 문제 또는 비유계 문제를 감지하면 실행이 중단되고 적절한 종료 메시지를 표시합니다.

알고리즘은 해를 나타내는 하나의 실현가능점에 도달할 수 있습니다.

알고리즘이 풀이 전처리 단계에서 실현불가능 문제 또는 비유계 문제를 감지하지 않고 풀이 전처리에서 해를 생성하지 않는 경우 알고리즘은 다음 단계로 계속 진행합니다. 중지 기준에 도달하면 알고리즘은 풀이 전처리에서의 변환을 실행 취소하여 원래 문제를 다시 생성합니다. 이 최종 단계를 풀이 후처리 단계라고 합니다.

자세한 내용은 굴드(Gould)와 토인트(Toint)의 문헌 [63]을 참조하십시오.

초기점 생성하기

이 알고리즘의 초기점 x0은 다음과 같이 생성합니다.

  1. x0ones(n,1)로 초기화합니다. 여기서 n은 H의 행 개수입니다.

  2. 상한 ub와 하한 lb를 모두 갖는 성분에 대해 x0의 성분이 엄밀하게 하한 안쪽에 있지 않은 경우 성분을 (ub + lb)/2로 설정합니다.

  3. 한쪽 경계만 있는 성분의 경우, 명확하게 그 경계 내에 놓이도록 성분을 수정합니다(필요한 경우).

  4. 비희소 예측자-수정자 스텝이 아니라 실현가능성을 위해 약간 수정한 예측자 스텝(예측자-수정자 참조)을 실행합니다. 그러면 비희소 예측자-수정자 스텝의 오버헤드를 수반할 필요 없이 초기점이 중앙 경로에 더 가깝게 이동됩니다. 중앙 경로에 대한 자세한 내용은 노세달(Nocedal)과 라이트(Wright)의 문헌 [7], 397페이지를 참조하십시오.

예측자-수정자

희소 interior-point-convex 알고리즘과 비희소 interior-point-convex 알고리즘은 주로 예측자-수정자 단계에서 차이가 납니다. 이들 알고리즘은 서로 비슷하지만 몇몇 세부적인 측면에서는 서로 다릅니다. 기본적인 알고리즘 설명은 메로트라(Mehrotra)의 문헌 [47]을 참조하십시오.

이들 알고리즘은 선형 부등식 Ax <= b를 Ax >= b 형식의 부등식으로 변환(이를 위해 A와 b에 -1을 곱함)하는 것으로 시작됩니다. 이는 해와 관계가 없지만, 일부 참고 문헌에서 찾을 수 있는 것과 동일한 형식의 문제를 만드는 데 도움이 됩니다.

희소 예측자-수정자.  fminconinterior-point 알고리즘과 유사하게 희소 interior-point-convex 알고리즘은 카루쉬-쿤-터커(KKT) 조건이 성립하는 점을 구하려고 합니다. 2차 계획법 정의에서 설명한 2차 계획법 문제의 경우 다음 조건이 적용됩니다.

Hx+cAeqTyA¯Tz=0A¯xb¯s=0Aeqxbeq=0sizi=0, i=1,2,...,ms0z0.

여기서

  • A¯는 선형 부등식으로 작성된 범위를 포함하는 확장된 선형 부등식 행렬입니다. b¯는 범위를 포함하는 대응하는 선형 부등식 벡터입니다.

  • s는 부등식 제약 조건을 등식 제약 조건으로 변환하는 여유 변수로 구성된 벡터입니다. s는 길이가 m이고, 이는 선형 부등식과 범위의 개수를 나타냅니다.

  • z는 s에 대응하는 라그랑주 승수로 구성된 벡터입니다.

  • y는 등식 제약 조건과 연결된 라그랑주 승수로 구성된 벡터입니다.

이 알고리즘은 먼저 뉴턴-랩슨(Newton-Raphson) 식에서 스텝을 예측한 후 수정자 스텝을 계산합니다. 수정자는 비선형 제약 조건 sizi = 0을 더 효율적으로 적용하도록 시도합니다.

예측자 스텝의 정의:

  • rd(쌍대 문제 잔차):

    rd=Hx+cAeqTyA¯Tz.

  • req(원문제 등식 제약 조건 잔차):

    req=Aeqxbeq.

  • rineq(범위와 여유 변수를 포함하는 원문제 부등식 제약 조건 잔차):

    rineq=A¯xb¯s.

  • rsz(상보성 잔차):

    rsz = Sz.

    S는 여유 변수 항으로 구성된 대각 행렬이고, z는 라그랑주 승수로 구성된 열 행렬입니다.

  • rc(평균 상보성):

    rc=sTzm.

뉴턴 스텝에서 x, s, y, z의 변화량은 다음으로 지정됩니다.

(H0AeqTA¯TAeq000A¯I000Z0S)(ΔxΔsΔyΔz)=(rdreqrineqrsz).(2)

하지만, 비희소 뉴턴 스텝은 실현 가능하지 않을 수 있습니다 그 이유는 s와 z에 대한 양부호 제약 조건 때문입니다. 따라서, quadprog는 양부호를 유지하기 위해 필요한 경우 스텝을 단축합니다.

또한 내부에서 “중심화된” 위치를 유지하기 위해, 이 알고리즘은 sizi = 0을 풀려고 시도하는 대신 양수 파라미터 σ를 사용하여 다음을 풀려고 시도합니다.

sizi = σrc.

quadprog는 뉴턴 스텝 방정식에서 rszrsz + ΔsΔz – σrc1로 바꿉니다. 여기서 1은 1로 구성된 벡터입니다. 또한, quadprog는 예측자 스텝 계산을 위한 수치적으로 더욱 안정적인 대칭 시스템을 얻기 위해 뉴턴 방정식을 재정렬합니다.

수정된 뉴턴 스텝을 계산한 후, 이 알고리즘은 더 긴 현재 스텝을 구하고 더 나은 후속 스텝을 준비하기 위해 더 많은 계산을 수행합니다. 이러한 여러 수정 계산은 성능과 견고성을 모두 향상시킬 수 있습니다. 자세한 내용은 곤지오(Gondzio)의 문헌 [4]을 참조하십시오.

비희소 예측자-수정자.  비희소(Full) 예측자-수정자 알고리즘은 범위를 선형 제약 조건에 결합하지 않으므로 범위에 대응하는 또 다른 여유 변수 집합을 가집니다. 이 알고리즘은 하한을 0으로 이동시킵니다. 그리고, 변수에 대한 경계가 하나만 있을 경우 상한의 부등식의 부호를 변환하여 이 경계를 하한 0이 되도록 변환합니다.

A¯는 선형 부등식과 선형 등식 모두를 포함하는 확장된 선형 행렬입니다. b¯는 대응하는 선형 등식 벡터입니다. A¯는 부등식 제약 조건을 등식 제약 조건으로 변환하는 여유 변수 s로 벡터 x를 확장하는 항도 포함합니다.

A¯x=(Aeq0AI)(x0s),

여기서 x0은 원래의 x 벡터를 의미합니다.

KKT 조건은 다음과 같습니다.

Hx+cA¯Tyv+w=0A¯x=b¯x+t=uvixi=0, i=1,2,...,mwiti=0, i=1,2,...,nx,v,w,t0.(3)

수식 3의 해 x, 여유 변수 및 쌍대 변수(Dual Variable)를 구하기 위해 이 알고리즘은 기본적으로 뉴턴-랩슨(Newton-Raphson) 스텝을 고려합니다.

(HA¯T0IIA¯0000I0I00V00X000W0T)(ΔxΔyΔtΔvΔw)=(Hx+cA¯Tyv+wA¯xb¯uxtVXWT)=(rdrprubrvxrwt),(4)

여기서 X, V, W, T는 각각 벡터 x, v, w, t에 대응하는 대각 행렬입니다. 방정식의 가장 오른쪽 변에 있는 잔차 벡터는 다음과 같습니다.

  • rd - 쌍대 문제(Dual) 잔차

  • rp - 원문제(Primal) 잔차

  • rub - 상한 잔차

  • rvx - 하한 상보성 잔차

  • rwt - 상한 상보성 잔차

이 알고리즘은 수식 4을 먼저 다음과 같은 대칭 행렬 형식으로 변환하여 풉니다.

(DA¯TA¯0)(ΔxΔy)=(Rrp),(5)

여기서는 다음이 성립합니다.

D=H+X1V+T1WR=rdX1rvx+T1rwt+T1Wrub.

D와 R의 정의에서 모든 역행렬은 대각 행렬이기 때문에 계산하기가 간단합니다.

수식 4에서 수식 5를 도출하기 위해서는 수식 5의 두 번째 행이 수식 4의 두 번째 행렬 행과 같다는 것을 알고 있어야 합니다. 수식 5의 첫 번째 행은 Δv와 Δw를 구하기 위해 수식 4의 마지막 두 행을 푼 후 Δt를 구하는 과정에서 도출됩니다.

수식 5를 풀기 위해 이 알고리즘은 올트먼(Altman)과 곤지오(Gondzio)[1]의 기본 요소를 따릅니다. 이 알고리즘은 LDL 분해를 사용하여 대칭 시스템을 풉니다. 밴더베이(Vanderbei)와 카펜터(Carpenter)[2] 등의 저자가 지적한 대로 이 분해는 어떠한 피벗 연산도 수행하지 않고 수치적으로 안정적이므로 속도가 빠를 수 있습니다.

수정된 뉴턴 스텝을 계산한 후, 이 알고리즘은 더 긴 현재 스텝을 구하고 더 나은 후속 스텝을 준비하기 위해 더 많은 계산을 수행합니다. 이러한 여러 수정 계산은 성능과 견고성을 모두 향상시킬 수 있습니다. 자세한 내용은 곤지오(Gondzio)의 문헌 [4]을 참조하십시오.

비희소 quadprog 예측자-수정자 알고리즘은 linprog'interior-point' 알고리즘과 대체로 같으며, 2차 항도 포함한다는 점만 다릅니다. 예측자-수정자 항목을 참조하십시오.

참고 문헌

[1] Altman, Anna and J. Gondzio. Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization. Optimization Methods and Software, 1999. Available for download here.

[2] Vanderbei, R. J. and T. J. Carpenter. Symmetric indefinite systems for interior point methods. Mathematical Programming 58, 1993. pp. 1–32. Available for download here.

중지 조건

예측자-수정자 알고리즘은 실현가능점(허용오차 내에서 제약 조건을 충족함)에 도달할 때까지 반복하며, 여기서 반복 스텝의 상대적 크기는 작습니다. 구체적으로, 다음과 같이 정의합니다.

ρ=max(1,H,A¯,Aeq,c,b¯,beq)

알고리즘은 다음 조건이 모두 충족되는 경우 중지됩니다.

rp1+rub1ρTolConrdρTolFunrcTolFun,

여기서는 다음이 성립합니다.

rc=maxi(min(|xivi|,|xi|,|vi|),min(|tiwi|,|ti|,|wi|)).

rc는 기본적으로 해에서 각각 0으로 구성된 벡터인 상보성 잔차 xv와 tw의 크기를 측정합니다.

실현불가능성 감지

quadprog는 매 반복마다 이득 함수 φ를 계산합니다. 이득 함수는 실현가능성에 대한 측정값입니다. 이득 함수가 너무 커지면 quadprog가 중지됩니다. 이 경우, quadprog는 문제를 실현 가능하지 않다고 선언합니다.

이득 함수는 문제에 대한 KKT 조건과 관련이 있습니다. 예측자-수정자 항목을 참조하십시오. 다음 정의를 사용합니다.

ρ=max(1,H,A¯,Aeq,c,b¯,beq)req=Aeqxbeqrineq=A¯xb¯srd=Hx+c+AeqTλeq+A¯Tλ¯ineqg=12xTHx+cTxb¯Tλ¯ineqbeqTλeq.

표기법 A¯b¯는 희소 알고리즘의 범위를 나타내는 항으로 확장된 선형 부등식 계수를 의미합니다. 이와 유사하게 표기법 λ¯ineq는 범위 제약 조건을 포함해 선형 부등식 제약 조건의 라그랑주 승수를 나타냅니다. 예측자-수정자에서는 이를 z라고 했으며, λeq는 y라고 했습니다.

이득 함수 φ는 다음과 같습니다.

1ρ(max(req,rineq,rd)+g).

이 이득 함수가 너무 커지면 quadprog는 문제를 실현 가능하지 않은 것으로 선언하고 종료 플래그 -2를 발생시키고 중단합니다.

quadprogtrust-region-reflective 알고리즘

Optimization Toolbox™ 솔버에 사용되는 대부분의 방법이 최적화의 단순하지만 강력한 개념인 신뢰 영역을 기반으로 합니다.

최적화에 대한 trust-region 접근법을 이해하기 위해 제약 조건이 없는 최소화 문제를 살펴보고, f(x)를 최소화해 보겠습니다. 여기서 함수는 벡터 인수를 받고 스칼라를 반환합니다. n 공간에서 점 x에 있고 향상, 즉 더 낮은 함수 값을 가지는 점으로 이동하기를 원한다고 가정해 보겠습니다. 기본적인 발상은 점 x 주위에 있는 이웃 N에서 함수 f의 동작을 잘 반영하는 더 간단한 함수 q를 사용하여 f를 근사하는 것입니다. 이 이웃을 신뢰 영역이라고 합니다. 시행 스텝 s는 N에 대한 최소화(또는 근사 최소화)를 수행하여 계산됩니다. 이를 trust-region 하위 문제라고 하며, 다음과 같습니다.

mins{q(s), sN}.(6)

현재 점은 f(x + s) < f(x)인 경우 x + s가 되도록 업데이트됩니다. 그렇지 않은 경우 현재 점은 변경되지 않고 그대로 유지되며 신뢰 영역 N은 축소되고 시행 스텝 계산이 반복됩니다.

f(x)를 최소화하기 위한 특정 trust-region 접근법을 정의할 때 고려해야 할 핵심 질문은 근삿값 q(현재 점 x에서 정의됨)를 선택하고 계산하는 방법은 무엇인가, 신뢰 영역 N을 선택하고 수정하는 방법은 무엇인가, 그리고 trust-region 하위 문제를 얼마나 정확하게 풀 수 있는가입니다. 이 섹션에서는 제약 조건이 없는 문제를 집중적으로 설명합니다. 뒷부분에 나오는 섹션에서는 변수에 대한 제약 조건이 존재함으로 인해 복잡성이 얼마나 가중되는지에 대해 설명합니다.

표준 trust-region 방법([48])에서는 2차 근삿값 q가 x에서 F에 대한 테일러 근사의 처음 두 항으로 정의되며, 이웃 N은 일반적으로 구면 또는 타원 형태입니다. 수학적으로 trust-region 하위 문제는 대개 다음과 같이 표기됩니다.

min{12sTHs+sTg  such that  DsΔ},(7)

여기서 g는 현재 점 x에서 f의 기울기이고, H는 헤세 행렬(2계 도함수의 대칭 행렬)이고, D는 대각 스케일링 행렬이고, Δ는 양의 스칼라이며, ∥ . ∥는 2-노름입니다. 수식 7을 푸는 데 사용할 수 있는 좋은 알고리즘이 있습니다([48] 참조). 이러한 알고리즘은 일반적으로 다음과 같은 고유방정식에 적용되는 뉴턴 과정 및 H의 모든 고유값에 대한 계산을 포함합니다.

1Δ1s=0.

이러한 알고리즘은 수식 7에 대한 정확한 해를 제공합니다. 하지만, 이 알고리즘을 사용하려면 H에 대한 여러 행렬 분해에 비례하는 시간이 필요합니다. 따라서, 대규모 문제에는 다른 접근법이 필요합니다. 수식 7 기반한 여러 근사법과 발견법 전략이 참고 문헌([42][50])에서 제안되었습니다. Optimization Toolbox 솔버에서 따르는 근사 접근법은 trust-region 하위 문제를 2차원 부분공간 S([39][42])로 제한하는 것입니다. 부분공간 S가 계산되고 나면 수식 7을 푸는 방법은 간단합니다. 비희소 고유값/고유벡터 정보가 필요한 경우에도 마찬가지입니다. 그 이유는 부분공간에서는 문제가 2차원뿐이기 때문입니다. 이제 수행해야 하는 주된 작업은 부분공간을 결정하는 것입니다.

2차원 부분공간 S는 아래에 설명되어 있는 선조건 적용 켤레 기울기법 과정을 통해 결정됩니다. 솔버는 S를 s1 및 s2에 의해 생성되는 선형 공간으로 정의합니다. 여기서 s1은 기울기 g의 방향이고 s2는 근사 뉴턴 방향, 즉 다음 수식에 대한 해를 말합니다.

Hs2=g,(8)

또는 다음과 같은 음의 곡률의 방향입니다.

s2THs2<0.(9)

이러한 S 선택의 바탕이 되는 철학은 (최속강하법 방향 또는 음의 곡률 방향을 통해) 전역 수렴을 강제 적용하고 (존재하는 경우 뉴턴 스텝을 통해) 신속하게 국소 수렴을 달성한다는 것입니다.

trust-region 알고리즘을 사용한 제약 조건이 없는 최소화 과정은 이제 다음과 같이 간단하게 요약할 수 있습니다.

  1. 2차원 trust-region 하위 문제를 정식화합니다.

  2. 수식 7을 풀어서 시행 스텝 s를 결정합니다.

  3. f(x + s) < f(x)이면 x = x + s입니다.

  4. Δ를 조정합니다.

이 네 단계는 수렴할 때까지 반복됩니다. trust-region 차원 Δ는 표준 규칙에 따라 조정됩니다. 특히, 시행 스텝이 받아들여지지 않은 경우, 즉 f(x + s) ≥ f(x)인 경우에는 trust-region 차원이 축소됩니다. 이 사항에 대한 자세한 내용은 [46] 항목과 [49] 항목을 참조하십시오.

Optimization Toolbox 솔버는 비선형 최소제곱, 2차 함수, 선형 최소제곱 등의 특화된 함수를 사용하여 f에 대한 몇 가지 중요한 특수 사례를 처리합니다. 하지만, 기반이 되는 알고리즘적 발상은 일반적인 사례와 동일합니다. 이러한 특수 사례에 대해서는 뒷부분에 나오는 섹션에서 설명합니다.

부분공간 trust-region 방법은 탐색 방향을 결정하는 데 사용됩니다. 하지만, 비선형 최소화 사례에서처럼 스텝을 (가능한) 하나의 반사 스텝으로 제한하는 대신 각 반복마다 조각별 반사 직선 탐색이 수행됩니다. 직선 탐색에 대한 자세한 내용은 [45] 항목을 참조하십시오.

선조건 적용 켤레 기울기법(Preconditioned Conjugate Gradient Method)

선조건 적용 켤레 기울기법(PCG)은 대규모 양의 정부호 대칭 선형 연립방정식 Hp = –g를 푸는 데 자주 사용되는 방법입니다. 이 반복적인 접근법을 사용하려면 H·v 형식의 행렬-벡터 곱을 계산할 수 있어야 합니다. 여기서 v는 임의 벡터입니다. 양의 정부호 대칭 행렬 M 은 H에 대한 선조건자입니다. 즉, M = C2입니다. 여기서 C–1HC–1은 조건이 좋은 행렬이거나 서로 다른 고유값이 모여 있는 행렬입니다.

최소화의 맥락에서는 헤세 행렬 H가 대칭 행렬이라고 간주할 수 있습니다. 하지만, H는 강력한 최소점의 이웃인 경우에만 양의 정부호 행렬 여부가 보장됩니다. 알고리즘 PCG는 음의 곡률(또는 영곡률) 방향이 발생한 경우, 즉 dTHd ≤ 0인 경우에 종료됩니다. PCG 출력값 방향 p는 음의 곡률의 방향이거나 뉴턴 시스템 Hp = –g에 대한 근사해입니다. 어느 경우이든 p는 비선형 최소화를 위한 Trust-Region 방법에 설명된 trust-region 접근법에 사용되는 2차원 부분공간을 정의하는 데 도움이 됩니다.

선형 등식 제약 조건

선형 제약 조건이 있으면 제약 조건이 없는 최소화보다 상황이 복잡해집니다. 그러나, 앞에서 설명한 기본 아이디어를 깔끔하고 효율적인 방식으로 수행할 수 있습니다. Optimization Toolbox 솔버의 trust-region 방법은 엄밀하게 실현 가능한 반복을 생성합니다.

일반적인 선형 등식 제약 조건이 있는 최소화 문제는 다음과 같이 작성할 수 있습니다.

min{f(x)  such that  Ax=b},(10)

여기서 A는 mxn 행렬(m ≤ n)입니다. 일부 Optimization Toolbox 솔버는 AT [46]의 LU 분해를 기반으로 하는 기법을 사용하여 A를 전처리함으로써 엄밀한 선형 종속성을 제거합니다. 여기서, A의 랭크가 m이 된다고 가정합니다.

수식 10를 풀 때 사용하는 방법은 두 가지 중요한 측면에서 제약 조건이 없는 접근법과 다릅니다. 먼저, 희소 최소제곱 스텝을 사용하여 Ax0 = b가 되도록 초기 실현가능점 x0이 계산됩니다. 둘째로, 감소된 근사 뉴턴 스텝(또는 A의 영공간에서 음의 곡률의 방향)을 계산하기 위해 알고리즘 PCG가 감소된 선조건 적용 켤레 기울기(RPCG)([46] 참조)로 대체됩니다. 주요 선형 대수 스텝에는 다음 형식의 시스템을 푸는 과정이 포함됩니다.

[CA˜TA˜0][st]=[r0],(11)

여기서 A˜는 A를 근사하고(랭크가 손실되지 않는 경우 A의 몇 안 되는 0이 아닌 요소는 0으로 설정됨) C는 H에 대한 양의 정부호 희소 대칭 근사입니다(즉, C = H). 자세한 내용은 [46] 항목을 참조하십시오.

상자 제약 조건

상자 제약 조건이 있는 문제의 형식은 다음과 같습니다.

min{f(x)  such that  lxu},(12)

여기서 l은 하한으로 구성된 벡터이고, u는 상한으로 구성된 벡터입니다. l의 일부(또는 전체) 성분은 –∞와 같을 수 있으며 u의 일부(또는 전체) 성분은 ∞와 같을 수 있습니다. 이 방법은 일련의 엄밀한 실현가능점을 생성합니다. 견고한 수렴을 달성하는 동시에 실현가능성을 유지하기 위해 두 기법이 사용됩니다. 먼저, 스케일링되고 수정된 뉴턴 스텝이 제약 조건이 없는 뉴턴 스텝을 대체합니다(2차원 부분공간 S를 정의하기 위해). 둘째로, 스텝 크기를 늘리기 위해 반사가 사용됩니다.

스케일링되고 수정된 뉴턴 스텝은 다음과 같은 수식 12에 대한 쿤-터커(Kuhn-Tucker) 필요 조건을 검토하는 과정에서 발생합니다.

(D(x))2g=0,(13)

여기서는 다음이 성립합니다.

D(x)=diag(|vk|1/2),

벡터 v(x)는 1 ≤ i ≤ n에 대해 아래와 같이 정의됩니다.

  • gi < 0이고 ui < ∞이면 vi = xi – ui가 됩니다.

  • gi ≥ 0이고 li > –∞이면 vi = xi – li가 됩니다.

  • gi < 0이고 ui = ∞이면 vi = –1이 됩니다.

  • gi ≥ 0이고 li = –∞이면 vi = 1이 됩니다.

비선형 시스템 수식 13가 모든 경우에 미분 가능한 것은 아닙니다. vi = 0인 경우 미분 불가능 점이 발생합니다. 엄밀한 실현가능성을 유지하여, 즉 l < x < u으로 제한을 두어 이러한 점을 방지할 수 있습니다.

수식 13로 주어진 비선형 연립방정식에 대해 스케일링되고 수정된 뉴턴 스텝 sk는 다음 선형 시스템의 해로 정의됩니다.

M^DsN=g^(14)

아래 두 식이 성립하는 k번째 반복에서의 해로 정의되는 것입니다.

g^=D1g=diag(|v|1/2)g,(15)

그리고,

M^=D1HD1+diag(g)Jv.(16)

여기서 Jv는 |v|의 야코비 행렬 역할을 합니다. 대각 행렬 Jv의 각 대각 성분은 0, –1 또는 1입니다. l과 u의 모든 성분이 유한하면 Jv = diag(sign(g))입니다. gi = 0을 충족하는 점에서 vi는 미분 가능하지 않을 수 있습니다. 이러한 점에서는 Jiiv=0이 정의됩니다. 이러한 성분에 대해 vi가 받는 값이 무엇인지는 중요하지 않기 때문에 이 유형의 미분 불가능성이 문제의 원인이 되지는 않습니다. 이와 더불어, |vi|는 이 점에서 여전히 불연속이지만, 함수 |vi|·gi는 연속입니다.

둘째로, 스텝 크기를 늘리기 위해 반사가 사용됩니다. (단일) 반사 스텝은 다음과 같이 정의됩니다. 범위 제약 조건을 교차하는 스텝 p가 주어진 경우, p가 교차하는 첫 번째 범위 제약 조건을 살펴보고, 이것이 i번째 범위 제약 조건(i번째 상한 또는 i번째 하한)이라고 가정하겠습니다. 그러면 반사 스텝에 대해 pR = p가 성립합니다. 단, i번째 성분은 예외입니다(이 경우 pRi = –pi).

quadprogactive-set 알고리즘

active-set 알고리즘은 풀이 전처리 단계를 완료한 후 두 단계를 진행합니다.

  • 단계 1 — 모든 제약 조건에 대해 실현가능점을 얻습니다.

  • 단계 2 — 활성 제약 조건의 목록과 각 반복 시의 실현가능성을 유지하면서 반복적으로 목적 함수를 낮춥니다.

active-set 전략(투영법이라고도 함)은 길(Gill) 등이 작성한 문헌 [18][17]에 설명되어 있는 전략과 유사합니다.

풀이 전처리 단계

이 알고리즘은 먼저 중복 항목을 제거하고 제약 조건을 단순화함으로써 문제를 단순화하려고 합니다. 풀이 전처리 단계 중 수행되는 작업에는 다음이 포함될 수 있습니다.

  • 상한과 하한이 동일한 변수가 있는지 확인합니다. 그럴 경우, 실현가능성을 검사한 후 변수를 수정하고 제거합니다.

  • 하나의 변수만 포함하는 선형 부등식 제약 조건이 있는지 확인합니다. 그럴 경우, 실현가능성을 검사한 다음 선형 제약 조건을 범위로 변경합니다.

  • 하나의 변수만 포함하는 선형 등식 제약 조건이 있는지 확인합니다. 그럴 경우, 실현가능성을 검사한 후 변수를 수정하고 제거합니다.

  • 0으로 이루어진 행을 갖는 선형 제약 조건 행렬이 있는지 확인합니다. 그럴 경우, 실현가능성을 검사한 다음 행을 삭제합니다.

  • 범위와 선형 제약 조건이 일치하는지 확인합니다.

  • 목적 함수의 일차항으로만 표시되고 선형 제약 조건에는 표시되지 않는 변수가 있는지 확인합니다. 그럴 경우, 실현가능성과 유계성(Boundedness)을 검사한 다음 적합한 범위에서 변수를 수정합니다.

  • 여유 변수를 추가하여 선형 부등식 제약 조건을 선형 등식 제약 조건으로 변경합니다.

알고리즘이 실현불가능 문제 또는 비유계 문제를 감지하면 실행이 중단되고 적절한 종료 메시지를 표시합니다.

알고리즘은 해를 나타내는 하나의 실현가능점에 도달할 수 있습니다.

알고리즘이 풀이 전처리 단계에서 실현불가능 문제 또는 비유계 문제를 감지하지 않고 풀이 전처리에서 해를 생성하지 않는 경우 알고리즘은 다음 단계로 계속 진행합니다. 중지 기준에 도달하면 알고리즘은 풀이 전처리에서의 변환을 실행 취소하여 원래 문제를 다시 생성합니다. 이 최종 단계를 풀이 후처리 단계라고 합니다.

자세한 내용은 굴드(Gould)와 토인트(Toint)의 문헌 [63]을 참조하십시오.

단계 1 알고리즘

단계 1에서 알고리즘은 목적 함수를 전혀 고려하지 않고 모든 제약 조건을 충족하는 점 x를 구하려고 시도합니다. quadprog는 제공된 초기점 x0이 실현 가능하지 않을 경우에만 단계 1 알고리즘을 실행합니다.

먼저 알고리즘은 X = Aeq\beq 같은 모든 등식 제약 조건에 대해 실현 가능한 점을 구하려고 시도합니다. 등식 Aeq*x = beq의 해 x가 없으면 알고리즘이 중단됩니다. 해 X가 있는 경우 그다음 단계는 범위와 선형 부등식을 충족하는 것입니다. 등식 제약 조건이 없는 경우에는 초기점 X = x0을 설정하십시오.

알고리즘은 X에서 시작하여 M = max(A*X – b, X - ub, lb – X)를 계산합니다. M <= options.ConstraintTolerance이면 점 X는 실현 가능하며 단계 1 알고리즘이 중단됩니다.

M > options.ConstraintTolerance이면 알고리즘은 보조 선형 계획법 문제에 대해 음이 아닌 여유 변수 γ를 추가합니다.

minx,γγ

적용되는 조건은 다음과 같습니다.

AxγbAeqx=beqlbγxub+γγρ.

여기서 ρ는 AAeq에 있는 가장 큰 요소의 절댓값을 곱한 ConstraintTolerance 옵션입니다. 알고리즘이 γ = 0과 방정식 및 부등식을 충족하는 점 x를 구하면 x가 단계 1의 실현가능점입니다. γ = 0에서 보조 선형 계획법 문제 x의 해가 없는 경우 단계 1 문제는 실현 가능하지 않습니다.

보조 선형 계획법 문제를 풀기 위해 알고리즘은 γ0 = M + 1을 설정하고, x0 = X를 설정하며, 활성 세트를 고정 변수(있는 경우)와 모든 등식 제약 조건으로 초기화합니다. 알고리즘은 선형 계획법 변수 p가 현재 점 x0에서 x 의 오프셋이 되도록 다시 정식화합니다(즉, x = x0 + p). 그리고 적절히 수정된 헤세 행렬을 사용하여, 단계 2에서 2차 계획법 문제를 풀기 위해 수행하는 동일한 반복으로 선형 계획법 문제를 풉니다.

단계 2 알고리즘

변수 d의 관점에서 문제는 다음과 같습니다.

mindnq(d)=12dTHd+cTd,Aid=bi,  i=1,...,meAidbi,  i=me+1,...,m.(17)

여기서 Ai는 mxn 행렬 A의 i번째 행에 해당합니다.

단계 2에서 활성 세트 A¯k는 해에 해당하는 점의 활성 제약 조건(제약 조건 경계에 있는 제약 조건)의 추정값입니다.

알고리즘은 k번째 반복마다 A¯k를 업데이트하여 탐색 방향 dk에 대한 기반을 구성합니다. 등식 제약 조건은 항상 활성 세트 A¯k에 유지됩니다. 탐색 방향 dk가 계산되고 활성 제약 조건 경계에 남아 있으면서 목적 함수를 최소화합니다. 알고리즘은 열이 활성 세트 A¯k의 추정값에 직교 상태(즉, A¯kZk=0)인 기저 Zk에서 dk의 실현 가능한 부분 공간을 구성합니다. 따라서 Zk의 열에 대한 임의 조합의 선형 합으로부터 구성되는 탐색 방향은 활성 제약 조건의 경계에 유지되도록 보장됩니다.

알고리즘은 행렬 A¯kT에 대한 QR 분해의 마지막 m – l개 열로부터 행렬 Zk를 구성합니다. 여기서 l은 활성 제약 조건의 개수이고 l < m입니다. 즉, Zk는 다음과 같이 지정됩니다.

Zk=Q[:,l+1:m],(18)

여기서는 다음을 조건으로 합니다.

QTA¯kT=[R0].

알고리즘은 Zk를 발견하고 나면 q(d)를 최소화하는 새로운 탐색 방향 dk를 찾습니다. 여기서 dk는 활성 제약 조건의 영공간에 있습니다. 즉, dk는 Zk의 열의 일차 결합입니다(어떤 벡터 p에 대해 d^k=Zkp).

dk 대신, p에 대한 함수로 2차 함수를 표시하면 다음이 생성됩니다.

q(p)=12pTZkTHZkp+cTZkp.(19)

이 방정식을 p에 대해 미분하면 다음이 생성됩니다.

q(p)=ZkTHZkp+ZkTc.(20)

∇q(p)는 Zk로 정의된 부분 공간에서 투영된 기울기이므로 2차 함수의 투영된 기울기라고 합니다. 항 ZkTHZk는 투영된 헤세 행렬이라고 합니다. 투영된 헤세 행렬 ZkTHZk가 양의 준정부호라고 가정하면 ∇q(p) = 0을 충족하는 경우 Zk로 정의된 부분 공간에서 함수 q(p)의 최솟값이 나타납니다. 이것이 선형 연립방정식의 해입니다.

ZkTHZkp=ZkTc.(21)

그런 다음 알고리즘은 다음 형식의 스텝을 취합니다.

xk+1=xk+αdk,

여기서는 다음을 조건으로 합니다.

dk=Zkp.

목적 함수의 2차식 특성으로 인해 각 반복마다 스텝 길이 α에는 두 개의 선택 사항만 있습니다. dk를 따라 변화하는 단위 스텝은 A¯k의 영공간으로 제한되는 함수의 최솟값으로 이르는 정확한 스텝입니다. 알고리즘이 제약 조건 위반 없이 이러한 스텝을 수행할 수 있으면 이 스텝이 2차 계획법의 해가 됩니다(수식 18). 그렇지 않은 경우, 최근접 제약 조건에 도달하기 위해 dk를 따라 변화하는 스텝은 단위보다 작으며 알고리즘은 새 제약 조건을 다음 반복에서 활성 세트에 포함합니다. 임의의 방향 dk에서 제약 조건 경계까지의 거리는 다음과 같이 지정됩니다.

α=mini{1,...,m}{(Aixkbi)Aidk},

이는 활성 세트에 포함되지 않은 제약 조건에 대해 정의된 것이며, 여기서 방향 dk는 제약 조건 경계를 향합니다(즉, Aidk>0, i=1,...,m).

최솟값을 갖는 위치 없이 n개의 독립 제약 조건이 활성 세트에 포함되어 있는 경우, 알고리즘은 라그랑주 승수 λk가 다음과 같은 선형 방정식으로 구성된 정칙 행렬 세트를 충족하도록 계산합니다.

A¯kTλk=c+Hxk.(22)

λk의 모든 요소가 양수이면 xk가 2차 계획법 문제(수식 1)의 최적 해입니다. 하지만 λk의 성분 중 하나라도 음수이고 이 성분이 등식 제약 조건에 부합되지 않는 경우 최소화가 완료되지 않습니다. 알고리즘은 대부분의 음의 승수에 대응하는 요소를 삭제하고 새 반복을 시작합니다.

때때로 솔버가 음이 아닌 모든 라그랑주 승수로 동작을 마치면, 1차 최적성 측정값이 허용오차를 초과하거나 제약 조건 허용오차가 충족되지 않는 것입니다. 이러한 경우 솔버는 [1]에 설명된 다시 시작 절차에 따라 더 나은 해를 구하려고 시도합니다. 그 절차에 따라 솔버는 현재 활성 제약 조건 세트를 삭제하고 제약 조건을 약간 완화하고 새로운 활성 제약 조건 세트를 생성하면서, 순환(반복적으로 동일한 상태로 돌아감)을 피하는 방식으로 문제를 풀려고 시도합니다. 필요에 따라 솔버는 다시 시작 절차를 여러 번 수행할 수 있습니다.

참고

ConstraintTolerance 옵션 및 OptimalityTolerance 옵션에 큰 값을 설정하여 알고리즘을 조기에 중지하려고 하지 마십시오. 일반적으로 솔버는 잠재적 중지점에 도달할 때까지 이들 값을 확인하지 않고 반복을 수행한 다음, 허용오차가 충족되었는지 여부만 확인합니다.

때로는 문제가 비유계일 때 active-set 알고리즘이 감지하기 어려울 수 있습니다. 이러한 문제는 비유계 v의 방향이 2차 항 v'Hv = 0인 방향일 때 발생할 수 있습니다. 수치적 안정성과 촐레스키 분해 실행을 위해 active-set 알고리즘은 2차 목적 함수에 크기가 작은 순 볼록 항을 추가합니다. 이 작은 항은 목적 함수를 –Inf로부터 멀리 떨어지도록 유계합니다. 이 경우 active-set 알고리즘은 해가 비유계라고 보고하는 대신 반복 제한에 도달합니다. 다시 말해서, 알고리즘은 종료 플래그 –3 대신 0을 발생시키고 중단됩니다.

참고 문헌

[1] Gill, P. E., W. Murray, M. A. Saunders, and M. H. Wright. A practical anti-cycling procedure for linearly constrained optimization. Math. Programming 45 (1), August 1989, pp. 437–474.