Second-order cone program
=========================

A second-order cone program (SOCP) is an optimization problem of the
form

.. math::

     
       \begin{array}{ll}
       \mbox{minimize}   & f^Tx\\
       \mbox{subject to} & \|A_ix + b_i\|_2 \leq c_i^Tx + d_i, \quad i=1,\ldots,m \\
                         & Fx = g,
       \end{array}

where :math:`x \in \mathcal{R}^{n}` is the optimization variable and
:math:`f \in \mathcal{R}^n`, :math:`A_i \in \mathcal{R}^{n_i \times n}`,
:math:`b_i \in \mathcal{R}^{n_i}`, :math:`c_i \in \mathcal{R}^n`,
:math:`d_i \in \mathcal{R}`, :math:`F \in \mathcal{R}^{p \times n}`, and
:math:`g \in \mathcal{R}^p` are problem data.

An example of an SOCP is the robust linear program

.. math::

     
       \begin{array}{ll}
       \mbox{minimize}   & c^Tx\\
       \mbox{subject to} & (a_i + u_i)^Tx \leq b_i \textrm{ for all } \|u_i\|_2 \leq 1, \quad i=1,\ldots,m,
       \end{array}

where the problem data :math:`a_i` are known within an
:math:`\ell_2`-norm ball of radius one. The robust linear program can be
rewritten as the SOCP

.. math::

     
       \begin{array}{ll}
       \mbox{minimize}   & c^Tx\\
       \mbox{subject to} & a_i^Tx + \|x\|_2 \leq b_i, \quad i=1,\ldots,m,
       \end{array}

When we solve a SOCP, in addition to a solution :math:`x^\star`, we
obtain a dual solution :math:`\lambda_i^\star` corresponding to each
second-order cone constraint. A non-zero :math:`\lambda_i^\star`
indicates that the constraint :math:`\|A_ix + b_i\|_2 \leq c_i^Tx + d_i`
holds with equality for :math:`x^\star` and suggests that
changing :math:`d_i` would change the optimal value.

Example
-------

In the following code, we solve a SOCP with CVXPY.

.. code:: python

    # Import packages.
    import cvxpy as cp
    import numpy as np
    
    # Generate a random feasible SOCP.
    m = 3
    n = 10
    p = 5
    n_i = 5
    np.random.seed(2)
    f = np.random.randn(n)
    A = []
    b = []
    c = []
    d = []
    x0 = np.random.randn(n)
    for i in range(m):
        A.append(np.random.randn(n_i, n))
        b.append(np.random.randn(n_i))
        c.append(np.random.randn(n))
        d.append(np.linalg.norm(A[i] @ x0 + b, 2) - c[i].T @ x0)
    F = np.random.randn(p, n)
    g = F @ x0
    
    # Define and solve the CVXPY problem.
    x = cp.Variable(n)
    # We use cp.SOC(t, x) to create the SOC constraint ||x||_2 <= t.
    soc_constraints = [
          cp.SOC(c[i].T @ x + d[i], A[i] @ x + b[i]) for i in range(m)
    ]
    prob = cp.Problem(cp.Minimize(f.T@x),
                      soc_constraints + [F @ x == g])
    prob.solve()
    
    # Print result.
    print("The optimal value is", prob.value)
    print("A solution x is")
    print(x.value)
    for i in range(m):
        print("SOC constraint %i dual variable solution" % i)
        print(soc_constraints[i].dual_value)


.. parsed-literal::

    The optimal value is -9.582695716265503
    A solution x is
    [ 1.40303325  2.4194569   1.69146656 -0.26922215  1.30825472 -0.70834842
      0.19313706  1.64153496  0.47698583  0.66581033]
    SOC constraint 0 dual variable solution
    [ 0.61662526  0.35370661 -0.02327185  0.04253095  0.06243588  0.49886837]
    SOC constraint 1 dual variable solution
    [ 0.35283078 -0.14301082  0.16539699 -0.22027817  0.15440264  0.06571645]
    SOC constraint 2 dual variable solution
    [ 0.86510445 -0.114638   -0.449291    0.37810251 -0.6144058  -0.11377797]