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


6

假設我知道某些非凸程序:

\ 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}

此問題的最優目標值是否總是等於原始原始問題的最優目標值?換句話說,這兩個問題之間是否存在"強對偶性",或者僅當通過雙重約束所有約束形成對偶問題時,強對偶性才成立?

7

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.