6
$\begingroup$

In general, suppose you have a non-convex optimization problem with constraints and you form the dual problem. If you find a local optimum for the dual problem, will the corresponding primal solution always be feasible? If not, when is it not feasible?

$\endgroup$
3
$\begingroup$

I guess you are assuming that the dual problem was obtained by only dualizing some of the constraints. The answer below makes sense if I am right about my guess.

In general, I believe the answer to your problem is no. Take for instance the multi-commodity flow problem. If you dualize the capacity constraints, then the dual problem you will be solving involves computing a min-cost flow problem for each commodity. If you treat the flows that you have obtained as the primal solution to your dual problem, then the primal solution corresponding to your optimal dual multipliers may still violate some capacity constraints when the flows for the different commodities have been aggregated.

To answer about the second problem, I do not know how to characterize when the primal solution is not feasible. However, let me tell you of a case when the primal solution will be feasible. Suppose you know that strong duality holds for your problem and the primal solution corresponding to your optimal dual multipliers is unique, then we know that the primal solution will also be feasible. I guess you can convince yourself of this fact from the KKT conditions and strong duality theorem. For an example of such a case, consider the problem of optimizing a strongly convex quadratic function over a set of linear constraints.

| improve this answer | |
$\endgroup$
2
$\begingroup$

From duality theory:

At each feasible $x$,$f(x)=\sup_{u>0,v}L(x,u,v)$, and the supremum is taken iff $u\geq 0$ satisfying $u_ih(x)=0,i=1,...,m$. The optimal value of the primal problem, named as $f^*$ satisfies:

\begin{equation} f^*=\inf_x\sup_{u>0,v}L(x,u,v) \end{equation}

This means that if the dual is feasible, the primal has to be feasible as well. If the problem is convex, then we have strong duality (subject to Slater's condition) and the values are also equal.

For non-feasible $x$, the value of the Lagrangian would be $\infty$.

However, for non-convex optimisation, failing to solve the dual problem does not imply that the primal is infeasible, merely that we failed to find a feasible point. If we prove that the dual problem is unbounded (which is a global optimisation problem), then the primal has to be infeasible.

| improve this answer | |
$\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.