Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have been reading a lot about nonlinear optimization and duality, and it seems that duality theory is extremely useful. I feel that I am missing some of the negative aspects/difficulties associated with it though and am hoping that someone can give me some more perspective.

The fact that the dual function is always concave, for any nonlinear primal optimization problem, seems like quite a significant result. Now I know that the duality gap associated with the optima of the primal and dual may be non-zero, but I feel that I don't have a sense for how large this gap can be for some of the common (nonlinear) problems that arise in optimization.

What are some useful techniques for ensuring that strong duality holds, or being able to say that the duality gap is small enough for practical purposes? Is forming the dual function in attempts to solve a nonlinear program typically a good first-step?

I know this is a rather vague post but I am just hoping to gain some more intuition about the practical usefulness of duality theory in nonlinear optimization.

share|improve this question
    
I would try asking a more specific question. You can't ensure strong duality holds for all problems. But in all real-world driven problems I've encountered there has been no duality gap. –  Jeff Snider Jan 21 at 19:53

1 Answer 1

I can partially answer one question you're asking.

One common method for ensuring that strong duality holds in convex problems (and convex problems only) is Slater's condition. Consider a problem of the form: \begin{equation} \min f_0(x) \end{equation} subject to \begin{equation} f_i(x) \leq 0, \,\,\,\,\,\,\,\, i = 1, \ldots, m \end{equation} and \begin{equation} Ax = b \end{equation} where $f_i(x)$ is convex for every $i \in \{1, \ldots, m\}$. Define the set $D$ as the intersection of the domains of the functions $f_i$, i.e., $D = \cap_{i = 0}^{m} dom(f_i)$. Slater's condition says that if there is some $x \in relint(D)$ (where $relint(D)$ denotes the relative interior of $D$) such that \begin{equation} f_i(x) < 0 \end{equation} for each $i = 1, \ldots, m$ and that same $x$ satisfies $Ax = b$, then strong duality holds. Here, using the relative interior of $D$ rather than the interior of $D$ means that linear inequalities do not need to be strict; if there is some $f_j(x)$ that is linear in $x$, then Slater's condition holds as long as $f_j(x) \leq 0$. In other words being just equal to $0$ is allowed for linear inequality constraints when applying Slater's condition. There are of course other methods, termed "constraint qualifications," for guaranteeing strong duality, but Slater's condition is used frequently since it is so simple.

As is often the case in optimization, it is hard to say anything general about the non-convex case and I don't believe that any broad generalizations about strong duality for the non-convex case can be made.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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