# Duality

1. Toy example

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

as a function of the parameter $u$. Plot $p^*(u)$. Verify that $\dfrac{dp^*(0)}{du} = -\mu^*$

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, $d^* ≤ p^*$ , clearly holds when $d^* = -\infty$ or $p^* = \infty$. Show that it holds in the other two cases as well: If $p^* = −\infty$, then we must have $d^* = −\infty$, and also, if $d^* = \infty$, then we must have $p^* = \infty.$

7. Express the dual problem of

with $c \neq 0$, in terms of the conjugate function $f^*$. Explain why the problem you give is convex. We do not assume $f$ 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 $f_0(x): \mathbb{R}^n \to\mathbb{R}$ is convex and differentiable, and $\alpha \in \mathbb{R}^{m \times n}$ with $\mathbf{rank }A = m$. In a quadratic penalty method, we form an auxiliary function

where $\alpha > 0$ is a parameter. This auxiliary function consists of the objective plus the penalty term $\alpha \|Ax - b\|_2^2$. The idea is that a minimizer of the auxiliary function, $\tilde{x}$, should be an approximate solution of the original problem. Intuition suggests that the larger the penalty weight $\alpha$, the better the approximation $\tilde{x}$ to a solution of the original problem. Suppose $\tilde{x}$ is a minimizer of $\phi(x)$. Show how to find, from $\tilde{x}$, 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]}$. First introduce new variables$y_i$and equality constraints$y_i = b_i − a^\top_i x$. (The solution of this problem is called the analytic center of the linear inequalities$a^\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]}$. First introduce new variables$y_i$and equality constraints$y_i = b_i − a^\top_i x$. (The solution of this problem is called the analytic center of the linear inequalities$a^\top_i x \leq b_i ,i = [1,m]$$. Analytic centers have geometric applications, and play an important role in barrier methods.)