Is the result of dual function valid?

Question

I have a question about dual function in Machine Learning.

According to my understanding, dual problem is:
Give a difficult optimization problem: $$\min \limits_x f(x) \\ \text{subject to: } \left \{ \begin{matrix} Ax = b \\ Gx \leq h \end{matrix}\right .$$ The idea is that if our problem is so difficult, then we can maximize the lower bound instead. We create a lower bound by Lagrange approach:
$$ f(x) \ge L(x, u, v) = f(x) + u^T(Ax-b) + v^T(Gx-h) \text{ with } v \ge 0$$ $$\Rightarrow \min \limits_x f(x) \ge \min \limits_x L(x, u, v)$$ Then we find x by: $$\nabla_xL(x, u, v) = 0 \Rightarrow x = t(u, v) \text{ with } t(u, v) \text{ is a function of u and v.}$$ After that, let $$g(u, v) = L(t(u, v), u, v)$$ Our dual problem is that: $$\max \limits_{u, v} g(u, v) \\ \text{subject to: } v \ge 0$$

My question is that: what will happen if our result u and v make x be not feasible, $Ax \neq b \text{ and/or } Gx > h$ ? Because if x is not feasible, we will not have $f(x) \ge L(x, u, v)$, then our solution is wrong.
Is there any way to proof that u and v always make x be feasible ? Or unfeasible x is OK ?

Answer 1

I think you got some misunderstandings here.

To answer your questions:

• There's no way to proof that all results of u and v can make x feasible, because it does not exist.
• Unfeasible x may be OK, depend on your purpose. In this problem, I see that you want to find the largest lower bound, so unfeasible x is OK. But if you want to find the x, then it's not OK.

I think you got that you need to find the lower bound but you are confusing that: Does the lower bound $g(u, v)$ always exist even if x is unfeasible ? The answer is yes.
I will proof it right here:

• First, I will rewrite your difficult optimization problem: $$\min \limits_{x \in C} f(x) \\ \text{with } C = \{x \in R^n | Ax=b \text{ and } Gx \le h\}$$
• Then, when you you use that $f(x) \ge L(x, u, v)$, it must be $$f(x) \ge L(x, u, v) \text{ }\forall \text{ } x \in C$$ $$\Rightarrow \min \limits_{x \in C} f(x) \ge \min \limits_{x \in C} L(x, u, v) \ge \min \limits_{x \in R^n} L(x, u, v)$$
• Finally, you put $g(u, v) = \min \limits_{x \in R^n} L(x, u, v)$, then solve the dual problem: $$\max \limits_{(u, v) \in D} g(u, v) \\ \text{with } D = \{(u, v) \in R^{n+n} | v \succeq 0\}$$
• If you can solve that, you will get the lower bound of primal problem, and in contrast, if you can's solve then you do not get it.

But notice that all functions have its smallest value, even it's $-\infty$, then your primal problem always has the lower bound $g(u, v)$.
I think that the lack of "$\forall \text{ } x \in C$" is the reason for your misunderstanding.