非凸约束优化问题中全局最小值与拉格朗日函数极大极小值的等价性问询

Hey there, great question! Let's break this down clearly—short answer is no, they don't always coincide, but there are edge cases where they might. Let's dive into the details:

First, to recap your setup: we have a nonconvex differentiable objective $f:X\to\mathbb{R}$, a differentiable constraint $g(x)\leq0$, and $X$ is convex. You're asking if the global minimum $f(x^\star)$ (where $g(x^\star)\leq0$) equals the max-min value of the Lagrangian $\max_{\lambda\geq0}\min_{x\in X}{f(x)+\lambda g(x)}$.

First, the general rules #

• Weak duality always holds: The dual value (max-min of the Lagrangian) is always a lower bound for the primal global minimum. In other words:
  $$\max_{\lambda\geq0}\min_{x\in X}{f(x)+\lambda g(x)} \leq f(x^\star)$$
  This is true regardless of convexity.
• Strong duality (equality) is NOT guaranteed for nonconvex $f$: Unlike convex optimization (where strong duality holds if Slater's condition is satisfied), nonconvexity breaks this guarantee. We can have a strict duality gap where the dual value is strictly less than the primal global minimum.

A concrete example where equality fails #

Let's use a simple case to see this gap in action:

• $X=\mathbb{R}$ (convex)
• Nonconvex objective $f(x)=x^3-3x$
• Constraint $g(x)=x^2-1\leq0$ (feasible set is $x\in[-1,1]$)

Step 1: Compute the primal global minimum

$f(x)$ is decreasing on the interval $[-1,1]$, so it's minimized at $x=1$. The global minimum value is:
$$f(x^\star)=13 - 3*1 = -2$$

Step 2: Compute the Lagrangian max-min

The Lagrangian is $\mathcal{L}(x,\lambda)=x^{3-3x+\lambda(x}2-1)$ with $\lambda\geq0$. We first minimize over all $x\in\mathbb{R}$, then maximize over $\lambda\geq0$.

For any fixed $\lambda\geq0$, as $x\to-\infty$, the $x^3$ term dominates the Lagrangian, so $\mathcal{L}(x,\lambda)\to-\infty$. That means $\min_{x\in\mathbb{R}} \mathcal{L}(x,\lambda)=-\infty$ for every $\lambda\geq0$. Taking the maximum over $\lambda\geq0$ still gives $-\infty$, which is strictly less than the primal global minimum of -2.

This is a clear case where the equality you're asking about does not hold.

When might they coincide? #

There are edge cases where strong duality still holds for nonconvex problems—for example, if the nonconvex objective happens to behave like a convex function over the feasible region, or if the constraint is tight in a way that eliminates the nonconvex parts of $f$. But these are special cases, not general rules.

In short: you can't assume the global minimum equals the Lagrangian's max-min value when dealing with nonconvex objectives. Weak duality gives you a lower bound, but equality isn't guaranteed.

备注：内容来源于stack exchange，提问作者shnnnms