I am learning Non-Linear optimisation. Last time I read about KKT (Prof notes and some googling) and Basic constraint qualification and somehow tried to convince myself this and that but now when I am revising it, I feel that I am just storing everything without proper understanding of what is going on.
For equality constraint we form a function (Lagrangian function) , and try to optimise it using unconstrained optimisation i.e $ \nabla f(x) $. Ques: Why does this work ? How can i visualise it?
Then for inequality constraints we can write every inequality constraint as equality constraint :
$$ g(x) \ge C $$ is equal to
$$ g(x) + S^2 = C $$
Now equality constraint problem can be solved as we solved 1. We will get following conditions
$$ \nabla f(x) + \sum{\lambda \nabla g(x)} $$ $$ g(x) \ge C $$ $$ h(x) = K $$ $$ \lambda(i) * g(x) = 0 $$
Now till here It made sense to me if I assumed 1 to be correct. After that I read that these are necessary conditions but not sufficient conditions and since then I am scrolling over and over but unable to find a proper place that summarises what is going on.
I read (in prof notes) that BCQ : Basic constraint qualification, says that if BSC is satisfied the KKT multipliers exist. Now what is meaning of they exist ? They exist as in can be found ? That I can know from solving the above 4 equations is not it?
If it means that BCQ is sufficient condition, later he writes that holding BCQ doesn't mean that a given x* is minima. Now if it doesn't hold why we were dealing with BCQ in first place?
I just want to ask :
- Why Lagrangian method of optimising works?
- How KKT Works, what are necessary and sufficient conditions?
- What are we trying to do using BCQ and why even if BCQ is satisfied the multipliers doesn't exist?
- What is the meaning of "multipliers exist"?
- Something that you learned and feel that this should be known for better understanding of this topic.