Skip to content
Tutorials Center
My learning

Topics

Convex Optimization Tutorial

Learn Convex Optimization step by step: 38 lessons in 9 chapters with examples, quizzes, diagrams and practice.

Start learning →

of lessons completed

Getting Started

  1. 1 What Is Optimization? Meet optimization: choosing the best option under rules. See real examples, write your first objective function and find its minimum with a few lines of code.
  2. 2 Anatomy of an Optimization Problem Learn the standard form of an optimization problem: objective, feasible set, minimizers, minimum values and what happens when no solution exists.
  3. 3 Local and Global Minima Understand local and global minima, saddle points and why non-convex functions trap algorithms. Run code that finds different valleys from different starts.
  4. 4 Gradients and Hessians Review the calculus you need: partial derivatives, the gradient, the Hessian matrix and the chain rule. Check your formulas with numerical differences in Python.
  5. 5 Your First Solvers: Grid Search and Newton Build three simple solvers from scratch: grid search, bisection on the derivative and Newton's method. Compare their speed and learn when each one works.

Convex Sets and Functions

  1. 6 Convex Sets Learn what a convex set is, see examples such as balls, half-spaces and polyhedra, and test convexity numerically by sampling line segments in Python.
  2. 7 Convex Functions Define convex functions with the chord rule, see classic examples like x squared, absolute value and exp, and test the inequality on random points in Python.
  3. 8 Testing Convexity with Derivatives Use f'' โ‰ฅ 0 and the Hessian's eigenvalues to prove convexity, check quadratic functions, and build a numerical convexity tester with sympy and numpy.
  4. 9 Operations That Preserve Convexity Build complicated convex functions from simple ones: non-negative sums, pointwise maximum, affine composition and more, with numerical checks in Python.
  5. 10 Convex Optimization Problems and Optimality Define a convex optimization problem, prove why local minima are global, state the optimality condition for constrained problems, and verify it numerically.

Gradient Descent

  1. 11 Gradient Descent Build gradient descent from scratch: the update rule, a stopping test, trajectories on a 2D bowl and least squares. See how the step size changes the path.
  2. 12 Step Size and Line Search See what happens with steps too small or too large, learn the safe step 1/L, and implement backtracking line search with the Armijo condition in Python.
  3. 13 Convergence Rates of Gradient Descent Learn the O(1/k) guarantee for smooth convex functions, check it numerically, and see why 'rate' means how fast the error shrinks as iterations grow.
  4. 14 Conditioning and Strong Convexity Understand strong convexity, the condition number L/ฮผ and why ill-conditioned problems make gradient descent slow. Includes linear convergence experiments.
  5. 15 Momentum and Accelerated Gradient Speed up gradient descent with heavy-ball momentum and Nesterov acceleration. Implement both from scratch and compare iterations on ill-conditioned problems.

Constrained Optimization and Lagrange

  1. 16 Lagrange Multipliers for Equality Constraints Solve constrained problems with Lagrange multipliers: the gradient condition, geometric meaning, the Lagrangian and worked examples verified with sympy and numpy.
  2. 17 Inequality Constraints and Active Sets Handle constraints of the form g(x) โ‰ค 0: active versus inactive, sign rules for multipliers and complementary slackness, with a brute-force active-set solver.
  3. 18 Projected Gradient Descent Handle simple constraints by projecting after each gradient step. Learn projections onto boxes, balls and the simplex, and run a complete example in Python.
  4. 19 Penalty and Barrier Methods Turn constrained problems into unconstrained ones with quadratic penalties and logarithmic barriers. Implement both, watch the solutions approach the constraint and see the trade-offs.

Duality and KKT Conditions

  1. 20 The Lagrangian and the Dual Function Build the Lagrangian, minimize it over x to get the dual function, and see why it always gives a lower bound on the best value of a constrained problem.
  2. 21 Weak and Strong Duality Learn why the dual value never exceeds the primal value, when the two are equal (Slater's condition), and see an example where the gap closes only in the limit.
  3. 22 The KKT Conditions Learn the four Karush-Kuhn-Tucker conditions, why they are necessary and sufficient for convex problems, and write a checker that verifies a candidate solution.
  4. 23 Sensitivity and Shadow Prices See what the Lagrange multiplier means: the rate at which the optimal value changes when a constraint is relaxed. Verify it with finite differences and a linear program.

Linear and Quadratic Programs

  1. 24 Linear Programs Learn linear programs in standard form, why the best point sits at a vertex, how LP duality works, and how to solve one with SciPy, including infeasible and unbounded cases.
  2. 25 The Simplex Method from Scratch Build the simplex method step by step: slack variables, the tableau, choosing the entering and leaving variables, pivoting, and reading the dual prices from the result.
  3. 26 Quadratic Programs Solve quadratic programs: write the problem in matrix form, solve the equality-constrained case with one linear system, and handle inequalities with an active-set search.
  4. 27 Portfolio Optimization as a QP Model the mean-variance portfolio problem as a QP: minimize risk for a target return with no short selling, then trace the efficient frontier with a solver. Educational, not advice.

Proximal and Stochastic Methods

  1. 28 Proximal Operators Meet the proximal operator, the building block for non-smooth convex optimization. Derive soft thresholding for the L1 norm, relate projections to prox, and verify each by brute force.
  2. 29 Proximal Gradient and ISTA Solve composite problems smooth + non-smooth with proximal gradient descent. Implement ISTA for the lasso, accelerate it to FISTA and check the result with optimality conditions.
  3. 30 Stochastic Gradient Descent Learn why SGD uses one sample or a mini-batch per step, how batch size and learning rate change its path, and why a decaying step size is needed for exact convergence.
  4. 31 Momentum, Nesterov and Adam See why plain gradient descent crawls in narrow valleys and how momentum, Nesterov acceleration and Adam fix it. Implement each one and race them on an ill-conditioned problem.

Applications in Machine Learning

  1. 32 Ridge Regression as an Optimization Problem Treat ridge regression as a strongly convex problem: derive the closed-form solution, solve it with gradient descent, and see how the penalty stabilizes correlated features.
  2. 33 The Lasso and Sparsity Understand why the L1 penalty zeroes out coefficients, compute the smallest penalty that kills all weights, trace a lasso path, and compare it with ridge.
  3. 34 Logistic Regression as a Convex Problem Show that the logistic loss is convex, derive its gradient and Hessian, and train a classifier with gradient descent and Newton's method on a small two-class dataset.
  4. 35 Support Vector Machines and Duality Train a linear SVM two ways: subgradient descent on the hinge loss and the dual QP. Verify strong duality numerically and identify the support vectors.

Projects and Practice

  1. 36 Practice Set: Duality, KKT and Solvers Six worked practice problems on dual functions, LP duality, shadow prices, KKT points and proximal operators, each with a code check you can run to verify your answer.
  2. 37 Project: Recovering a Sparse Signal Recover a sparse signal from far fewer measurements than unknowns using L1 minimization and FISTA. Compare with least squares, debias the result and map success against measurements.
  3. 38 Project: A Classifier from Scratch Build a logistic-regression classifier on synthetic data, train it with gradient descent, Nesterov, SGD and Newton, then add an L1 penalty with proximal gradient for a sparse model.