On page 12 in https://see.stanford.edu/materials/aimlcs229/cs229-notes3.pdf, the author uses the claim that the gradient of the lagrangian with respect to the non-constraint variables is zero. Why is this true? When we're trying to minimize the lagrangian for fixed $\alpha$ - a constraint variable, how does it follow that the minimum is at a point of local minima/stationary point, and the function isn't perhaps unbound? Does it follow from convexity of the lagrangian (convexity implies that a local minima is global)? Or does it have something to do with KKT conditions?

Could someone give me a counterexample of type:

$\textrm{max}_{\lambda} \textrm{min}_x f(x,\lambda) \neq \textrm{max}_{\lambda} \tilde{f}(\lambda)$

where $\tilde{f}{(\lambda)}$ is chosen to be $f(x_0,\lambda)$ for some $x_0$ local minima of $f$ with respect to $\lambda$ being fixed (assuming that a local minima exists for each $\lambda$). I think a function like $f(x,\lambda) = x^3$ could be an example.

Alternatively, in the equation above, is there some sort of neat condition on $\tilde{f}$ could imply an equality? Suppose that the actual extrema is reached at $f(x^*,\lambda^*)=M$ and that we're interested in somehow defining $\tilde{f}$ based on $f$, using $\tilde{f}(\lambda) = f(x_0,\lambda)$ for some choice of $x_0$.

Working with $x_0$ being chosen as some (existing) stationary point with respect to a fixed $\lambda$, and assuming that $x^*$ is the unique stationary point with respect to $\lambda^*$ where minimum is reached with respect to fixed $\lambda^*$, all that's necessary is for the value of $f$ in all the other stationary points to be lower than $M$. But I'm not sure if there's some sort of neat condition that would imply that.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.