6
$\begingroup$

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 C\end{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 C\setminus A\end{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?

$\endgroup$
  • 3
    $\begingroup$ Maybe you can use weak duality to squeeze the "new" dual between the old dual and the optimal value? $\endgroup$ – Sune Jul 17 at 16:37
7
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.