Complementary slackness and active constraints

ProofIntermediate⏱ 30 minAdvanced Optimizationkktcomplementary slacknessactive set

Theory: Lagrangian Duality and the KKT Conditions →

Problem

Prove that under strong duality with both optima attained, $\alpha_i^\star f_i(x^\star) = 0$ for every $i$ . Deduce that removing any constraint with $\alpha_i^\star = 0$ leaves the optimum unchanged, and explain the consequence for support vectors.

Write a complete argument. Every inequality you use should be one you could state precisely.

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems

Problem	Field	Type	Difficulty	Time
Weak duality holds without convexity	Advanced Optimization	Proof	Beginner	15 min
Derive the dual of a quadratic program	Advanced Optimization	Proof	Intermediate	30 min
A convex problem with a duality gap	Advanced Optimization	Proof	Advanced	30 min
Derive the optimal weight update abyss	Quantization	Proof	Advanced	1 hour
Projection onto the probability simplex	Advanced Optimization	Proof	Advanced	1 hour