1
$\begingroup$

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 ?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.