# Does strong duality hold when I dualize only a subset of the constraints?

Operations Research Asked by George Chang on August 19, 2021

Suppose I know that for some non-convex program:

begin{align}min_x&quad f(x)\text{s.t.}&quad g_i(x)leq 0, i in Cend{align}

strong duality holds for this problem. Now, suppose I form the dual by only dualizing a subset of the constraints so then the dual problem looks something like this:

begin{align}max_lambda min_x&quad f(x) + sum_{i in A}lambda_ig_i(x)\text{s.t.}&quad g_i(x)leq 0, i in Csetminus Aend{align}

Will the optimal objective value in this problem always equal the optimal objective value in the original primal problem? In other words, does "strong duality" hold between these two problems or does strong duality only hold when the dual problem is formed by dualizing all of the constraints?

If strong duality holds, then it also holds when only a subset of the constraints is dualized.

We define the following three problems: the original, the partially dualized, and the dual.

Problem (P1): begin{align}min_x&quad f(x)\text{s.t.}&quad g_i(x)leq 0, i in Cend{align}

Problem (P2): begin{align}max_{lambdage0} min_x&quad f(x) + sum_{i in A}lambda_ig_i(x)\text{s.t.}&quad g_i(x)leq 0, i in Csetminus Aend{align}

Problem (P3): begin{align}max_{muge0} max_{lambdage0} min_x&quad f(x) + sum_{i in A}lambda_ig_i(x) + sum_{i in Csetminus A}mu_ig_i(x)end{align}

It is given that strong duality holds, which means that (P1) and (P3) have the same objective value. For convenience, denote this by f(P1) = f(P3).

Using weak duality, we will show that f(P1) $$ge$$ f(P2) $$ge$$ f(P3). Because we know that f(P1) = f(P3), it must be that f(P1) = f(P2) = f(P3).

From (P1) to (P2): let $$bar{x}$$ be an optimal solution to (P1). Because $$bar{x}$$ is feasible for (P1), we have $$g_i(bar{x})le0$$ for all $$iin C$$. Next, plug $$bar{x}$$ into (P2), which is feasible. Due to the non-negativity of the multipliers, it follows for any $$lambda ge 0$$ that $$f(bar{x}) ge f(bar{x}) + sum_{i in A}lambda_ig_i(bar{x})$$. Hence, f(P1) $$ge$$ f(P2).

From (P2) to (P3): let $$bar{lambda} ge 0$$ be optimal multipliers for (P2) and let $$bar{x}$$ be corresponding optimal primal variables. Using a similar argument, $$bar{lambda}$$ and $$bar{x}$$ can be plugged into (P3). Because $$mu ge 0$$ and $$g_i(bar{x})le0$$ for all $$iin Csetminus A$$, we have for all $$mu ge 0$$ that $$quad f(bar{x}) + sum_{i in A}bar{lambda}_ig_i(bar{x}) ge f(bar{x}) + sum_{i in A}bar{lambda}_ig_i(bar{x}) + sum_{i in Csetminus A}mu_ig_i(bar{x}).$$ It follows that f(P2) $$ge$$ f(P3), which completes the proof.

Answered by Kevin Dalmeijer on August 19, 2021