How can we derive the dual problem?
max$_{x} v^{T} x$
subject to $w^{T} x \le W, 0 \le x_i \le 1 ( i=1,...,n )$
where $ v \in \Bbb {R}^{n}, w_i \in \Bbb {R}^{n} $ and $ W \in \Bbb {R} $
Asked
Active
Viewed 31 times
-1
-
What is $w$? if $v \in R$, then how can you write $v^Tx$ assuming $x \in R^n$ ? Plz correct your Q. – CKM Dec 13 '15 at 06:17
1 Answers
0
Hint: Assuming $v \in R^n$, you can rewrite your problem as:
\begin{equation*} \begin{aligned} & \underset{x}{\text{-minimize}} & & -v^Tx \\ & \text{subject to} & & w^Tx \leq W, x \leq 0, -x \leq 1 \; . \end{aligned} \end{equation*}
Forming Lagrangian, we get: \begin{equation} L(x,\lambda,\mu_1,\mu_2)=v^Tx +\lambda(w^Tx-W)+\mu_1x+\mu_2(-x-1) \end{equation} Now, you can find dual by solving the following: \begin{equation} D(\lambda,\mu_1,\mu_2)=\min_x L(x,\lambda,\mu_1,\mu_2) \end{equation}
CKM
- 1,594