Derive the dual of a quadratic program

ProofIntermediate⏱ 30 minAdvanced Optimizationdualityquadratic programderivation

Theory: Lagrangian Duality and the KKT Conditions →

Problem

Derive the Lagrangian dual of

\min_x\ \tfrac12x^\top Qx + c^\top x \quad\text{subject to}\quad Ax\le b,

with $Q\succ0$ . Verify that the dual is a concave maximisation over the non-negative orthant, and give the map recovering $x^\star$ from $\alpha^\star$ .

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
Complementary slackness and active constraints	Advanced Optimization	Proof	Intermediate	30 min
Derive Hoeffding's inequality from Hoeffding's lemma	High-Dim Probability	Proof	Intermediate	30 min
A convex problem with a duality gap	Advanced Optimization	Proof	Advanced	30 min
Derive the DPO objective abyss	LLMs	Proof	Graduate	1 hour