# How to recover primal problem from its dual counterpart

I am asking this from context of optimization in machine learning. We often talk about a primal problem and how this primal problem can be solved by first converting it into a dual problem (Using Lagrange Duality concept).

However, I want to ask if opposite also holds i.e. given a dual problem formulation, is it possible to obtain its primal formulation ? What steps are required for the same ? Any resources online ?

## 1 Answer

In general, it is not (always) possible to obtain the primal form the dual.

The Dual problem is always a convex optimization problem (minimizing a convex function or maximizing a concave function, subject to convex constraints) - see Proposition 11.4 of http://www.stat.cmu.edu/~ryantibs/convexopt-F15/scribes/11-dual-gen-scribed.pdf . So the dual of the dual is always a convex optimization problem, which means it can not be equal or equivalent to the primal unless the primal is a convex optimization problem.

If there is no duality gap, as would be the case for a convex optimization problem satisfying the Slater Constraint Qualification https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions#Regularity_conditions_(or_constraint_qualifications), the dual of the dual is equivalent to the primal in the sense of having the same optimal argument value (argmin or argmax) and optimal objective value. Primal-Dual Interior Point solvers for convex optimization are predicated on the Slater Constraint Qualification, and try to drive the optimality gap to within an acceptable numerical tolerance of zero; and if the Slater Constraint Qualification is not satisfied, may fail to do so. See section 5.5.5 of "Convex Optimization", by Boyd and Vandenberghe http://web.stanford.edu/~boyd/cvxbook/ for how to recover the primal optimal solution from the dual solution.