Weak duality holds without convexity

ProofBeginner⏱ 15 minAdvanced Optimizationdualityweak dualitylagrangian

Theory: Lagrangian Duality and the KKT Conditions →

Problem

Prove weak duality $d^\star\le p^\star$ for the general problem $\min f_0(x)$ subject to $f_i(x)\le0$ , $h_j(x)=0$ , stating exactly which properties of the Lagrangian are used. Give an example with a strictly positive duality gap.

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
Complementary slackness and active constraints	Advanced Optimization	Proof	Intermediate	30 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 hard-margin SVM dual abyss	Classical ML	Proof	Graduate	3 hours