# 當我僅對約束的一個子集進行對偶時，強對偶性成立嗎？

\ begin {align} \ min_x＆\ quad f（x）\\\ text {st}＆\ quad g_i（x）\ leq 0，i \ in C \ end{align}

">開始{align} \ max_ \ lambda \ min_x＆\ quad f（x）+ \ sum_ {i \ in A} \ lambda_ig_i（x）\\\ text {st}＆\ quad g_i（x）\ leq 0，我\ in C \ setminus A \ end {align}

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 C\end{align}

Problem (P2): \begin{align}\max_{\lambda\ge0} \min_x&\quad f(x) + \sum_{i \in A}\lambda_ig_i(x)\\\text{s.t.}&\quad g_i(x)\leq 0, i \in C\setminus A\end{align}

Problem (P3): \begin{align}\max_{\mu\ge0} \max_{\lambda\ge0} \min_x&\quad f(x) + \sum_{i \in A}\lambda_ig_i(x) + \sum_{i \in C\setminus 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 $$i\in 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 $$i\in C\setminus 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 C\setminus A}\mu_ig_i(\bar{x}).$$ It follows that f(P2) $$\ge$$ f(P3), which completes the proof.