假设我们有一个原始问题

$$p^{*}=\min_x f(x), \\\text{s.t.}~~ h_i(x) \leq 0,$$

在哪里$f(.)$和$h_i(.)$可能是非凸的。

那么它的拉格朗日量是

$$\mathcal{L}(x,z_i)= f(x) + \sum_i z_i h_i(x)$$

双重问题是

$$d^{*}=\max_{z_i\geq 0} \min_x \mathcal{L}(x,z_i)$$

现在众所周知的是$p^{*}\geq d^{*}$并且对偶问题是凸的。这是一般最好的凸下限吗？是否存在众所周知的问题实例，我们知道存在更好的下界，这也来自凸优化问题。