Duality

  1. Toy example

    1. Give the feasible set, the optimal value, and the optimal solution.
    2. Plot the objective versus . On the same plot, show the feasible set, optimal point and value, and plot the Lagrangian versus for a few positive values of . Verify the lower bound property ( for ). Derive and sketch the Lagrange dual function .
    3. State the dual problem, and verify that it is a concave maximization problem. Find the dual optimal value and dual optimal solution . Does strong duality hold?
    4. Let denote the optimal value of the problem

    as a function of the parameter . Plot . Verify that

  2. Dual vs conjugate. Consider the following optimization problem

    1. Find Lagrangian of the primal problem
    2. Find the dual function
    3. Write down the dual problem
  3. Dual vs conjugate.Consider the following optimization problem

    1. Find Lagrangian of the primal problem
    2. Find the dual function
    3. Write down the dual problem
  4. Dual vs conjugate.Consider the following optimization problem

    1. Find Lagrangian of the primal problem
    2. Find the dual function
    3. Write down the dual problem
  5. New variables. Consider an unconstrained problem of the form:

    And its equivalent reformulation:

    1. Find Lagrangian of the primal problems
    2. Find the dual functions
    3. Write down the dual problems
  6. The weak duality inequality, , clearly holds when or . Show that it holds in the other two cases as well: If , then we must have , and also, if , then we must have

  7. Express the dual problem of

    with , in terms of the conjugate function . Explain why the problem you give is convex. We do not assume is convex.

  8. Least Squares. Let we have the primal problem:

    1. Find Lagrangian of the primal problem
    2. Find the dual function
    3. Write down the dual problem
    4. Check whether problem holds strong duality or not
    5. Write down the solution of the dual problem
  9. Standard form LP. Let we have the primal problem:

    1. Find Lagrangian of the primal problem
    2. Find the dual function
    3. Write down the dual problem
    4. Check whether problem holds strong duality or not
    5. Write down the solution of the dual problem
  10. Two-way partitioning problem. Let we have the primal problem:

    1. Find Lagrangian of the primal problem
    2. Find the dual function
    3. Write down the dual problem
    4. Check whether problem holds strong duality or not
    5. Write down the solution of the dual problem
    6. Can you reduce this problem to the eigenvalue problem? 🐱
  11. Entropy maximization. Let we have the primal problem:

    1. Find Lagrangian of the primal problem
    2. Find the dual function
    3. Write down the dual problem
    4. Check whether problem holds strong duality or not
    5. Write down the solution of the dual problem
  12. Minimum volume covering ellipsoid. Let we have the primal problem:

    1. Find Lagrangian of the primal problem
    2. Find the dual function
    3. Write down the dual problem
    4. Check whether problem holds strong duality or not
    5. Write down the solution of the dual problem
  13. Equality constrained norm minimization. Let we have the primal problem:

    1. Find Lagrangian of the primal problem
    2. Find the dual function
    3. Write down the dual problem
    4. Check whether problem holds strong duality or not
    5. Write down the solution of the dual problem
  14. Inequality form LP. Let we have the primal problem:

    1. Find Lagrangian of the primal problem
    2. Find the dual function
    3. Write down the dual problem
    4. Check whether problem holds strong duality or not
    5. Write down the solution of the dual problem
  15. Nonconvex strong duality Let we have the primal problem:

    1. Find Lagrangian of the primal problem
    2. Find the dual function
    3. Write down the dual problem
    4. Check whether problem holds strong duality or not
    5. Write down the solution of the dual problem
  16. A penalty method for equality constraints. We consider the problem minimize

    where is convex and differentiable, and with . In a quadratic penalty method, we form an auxiliary function

    where is a parameter. This auxiliary function consists of the objective plus the penalty term . The idea is that a minimizer of the auxiliary function, , should be an approximate solution of the original problem. Intuition suggests that the larger the penalty weight , the better the approximation to a solution of the original problem. Suppose is a minimizer of . Show how to find, from , a dual feasible point for the original problem. Find the corresponding lower bound on the optimal value of the original problem.

  17. Analytic centering. Derive a dual problem for

    with domain $${x a^\top_i x < b_i , i = [1,m]}y_iy_i = b_i − a^\top_i xa^\top_i x \leq b_i ,i = [1,m]$$. Analytic centers have geometric applications, and play an important role in barrier methods.)
    with domain $${x a^\top_i x < b_i , i = [1,m]}y_iy_i = b_i − a^\top_i xa^\top_i x \leq b_i ,i = [1,m]$$. Analytic centers have geometric applications, and play an important role in barrier methods.)