Optimization

Convexity, gradients, constraints and duality

About this course

Optimisation as a subject: why convexity is the right object, how gradient methods behave, what constraints change, and what duality buys.

What you will be able to do

  • Recognise convex sets and functions and explain the global-optimum guarantee
  • Analyse gradient descent's rate in terms of smoothness and conditioning
  • Apply momentum, Newton and stochastic methods, and say when each helps
  • Handle constraints with Lagrange multipliers and the KKT conditions
  • Form the dual, interpret the duality gap, and solve linear programs

What this course covers

  • Linear programs and the collapse to finite candidates
  • Basis vs. vertex: degeneracy distinction
  • Fundamental theorem of linear programming
  • Linear programming duality and certificates
  • Unboundedness: when no optimum exists
  • Degeneracy, shadow prices, and the kink in the value function
  • Gradient Descent Algorithm and Step-Size Problem
  • Steepest Descent Direction via Cauchy-Schwarz
  • L-Smoothness and the Descent Lemma
  • Step-Size Strategies: Fixed, Exact Line Search, Backtracking
  • Convergence Rate: Order 1/K for Convex Smooth Problems
  • Zigzag Phenomenon and the Condition Number
  • Worked Example and Master Summary
  • The Dual Function: Definition and Concavity
  • Weak Duality Theorem
  • Certificates: Valid vs. Useful Bounds
  • Strong Duality and Slater's Condition
  • Why Non-Negativity of Prices Is Not Decoration
  • The Duality Gap on a Non-Convex Problem
  • Slater's Condition: Sufficiency, Not Necessity
  • Optimality Verification via the Sandwich Argument
  • Failure of unconstrained optimality conditions
  • Feasible set and its corners by wall-pair enumeration
  • Active and inactive constraints; the active set
  • Replacement optimality condition for constrained problems
  • Gradient balanced against the active wall, not zero
  • Active set depends on the solution, not the constraints
  • Enumeration as a bridge and its scaling limit
  • Optimization vocabulary: objective, feasible set, minimizer vs minimum
  • First-order necessary condition (Fermat's rule)
  • Second-order test and its limits
  • Local vs global minimizers and basins of attraction
  • Higher dimensions: saddle points and exponential critical-point growth
  • Convexity as certificate: tangent global underestimator
  • Working procedure and course architecture
  • Simplex method and the Klee–Minty exponential tour
  • Worst-case as a maximum over a constructed family
  • Pivot rules and exponential growth rates
  • Honest interpretation of simplex's practical performance
  • Interior-point methods and the central path
  • Non-convex objective: local optimality without global guarantee
  • Convexity as the foundation of all course guarantees
  • Strong convexity and the two-parabola sandwich
  • Linear (geometric) convergence of gradient descent
  • Tikhonov regularisation as a fix for µ = 0
  • The condition number κ and the cost formula
  • κ as a property of coordinates, not the problem
  • Diagonal preconditioning
  • Worked procedure and diagnostic checklist
  • Convex set definition and segment test
  • Standard examples and non-examples of convex sets
  • Operations that preserve convexity
  • Standard convex families
  • Convex hull and Carathéodory's theorem
  • Separating and supporting hyperplane theorems
  • Worked example: convexity, vertices, and separation certificate
  • Convex function: chord definition and vocabulary
  • Epigraph and its connection to convex sets
  • First-order (tangent) condition for convexity
  • Second-order (Hessian) condition and calculus of convexity
  • Jensen's inequality
  • Key convex function examples: XlogX, logsumexp
  • Working procedure, cautions, and capstone example
  • Active vs. slack constraints and the active-set problem
  • The four KKT conditions stated
  • The factory problem and exhaustive enumeration of all eight candidates
  • Complementary slackness is satisfied by construction in the enumeration table
  • Independent geometric verification of multipliers (Route B)
  • Complementary slackness as the condition that pins the multiplier
  • Honest limits of the KKT conditions: non-convexity and constraint qualification
  • Summary: the spine and limits of enumeration as a proof device
  • Stochastic gradient estimate and unbiasedness
  • Variance of the estimate and its independence from position
  • Fixed step-size recursion and the convergence floor
  • Independence assumption underlying the recursion
  • Decaying step-size schedule and the two convergence conditions
  • Minibatch vs full-batch compute trade-off
  • Convex problem definition and structure
  • Every local minimum is global: proof
  • The minimizer set is convex; strict convexity gives at most one
  • Existence requires coercivity: the Weierstrass theorem
  • What convexity does not guarantee: limits of the guarantee
  • Quasiconvexity and sublevel sets
  • Worked checklist and four-problem procedure

Syllabus

  1. Convexity

    1. L1 · Why Local Is Not Global
    2. L2 · Convex Sets, and Why They Are the Right Object
    3. L3 · Convex Functions, and Three Ways to Check One
    4. L4 · The Guarantee, and What It Does Not Cover

  2. Gradient Methods

    1. L5 · Gradient Descent, and the Step-Size Question
    2. L6 · How Fast, and Why: Smoothness, Strong Convexity, Conditioning
    3. L8 · Stochastic Gradients, and Optimizing What You Cannot See

  3. Constraints

    1. L9 · Constraints, and Why They Change the Question
    2. L11 · KKT, and the Conditions That Handle Inequalities

  4. Duality

    1. L12 · Duality, and the Gap That Sometimes Closes

  5. Linear Programming

    1. L13 · Linear Programs, and Why the Answer Sits at a Corner
    2. L14 · Simplex, Interior Points, and Where Optimization Stops