# Best Possible Convex bounds for optimization problems

Suppose we have a primal problem

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

where $f(.)$ and $h_i(.)$ are possibly non-convex.

Then its Lagrangian is

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

and the dual problem is

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

Now it is well-known that $p^{*}\geq d^{*}$ and that the dual problem is convex. Is this the best possible convex lower bound in general? Are there instances of well-known problems where we know that there exists a better lower bound which also comes from a convex optimization problem.

• If you have strong duality, then $p^*=d^*$, so the lower bound is tight. For linear problems, this holds as long as either the primal or dual problem is infeasible (in which case there cannot be a tight bound). For nonlinear convex problems, strong duality holds if there is a strictly feasible point (i.e., $h_i(x_0)<0$). So you'd have to look at situations where this is violated (which might not be interesting depending on what you actually want to do -- which you haven't told us). – Christian Clason May 28 '18 at 9:05
• @ChristianClason probably my question is not well written. The cases you are talking about are familiar to me. My question was more about lower bounds in general. For instance, the dual problem (if it exists) is a convex lower bound. In the same spirit, are there other known convex lower bounds which are known to better than the dual problem. For instance, can you point out an example of a famous non-convex non-linear problem where a better known bound than the lagrangian exists. – dineshdileep May 28 '18 at 9:48
• Indeed, it is not clear to me what you want. Maybe you should be (mathematically) precise what you mean by "lower bound" and in particular by "better". – Christian Clason May 28 '18 at 13:53
• "lower bound" in the sense $p^{*}\geq d_{o}^{*}$ and "better" in the sense $d_{o}^{*} \geq d^{*}$. Here $d_{o}^{*}$ is the objective value at optimum of some convex optimization problem other than the dual problem. – dineshdileep May 28 '18 at 16:39
• But if $p^*=d^*$ (which is the case except in degenerate situations), this implies $d_0^* = d^*$, so it's not clear to me what the point would be. – Christian Clason May 29 '18 at 6:05