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

2차 계획법 알고리즘

2차 계획법 정의

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

minx12xTHx+cTx

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

quadproginterior-point-convex 알고리즘

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

참고

이 알고리즘에는 두 개의 코드 경로가 있습니다. 하나는 헤세 행렬 H가 double형으로 구성된 일반(비희소) 행렬인 경우 실행하고, 다른 하나는 H가 희소 행렬인 경우 실행합니다. 희소 데이터형에 대한 자세한 내용은 희소 행렬 (MATLAB) 항목을 참조하십시오. 일반적으로, 이 알고리즘은 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).(1)

하지만, 비희소 뉴턴 스텝은 실현 가능하지 않을 수 있습니다 그 이유는 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.(2)

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

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

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

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

  • rp - 원문제(Primal) 잔차

  • rub - 상한 잔차

  • rvx - 하한 상보성 잔차

  • rwt - 상한 상보성 잔차

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

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

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

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

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

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

수식 4를 풀기 위해 이 알고리즘은 올트먼(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}.(5)

현재 점은 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Δ},(6)

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

1Δ1s=0.

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

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

Hs2=g,(7)

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

s2THs2<0.(8)

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

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

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

  2. 수식 6을 풀어서 시행 스텝 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},(9)

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

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

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

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

상자 제약 조건

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

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

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

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

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

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

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이 됩니다.

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

수식 12로 지정되는 비선형 연립방정식에 대해 스케일링되고 수정된 뉴턴 스텝 sk는 다음과 같이 선형 시스템의 해로 정의됩니다.

M^DsN=g^(13)

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

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

그리고,

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

여기서 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).