If the Lagrangian dual function is always concave, why aren't we "just" solving dual problems optimally?

Question

Let $\mathcal{P}$ be the following primal optimization problem

\begin{align} \mathcal{P}: \text{minimize}_x \quad & f_0(x)\\ \text{subject to} \quad & f_i(x) \leq 0, \quad i = 1, ..., m \\ & h_i(x) = 0, \quad i = 1, ...,p \end{align}

Let $\mathbf{\lambda}$ be a vector of dual variables associated with the inequality constraints and $\mathbf{\nu}$ be a vector of dual variables associated with the equality constraints.

The Lagrangian dual function for this problem can be stated as

$$ g(\lambda, \nu) = \inf_{x \in \mathcal{D}} \Bigg(f_0(x) + \sum_{i = 1}^m \lambda_i f_i(x) + \sum_{i = 1}^p \nu_i h_i(x) \Bigg) $$

The Lagrangian dual function (LDF) is always concave — even when the primal problem $\mathcal{P}$ is not convex. From the LDF, we can write the Lagrangian dual problem, $\mathcal{D}$, as follows

\begin{align} \mathcal{D}: \text{maximize}_{\lambda, \nu} \quad & g(\lambda,\nu)\\ \text{subject to} \quad & \lambda \geq 0 \end{align}

Q1: Can I assume $\mathcal{D}$ is always concave, given that the LDF is always concave?

If the answer to the Q1 is "Yes", then

Q2: Why aren't we "just" taking duals and solving them optimally?

The only answer I could come up with for Q2 is related to strong duality. When strong duality does not hold, the optimal solution from the dual problem is not feasible for the primal problem. Therefore, solving a concave dual problem won't help because the solution won't apply to the real-world problem we modeled as the primal optimization problem. Is my reasoning correct? Am I missing something?

Answer 1

It is difficult to reason about duality in the general NLP form you have stated. Consider instead the following notation:

$$ \begin{array}{rl} z_P = \text{min}& c^T x,\\ \text{s.t}& Ax = b,\\ & x \in X, \end{array} $$

for an arbitrary set X, which satisfies weak duality to its Lagrangian dual problem $$ \begin{array}{rl} z_D = \text{max}& b^T y,\\ \text{s.t}& A^T y + s = c,\\ & s \in X^*, \end{array} $$

as proven by $$ z_P - z_D = c^T x - b^T y = c^T x - (Ax)^T y = x^T (c - A^T y) = x^T s \geq 0, $$

where nonnegativity follows by definition of $X^* = \{ s \;|\; s^T x \geq 0, \forall x \in X \}$, which is commonly denoted the dual cone of $X$. Taking the Lagrangian dual of the Lagrangian dual problem leads to

$$ \begin{array}{rl} z_{P'} = \text{min}& c^T x,\\ \text{s.t}& Ax = b,\\ & x \in (X^*)^*, \end{array} $$

in which $(X^*)^*$ is the closed conical hull of $X$. By weak duality, and $X \subseteq (X^*)^*$, it follows that $$ z_P \geq z_{P'} \geq z_D, $$

which gives you a feeling of the duality gap. Namely, the Lagrangian dual problem with value, $z_D$, is at least as weak as the original problem in which you replaced the set X by its closed conical hull.

For particular objectives, $c^T x$, you may be lucky that the intersection of $X$ and $(X^*)^*$ contains an optimal point. In general, however, you should expect stronger Langrangian duals if you reformulate your problem such that $X$ is closer to $(X^*)^*$. That is, closer to being a nonempty closed convex cone.

If $X$ is a nonempty closed convex cone, you are guaranteed to have $z_P = z_{P'}$, and so will only observe duality gaps on illposed problems (e.g., without Slater point). Conic modeling with the cones of MOSEK gives you this nice property, and have shown capable of representing most convex nonlinear problems that people care about.

You may also want to watch the first 7 minutes of my video presentation, The conic advantage in MINLP, where I explain other advantages of migrating from the general NLP form to conic standard form, even if the problem is nonconvex!