Prev Next Top DualEqIneq

Duality with Equality and Inequality Constraints

General Notation
We are given a certain number of equality constraints  m(=) , a number of inequality constraints  m(\leq) , a number of free variables  n(\pm) , and a number of non-negative variables  n(+) . These constraints are define by  A_{=,\pm} \in \R^{m(=) \times n(\pm)} ,  A_{=,+} \in \R^{m(=) \times n(+)} ,  A_{\leq,\pm} \in \R^{m(\leq) \times n(\pm)} ,  A_{\leq,+} \in \R^{m(\leq) \times n(+)} ,  b_= \in \R^{m(=)} ,  b_\leq \in \R^{m(\leq)} ,  c_\pm \in \R^{n(\pm)} , and  c_+ \in \R^{n(+)} .

Primal Problem
 \[
\begin{array}{ll}
{\rm maximize} & c_\pm^T x_\pm \; + \; c_+^T x_+
     \; {\rm with \; respect \; to}
     x_\pm \in \R^{n(\pm)} \; , \; x_+ \in \R_+^{n(+)}
\\
{\rm subject \; to} 
&     A_{=,\pm} x_\pm \; + \;     A_{=,+} x_+  \; = \;    b_=
\\
                    
& A_{\leq ,\pm} x_\pm \; + \; A_{\leq ,+} x_+ \; \leq \;  b_\leq 
\end{array}
\] 

Standard Primal Form
Define  x_\pm = x_\pm^+ - x_\pm^- where  x_\pm^+ \in \R_+^{n(\pm)} , and  x_\pm^- \in \R_+^{n(\pm)} . The primal problem above is equivalent to  \[
\begin{array}{ll}
{\rm maximize} & c_\pm^T x_\pm^+ \; - \; c_\pm^T x_\pm^- \; + \; c_+^T x_+
     \; {\rm w.r.t.} \;
     x_\pm^+ \in \R_+^{n(\pm)} \; , \; 
     x_\pm^- \in \R_+^{n(\pm)} \; , \; 
     x_+ \in \R_+^{n(+)}
\\
{\rm subject \; to} 
&   + A_{=,\pm} x_\pm^+ \; - \;
      A_{=,\pm} x_\pm^- \; + \;     A_{=,+} x_+    \; \leq \; +  b_=
\\
&   - A_{=,\pm} x_\pm^+ \; + \;
      A_{=,\pm} x_\pm^- \; - \;     A_{=,+} x_+    \; \leq \; - b_=
\\
&   + A_{\leq ,\pm} x_\pm^+ \; - \; 
      A_{\leq ,\pm} x_\pm^- \; + \; A_{\leq ,+} x_+ \; \leq \; + b_\leq 
\end{array}
\] 

Standard Dual Form
 \[
\begin{array}{ll}
{\rm maximize} & b_=^T y_=^+ \; - \; b_=^T y_=^- \; + \; b_\leq^T y_\leq
     \; {\rm w.r.t.} \;
     y_=^+ \in \R_+^{m(=)} \; , \; 
     y_=^- \in \R_+^{m(=)} \; , \; 
     y_\leq \in \R_+^{m(\leq)}
\\
{\rm subject \; to} 
&  + A_{=,\pm}^T y_=^+ \; - \;
     A_{=,\pm}^T y_=^- \; + \;   A_{\leq,\pm}^T y_\leq   \; \geq \; +  c_\pm
\\
&  - A_{=,\pm}^T y_=^+ \; + \;
     A_{=,\pm}^T y_=^- \; - \;   A_{\leq,\pm}^T y_\leq   \; \geq \; -  c_\pm
\\
&  + A_{=,+}^T y_=^+   \; - \;
     A_{=,+}^T y_=^-   \; + \;   A_{\leq,+}^T y_\leq     \; \geq \; +  c_+
\end{array}
\] 

Dual Problem
Define  y_= = y_=^+ - y_=^- where  y_= \in \R^{m(=)} . The primal problem above is equivalent to  \[
\begin{array}{ll}
{\rm minimize} & b_=^T y_= \; + \; b_\leq^T y_\leq 
     \; {\rm with \; respect \; to}
     y_= \in \R^{m(=)} \; , \; y_\leq \in \R_+^{m(\leq)}
\\
{\rm subject \; to} 
& A_{=,\pm}^T y_= \; + \; A_{\leq,\pm}^T y_\leq \;   =   \; c_\pm \\
\\
&   A_{=,+}^T y_= \; + \;   A_{\leq,+}^T y_\leq \; \geq  \; c_+
\end{array}
\] 
Input File: DualEqIneq.omh