# Is duality theory in optimization as useful as it seems?

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.

-
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 '14 at 19:53

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: $$\min f_0(x)$$ subject to $$f_i(x) \leq 0, \,\,\,\,\,\,\,\, i = 1, \ldots, m$$ and $$Ax = b$$ 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 $$f_i(x) < 0$$ 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.