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

Get help from others!

Recent Answers

- Peter Machado on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Joshua Engel on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP