Main Content

선형 계획법 알고리즘

선형 계획법 정의

선형 계획법은 다음과 같이 선형 제약 조건이 적용된 선형 함수 fTx를 최소화하는 벡터 x를 구하는 문제입니다.

minxfTx

다음 중 하나 이상이 성립해야 합니다.

A·xb
Aeq·x = beq
lxu.

linprog의 Interior-Point 알고리즘

linprog'interior-point' 알고리즘은 quadprog의 interior-point-convex 알고리즘과 아주 유사합니다. 이 알고리즘은 linprog'interior-point-legacy' 알고리즘과도 많은 특성을 공유합니다. 이러한 알고리즘은 다음과 같이 동일한 특징을 가집니다.

  1. 풀이 전처리. 이는 문제를 단순화하고 표준 형식으로 변환하는 과정을 의미합니다.

  2. 초기점 생성. 초기점 선택은 interior-point 알고리즘을 효율적으로 푸는 데 특히 중요하며, 이 단계에서 시간이 많이 걸릴 수 있습니다.

  3. KKT 방정식을 풀기 위한 예측자-수정자 반복. 이 단계는 일반적으로 시간이 가장 많이 걸립니다.

풀이 전처리

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

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

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

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

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

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

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

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

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

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

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

문제를 단순화하기 위해, 풀이 전처리 단계에서 문제를 풀지 못한 경우 이 알고리즘은 모든 유한 하한을 0으로 이동시킵니다.

초기점 생성하기

초기점 x0을 설정하기 위해 이 알고리즘은 다음을 수행합니다.

  1. x0ones(n,1)로 초기화합니다. 여기서 n은 목적 함수 벡터 f의 요소 개수입니다.

  2. 하한으로 0을 갖도록 모든 유계 성분을 변환합니다. 성분 i가 유한 상한 u(i)를 가질 경우 x0(i) = u/2입니다.

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

  4. x0이 중앙 경로 가까이 놓이도록 예측자-수정자 스텝을 한 번 실행한 후, 결과로 생성되는 위치 변수와 여유 변수를 범위 내에 제대로 놓이도록 수정합니다. 중앙 경로에 대한 자세한 내용은 Nocedal과 Wright의 문헌[8], 397페이지를 참조하십시오.

예측자-수정자

fminconinterior-point 알고리즘과 유사하게 interior-point 알고리즘은 카루쉬-쿤-터커(KKT) 조건이 성립하는 점을 구하려고 합니다. 선형 계획법 문제에 대한 방정식을 설명하기 위해, 전처리를 거친 다음과 같은 표준 형식의 선형 계획법 문제를 살펴보겠습니다.

minxfTx subject to {A¯x=b¯x+t=ux,t0.

  • 일단, 모든 변수가 최소 하나의 유한 경계를 갖는다고 가정하겠습니다. 필요한 경우 성분을 이동시키고 부호를 변환하여, 이 가정에서는 모든 x 성분의 하한이 0이라고 간주합니다.

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

    A¯x=(Aeq0AI)(x0s),

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

  • t는 상한을 등식으로 변환하는 여유 변수로 구성된 벡터입니다.

이 시스템의 라그랑주에는 다음 벡터가 포함됩니다.

  • y - 선형 등식과 연결된 라그랑주 승수

  • v - 하한(양부호 제약 조건)과 연결된 라그랑주 승수

  • w - 상한과 연결된 라그랑주 승수

라그랑주는 다음과 같습니다.

L=fTxyT(A¯xb¯)vTxwT(uxt).

따라서, 이 시스템의 KKT 조건은 다음과 같습니다.

fA¯Tyv+w=0A¯x=b¯x+t=uvixi=0witi=0(x,v,w,t)0.

linprog 알고리즘은 반환된 라그랑주 승수에 대해 여기서 다룬 것과 다른 부호 규칙을 사용합니다. 여기서는 대부분의 문헌에서 사용하는 것과 동일한 부호를 사용합니다. lambda를 참조하십시오.

이 알고리즘은 먼저 뉴턴-랩슨(Newton-Raphson) 식에서 스텝을 예측한 후 수정자 스텝을 계산합니다. 수정자는 비선형 상보성 방정식 sizi = 0의 잔차를 줄이려고 합니다. 뉴턴-랩슨 스텝은 다음과 같습니다.

(0A¯T0IIA¯0000I0I00V00X000W0T)(ΔxΔyΔtΔvΔw)=(fA¯Tyv+wA¯xb¯uxtVXWT)=(rdrprubrvxrwt),(1)

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

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

  • rp - 원문제(Primal) 잔차

  • rub - 상한 잔차

  • rvx - 하한 상보성 잔차

  • rwt - 상한 상보성 잔차

반복 과정 표시에는 다음 수량이 보고됩니다.

Primal infeasibility=rp1+rub1Dual infeasibility=rd.

수식 1을 풀려면 먼저 이를 다음과 같은 대칭 행렬 형식으로 변환해야 합니다.

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

여기서

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

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

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

수식 2는 대칭이지만 –D 항으로 인해 양의 정부호가 아닙니다. 따라서, 촐레스키 분해(Cholesky Factorization)를 사용하여 풀 수 없습니다. 몇 단계를 더 거쳐 양의 정부호인 다른 부등식을 생성한 후, 촐레스키 분해를 사용하여 효율적으로 풀 수 있습니다.

수식 2의 두 번째 행 집합은 다음과 같습니다.

A¯Δx=rp

첫 번째 행 집합은 다음과 같습니다.

DΔx+A¯TΔy=R.

다음과 같이 대입하면

Δx=D1A¯TΔy+D1R

다음이 생성됩니다.

A¯D1A¯TΔy=A¯D1Rrp.(3)

일반적으로, 뉴턴 스텝을 구하는 가장 효율적인 방법은 촐레스키 분해를 사용하여 수식 3을 풀어 Δy를 구하는 것입니다. Δy에 곱한 행렬은 확실히 대칭이고, 퇴화(Degeneracy)가 없는 경우 양의 정부호이므로 촐레스키 분해가 가능합니다. 그 후에 뉴턴 스텝을 구하려면 역대입하여 Δx, Δt, Δv, Δw를 구해야 합니다. 하지만, A¯에 조밀한 열이 있는 경우 수식 2를 대신 푸는 것이 더 효율적일 수 있습니다. linprog의 interior-point 알고리즘은 열의 밀도를 기반으로 하여 해 알고리즘을 선택합니다.

알고리즘에 대한 자세한 내용은 Mehrotra의 문헌[7]을 참조하십시오.

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

예측자-수정자 알고리즘은 2차 항을 제외하고는 비희소 quadprog 'interior-point-convex' 버전과 대체로 같습니다. 비희소 예측자-수정자 항목을 참조하십시오.

중지 조건

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

ρ=max(1,A¯,f,b¯).

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

rp1+rub1ρTolConrdρTolFunrcTolFun,

여기서

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

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

Interior-Point-Legacy 선형 계획법

소개

Interior-point-legacy 방법은 Mehrotra의 예측자-수정자 알고리즘([47])의 변형인 원문제-쌍대 문제(Primal-Dual) interior-point 방법에 해당하는 LIPSOL([52])을 기반으로 합니다.

주 알고리즘

이 알고리즘은 먼저 일련의 전처리 단계를 적용합니다(전처리 참조). 전처리 후 문제의 형식은 다음과 같습니다.

minxfTx such that {Ax=b0xu.(4)

상한 제약 조건이 제약 조건 행렬 A에 묵시적으로 포함되어 있습니다. 원문제 여유 변수 s를 추가하면 수식 4가 다음과 같이 됩니다.

minxfTx such that {Ax=bx+s=ux0, s0.(5)

이를 원문제라고 합니다. x는 원문제 변수로 구성되고 s는 원문제 여유 변수로 구성됩니다. 쌍대 문제는 다음과 같습니다.

maxbTyuTw  such that  {ATyw+z=fz0, w0,(6)

여기서 yw는 쌍대 변수(Dual Variable)로 구성되고 z는 쌍대 여유 변수로 구성됩니다. 이 선형 계획(즉, 원문제 수식 5 및 쌍대 문제 수식 6)에 대한 최적성 조건은 다음과 같습니다.

F(x,y,z,s,w)=(Axbx+suATyw+zfxizisiwi)=0,                 x0, z0, s0, w0,(7)

여기서 xizisiwi는 성분별 곱셈을 나타냅니다.

linprog 알고리즘은 반환된 라그랑주 승수에 대해 여기서 다룬 것과 다른 부호 규칙을 사용합니다. 여기서는 대부분의 문헌에서 사용하는 것과 동일한 부호를 사용합니다. lambda를 참조하십시오.

2차 방정식 xizi = 0siwi = 0은 선형 계획에 대한 상보성 조건이라고 하고, 다른 (선형) 방정식은 실현가능성 조건이라고 합니다. 다음 수량은

xTz + sTw

쌍대 격차이며, 이는 (x,z,s,w) ≥ 0인 경우 F의 상보성 부분의 잔차를 측정합니다.

이 알고리즘은 원문제-쌍대 문제 알고리즘이며, 이는 원문제 계획과 쌍대 문제 계획을 모두 동시에 푼다는 것을 의미합니다. 이는 뉴턴의 방법과 유사한 것으로 간주될 수 있으며, 수식 7에서 선형-2차 시스템 F(x,y,z,s,w) = 0에 적용될 수 있지만 이와 동시에 반복 요소 x, z, w, s를 양수로 유지하므로 interior-point 방법이라고 합니다. 이 반복 요소들은 수식 5의 부등식 제약 조건으로 나타낸 엄격한 내부 영역에 있습니다.

이 알고리즘은 메로트라가 제안한 예측자-수정자 알고리즘의 변형입니다. 반복 v = [x;y;z;s;w]를 살펴보겠습니다. 여기서 [x;z;s;w] > 0입니다. 먼저, 다음과 같이 예측 방향을 계산합니다.

Δvp=(FT(v))1F(v),

이는 뉴턴 방향입니다. 그런 다음 다음과 같이 수정자 방향을 계산합니다.

Δvc=(FT(v))1F(v+Δvp)μe^,

여기서 μ > 0중심화 파라미터라고 하며 신중하게 선택해야 합니다. e^F(v)에서 2차 방정식에 대응하는 1을 갖는 0-1 벡터입니다. 즉, 섭동은 모두 2차인 상보성 조건에만 적용되며 모두 선형인 실현가능성 조건에는 적용되지 않습니다. 이 두 방향을 스텝 길이 파라미터 α > 0에 결합하고 새 반복 v+를 구하도록 다음과 같이 v를 업데이트합니다.

v+=v+α(Δvp+Δvc),

여기서 스텝 길이 파라미터 α는 다음이

v+ = [x+;y+;z+;s+;w+]

다음을 충족하도록 선택됩니다.

[x+;z+;s+;w+] > 0.

앞에서 설명한 예측자/수정자 방향에 대한 풀이 과정에서 이 알고리즘은 A·AT의 촐레스키 인수를 수정할 때 (희소) 직접 분해를 계산합니다. A에 조밀한 열이 있는 경우 셔먼-모리슨(Sherman-Morrison) 식을 대신 사용합니다. 해가 적합하지 않으면(잔차가 너무 큼) 확장된 시스템 형식의 스텝 방정식에 대해 LDL 분해를 수행하여 해를 구합니다. ldl 항목을 참조하십시오.

그런 다음 반복이 수렴할 때까지 루프를 실행합니다. 주요 중지 기준은 다음과 같은 표준 조건입니다.

max(rbmax(1,b),rfmax(1,f),rumax(1,u),|fTxbTy+uTw|max(1,|fTx|,|bTyuTw|))tol,

여기서

rb=Axbrf=ATyw+zfru={x}+su

이는 각각 원문제 잔차, 쌍대 문제 잔차, 상한 실현가능성이며({x}는 유한 상한이 있는 x를 의미함) 다음은

fTxbTy+uTw

원문제 목적 함수 값과 쌍대 문제 목적 함수 값 사이의 차이이고 tol은 허용오차입니다. 중지 기준에 있는 합은 수식 7의 최적성 조건에서 총 상대 오차를 측정합니다.

원문제 실현불가능성에 대한 측정값은 ||rb||이고, 쌍대 문제 실현불가능성에 대한 측정값은 ||rf||입니다. 여기서 노름은 유클리드 노름입니다.

전처리

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

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

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

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

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

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

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

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

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

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

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

문제를 단순화하기 위해 알고리즘은 모든 하한을 0으로 이동시킵니다.

라그랑주 승수가 필요한 경우 이러한 전처리 단계는 알고리즘에서 반복되는 부분의 속도를 높이는 데 크게 기여할 수 있지만, 알고리즘 실행 도중에 계산되는 승수는 원래 문제에 대한 것이 아니라 변환된 문제에 대한 것이므로 전처리 단계의 실행을 취소해야 합니다. 따라서, 승수가 필요하지 않은 경우에는 이러한 역변환에 대한 계산 과정이 없으므로 계산 차원에서 시간을 일부 절약할 수 있습니다.

Dual-Simplex-Legacy 알고리즘

대략적으로 설명하자면 linprog'dual-simplex-legacy' 알고리즘은 기본적으로 쌍대(Dual) 문제에 대해 단체 알고리즘을 수행합니다.

이 알고리즘은 먼저 전처리에 설명된 대로 전처리를 수행합니다. 자세한 내용은 Andersen과 Andersen의 문헌[1] 및 Nocedal과 Wright의 문헌[8], 13장을 참조하십시오. 이 전처리는 다음과 같이 원래 선형 계획법 문제를 수식 4 형식으로 줄여줍니다.

minxfTx such that {Ax=b0xu.

Ab는 원래 제약 조건 행렬을 변환한 것입니다. 이것이 바로 원문제(Primal)입니다.

원문제 실현가능성은 다음과 같이 + 함수로 정의될 수 있습니다.

x+={xif x>00if x0.

원문제 실현불가능성의 측정값은 다음과 같습니다.

Primal infeasibility=((lbx)+)2+((xub)+)2+((Axb)+)2+|Aeqxbeq|2.

수식 6에 설명된 대로 쌍대 문제는 벡터 yw, 그리고 여유 변수 벡터 z를 구하여 다음 문제를 푸는 것이 목적입니다.

maxbTyuTw  such that  {ATyw+z=fz0, w0.

linprog 알고리즘은 반환된 라그랑주 승수에 대해 여기서 다룬 것과 다른 부호 규칙을 사용합니다. 여기서는 대부분의 문헌에서 사용하는 것과 동일한 부호를 사용합니다. lambda를 참조하십시오.

쌍대 문제 실현불가능성의 측정값은 다음과 같습니다.

Dual infeasibility=ATy+zwf2.

쌍대 문제에 대한 임의의 유한 해는 원문제의 해를 제공하고 원문제에 대한 임의의 유한 해는 쌍대 문제의 해를 제공하는 것으로 잘 알려져 있습니다(예를 들어, [8] 참조). 또한, 원문제와 쌍대 문제 중 어느 한쪽이 비유계이면 다른 쪽 문제는 실현 가능하지 않습니다. 그리고 원문제와 쌍대 문제 중 어느 한쪽이 실현 가능하지 않으면 다른 쪽 문제는 실현 가능하지 않거나 비유계입니다. 따라서, 유한 해가 존재할 경우 이를 구한다는 차원에서 두 문제는 동일합니다. 원문제와 쌍대 문제가 수학적으로 동일하지만 계산 단계는 다르기 때문에 쌍대 문제를 풀어서 원문제를 푸는 것이 더 나을 수 있습니다.

퇴화(Degeneracy)를 완화시키는 데 도움이 되도록(Nocedal과 Wright의 문헌[8], 366페이지 참조), 쌍대 문제 단체 알고리즘은 먼저 목적 함수에 섭동을 적용합니다.

쌍대 문제 단체 알고리즘의 단계 1은 쌍대 문제 실현가능점을 구하는 것입니다. 이 알고리즘은 보조 선형 계획법 문제를 풀어 이를 수행합니다.

 단계 1 개요

단계 2에서 솔버는 진입 변수와 탈락 변수를 반복적으로 선택합니다. 알고리즘은 쌍대 최대경사면 가격결정(Dual Steepest-Edge Pricing)이라고 하는 포레스트(Forrest)와 골드파브(Goldfarb)가 제안한 기법[3]에 따라 탈락 변수를 선택합니다. 진입 변수는 코버슈타인(Koberstein)[6]이 제안한 변형된 해리스의 비율판정법(Harris’ ratio test)을 사용하여 선택합니다. 퇴화(Degeneracy)를 완화하는 데 도움이 되도록 이 알고리즘은 단계 2 중에 추가적인 섭동을 적용할 수 있습니다.

 단계 2 개요

솔버는 원문제 실현불가능성을 줄이는 동시에 쌍대 문제 실현가능성을 유지하려고 하면서, 축소되고 섭동된 문제의 해가 원문제와 쌍대 문제 둘 모두에서 실현 가능해질 때까지 반복합니다. 알고리즘은 적용한 섭동을 취소합니다. (섭동된 문제의) 해가 섭동되지 않은 (원래) 문제에 대해 쌍대 문제 실현이 불가능할 경우 솔버는 원문제 단체 알고리즘이나 단계 1 알고리즘을 사용하여 쌍대 문제 실현가능성을 복원합니다. 마지막으로, 솔버는 전처리 단계를 취소하여 해를 원래 문제로 되돌립니다.

Dual-Simplex-Highs 알고리즘

'dual-simplex-highs' 알고리즘은 HiGHS 오픈소스 소프트웨어를 기반으로 합니다. 대략적으로 설명하자면 linprog'dual-simplex-highs' 알고리즘은 기본적으로 쌍대 문제 실현가능성을 유지하면서 원문제 실현가능성을 향해 반복하는 단체 알고리즘을 수행합니다. 원문제(Primal)와 쌍대 문제(Dual) 실현가능성 항목을 참조하십시오. 알고리즘에 대한 자세한 내용은 Huangfu와 Hall의 문헌[4], 섹션 2를 참조하십시오.

이 알고리즘은 먼저 전처리에 설명된 대로 전처리를 수행합니다. 배경 정보는 Andersen과 Andersen의 문헌[1] 및 Nocedal과 Wright의 문헌[8], 13장을 참조하십시오. 이 전처리는 일반적으로 원래 선형 계획법 문제를 해결하기 쉬운 더 작은 문제로 줄여줍니다.

쌍대 문제에 대한 임의의 유한 해는 원문제의 해를 제공하고 원문제에 대한 임의의 유한 해는 쌍대 문제의 해를 제공하는 것으로 잘 알려져 있습니다(예를 들어, [8] 참조). 또한, 원문제와 쌍대 문제 중 어느 한쪽이 비유계이면 다른 쪽 문제는 실현 가능하지 않습니다. 그리고 원문제와 쌍대 문제 중 어느 한쪽이 실현 가능하지 않으면 다른 쪽 문제는 실현 가능하지 않거나 비유계입니다. 따라서, 유한 해가 존재할 경우 이를 구한다는 차원에서 두 문제는 동일합니다. 원문제와 쌍대 문제가 수학적으로 동일하지만 계산 단계는 다르기 때문에 쌍대 문제를 풀어서 원문제를 푸는 것이 더 나을 수 있습니다.

퇴화(Degeneracy)를 완화시키는 데 도움이 되도록(Nocedal과 Wright의 문헌[8], 366페이지 참조), 쌍대 문제 단체 알고리즘은 먼저 목적 함수 계수에 섭동을 적용합니다.

쌍대 문제 단체 알고리즘의 단계 1은 쌍대 문제 실현가능점을 구하는 것이 목표입니다. 알고리즘은 단계 1 문제에 적용된 단계 2 알고리즘(아래)을 사용하여 이를 수행합니다. 이 문제는 (섭동된) 목적 함수 비용 계수를 가지며, 변수와 제약 조건의 범위가 다음과 같이 수정됩니다. 단방향 상한(하한) 변수와 제약 조건의 범위는 [0, 1]([–1, 0])로, 고정 변수와 방정식의 범위는 0으로, 자유 변수와 제약 조건의 범위는 [–1000, 1000]으로 설정됩니다. 모든 범위는 유한하기 때문에 원문제 변수를 적절한 범위로 설정하면 모든 기저 변수가 쌍대 문제에서 실현 가능해집니다. (비기저) 변수의 쌍대 문제 값이 원래 범위에 대해 실현 가능하지 않으면 이 값은 쌍대 문제 목적 함수 값에 부정적으로 기여합니다. 쌍대 문제 목적 함수의 범위가 0보다 위에 있는지 살펴보십시오. 단계 1 문제가 최적으로 풀릴 때 목적 함수 값이 0인 경우 현재 점은 원래 범위에 대해 쌍대 문제에서 실현 가능합니다. 음의 목적 함수 값은 섭동된 목적 함수 비용 계수가 있는 원래 문제의 쌍대 문제 실현불가능성을 의미하며, 섭동되지 않은 원래 문제의 쌍대 문제 실현불가능성을 강력하게 시사합니다. 이 시나리오는 섭동되지 않은 목적 함수 계수로 되돌리고 현재의 쌍대 문제 해에서 단계 1 문제를 계속 해결하려고 시도함으로써 그 유용성을 평가받게 됩니다.

단계 1의 해는 주 알고리즘의 단계 2에 대한 초기점입니다.

단계 2에서 솔버는 탈락 변수와 진입 변수를 반복적으로 선택합니다. 알고리즘은 쌍대 최대경사면 가격결정(Dual Steepest-Edge Pricing)이라고 하는 포레스트(Forrest)와 골드파브(Goldfarb)가 제안한 기법[3]에 따라 탈락 변수를 선택합니다. 진입 변수는 코버슈타인(Koberstein)[6]이 제안한 변형된 해리스의 비율판정법(Harris’ ratio test)을 사용하여 선택합니다. 반올림으로 인한 미소한 쌍대 문제 실현불가능성들은 비용 계수를 이동시킴으로써 제거됩니다.

단계 2에서는, 단계 1에서 구한 쌍대 문제 실현가능점에서 시작하는 쌍대 문제 단체 알고리즘이 원래 문제를 푸는 데 사용됩니다. 각 반복마다 알고리즘은 최적성 조건(원문제 실현가능성)을 테스트하고 현재 해가 최적이면 중지합니다. 현재 해가 최적이 아니면 알고리즘은 기저 변수와 비기저 변수를 정의에 사용하여 다음을 수행합니다.

  1. 원문제 값이 실현 가능하지 않은 기저 변수에서 변수 하나(탈락 변수라고 함)를 선택합니다.

  2. 비기저 변수에서 변수 하나(진입 변수라고 함)를 선택하고 해당 변수를 사용하여 기저 변수의 탈락 변수를 대체합니다.

  3. 현재 원문제 해와 쌍대 문제 해, 그리고 현재 목적 함수 값을 업데이트합니다.

쌍대 문제 비율 판정에서 탈락 변수의 쌍대 문제 값은 쌍대 문제 실현가능성을 유지하는 선에서 가능한 한 최대로 증가합니다. 진입 변수는 이 제한에서 쌍대 문제 값이 0이 되는 비기저 변수입니다. 쌍대 문제 비율에 대한 데이터를 계산하려면 하나의 연립방정식의 해가 필요합니다. 기저 변수가 바뀐 후에, 원문제 해를 업데이트하려면 두 번째 연립방정식이 풀려야 합니다. 쌍대 문제 비율 판정에서 한계가 없으면, 섭동된 문제는 쌍대 문제가 비유계인 것입니다(따라서 원문제가 실현 가능하지 않습니다).

솔버는 원문제 실현불가능성을 줄이는 동시에 쌍대 문제 실현가능성을 유지하면서, 축소되고 섭동된 문제의 해가 원문제와 쌍대 문제 둘 모두에서 실현 가능해질 때까지 반복합니다. 그런 다음 알고리즘은 목적 함수 비용 섭동을 제거합니다. (섭동된 문제의) 해가 섭동되지 않은 (원래) 문제에 대해 쌍대 문제 실현이 불가능할 경우 솔버는 원문제 단체 단계 2 알고리즘을 사용하여 쌍대 문제 실현가능성을 복원합니다. 마지막으로, 솔버는 전처리 단계를 취소하여 해를 원래 문제로 되돌립니다.

기저 변수와 비기저 변수

이 섹션에서는 선형 계획법 문제에서 기저, 비기저, 그리고 실현 가능한 기저해라는 용어를 정의합니다. 이 정의에서는 문제가 다음과 같은 표준 형식으로 지정되었다고 가정합니다.

minxfTx such that {Ax=b,lbxub.

참고로, Ab는 원래 문제에서 부등식을 정의하는 데 사용한 행렬 및 벡터와는 다릅니다. A는 열이 {a1, a2, ..., an}인 랭크 m < nm×n 행렬이라고 간주합니다. {ai1,ai2,...,aim}은 인덱스 집합 B = {i1, i2, ..., im}을 갖는 A의 열 공간에 대한 기저이고 N = {1, 2, ..., n}\BB의 여집합이라고 가정하겠습니다. 부분행렬 AB기저라고 하고 상보 부분행렬 AN비기저라고 합니다. 기저 변수의 벡터는 xB이고 비기저 변수의 벡터는 xN입니다. 단계 2의 각 반복마다 알고리즘은 현재 기저의 한 열을 비기저의 한 열로 대체하고 이에 따라 변수 xBxN을 업데이트합니다.

xA·x = b의 해이고 xN의 모든 비기저 변수가 하한 또는 상한과 같을 경우 x기저해라고 합니다. 또한 xB의 기저 변수가 하한과 상한을 충족하여 x가 실현가능점이 되는 경우 x실현 가능한 기저해라고 합니다.

원문제(Primal)와 쌍대 문제(Dual) 실현가능성

원문제 실현불가능성을 측정한 값은 최대 절대적 제약 조건 위반으로 보고되는데, 이는 원래 문제 변수로 볼 때 다음과 같습니다.

max(0, lb – x, x – ub, abs(Aeqx – beq), Ax – b).(8)

쌍대 문제 실현가능성을 정의하려면 먼저 선형 행렬 A(기저 변수와 비기저 변수에서 가져옴)를 선형 독립 열을 포함하는 기저 변수 행렬 B와 비기저 변수 행렬 N의 두 블록으로 다음과 같이 분할합니다.

Ax=[BN][xBxN]=BxB+NxN=b.

방정식 A x = b에 대한 변수 x는 자연스럽게 다음과 같이 xBxN으로 분할됩니다.

Ax=[BN][xBxN]=BxB+NxN=b.

B는 선형 독립 열로 구성되어 있으므로 가역적이고 따라서 다음과 같습니다.

xB=B1(bNxN)=B1bB1NxN.

목적 함수 fTx는 유사하게 다음과 같이 쓸 수 있습니다.

fTx=fBTxB+fNTxN=fBT(B1bB1NxN)+fNTxN=fBTB1b+(fNTfBTB1N)xN.

감소된 비용은 비기저 변수의 조정된 비용 계수입니다.

cNT=fNTfBTB1N.

이 감소된 비용 값의 하한 cj(cNT의 j번째 요소)에 있는 모든 비기저 변수가 0보다 크거나 같고 상한 cj에 있는 모든 비기저 변수가 0보다 작거나 같은 경우 현재 해는 쌍대 문제에서 실현 가능합니다. 쌍대 문제 단체 알고리즘은 이 쌍대 문제 실현가능성을 유지하고 단체 반복을 통해 원문제를 실현 가능하게 만들려고 시도합니다.

참고 문헌

[1] Andersen, E. D., and K. D. Andersen. Presolving in linear programming. Math. Programming 71, 1995, pp. 221–245.

[2] Applegate, D. L., R. E. Bixby, V. Chvátal and W. J. Cook, The Traveling Salesman Problem: A Computational Study, Princeton University Press, 2007.

[3] Forrest, J. J., and D. Goldfarb. Steepest-edge simplex algorithms for linear programming. Math. Programming 57, 1992, pp. 341–374.

[4] Huangfu, Q. and J. A. J. Hall. Parallelizing the dual revised simplex method. Math. Prog. Comp. 10, pp. 119–142, 2018. Available at https://link.springer.com/article/10.1007/s12532-017-0130-5.

[5] Gondzio, J. “Multiple centrality corrections in a primal dual method for linear programming.” Computational Optimization and Applications, Volume 6, Number 2, 1996, pp. 137–156. Available at https://www.maths.ed.ac.uk/~gondzio/software/correctors.ps.

[6] Koberstein, A. Progress in the dual simplex algorithm for solving large scale LP problems: techniques for a fast and stable implementation. Computational Optim. and Application 41, 2008, pp. 185–204.

[7] Mehrotra, S. “On the Implementation of a Primal-Dual Interior Point Method.” SIAM Journal on Optimization, Vol. 2, 1992, pp 575–601.

[8] Nocedal, J., and S. J. Wright. Numerical Optimization, Second Edition. Springer Series in Operations Research, Springer-Verlag, 2006.