2
$\begingroup$

I'm trying to solve a simple LP using Lagrangian method. But I don't know how to use the soloution of the dual problem to find the solution of the main LP.

I consider the following simple problem: $$ \min_{x} \sum_{i=1}^n -f_ix_i $$ $$ \text{s.t.}\quad \sum_{i=0}^n x_i=1, x\ge 0 $$

The general form is: $$ \min c^Tx $$ $$ \text{s.t.}\quad Ax=b, x\ge 0 $$

In my problem: $A=[1 \, 1\,1 \cdots \,1]$, $c=-f=[-f_1\,-f_2\,\cdots\,-f_n]^T$ and $b=1$.

The dual problem will be: $$\max \,-v$$ $$\text{s.t. }A^Tv-f\ge 0$$

The constraint means: $$\forall i\le n, \, v\ge f_i\Rightarrow -v\le -f_i$$ $$\Rightarrow -v\le \min{-f_i} \Rightarrow \,-v= \min{-f_i}= -\max f_i\Rightarrow v=\max f_i$$

Therefore I've solved the dual problem. but what is the solution of the original problem? My question is:

In general how can I find the solution $x$ after solving the dual problem for $v$?

$\endgroup$
1
$\begingroup$

Complementary Slackness Principle tells us that either the inequality $i$ in $A^Tv_{opt}-f\ge 0$ becomes equality or $x_i=0$. Assuming all the numbers $f_i$ are distinct and $\nu_{opt}=\max f_i=f_k$. Then $\nu_{opt}>f_i$ for $i\ne k$, hence, $x_i=0$ for $i\ne k$. Clearly then $x_k=1$.

$\endgroup$
  • $\begingroup$ Thanks for answering. Is it similar to KKT? I didn't understand the descriptions of Wikipedia for complementary slackness. $\endgroup$ – SMA.D Dec 20 '18 at 8:50
  • $\begingroup$ @SMA.D It is a part of KKT. For inequalities $g(x)\le 0$ the Lagrange function is $f(x)+u^Tg(x)$, then in KKT there is a condition that $u_i g_i(x)=0$. It is CSP. $\endgroup$ – A.Γ. Dec 20 '18 at 8:57

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.