Linear Programming, Part II

Simplex Derivation, Duality, and Quadratic Programming

Reference: Jasbir Singh Arora, Introduction to Optimum Design, 4th ed., Academic Press, 2017, Ch. 9.

이 장에서는 simplex method의 entering-variable rule, minimum-ratio rule, pivot step을 canonical form에서 유도한다. 이어서 Big-M method와 LP duality를 정리하고, simplex optimality condition이 LP의 KKT conditions와 같음을 보인다. 마지막으로 이 구조를 convex quadratic programming problem의 KKT system에 확장한다.


Simplex Method: Algebraic Derivation

$A\in\mathbb{R}^{m\times n}$, $\operatorname{rank}(A)=m$, $m<n$인 canonical system을

\[x_i+ \sum_{j=m+1}^{n}a_{ij}x_j = b_i, \qquad i=1,\ldots,m\]

이라 하자. Basic variables는

\[x_i = b_i- \sum_{j=m+1}^{n}a_{ij}x_j\]

로 표현된다. 이를 $f=\sum_{j=1}^{n}c_jx_j$에 대입하면

\[f = f_0+ \sum_{j=m+1}^{n}c_j^{\prime}x_j,\] \[f_0 = \sum_{i=1}^{m}b_ic_i, \qquad c_j^{\prime} = c_j- \sum_{i=1}^{m}a_{ij}c_i.\]

$c_j^{\prime}$는 nonbasic variable $x_j$의 reduced cost coefficient이다. 모든 $c_j^{\prime}\geq0$이면 current basic feasible solution은 optimum이고, $c_j^{\prime}<0$인 variable은 cost를 감소시킬 수 있다.


Entering and Leaving Variables

$c_q^{\prime}<0$인 nonbasic variable $x_q$를 entering variable로 선택하자. 다른 nonbasic variables를 zero로 유지하면

\[x_i=b_i-a_{iq}x_q.\]

Feasibility를 위해 $x_i\geq0$이어야 하므로 $a_{iq}>0$인 rows에서

\[x_q\leq\frac{b_i}{a_{iq}}.\]

따라서 maximum feasible value와 leaving row $p$는

\[x_q = \frac{b_p}{a_{pq}} = \min_{i:a_{iq}>0} \frac{b_i}{a_{iq}}\]

로 정해진다. Tied minimum은 degenerate basic feasible solution을 만들 수 있다. Pivot column의 모든 coefficients가 nonpositive이면 $x_q$를 indefinitely 증가시킬 수 있으므로 problem은 unbounded이다.


Pivot Step and Simplex Algorithm

Pivot element가 $a_{pq}$이면 pivot row는

\[a_{pj}^{\prime} = \frac{a_{pj}}{a_{pq}}, \qquad b_p^{\prime} = \frac{b_p}{a_{pq}}\]

로 바뀐다. $i\neq p$인 rows는

\[a_{ij}^{\prime} = a_{ij} - \frac{a_{pj}}{a_{pq}}a_{iq}, \qquad b_i^{\prime} = b_i - \frac{b_p}{a_{pq}}a_{iq}\]

로 갱신한다. Cost row에도 같은 elimination을 적용한다.

Simplex method는 negative reduced cost의 column을 선택하고, ratio test로 leaving row를 정하고, pivot하여 new basic feasible solution을 만드는 과정을 반복한다. 모든 nonbasic reduced costs가 nonnegative가 되면 종료한다.


Artificial Cost and Big-M Methods

Equality와 $\geq$ constraints 때문에 initial basis가 없으면 artificial variables를 도입한다. Phase I의 artificial cost는

\[w = \sum_i x_{a_i}\]

이며, constraints를 대입해 $w$를 nonbasic variables만의 식으로 만든 뒤 simplex method를 적용한다. $w=0$이면 original feasible set에 도달하고, $w>0$에서 더 이상 감소하지 않으면 problem은 infeasible이다.

Big-M method는 separate artificial cost 대신 original minimization objective를

\[f_M = f + M\sum_i x_{a_i}, \qquad M>0\]

로 바꾼다. Artificial variables를 cost row에서 제거한 뒤 regular simplex method를 적용한다. Two-phase method는 feasibility와 optimality를 분리하고, Big-M method는 large penalty를 포함한 하나의 objective를 사용한다.


Standard Primal and Dual Problems

Chapter 9의 standard primal은

\[\begin{aligned} \underset{x}{\operatorname{maximize}}\quad & z_p=d^Tx \\ \text{subject to}\quad & Ax\leq e, \\ & x\geq0 \end{aligned}\]

이고 corresponding dual은

\[\begin{aligned} \underset{y}{\operatorname{minimize}}\quad & f_d=e^Ty \\ \text{subject to}\quad & A^Ty\geq d, \\ & y\geq0. \end{aligned}\]

Primal constraint 하나마다 dual variable 하나가 생기고, primal variable 하나마다 dual constraint 하나가 생긴다. Coefficient matrix는 transpose되고, $d$는 dual right side, $e$는 dual cost coefficient가 된다.


Equality Constraints and Dual of the Dual

Primal equality는 반대 방향의 두 inequalities로 분해할 수 있다. 두 nonnegative dual variables의 difference를 취하면 corresponding dual variable은 unrestricted in sign이다.

\[y_i=y_i^+-y_i^-, \qquad y_i^+,y_i^-\geq0.\]

따라서 다음 대응을 얻는다.

  • Primal equality constraint $\Longleftrightarrow$ unrestricted dual variable.
  • Unrestricted primal variable $\Longleftrightarrow$ dual equality constraint.
  • Primal $\geq$ constraint는 $-1$을 곱해 $\leq$ form으로 만든 뒤 standard rule을 적용한다.

Theorem 9.1 — Dual of a Dual Problem. Dual problem의 dual은 original primal problem이다.


Weak and Strong Duality

Primal-feasible $x$와 dual-feasible $y$에 대해

\[x^TA^Ty\geq x^Td, \qquad y^TAx\leq y^Te.\]

$x^TA^Ty=y^TAx$이므로

\[f_d(y)=y^Te \geq x^Td=z_p(x).\]

Theorem 9.2 — Relationship between Primal and Dual Problems. 모든 feasible pair에 대해 $f_d\geq z_p$이다. Equality가 성립하면 두 points는 각각 dual과 primal optimum이다. 한 problem이 unbounded이면 대응 problem은 infeasible이다.

Theorem 9.3 — Primal and Dual Solutions. Primal과 dual이 모두 feasible이면 양쪽 모두 optimum solution을 가지며 $f_d=z_p$이다.

따라서 feasible primal–dual pair에서 objective values가 같으면 global optimality certificate를 얻는다.


Primal–Dual Solution Recovery

Theorem 9.4 — Solution to Primal from Dual. Optimum에서 $j$번째 dual constraint가 strict inequality이면 $x_j=0$이다. 또한 $y_i>0$이면 corresponding primal constraint는 equality로 만족된다.

\[\sum_{i=1}^{m}a_{ij}y_i>d_j \quad\Longrightarrow\quad x_j=0,\] \[y_i>0 \quad\Longrightarrow\quad \sum_{j=1}^{n}a_{ij}x_j=e_i.\]

Theorem 9.5 — Recovery from the Final Tableau. Final dual tableau에서 dual constraint의 slack 또는 surplus column에 있는 reduced cost coefficient는 corresponding primal-variable value이다. 반대로 final primal tableau의 slack, surplus, artificial columns에 있는 reduced costs로 dual variables를 복원할 수 있다.

Equality constraint의 dual variable은 equality를 두 inequalities로 나누어 두 multipliers의 difference를 취하거나, artificial-variable column을 Phase II까지 유지해 final reduced cost를 읽는 방법으로 구한다.


Dual Variables as Lagrange Multipliers

Primal maximization을 minimization으로 바꾸고

\[L(x,y,\xi) = -d^Tx + y^T(Ax-e) - \xi^Tx\]

로 두자. Stationarity는

\[-d+A^Ty-\xi=0\]

이므로

\[A^Ty-d=\xi\geq0,\]

즉 dual feasibility를 준다. KKT complementarity를 함께 적용하면 primal과 dual objective values가 일치한다.

Theorem 9.6 — Dual Variables as Lagrange Multipliers. Standard primal과 dual의 optimum solutions를 각각 $x$와 $y$라 하면 dual variables $y$는 primal constraints의 Lagrange multipliers이다.


KKT Conditions for the Standard LP

Chapter 8의 standard minimization LP는

\[\underset{x}{\operatorname{minimize}}\ c^Tx \qquad \text{subject to} \qquad Ax=b, \quad x\geq0.\]

Lagrangian은

\[L(x,y,\xi) = c^Tx + y^T(Ax-b) - \xi^Tx\]

이고 KKT conditions는

\[c+A^Ty-\xi=0, \qquad Ax=b,\] \[x_i\xi_i=0, \qquad x_i\geq0, \qquad \xi_i\geq0.\]

LP는 convex이므로 feasible KKT point는 global optimum이다.


Simplex as a KKT Method

Basic and nonbasic parts에 따라

\[A= \begin{bmatrix} B&N \end{bmatrix}, \qquad x= \begin{bmatrix} x_B\\ x_N \end{bmatrix}, \qquad c= \begin{bmatrix} c_B\\ c_N \end{bmatrix}\]

로 partition한다. Constraint equation은

\[x_B=B^{-1}(b-Nx_N)\]

이고, $x_N=0$이면 $x_B=B^{-1}b$이다. Nondegenerate basic solution에서 $x_B>0$이므로 complementarity에 의해 $\xi_B=0$이다. 따라서

\[y=-B^{-T}c_B,\] \[\xi_N = c_N-N^TB^{-T}c_B.\]

Cost function은

\[f = c_B^TB^{-1}b + \xi_N^Tx_N.\]

즉 simplex reduced costs는 $\xi_N$이며, simplex optimality test $\xi_N\geq0$은 KKT multiplier feasibility와 같다. Simplex method는 primal-feasible basis를 이동하면서 KKT conditions를 만족하는 basis를 찾는다.


Quadratic Programming and KKT Conditions

Chapter 9의 QP problem은

\[\begin{aligned} \underset{x}{\operatorname{minimize}}\quad & q(x)=c^Tx+\frac{1}{2}x^THx \\ \text{subject to}\quad & N^Tx=e, \\ & A^Tx\leq b, \\ & x\geq0. \end{aligned}\]

$H\succeq0$이면 convex QP이고, $H\succ0$이면 solution이 존재할 때 unique하다. Slack $s\geq0$, inequality multiplier $u\geq0$, equality multiplier $v$, nonnegativity multiplier $\xi\geq0$을 사용하면 KKT conditions는

\[c+Hx+Au+Nv-\xi=0,\] \[A^Tx+s=b, \qquad N^Tx=e,\] \[u_is_i=0, \qquad \xi_ix_i=0,\] \[x,s,u,\xi\geq0\]

이다.


Complementary Simplex Method for QP

Free equality multiplier를 $v=y-z$, $y,z\geq0$로 분해하면 stationarity와 feasibility를

\[BX=D\]

인 linear system으로 묶을 수 있다. Variable vector는

\[X= \begin{bmatrix} x&u&\xi&s&y&z \end{bmatrix}^T\]

이고 complementary slackness는

\[X_iX_{n+m+i}=0, \qquad i=1,\ldots,n+m\]

로 쓴다. 앞의 $n$ pairs는 $(x_i,\xi_i)$, 뒤의 $m$ pairs는 $(u_i,s_i)$이다.

Initial basis를 만들기 위해

\[BX+Y=D, \qquad w=\sum_{i=1}^{n+m+p}Y_i\]

로 artificial variables를 도입하고 Phase I simplex를 적용한다. Pivot을 선택할 때 complementary pair가 동시에 positive basic variables가 되지 않도록 제한한다. Artificial cost가 zero가 되면 linear equations, nonnegativity, complementarity를 모두 만족하는 QP KKT solution을 얻는다.

Wolfe–Hadley procedure는 $H\succ0$이면 finite number of steps 안에 수렴하며, Chapter 9은 alternative로 Lemke complementary pivot method도 언급한다.


Summary

  • Canonical cost representation에서 reduced-cost rule이, basic-variable feasibility에서 minimum-ratio rule이 유도된다.
  • Big-M method는 artificial variables에 large penalty를 부여하는 two-phase method의 대안이다.
  • Standard primal과 dual은 objective direction, constraint direction, coefficient matrix transpose를 통해 대응한다.
  • Theorems 9.1–9.6은 duality, solution recovery, dual variables와 Lagrange multipliers의 관계를 정리한다.
  • LP reduced costs는 nonnegativity constraints의 KKT multipliers이며 simplex method는 LP KKT system을 해결한다.
  • Convex QP의 KKT system은 linear equations와 complementary pairs로 변환되어 modified Phase-I simplex로 풀 수 있다.