풀이 전처리/풀이 후처리

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

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

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

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

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

초기점 생성하기

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

예측자-수정자

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

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

• 희소 예측자-수정자

• 비희소 예측자-수정자

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

여기서

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

예측자 스텝의 정의:

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

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

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

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

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

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

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

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

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

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

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

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

여기서

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차 항도 포함한다는 점만 다릅니다. 예측자-수정자 항목을 참조하십시오.

중지 조건

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

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

여기서

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

실현불가능성 감지

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

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

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

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

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

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

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

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

선형 등식 제약 조건

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

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

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

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

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

상자 제약 조건

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

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

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

여기서

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

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

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

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

그리고,

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

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

풀이 전처리 단계

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

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

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

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

자세한 내용은 굴드(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이면 알고리즘은 보조 선형 계획법 문제에 대해 음이 아닌 여유 변수 γ를 추가합니다.

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

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

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

단계 2 알고리즘

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

여기서 A_i는 m×n 행렬 A의 i번째 행에 해당합니다.

단계 2에서 활성 세트 $${\overline{A}}_k$$는 해에 해당하는 점의 활성 제약 조건(제약 조건 경계에 있는 제약 조건)의 추정값입니다.

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

알고리즘은 행렬 $${\overline{A}}_k^T$$에 대한 QR 분해의 마지막 n – l개 열로부터 행렬 Z_k를 구성합니다. 여기서 l은 활성 제약 조건의 개수이고 l < n입니다. 즉, Z_k는 다음과 같이 지정됩니다.

여기서

알고리즘은 Z_k를 발견하고 나면 q(d)를 최소화하는 새로운 탐색 방향 d_k를 찾습니다. 여기서 d_k는 활성 제약 조건의 영공간에 있습니다. 즉, d_k는 Z_k의 열의 선형 결합입니다(어떤 벡터 p에 대해 $${\widehat{d}}_k=Z_{k}p$$).

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

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

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

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

여기서

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

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

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

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

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

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

웜 스타트

warm start 객체를 시작점으로 사용하여 quadprog 또는 lsqlin의 'active-set' 알고리즘을 실행할 경우 솔버는 단계 1 스텝과 단계 2 스텝 중 많은 스텝을 건너뛰려고 시도합니다. warm start 객체는 활성 제약 조건 세트를 포함하며, 이 세트는 새 문제에 대해 올바르거나 거의 올바를 수 있습니다. 따라서, 솔버는 반복을 방지하여 활성 세트에 제약 조건을 추가할 수 있습니다. 또한 초기점이 새 문제에 대한 해에 근접할 수도 있습니다. 자세한 내용은 optimwarmstart 항목을 참조하십시오.