1
$\begingroup$

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.

$\endgroup$

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.