Duality

Toy example
 Give the feasible set, the optimal value, and the optimal solution.
 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 .
 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?
 Let denote the optimal value of the problem
as a function of the parameter . Plot . Verify that

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

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

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

New variables. Consider an unconstrained problem of the form:
And its equivalent reformulation:
 Find Lagrangian of the primal problems
 Find the dual functions
 Write down the dual problems

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

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.

Least Squares. Let we have the primal problem:
 Find Lagrangian of the primal problem
 Find the dual function
 Write down the dual problem
 Check whether problem holds strong duality or not
 Write down the solution of the dual problem

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

Twoway partitioning problem. Let we have the primal problem:
 Find Lagrangian of the primal problem
 Find the dual function
 Write down the dual problem
 Check whether problem holds strong duality or not
 Write down the solution of the dual problem
 Can you reduce this problem to the eigenvalue problem? 🐱

Entropy maximization. Let we have the primal problem:
 Find Lagrangian of the primal problem
 Find the dual function
 Write down the dual problem
 Check whether problem holds strong duality or not
 Write down the solution of the dual problem

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

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

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

Nonconvex strong duality Let we have the primal problem:
 Find Lagrangian of the primal problem
 Find the dual function
 Write down the dual problem
 Check whether problem holds strong duality or not
 Write down the solution of the dual problem

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.

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.)