I want to ask whether the following question has a closed form solution: { <mtable

Edith Mayer

Edith Mayer

Answered question

2022-04-07

I want to ask whether the following question has a closed form solution:
{ min x c T x  s.t.  1 T x = b x 0
We can write down the kkt condition as:
L = c T x λ 1 , 1 T x b λ 2 , x L / x = c 1 λ 1 λ 2 = 0 [ λ 2 ] i x i = 0 [ λ 2 ] i 0
Denote ith component of c as c i . Now we can see that when ( c i λ 1 ) 0, then we must have x i = 0 and ( c i λ 1 ) = 0, we also must have x i > 0. But I am not sure how to proceed to the next.

Answer & Explanation

Lara Alvarez

Lara Alvarez

Beginner2022-04-08Added 14 answers

You are almost there. First, notice that c λ 1 1 λ 2 = 0 λ 2 = c λ 1 1 . Plugging this back into L we get that,
L = c T x λ 1 , 1 T x b λ 2 , x = c T x λ 1 , 1 T x b c λ 1 1 , x = λ 1 b
Second, you are technically missing the condition that 1 T x = b and x 0 in your KKT conditions.
Lastly, you found that for all i that c i λ 1 . There are two cases you need to check, λ 1 = min i c i or λ 1 < min i c i . If λ 1 < min i c i then [ λ 2 ] i > 0 for all i, which implies that x i = 0 for all i. This can only occur if b = 0 and is a kind of a degenerate case since the constraint 1 T x = 0 plus x 0 implies x = 0. If b > 0 then it must be the case that λ 1 = min i c i . From here it should be straightforward to determine what λ 2 is and also what x i is.

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Multivariable calculus

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?