Andrew Naguib's Homepage
(آندرو نجيب؛ الصفحة الشخصية)

Dual problems

• LP
  

  (P) LP-SEF: \(\min_x \langle c, x \rangle: A x = b, x \geq 0\) (D) LP-SEF: \(\max_y \langle b, y \rangle: ( A y + \lambda = c, \lambda \geq 0) \equiv Ay \leq c\)

• QP
  
  • primal problem
    

    \(\min_x \frac{1}{2} x^T H x + c^T x: A x \leq b, H \succeq 0\)

  • dual problem
    

    \(\max_{\lambda, z} - \frac{1}{2} z^T H z - b^T \lambda : H z = - (c + A^T \lambda), \lambda \geq 0\)

• QCQP
  
  • primal problem
    

    \(\min \frac{1}{2} x^T P_0 x + c_0^T x : \frac{1}{2} x^T P_i x + c_i^T + d_i \leq 0; i \in \{1, \cdots, m \}, m \in \mathbb{N}\)

  • dual problem (\(P\) invertible)
    

    \(\max -(1/2) q(\lambda)^T P(\lambda)^{-1} q(\lambda) + r(\lambda) : \lambda \succeq 0\)
    

  • dual problem (\(P\) not invertible)
    

    \(\max_{\gamma, \lambda} - \gamma + d^T \lambda : \begin{pmatrix} P_0 + \sum_{i=1}^m \lambda_i P_i & c_0 + \sum_{i=1}^m \lambda_i c_i \\ c_0^T + \sum_{i=1}^m \lambda_i c_i^T & \gamma \end{pmatrix} \succeq 0\)

• SOCP
  
  • primal problem
    

    \(\min_x c^T x : A x = b, x \in C_2^{k_1} \times \cdots \times C_2^{k_n}\)

    linear objective, equality constraints, single second order cone constraint.

• SDP
  
  • primal problem
    

    SDP: \(\min_X \langle C, X \rangle: \langle A_i, X \rangle= b_i, X \in \mathbb{S}^n_+, C_, A_i \in \mathbb{S}^n, b \in \mathbb{R}^n\)

• SCF
  
  • primal problem
    

    \(\min_x c^T x : A x = b; x \in K\)
    \(\left(\text{SOCP: } K = C_2^{k_1} \times \cdots \times C_2^{k_n}; \text{SDP: }K = \mathbb{S}^n_+ \right)\)

  • dual problem
    

    \(\max_{y} - b^T \nu : c - \lambda + A^T \nu = 0, \lambda \succeq_{K^\ast} 0 \equiv c - A^Ty \succeq_{K^\ast} 0\) or (\(y = -\nu\)) \(\max_{y} b^T y : c - A^T y \succeq_{K^\ast} 0\) (\(X \in \mathbb{S}^n_+\) can be rewritten \(X \in \mathbb{S}^n \wedge \lambda_{\max} (-X) \leq 0\))

Formulation

• QP \(\to\) LP: \(H = 0\).
  
• QCQP \(\to\) QP: \(P_i = 0\)
  
• QCQP \(\to\) SOCP
  

  \(\left\lVert \begin{pmatrix} \frac{1}{\sqrt{2}} G x \\ d - \langle p, x \rangle \\ \frac{1}{2} \end{pmatrix} \right\lVert \leq d - \langle p, x \rangle+ \frac{1}{2}\),

  e.g., \(||u - u_0||^2 \leq s \Leftrightarrow \left\lVert\begin{pmatrix} u - u_0 \\ s \\ 1/2 \end{pmatrix}\right\lVert \leq s + 1/2\)

• SOCP \(\to\) SDP
  

  \(||x|| \leq t \Leftrightarrow \begin{pmatrix} t & x^T \\ x & t I_n \end{pmatrix} \succeq 0\)

500 AD-2005

2005-Present