Chapter Summary

Chapter Summary

Key Points

• 1.

  A set is convex if the line segment between any two of its points stays in the set; a function is convex if its epigraph is convex. The Hessian test ($\nabla^2 f \succeq 0$) is the workhorse for verifying convexity.

• 2.

  The hierarchy LP $\subset$ QP $\subset$ SOCP $\subset$ SDP organises convex programs from simplest to most general. All are solvable in polynomial time. Every wireless resource-allocation problem should first be checked for membership in this hierarchy.

• 3.

  Lagrangian duality provides lower bounds (weak duality) and, under Slater's condition, exact solutions (strong duality). The KKT conditions are the necessary and sufficient optimality conditions for convex problems with strong duality.

• 4.

  Water-filling is the canonical application of KKT: $p_i^\star = (\mu - \sigma_i^2 / g_i)^+$ allocates power only to sub-channels whose noise floor is below the water level $\mu$.

• 5.

  Gradient descent converges at $O(1/k)$ for convex functions and $O((1 - \mu/L)^k)$ for strongly convex functions. The condition number $\kappa = L/\mu$ controls convergence speed. Projected and proximal variants handle constraints and non-smooth terms.

• 6.

  Many wireless problems (scheduling, detection, antenna selection) are NP-hard combinatorial problems. LP/SDP relaxation and greedy algorithms with submodularity provide principled approximations with provable guarantees.