Lagrangian quation 7.12 #189

qbolec opened this Issue Nov 28, 2015 · 1 comment


None yet

1 participant

qbolec commented Nov 28, 2015

I think I've already reported it via the old submit form, but I can not see this issue here, so let me repost it.
I think the order of min and max quantifiers in equation 7.12 is swapped.
The narrative about game with adversary suggests that we should be the first player and the adversary chooses lambda knowing our sigmas (not the other way around).
For if lambda is known in advance, then seeing which sign it has I know that there will be no penalty for violating constraints in that direction.
You wrote, that solving the inner optimization problem yelds sigma_1 = x_1 / lambda, which I believe is not really true for two reasons:

  1. I think that by differentiating the expression and comparing to zero you get :
    -x_1/sigma_1 - lambda = 0
    which gives sigma_1 = -x_1/lambda
  2. I think that while this is the extreme point it is not really the global minimum. From the point of view of sigma_1 the important part of objective function is :

Now, this whole problem vanishes if we swap the order of quantifiers.
Then the inner optimization problem is a
max_lambda of something - lambda * (sum sigma_k - 1)
and one can see that the best choice of lambda for our adversary depends on the sign of (sum sigma_k - 1).
If it is zero, then adversary has no influence on the value.
if it is positive, then the best move is to set lambda to minus infinity
if it is negative, then adversary chooses plus infinity.

I really hope I did not make any plus/minus mistake in this description:)

qbolec commented Nov 28, 2015

The funny thing is that it does not really change the solution: indeed we should pick sigma_k to be equal to x_k/(sum x_i). But the reason for that must be different than the one presented in the text.

The part that really seems to magical to me and made me wonder in the first place is this: "we can set λ = ∑k xk and verify that this is a solution" - how come we can decide for the adversary which lambda to choose?:)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment