Operations Research Asked on August 19, 2021

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?

From duality theory:

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

begin{equation} f^*=inf_xsup_{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.

Answered by Nikos Kazazakis on August 19, 2021

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.

Answered by batwing on August 19, 2021

1 Asked on September 1, 2020

1 Asked on July 27, 2020 by betty

0 Asked on July 24, 2020 by daniel

constraint programming linear programming mixed integer programming

Get help from others!

Recent Answers

- Joshua Engel on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- haakon.io on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?

Recent Questions

- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?
- Does Google Analytics track 404 page responses as valid page views?
- Why fry rice before boiling?

© 2022 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP