Math for Data Science · MDS-9
Turn 'find the best answer' into math you can solve — from convex sets and gradient descent to Lagrange multipliers, LPs, and the loss landscapes behind machine learning.
Optimization is how data science chooses the best model, the best decision, or the best allocation under constraints. This course builds the subject from the geometry of convex sets through first-order methods (gradient descent, SGD, momentum, Adam), Lagrangian duality and the KKT conditions, linear and quadratic programs, and the convex-optimization toolkit. Every idea is paired with hands-on solvers in Python (NumPy/SciPy/CVXPY) or Julia, ending with how optimization actually drives machine-learning training.
Course Outline
Every lesson is self-contained: a full explanation, worked step-by-step examples (in Python and R/Julia), common mistakes, a try-it-yourself, and an interactive quiz. Jump to a unit:
Every modeling, fitting, and decision task in data science is secretly an optimization problem. Here we name its three pieces.
An optimization problem asks: choose decision variables x to make an objective function f(x) as small (or large) as possible, while respecting constraints. The variables are the knobs you control (model weights, allocations). The objective f(x) scores every candidate. Constraints g_i(x) <= 0 and h_j(x) = 0 carve out the feasible set of allowed choices. In ML, x is the parameter vector, f is the training loss, and constraints might cap weight norms or enforce probabilities summing to one. Recognizing these three pieces lets you hand a problem to a solver and reason about whether a solution exists, is unique, or is even attainable. Almost all of supervised learning, portfolio choice, and resource planning fits this template.
Worked Example 1
Problem. A bakery makes profit 3 per cake and 2 per pie. It has 60 units of flour; a cake uses 4, a pie uses 3. Identify objective, variables, constraints.
Answer. Variables (c,p)>=0; objective max 3c+2p; constraint 4c+3p<=60. Candidate (9,8) is feasible with profit 43.
Worked Example 2
Problem. Frame least-squares line fitting y ~ a x + b on data (xi, yi) as an optimization problem.
Answer. min over (a,b) of sum_i (a xi + b - yi)^2; solved by np.linalg.lstsq giving the best-fit slope and intercept.
Problem. A factory makes profit 5 per unit of A and 4 per unit of B. Each A needs 2 labor-hours, each B needs 1; 100 labor-hours are available. Write objective, variables, constraints.
Solution. Variables a,b >= 0. Objective: maximize 5a + 4b. Constraint: 2a + b <= 100. The feasible set is the triangle bounded by a>=0, b>=0, 2a+b<=100. This is a linear program; its optimum will sit at a corner of that triangle (a foreshadow of Unit 5).
Solvers expect minimization; here we convert maximize to minimize and pin down what 'feasible' and 'optimal value' mean.
By convention solvers minimize. Maximizing f(x) is identical to minimizing -f(x): argmax f = argmin(-f), and the optimal value flips sign. The feasible set is every x satisfying all constraints; if it is empty the problem is infeasible. The optimal value p* is the smallest objective over the feasible set; if the objective decreases without bound on the feasible set, p* = -infinity (unbounded). A minimizer x* is a point achieving p*. Distinguishing the optimal value (a number) from a minimizer (a point) matters because some problems have a finite value but no attaining point, or many minimizers with the same value. In ML this is the gap between the best achievable loss and the weights that realize it.
Worked Example 1
Problem. Convert: maximize f(x) = -x^2 + 4x over x in [0,3]. Give the equivalent minimization and the optimal value.
Answer. Minimize x^2-4x; minimizer x*=2, optimal value of original maximize is f(2)=4.
Worked Example 2
Problem. Is minimize f(x)=x subject to x >= 1 bounded? What is the feasible set and optimal value?
Answer. Feasible set [1, inf); optimal value p* = 1 at x* = 1; bounded.
Worked Example 3
Problem. Show minimize f(x) = -x over x >= 0 is unbounded.
Answer. p* = -infinity; the problem is unbounded below, so no optimal point exists.
Problem. Convert maximize 2x + 3y subject to x + y <= 5, x,y >= 0 into standard minimization form, and state the feasible set.
Solution. Minimize -(2x + 3y) = -2x - 3y subject to x + y <= 5, x >= 0, y >= 0. Feasible set is the triangle with corners (0,0), (5,0), (0,5). The optimum sits at a corner; (0,5) gives objective 15, the maximum. So min of -2x-3y is -15, attained at (0,5).
A method can get stuck at a point that only looks best nearby. Knowing the difference tells you whether to trust it.
A local minimum x* is best within some neighborhood: f(x*) <= f(x) for all x near x* in the feasible set. A global minimum is best over the entire feasible set. For nonconvex problems these differ — gradient methods may converge to a local minimum far worse than the global one. This matters enormously in ML: neural-network losses are nonconvex, so training finds a local (often good-enough) minimum, not provably the global one. The payoff of convexity, covered later, is that every local minimum is global, so any descent method that stops at a stationary point has found the best answer. Until then, you must reason about basins of attraction, restarts, and whether your landscape has one valley or many.
Worked Example 1
Problem. f(x) = x^4 - 3x^2 + 1. Find stationary points and classify global vs. local minima.
Answer. Two global minima at x = +/- sqrt(1.5) with value -1.25; x=0 is a local maximum.
Worked Example 2
Problem. Run gradient descent on f(x)=x^4-3x^2+1 from x0=0.1 vs x0=-0.1 and observe which minimum each finds.
Answer. Starting point determines which basin/minimum gradient descent reaches; nonconvexity makes the result initialization-dependent.
Problem. For f(x) = (x^2 - 1)^2, find all minima and say whether they are local, global, or both.
Solution. f'(x) = 2(x^2-1)(2x) = 4x(x^2-1) = 0 at x=0 and x=+/-1. f(0)=1, f(+/-1)=0. So x=+/-1 are minima with value 0 (both global, tied by symmetry) and x=0 is a local maximum with value 1. Any descent method lands at +1 or -1 depending on the starting side.
Convexity is the single property that turns hard optimization into reliably solvable optimization. Define it precisely.
A set C is convex if, for any two points x, y in C, the whole segment tx + (1-t)y (for t in [0,1]) stays in C — no dents or holes. A function f is convex if its domain is convex and its graph lies on or below every chord: f(tx + (1-t)y) <= t f(x) + (1-t) f(y). Equivalently the region above the graph (the epigraph) is a convex set. Convex functions bowl upward, so they have a single connected set of minimizers. This is why convexity is the dividing line in optimization: convex problems have no spurious local minima, and efficient algorithms find the global optimum. Norms, squared error, log-sum-exp, and L2-regularized linear losses are all convex.
Worked Example 1
Problem. Is the set {(x,y) : x^2 + y^2 <= 1} convex? Verify numerically.
Answer. Yes, the unit disk is convex; every segment between its points stays inside.
Worked Example 2
Problem. Check whether f(x) = |x| is convex using the chord inequality at x=-2, y=4, t=0.5.
Answer. f(x)=|x| is convex (chord lies above the graph for every pair of points).
Worked Example 3
Problem. Show the set {(x,y) : xy >= 1, x > 0} is NOT convex.
Answer. Without the x>0 restriction, {xy >= 1} has two disconnected branches; a segment from one branch to the other leaves the set, so it is nonconvex.
Problem. Is f(x,y) = x^2 + y^2 convex? Verify the chord inequality at p=(0,0), q=(2,2), t=0.5.
Solution. LHS: f(0.5*(0,0)+0.5*(2,2)) = f(1,1) = 1+1 = 2. RHS: 0.5*f(0,0) + 0.5*f(2,2) = 0.5*0 + 0.5*8 = 4. Since 2 <= 4, the inequality holds. The function is a paraboloid bowl; its Hessian is 2I (positive definite), so it is convex everywhere.
Two practical tests tell you whether a differentiable function is convex without checking every chord.
For a differentiable f, the first-order condition says f is convex iff its graph lies above every tangent: f(y) >= f(x) + grad f(x).(y - x) for all x, y. The tangent line/plane underestimates the function. For a twice-differentiable f, the second-order condition is cleaner: f is convex iff its Hessian H(x) is positive semidefinite (all eigenvalues >= 0) everywhere on its domain; in one variable this is just f''(x) >= 0. Strict positive definiteness gives strict convexity and a unique minimizer. These tests are the workhorse for proving a loss is convex — checking the Hessian of squared error or logistic loss is how you certify that gradient descent will find the global optimum.
Worked Example 1
Problem. Use the second-order test to confirm f(x) = e^x is convex.
Answer. e^x is strictly convex since f''(x) = e^x > 0 for all x.
Worked Example 2
Problem. Is f(x,y) = x^2 + 3y^2 - xy convex? Check the Hessian.
Answer. Yes; the Hessian [[2,-1],[-1,6]] has positive eigenvalues (~1.75, ~6.25), so f is strictly convex.
Worked Example 3
Problem. Show f(x,y) = x^2 - y^2 is NOT convex.
Answer. Not convex; the Hessian is indefinite (eigenvalue -2), giving a saddle shape.
Problem. Determine whether f(x,y) = 2x^2 + 2y^2 + 2xy is convex using the Hessian eigenvalue test.
Solution. Hessian H = [[4, 2], [2, 4]]. Eigenvalues solve det(H - lambda I)=0: (4-lambda)^2 - 4 = 0, so 4-lambda = +/-2, giving lambda = 2 and 6. Both positive, so H is positive definite and f is strictly convex. In code: np.linalg.eigvalsh([[4,2],[2,4]]) -> [2., 6.].
This lesson states the central payoff: for convex problems, 'local' equals 'global' and solvers are reliable.
The defining benefit of convexity: in a convex optimization problem (convex objective over a convex feasible set), every local minimum is a global minimum, and the set of optimal points is itself convex. Therefore any algorithm that reaches a stationary point — where the gradient is zero, or KKT conditions hold — has found the global optimum; there are no spurious traps. This makes convex problems polynomial-time solvable to high accuracy with interior-point or first-order methods, and it is why disciplined-convex tools like CVXPY can guarantee a correct answer. In ML, framing a model so its training loss is convex (linear/logistic regression, SVM, lasso, ridge) means optimization is a solved problem; the difficulty in deep learning is precisely that its loss is nonconvex.
Worked Example 1
Problem. Explain why minimizing the convex f(x) = (x-3)^2 needs no global search.
Answer. x* = 3 is the unique global minimum; any starting point converges there because the problem is convex.
Worked Example 2
Problem. Contrast: minimize convex 0.5*||Ax - b||^2 vs. a nonconvex neural loss, in terms of guarantees.
Answer. The convex least-squares problem has a guaranteed unique global solution; the nonconvex net loss does not.
Problem. A loss L(w) is shown to have a positive-semidefinite Hessian everywhere. A gradient-descent run stops where the gradient is essentially zero. What can you conclude about that point?
Solution. Because the Hessian is PSD everywhere, L is convex. For a convex function a point with zero gradient is a global minimizer. So the gradient-descent stopping point is a global optimum (one of possibly several if the Hessian is only PSD, not PD). No restarts or global search are needed to certify optimality.
Solvers expect a canonical layout. This lesson turns a word problem into minimize-subject-to standard form.
Standard form writes every problem as: minimize f(x) subject to g_i(x) <= 0 (inequalities) and h_j(x) = 0 (equalities). To convert a real problem: (1) name the decision variables, (2) write the objective and negate it if it was a maximization, (3) move every inequality to the form (something) <= 0, and (4) write equalities as (something) = 0. Variable bounds like x >= 0 become -x <= 0. Putting a problem in standard form is the interface to solvers like scipy.optimize and CVXPY, and it makes the structure (linear? quadratic? convex?) visible so you can pick the right algorithm. This discipline prevents sign errors and ensures the solver optimizes what you intend.
Worked Example 1
Problem. A diet must supply at least 50 units of protein. Food A gives 10/unit at cost 2; food B gives 5/unit at cost 1. Write in standard form.
Answer. minimize 2xA + xB s.t. 50 - 10xA - 5xB <= 0, -xA <= 0, -xB <= 0.
Worked Example 2
Problem. Maximize return 0.08 a + 0.05 b with a + b = 1 (full investment), a,b >= 0. Put in standard form and solve.
Answer. minimize -0.08a-0.05b s.t. a+b-1=0, a,b>=0; solution a=1,b=0, max return 0.08.
Problem. A shop maximizes profit 6x + 4y subject to x + y <= 10 and x <= 6, with x,y >= 0. Write it in standard minimization form.
Solution. Minimize -(6x + 4y) = -6x - 4y subject to: x + y - 10 <= 0, x - 6 <= 0, -x <= 0, -y <= 0. This is a linear program; in scipy: linprog(c=[-6,-4], A_ub=[[1,1],[1,0]], b_ub=[10,6], bounds=[(0,None),(0,None)]), which returns x=6, y=4 with profit 52.
Pick five functions of one or two variables (mix convex, concave, and neither). In Python with NumPy/Matplotlib, plot each and numerically check the chord/midpoint inequality and the sign of the second derivative or Hessian eigenvalues. Then take one small real decision (for example, a budget allocation) and write it in standard form. Argue whether each function is convex and whether your modeled problem is a convex program.
Deliverable · A notebook with plots, your convexity verdict for each function with evidence, and the standard-form statement of your modeled problem.
1. A set is convex if, for any two points in the set:
Answer B. Convexity means every convex combination tx+(1-t)y for t in [0,1] stays inside the set, i.e. the connecting segment is contained.
2. For a convex optimization problem, any local minimum is:
Answer A. A defining benefit of convexity is that local optima are global, so a method that finds a local min has found the best point.
3. A twice-differentiable function of one variable is convex on an interval when:
Answer B. f''(x) >= 0 on the interval is the second-order condition for convexity in one dimension.
4. Which is the standard form of a minimization problem?
Answer B. Standard form minimizes the objective subject to inequality constraints written as <= 0 and equality constraints written as = 0.
5. Maximizing f(x) is equivalent to:
Answer B. A maximization is converted to standard minimization form by negating the objective: argmax f = argmin (-f).
I can express a word problem as a standard-form optimization with objective, variables, and constraints.
I can decide whether a set or function is convex and explain why convexity guarantees a global optimum.
I can distinguish local from global minima and identify when they coincide.
Before running any solver, calculus tells you where minima can hide: where the gradient vanishes.
For a smooth, unconstrained function f, a necessary condition for an interior local minimum at x* is that the gradient is zero: grad f(x*) = 0. Such points are stationary points. The gradient points in the direction of steepest increase, so at a minimum there is no direction of first-order decrease left. This first-order condition is necessary but not sufficient — maxima and saddle points are also stationary — so it only narrows candidates. In ML, training a model means driving the gradient of the loss toward zero; convergence criteria check ||grad|| < tolerance. Finding stationary points by solving grad f = 0 analytically works for small problems and underlies every gradient-based optimizer used at scale.
Worked Example 1
Problem. Find the stationary point of f(x,y) = x^2 + y^2 - 2x - 4y + 5.
Answer. Unique stationary point (1, 2); value f(1,2) = 0.
Worked Example 2
Problem. For the squared-error loss L(w) = sum_i (w*xi - yi)^2 with x=[1,2,3], y=[2,4,5], find the stationary w.
Answer. Stationary (optimal) w = 25/14 ~ 1.786; gradient is zero there.
Problem. Find the stationary point of f(x,y) = 3x^2 + 2y^2 + 12x - 8y + 1.
Solution. grad f = (6x + 12, 4y - 8). Set to zero: 6x+12=0 -> x=-2; 4y-8=0 -> y=2. Stationary point (-2, 2). Since both pure second derivatives are positive and there is no cross term, the Hessian diag(6,4) is positive definite, so it is a minimum with value f(-2,2)=3*4+2*4-24-16+1 = 12+8-24-16+1 = -19.
Once you have a stationary point, the Hessian decides whether it is a minimum, maximum, or saddle.
At a stationary point x*, the Hessian H (matrix of second partials) classifies it via its eigenvalues. If H is positive definite (all eigenvalues > 0), x* is a strict local minimum — the function curves up in every direction. If H is negative definite, it is a local maximum. If H has both positive and negative eigenvalues, it is a saddle point. If H is positive semidefinite with a zero eigenvalue, the test is inconclusive. This second-order sufficient condition is how you confirm a candidate is genuinely a minimizer. For ML losses, checking the Hessian's definiteness certifies convexity locally and predicts how fast curvature-aware methods like Newton's will converge.
Worked Example 1
Problem. Classify the stationary point of f(x,y) = x^2 + y^2 - xy.
Answer. (0,0) is a strict local (and global) minimum; Hessian eigenvalues 1 and 3 are positive.
Worked Example 2
Problem. Classify the stationary point of f(x,y) = x^2 - y^2.
Answer. (0,0) is a saddle point: minimum along x, maximum along y.
Worked Example 3
Problem. For the Rosenbrock function f(x,y) = (1-x)^2 + 100(y - x^2)^2, classify the point (1,1).
Answer. (1,1) is the strict local minimum; Hessian is PD but highly ill-conditioned, foreshadowing slow plain gradient descent.
Problem. Classify the stationary point of f(x,y) = 2x^2 + y^2 + 2xy at (0,0).
Solution. grad = (4x + 2y, 2y + 2x); zero at (0,0). Hessian H = [[4, 2], [2, 2]]. Eigenvalues solve (4-l)(2-l) - 4 = 0 -> l^2 - 6l + 4 = 0 -> l = 3 +/- sqrt(5) ~ 0.76 and 5.24, both positive. So H is positive definite and (0,0) is a strict local minimum.
Knowing which direction to move is half the battle; line search picks how far to step.
Given a descent direction d at point x (one with grad f . d < 0), a line search chooses the step length alpha in the update x <- x + alpha d. Exact line search minimizes f along the ray, but it is usually too costly. Backtracking (Armijo) line search instead starts with a guess alpha and shrinks it by a factor until a sufficient-decrease condition holds: f(x + alpha d) <= f(x) + c1 * alpha * grad f . d, with c1 small (e.g. 1e-4). The Wolfe conditions add a curvature requirement to avoid steps that are too short. Good step-size selection is what keeps gradient and Newton methods stable; in ML this is the principled cousin of tuning a learning rate.
Worked Example 1
Problem. Backtracking on f(x) = x^2 from x=2 with direction d = -f'(2) = -4, start alpha=1, factor 0.5, c1=1e-4.
Answer. Backtracking selects alpha = 0.5, moving from x=2 to the minimizer x=0.
Worked Example 2
Problem. Implement Armijo backtracking generically in Python and apply to f(x)=(x-3)^2 from x0=0.
Answer. Backtracking finds alpha=0.5, stepping to x=3, the exact minimum of (x-3)^2.
Problem. From x=4 on f(x)=x^2 with direction d=-f'(4), starting alpha=1 and halving, find the accepted Armijo step (c1=1e-4).
Solution. f(4)=16, f'(4)=8, d=-8, grad.d=-64. alpha=1: x_new=4-8=-4, f=16; need 16 <= 16 + 1e-4*(-64)=15.9936, fails. alpha=0.5: x_new=4-4=0, f=0; need 0 <= 16 + 0.5*(-64)*1e-4 ~ 15.9968, holds. Accept alpha=0.5, landing at x=0, the minimum.
Newton's method uses curvature to take smart steps, converging dramatically fast near the optimum.
Newton's method models f locally as a quadratic using the Hessian and jumps to that quadratic's minimum. The update is x <- x - H(x)^{-1} grad f(x). Whereas gradient descent only knows the slope, Newton rescales the step by the inverse Hessian, automatically correcting for ill-conditioning and pointing toward the true minimum. Near a minimizer with positive-definite Hessian it converges quadratically — the number of correct digits roughly doubles each iteration. The costs are computing and inverting the Hessian (O(n^3)) and needing it positive definite to guarantee descent. For small-to-medium problems and the inner loops of many ML methods (e.g. Newton steps in logistic regression / IRLS), this speed is worth it.
Worked Example 1
Problem. One Newton step on f(x) = x^2 - 4x + 4 from x0 = 0.
Answer. x1 = 2 in one step; Newton finds the minimum of a quadratic immediately.
Worked Example 2
Problem. Two Newton steps on f(x) = x^4 from x0 = 1 (note f'' vanishes at the min, slowing convergence).
Answer. x2 ~ 0.444; Newton still converges but only linearly when f''=0 at the minimum.
Worked Example 3
Problem. Newton in 2D on f(x,y)=x^2+10y^2 from (1,1).
Answer. Reaches the minimizer (0,0) in one step; Newton neutralizes the 10x conditioning that would slow gradient descent.
Problem. Take one Newton step on f(x) = x^2 + 2x + 1 from x0 = 3.
Solution. f'(x) = 2x + 2, f''(x) = 2. Newton step: x1 = 3 - f'(3)/f''(3) = 3 - (8)/2 = 3 - 4 = -1. Check f'(-1) = 0, so x1 = -1 is the exact minimizer (f = (x+1)^2). Newton solves any quadratic in a single step.
BFGS gets Newton-like speed without ever forming the Hessian — the workhorse of scipy.optimize.
Quasi-Newton methods approximate the (inverse) Hessian using only gradient information gathered across iterations. BFGS, the most popular, updates an estimate B_k of the Hessian (or H_k of its inverse) from successive parameter changes s_k = x_{k+1} - x_k and gradient changes y_k = grad_{k+1} - grad_k, enforcing the secant equation B_{k+1} s_k = y_k. The step is then x <- x - H_k grad, like Newton but with H built up cheaply (O(n^2) per step, no second derivatives). BFGS achieves superlinear convergence and is the default for smooth unconstrained problems in scipy.optimize.minimize. For large-scale ML, the memory-limited L-BFGS variant stores only a few vectors, making it practical for logistic regression and conditional random fields.
Worked Example 1
Problem. Solve the Rosenbrock minimum with BFGS in scipy and report the iteration count.
Answer. BFGS converges to (1,1) in a few dozen iterations using only gradients (estimated numerically).
Worked Example 2
Problem. Why use L-BFGS over BFGS for a 1-million-parameter logistic regression?
Answer. L-BFGS uses O(m n) memory by storing a short history, making quasi-Newton feasible at ML scale.
Problem. Minimize f(x,y) = (x-2)^2 + (y+3)^2 with scipy BFGS and state the expected minimizer.
Solution. from scipy.optimize import minimize; res = minimize(lambda v:(v[0]-2)**2+(v[1]+3)**2, [0,0], method='BFGS'). The objective is a simple convex bowl with minimum at (2, -3). BFGS converges there in very few iterations (the gradient (2(x-2), 2(y+3)) vanishes at (2,-3)). res.x is approximately [2.0, -3.0] and res.fun approximately 0.
Tie it together: a single unified interface drives gradient descent, Newton, and quasi-Newton solvers.
scipy.optimize.minimize is the standard entry point for unconstrained (and some constrained) smooth optimization. You pass the objective, a starting point x0, optionally the gradient via jac and Hessian via hess, and choose a method: 'BFGS' or 'L-BFGS-B' (quasi-Newton, gradient-based), 'Newton-CG' or 'trust-ncg' (use the Hessian), or 'Nelder-Mead' (derivative-free). It returns an OptimizeResult with .x (the minimizer), .fun (optimal value), .nit (iterations), and .success. Supplying an analytic gradient speeds convergence and accuracy versus finite differences. Knowing how to call this, read the result, and pick a method by problem size and smoothness is the practical skill that turns optimization theory into working code for fitting models and tuning small systems.
Worked Example 1
Problem. Minimize f(x) = (x-5)^2 + 2 with an analytic gradient using minimize.
Answer. Minimizer x ~ 5, optimal value ~ 2; supplying jac makes it converge in a couple of iterations.
Worked Example 2
Problem. Fit a least-squares slope by minimizing loss with Newton-CG, providing gradient and Hessian.
Answer. Newton-CG returns w ~ 1.786 = 25/14, matching the closed-form least-squares slope.
Problem. Use scipy.optimize.minimize to find the minimum of f(x,y) = (x-1)^2 + (y-2)^2 + 3, and predict .x and .fun.
Solution. from scipy.optimize import minimize; res = minimize(lambda v:(v[0]-1)**2+(v[1]-2)**2+3, [0,0], method='BFGS'). The bowl is centered at (1,2) with floor value 3. The gradient (2(x-1), 2(y-2)) vanishes at (1,2). So res.x is approximately [1.0, 2.0] and res.fun is approximately 3.0, with res.success True.
Take a smooth convex test function such as a 2D quadratic or the Rosenbrock function. In Python, implement a simple backtracking line search and run both a basic steepest-descent loop and a Newton step loop from the same starting point. Track the objective and gradient norm each iteration. Then solve the same problem with scipy.optimize.minimize using BFGS and Newton-CG and compare iteration counts.
Deliverable · A notebook with convergence plots (objective and gradient norm vs. iteration) comparing your steepest-descent, Newton, and SciPy solver runs, plus a short note on why Newton converged faster.
1. A necessary condition for x* to be an interior local minimum of a smooth f is:
Answer B. First-order necessary condition: the gradient must vanish at an interior optimum, making it a stationary point.
2. At a stationary point, a positive definite Hessian indicates a:
Answer C. Positive definiteness of the Hessian means the function curves upward in every direction, so the stationary point is a local minimum.
3. Newton's method differs from steepest descent because it:
Answer B. Newton's step is -H^{-1} g, using second-order curvature information, which yields fast quadratic convergence near the optimum.
4. What problem do quasi-Newton methods like BFGS solve?
Answer B. BFGS builds an approximation to the (inverse) Hessian using successive gradients, getting Newton-like behavior without computing the true Hessian.
5. A backtracking line search is used to:
Answer B. Line search selects how far to move along a chosen direction, shrinking the step until a sufficient-decrease (Armijo) condition holds.
I can use the gradient and Hessian to find and classify candidate minimizers.
I can explain how line search and Newton's method choose directions and step sizes.
I can solve an unconstrained problem with scipy.optimize and interpret the result.
The single most important algorithm in ML training: step downhill against the full-data gradient.
Batch gradient descent minimizes a loss L(w) by repeatedly moving against the gradient: w <- w - eta * grad L(w), where eta is the learning rate (step size) and the gradient is computed over the entire training set. Each step reduces the loss provided eta is small enough; for a smooth loss with gradient Lipschitz constant beta, any eta < 2/beta converges. The learning rate is the central knob: too large and the iterates overshoot and diverge; too small and training crawls. In ML this exact rule trains linear and logistic regression and is the backbone of deep-learning optimizers. Convergence to the global optimum is guaranteed when L is convex; otherwise it finds a stationary point of whatever basin it starts in.
Worked Example 1
Problem. Two batch GD steps on L(w) = (w-3)^2 from w=0 with eta=0.1.
Answer. After two steps w ~ 1.08, converging geometrically to w* = 3.
Worked Example 2
Problem. Batch GD for linear regression on x=[1,2,3], y=[2,4,5], one step from w=0, b=0, eta=0.01.
Answer. One step gives w~0.167, b~0.073; iterating converges to the least-squares fit w~1.5, b~0.667.
Problem. Perform two batch GD steps on L(w) = (w-10)^2 from w=0 with eta=0.2. Where is it heading?
Solution. grad = 2(w-10). Step 1: w = 0 - 0.2*2*(0-10) = 0 + 4 = 4. Step 2: w = 4 - 0.2*2*(4-10) = 4 + 2.4 = 6.4. The contraction factor is (1 - 2*eta) = 0.6 per step on (w-10), so w -> 10. After two steps w = 6.4, converging to the minimizer w* = 10.
Why some losses train fast and others zigzag forever — it comes down to curvature and the step size.
For a convex quadratic with Hessian H, gradient descent converges at a rate governed by the condition number kappa = lambda_max / lambda_min of H. With the optimal fixed step, the error contracts by roughly (kappa - 1)/(kappa + 1) per iteration: a well-conditioned problem (kappa near 1) converges in a few steps, while an ill-conditioned one (large kappa) zigzags slowly across a narrow valley. The largest stable step is eta < 2/lambda_max; beyond it the iterates diverge. This is why feature scaling, normalization, and preconditioning matter in ML — they shrink kappa so plain gradient descent trains quickly. It also motivates momentum and adaptive methods, which partly cancel the effect of bad conditioning.
Worked Example 1
Problem. For L(w) = 0.5*(w1^2 + 100 w2^2), find the condition number and the max stable learning rate.
Answer. kappa = 100; eta must be < 0.02; convergence is slow at ~0.98 contraction per iteration.
Worked Example 2
Problem. Show how rescaling fixes conditioning: substitute u2 = 10 w2 in the loss above.
Answer. Rescaling drops kappa from 100 to 1, turning slow zigzag into near-instant convergence.
Problem. A quadratic loss has Hessian eigenvalues 4 and 36. Give the condition number and the largest stable learning rate for gradient descent.
Solution. Condition number kappa = lambda_max/lambda_min = 36/4 = 9 (moderately ill-conditioned). Largest stable step eta < 2/lambda_max = 2/36 ~ 0.0556. The per-iteration contraction at the best fixed step is (kappa-1)/(kappa+1) = 8/10 = 0.8, so each step removes about 20% of the error — slower than a well-conditioned problem but far better than kappa=100.
Full-data gradients are too expensive at scale; SGD trades exactness for many cheap, noisy steps.
Stochastic gradient descent estimates the gradient from a random mini-batch of examples instead of the whole dataset: w <- w - eta * grad L_batch(w). Each step is far cheaper (cost scales with batch size, not dataset size), enabling many more updates per epoch, which is why all large-scale ML uses it. The gradient is an unbiased but noisy estimate of the true gradient; the noise actually helps escape shallow saddle points and flat regions, but it also means a fixed step never fully settles — you typically decay eta over time. Mini-batches (e.g. 32-256) balance gradient-estimate variance against vectorization efficiency on hardware. SGD's variance also has a mild regularizing effect that can improve generalization.
Worked Example 1
Problem. Why is one SGD epoch with batch size 1 cheaper per step than batch GD on n=1,000,000 examples?
Answer. SGD does ~1,000,000 cheap updates per epoch vs. one expensive batch-GD update, dramatically speeding early progress.
Worked Example 2
Problem. Implement a minimal SGD loop for linear regression with mini-batches in NumPy.
Answer. The loop performs n/bs noisy updates per epoch; w converges near the least-squares solution with far less per-step cost than batch GD.
Problem. You have 10,000 examples and use mini-batches of size 50. How many SGD updates happen per epoch, and how does the gradient variance compare to batch size 500?
Solution. Updates per epoch = 10000 / 50 = 200. Batch size 500 would give 20 updates per epoch. The gradient-estimate variance scales like 1/batch_size, so the size-50 batches have about 10x the variance of size-500 batches (noisier per step) but yield 10x more updates per epoch. Smaller batches mean noisier but more frequent steps; larger batches mean smoother but fewer steps.
Momentum gives the optimizer inertia, smoothing oscillation and accelerating through long valleys.
Momentum augments gradient descent with a velocity that accumulates past gradients: v <- mu*v - eta*grad; w <- w + v, with momentum coefficient mu (e.g. 0.9). On a stretched, ill-conditioned loss, plain gradient descent zigzags across the valley; momentum cancels the oscillating components and reinforces the consistent downhill direction, effectively reducing the dependence on the condition number. Nesterov accelerated gradient evaluates the gradient at the look-ahead point w + mu*v rather than at w, giving a more accurate correction and better theoretical convergence. Both are standard in deep learning because they speed training and help carry the iterate through small bumps and saddle regions where the raw gradient is tiny.
Worked Example 1
Problem. Two momentum steps on L(w)=(w-2)^2 from w=0, eta=0.1, mu=0.9, v0=0.
Answer. After two steps momentum reaches w ~ 1.08 vs. plain GD's 0.72; the velocity term accelerates progress.
Worked Example 2
Problem. State the Nesterov update and contrast it with classical momentum.
Answer. Nesterov evaluates the gradient at the look-ahead point w+mu*v, yielding a more responsive, better-converging update than classical momentum.
Problem. Run one momentum step on L(w)=(w-5)^2 from w=1 with eta=0.1, mu=0.9, v0=0. Then one more step.
Solution. grad = 2(w-5). Step 1: grad at 1 = 2*(1-5) = -8; v = 0.9*0 - 0.1*(-8) = 0.8; w = 1 + 0.8 = 1.8. Step 2: grad at 1.8 = 2*(1.8-5) = -6.4; v = 0.9*0.8 - 0.1*(-6.4) = 0.72 + 0.64 = 1.36; w = 1.8 + 1.36 = 3.16. The accumulated velocity makes the iterate climb toward w*=5 faster than plain GD would (which would give 1.8 then 2.44).
These optimizers give each parameter its own learning rate, scaled by its gradient history — Adam is the deep-learning default.
Adaptive methods divide the step by an estimate of each parameter's gradient magnitude, so rarely-updated or steep coordinates get appropriately sized steps. AdaGrad accumulates squared gradients G += g^2 and steps eta*g/sqrt(G+eps); its denominator only grows, so the rate decays, sometimes too aggressively. RMSProp fixes this with an exponential moving average of squared gradients, keeping the scale responsive. Adam combines RMSProp's per-parameter scaling with momentum: it keeps an EMA of gradients m (first moment) and of squared gradients v (second moment), applies bias correction, and steps eta * m_hat / (sqrt(v_hat) + eps). Adam's robustness to learning-rate choice and bad conditioning makes it the default optimizer for training neural networks.
Worked Example 1
Problem. One Adam step for a single parameter with g=0.5, eta=0.1, beta1=0.9, beta2=0.999, eps=1e-8, t=1, m0=v0=0.
Answer. w decreases by 0.1 on the first step; bias correction makes the initial effective step ~eta independent of gradient scale.
Worked Example 2
Problem. Write the from-scratch Adam update in NumPy for a parameter vector.
Answer. Four lines implement Adam: EMA of g and g^2, bias-correct both, then take a per-parameter scaled step.
Problem. Compute the first RMSProp step for a parameter with g=2, eta=0.01, decay rho=0.9, eps=1e-8, accumulator s0=0.
Solution. Update accumulator: s = rho*s0 + (1-rho)*g^2 = 0.9*0 + 0.1*4 = 0.4. Step: delta = eta * g / (sqrt(s) + eps) = 0.01 * 2 / (sqrt(0.4) + 1e-8) = 0.02 / 0.6325 ~ 0.0316. So w decreases by about 0.0316. RMSProp normalized the raw gradient by its running RMS magnitude, giving a scale-robust step.
A constant learning rate is rarely best; schedules and loss curves are how practitioners control and debug training.
A learning-rate schedule changes eta over training: step decay (drop by a factor every k epochs), exponential decay, cosine annealing, and warmup (ramp eta up early to stabilize Adam) are common. Decaying eta lets training take big early steps and fine, settling steps near the optimum, which is essential for SGD's noise to average out. Diagnosing training means reading the loss curve: a loss that explodes or oscillates signals eta too large; a loss that barely moves signals eta too small or vanishing gradients; a training loss that keeps falling while validation loss rises signals overfitting. Plotting loss and gradient norm versus iteration is the primary tool for tuning the rate and catching divergence early.
Worked Example 1
Problem. Step decay: eta0=0.1, halved every 10 epochs. What is eta at epochs 0, 10, 25?
Answer. eta = 0.1, 0.05, 0.025 at epochs 0, 10, 25 respectively.
Worked Example 2
Problem. A loss curve rises and oscillates wildly after a few steps. Diagnose and fix.
Answer. Diagnosis: learning rate too large; remedy: lower eta (and standardize features), choosing the largest stable rate.
Worked Example 3
Problem. Cosine annealing: eta(t) = 0.5*eta_max*(1 + cos(pi*t/T)) with eta_max=0.2, T=100. Find eta at t=0, 50, 100.
Answer. eta = 0.2, 0.1, 0.0 at t = 0, 50, 100; cosine annealing smoothly cools the rate to zero.
Problem. Exponential decay eta(t) = eta0 * gamma^t with eta0=0.05, gamma=0.95. What is the learning rate at t=0, t=10, and t=20?
Solution. t=0: 0.05 * 0.95^0 = 0.05. t=10: 0.05 * 0.95^10 = 0.05 * 0.5987 ~ 0.0299. t=20: 0.05 * 0.95^20 = 0.05 * 0.3585 ~ 0.0179. The rate decays smoothly and multiplicatively, so big early steps shrink to small refining steps as training proceeds.
Coding GD, SGD, momentum, and Adam yourself cements exactly what each update rule does — the capstone of this unit.
Implementing optimizers from scratch means writing the parameter-update rule directly given a function that returns the loss gradient. The shared skeleton is a loop that computes grad = grad_loss(w) and applies an update; the optimizer differs only in how grad becomes a step. Plain GD: w -= eta*grad. Momentum: maintain v. Adam: maintain m, v, and a step counter t. Building these makes the mechanics concrete and lets you verify against a known optimum, test learning-rate sensitivity, and confirm momentum/Adam beat plain GD on ill-conditioned losses. This is also how you debug training in practice: a hand-written optimizer that matches a library's behavior proves you understand the math driving model fitting.
Worked Example 1
Problem. Write a generic gradient-descent optimizer and run it on a quadratic to verify the minimum.
Answer. The from-scratch GD converges to [3, -1], matching the analytic minimizer.
Worked Example 2
Problem. Add momentum and Adam variants that share the same gradient interface.
Answer. Sharing the gradient interface, momentum and Adam converge on the diag(1,100) bowl in many fewer iterations than plain GD, demonstrating their conditioning advantage.
Problem. Write pseudocode for a from-scratch momentum optimizer and apply it to minimize L(w)=(w-4)^2 from w=0, eta=0.1, mu=0.9. Give the first two w values.
Solution. Pseudocode: v=0; repeat { g = 2*(w-4); v = 0.9*v - 0.1*g; w = w + v }. Step 1: g=2*(0-4)=-8; v=0.9*0 - 0.1*(-8)=0.8; w=0+0.8=0.8. Step 2: g=2*(0.8-4)=-6.4; v=0.9*0.8 - 0.1*(-6.4)=0.72+0.64=1.36; w=0.8+1.36=2.16. The iterate accelerates toward w*=4 via accumulated velocity.
On a logistic-regression or least-squares loss with a known minimum, implement plain gradient descent, SGD with mini-batches, momentum, and Adam from scratch in Python (NumPy only). Run each from the same initialization and plot loss vs. iteration and vs. wall-clock. Sweep the learning rate to show one value that diverges and one that converges. Explain why momentum and Adam handle an ill-conditioned (stretched) loss better than plain GD.
Deliverable · A NumPy notebook with from-scratch optimizers, convergence plots comparing all four, and a short write-up on learning-rate sensitivity and conditioning.
1. In gradient descent x <- x - eta * grad, a learning rate that is too large typically causes:
Answer B. An overly large step overshoots the minimum, causing the loss to oscillate or blow up rather than settle.
2. What is the main difference between batch gradient descent and SGD?
Answer B. SGD computes a cheaper, noisier gradient from a sampled mini-batch each step, trading accuracy for speed and more updates.
3. Momentum improves gradient descent primarily by:
Answer B. Momentum keeps a running velocity of past gradients, damping oscillation across steep directions and accelerating along consistent ones.
4. Adam is best described as combining:
Answer B. Adam keeps exponential moving averages of the gradient (momentum) and of squared gradients (adaptive per-parameter step sizes).
5. A high condition number of the loss Hessian causes plain gradient descent to:
Answer B. Ill-conditioning stretches the level sets, so gradient descent bounces across the valley and progresses slowly; momentum/adaptive methods mitigate this.
I can implement batch gradient descent and explain how the learning rate affects convergence.
I can describe how SGD, momentum, and Adam modify the basic update rule and when each helps.
I can diagnose divergence or slow training and adjust the step size or schedule.
When you must optimize subject to an equation, Lagrange multipliers turn it back into solving for stationary points.
To minimize f(x) subject to an equality constraint h(x) = 0, form the Lagrangian L(x, lambda) = f(x) + lambda*h(x). At a constrained optimum the gradient of L with respect to x vanishes, giving grad f(x) = -lambda*grad h(x): the objective gradient is parallel to the constraint gradient. Solving grad_x L = 0 together with h(x) = 0 yields the candidate point and the multiplier lambda. The multiplier is not just bookkeeping — it measures the sensitivity of the optimal value to the constraint level (a shadow price). This method generalizes to several equalities (one lambda each) and is the foundation for KKT with inequalities. In ML it underlies constrained estimators and equality-constrained least squares.
Worked Example 1
Problem. Minimize f(x,y) = x^2 + y^2 subject to x + y = 1.
Answer. Minimizer (0.5, 0.5) with value 0.5; multiplier lambda = -1.
Worked Example 2
Problem. Find the rectangle of maximum area with perimeter 20 (maximize xy s.t. 2x + 2y = 20).
Answer. x = y = 5 (a 5x5 square), maximum area 25; lambda = 5.
Problem. Minimize f(x,y) = x^2 + 4y^2 subject to x + 2y = 8 using Lagrange multipliers.
Solution. L = x^2 + 4y^2 + lambda(x + 2y - 8). grad_x: 2x + lambda = 0 -> x = -lambda/2. grad_y: 8y + 2lambda = 0 -> y = -lambda/4. Constraint: x + 2y = 8 -> -lambda/2 - lambda/2 = -lambda = 8 -> lambda = -8. Then x = 4, y = 2. Check: 4 + 2*2 = 8. Minimum value = 16 + 16 = 32, attained at (4, 2).
The picture behind Lagrange: at the best feasible point, you cannot improve without violating the constraint.
Geometrically, the constraint h(x) = 0 defines a surface (a curve in 2D), and grad h is perpendicular to it. The objective's level sets f(x) = c are nested curves; moving along the constraint surface changes f unless the surface is tangent to a level set. At the constrained optimum the level set is tangent to the constraint, which means grad f is perpendicular to the surface too — hence parallel to grad h. That is exactly grad f = -lambda*grad h. If the gradients were not aligned, there would be a direction along the surface that decreases f, so you could improve. This tangency picture is the intuition that makes the Lagrange equations memorable and explains why the multiplier scales the two parallel gradients.
Worked Example 1
Problem. On x^2 + y^2 = 1, where is f(x,y) = x maximized? Use gradient alignment.
Answer. Maximum of f=x on the unit circle is at (1,0), where grad f and grad h align.
Worked Example 2
Problem. Why does a feasible point with non-parallel grad f and grad h fail to be optimal?
Answer. A nonzero tangential component of grad f means a feasible descent direction exists, so the point cannot be optimal; optimality forces gradient alignment.
Problem. Maximize f(x,y) = 3x + 4y on the circle x^2 + y^2 = 25 using gradient alignment, and interpret geometrically.
Solution. grad f = (3,4), grad h = (2x, 2y). Alignment: (3,4) = lambda(2x,2y) -> x = 3/(2lambda), y = 4/(2lambda) = 2/lambda. On the circle: x^2+y^2 = (9 + 16)/(4lambda^2) = 25/(4lambda^2) = 25 -> lambda^2 = 1/4 -> lambda = 1/2 (take positive for max). Then x = 3, y = 4. The level line 3x+4y is tangent to the circle at (3,4); the maximum value is 3*3+4*4 = 25.
Real problems cap and floor things with inequalities; here we handle <= constraints and the idea of active vs. slack.
An inequality constraint g(x) <= 0 either binds at the optimum (g(x*) = 0, active) or has slack (g(x*) < 0, inactive). If a constraint is inactive, the optimum is the same as if it were absent — its multiplier is zero. If it is active, it behaves like an equality and gets a non-negative multiplier. The first task is feasibility: the feasible set is the intersection of all g_i <= 0 and h_j = 0 regions, and you must check candidates lie inside it. Reasoning about which inequalities are active is the key step in solving constrained problems by hand; you guess an active set, solve the resulting equality-constrained system, and verify the multipliers are non-negative and the inactive constraints hold. This active-set logic powers QP solvers used throughout ML.
Worked Example 1
Problem. Minimize f(x) = (x-2)^2 subject to x <= 5. Is the constraint active?
Answer. x* = 2; the constraint x<=5 is inactive (slack), multiplier 0.
Worked Example 2
Problem. Minimize f(x) = (x-2)^2 subject to x <= 1. Now is the constraint active?
Answer. x* = 1; the constraint is active with multiplier mu = 2 (non-negative, as required).
Problem. Minimize f(x) = (x-4)^2 subject to x <= 6 and x >= 0. Which constraints are active, and what is x*?
Solution. Unconstrained minimizer is x=4. Check feasibility: 0 <= 4 <= 6 holds with slack on both sides. So both constraints are inactive (multipliers 0) and x* = 4 with f=0. Neither bound binds because the free optimum already lies inside the feasible interval [0,6].
KKT packages everything — equalities, inequalities, and optimality — into four conditions that characterize a solution.
For minimize f(x) s.t. g_i(x) <= 0 and h_j(x) = 0, the KKT conditions are the first-order necessary conditions (and, for convex problems with a constraint qualification, sufficient). They are: (1) Stationarity — grad f + sum mu_i grad g_i + sum lambda_j grad h_j = 0; (2) Primal feasibility — g_i(x) <= 0 and h_j(x) = 0; (3) Dual feasibility — mu_i >= 0; (4) Complementary slackness — mu_i*g_i(x) = 0. A point satisfying all four (with a qualification like Slater's) is optimal for a convex problem. KKT generalizes both the unconstrained gradient=0 condition and Lagrange's equality condition, and it is the certificate that solvers like CVXPY verify, returning the multipliers as dual values.
Worked Example 1
Problem. Write and check the KKT conditions for minimize x^2 s.t. x >= 1 (i.e. 1 - x <= 0).
Answer. x* = 1, mu = 2; all four KKT conditions hold, so x=1 is optimal.
Worked Example 2
Problem. Verify KKT for minimize (x-3)^2 s.t. x <= 5 where the constraint is inactive.
Answer. x* = 3, mu = 0; KKT confirmed with the constraint inactive.
Worked Example 3
Problem. Set up KKT for minimize x^2 + y^2 s.t. x + y = 1 and x >= 0.
Answer. x*=y*=0.5, lambda=-1, mu=0; the inequality is inactive and all KKT conditions are satisfied.
Problem. State and verify the KKT conditions for minimize (x-5)^2 subject to x <= 2.
Solution. g(x) = x - 2 <= 0. Stationarity: 2(x-5) + mu = 0. The free optimum x=5 violates x<=2, so guess active: x=2, then mu = -2(2-5) = 6 >= 0 (dual feasible). Complementary slackness: mu*(x-2) = 6*0 = 0, holds. Primal feasibility x=2<=2 holds. All four KKT conditions are satisfied, so x* = 2 with multiplier mu = 6.
This single condition links which constraints bind to which multipliers are nonzero — the heart of solving KKT by hand.
Complementary slackness states mu_i * g_i(x*) = 0 for every inequality. It forces an either/or: either the constraint is active (g_i = 0) so its multiplier may be positive, or the constraint is inactive (g_i < 0) so its multiplier must be zero. They cannot both be nonzero. This is what makes the active-set strategy work: you hypothesize a set of active constraints, set their slacks to zero and the inactive multipliers to zero, solve the reduced equality-constrained system, then verify dual feasibility (mu >= 0) and primal feasibility of the dropped constraints. The nonzero multipliers identify the binding constraints and quantify their shadow prices — how much the optimum would improve if you relaxed each binding limit.
Worked Example 1
Problem. A problem has constraints g1: x <= 4 and g2: y <= 10. At the optimum x=4, y=3. Which multipliers can be nonzero?
Answer. mu1 can be positive (g1 active); mu2 must be 0 (g2 has slack).
Worked Example 2
Problem. Use the active-set idea: minimize x^2 + y^2 s.t. x + y >= 4 (i.e. 4 - x - y <= 0). Solve.
Answer. x* = y* = 2, mu = 4 (constraint active); complementary slackness confirmed.
Problem. Minimize x^2 + y^2 subject to x >= 3 (i.e. 3 - x <= 0) and y >= 0. Use complementary slackness to find the optimum and active set.
Solution. Free optimum is (0,0), which violates x>=3, so guess g1: 3-x active. Then x=3. For y: the y>=0 constraint — the free optimum y=0 is feasible and minimizes y^2, so y=0 with that constraint exactly at its boundary but the unconstrained y optimum is already 0, multiplier 0. Stationarity in x: 2x + mu1*(-1)=0 -> mu1 = 2*3 = 6 >= 0. Complementary slackness: mu1*(3-x)=6*0=0. So x*=3, y*=0, mu1=6. Only x>=3 is the binding active constraint.
Bring KKT to code: solvers compute the same primal solution and return the multipliers as dual values you can interpret.
Constrained problems are solved in practice with scipy.optimize.minimize (using a constraints list of dicts for 'eq'/'ineq') or, for convex problems, CVXPY, which is more reliable and exposes dual values directly. In SciPy, inequality constraints are written as fun >= 0; in CVXPY you write natural relations like x >= 0 and read constraint.dual_value. The dual values are exactly the KKT multipliers, so you can confirm hand-derived lambdas/mus and interpret them as shadow prices. The practical workflow is: model the objective and constraints, solve, check the solver converged and the solution is feasible, then read the duals to understand which constraints bind and how sensitive the optimum is. This closes the loop between KKT theory and reliable computation.
Worked Example 1
Problem. Solve minimize x^2 + y^2 s.t. x + y = 1 in CVXPY and read the dual.
Answer. CVXPY returns x=[0.5,0.5], value 0.5, dual ~ -1, agreeing with the Lagrange solution.
Worked Example 2
Problem. Solve minimize (x-2)^2 s.t. x <= 1 with scipy.optimize.minimize and verify the multiplier.
Answer. x* = 1 (constraint active); multiplier mu = 2, matching the hand KKT derivation.
Problem. Set up CVXPY code to minimize x^2 + y^2 subject to x + y >= 4, and predict the solution and dual sign.
Solution. import cvxpy as cp; x = cp.Variable(2); con = [cp.sum(x) >= 4]; prob = cp.Problem(cp.Minimize(cp.sum_squares(x)), con); prob.solve(). The optimum is x = [2, 2] (value 8) since the constraint binds at x+y=4 and symmetry gives equal coordinates. The dual value of the binding x+y>=4 constraint is positive (about 4), reflecting that tightening the requirement raises the optimal cost — a positive shadow price.
Choose a small problem such as minimizing a quadratic subject to one linear equality and one inequality constraint. Solve it by hand with the Lagrangian and verify all four KKT conditions, identifying which constraint is active. Then reproduce the solution in Python with both scipy.optimize.minimize (using constraints) and CVXPY, and confirm the solver's dual values match your multipliers. Interpret one multiplier as a shadow price.
Deliverable · A notebook showing the hand KKT derivation, the SciPy and CVXPY solutions, and a paragraph interpreting the multipliers and the active constraint.
1. At the optimum of an equality-constrained problem, the gradient of the objective is:
Answer B. Lagrange's condition states grad f = sum lambda_j grad h_j, so the objective gradient lies in the span of the constraint gradients.
2. Which is NOT one of the KKT conditions?
Answer C. The KKT conditions are stationarity, primal feasibility, dual feasibility, and complementary slackness; nothing requires an identity Hessian.
3. Complementary slackness states that for each inequality constraint:
Answer A. mu_i * g_i(x) = 0 means either the constraint is active (g_i = 0) or its multiplier is zero, but not both nonzero.
4. For inequality constraints written as g_i(x) <= 0, dual feasibility requires the multipliers mu_i to be:
Answer B. KKT dual feasibility requires mu_i >= 0 for inequality constraints in standard form.
5. An inequality constraint that holds with equality at the optimum is called:
Answer B. A constraint satisfied as g_i(x) = 0 at the solution is active or binding and generally has a nonzero multiplier.
I can solve equality-constrained problems with Lagrange multipliers and interpret the multipliers.
I can write and check the KKT conditions for a problem with inequality constraints.
I can explain complementary slackness and identify which constraints are active at the optimum.
Linear programs optimize a linear objective over a region carved by linear constraints; their geometry explains why the optimum lives at a corner.
A linear program (LP) minimizes a linear objective c^T x subject to linear constraints A x <= b, A_eq x = b_eq, and bounds. The feasible region is a polytope: an intersection of half-spaces with flat faces and sharp corners (vertices). Because both the objective contours and the constraints are linear (flat), the objective can only be pushed lower until it hits the boundary; the lowest point is always attained at a vertex (or along an edge connecting two equally optimal vertices). This corner principle is the foundation of LP algorithms and matters in ML for resource allocation, L1-norm fitting recast as LPs, and optimal transport. Recognizing an LP and writing it in standard form (minimize c^T x s.t. linear constraints) lets you hand it to a guaranteed-optimal solver.
Worked Example 1
Problem. Put 'maximize 3x + 2y subject to x + y <= 4, x <= 3, x,y >= 0' into LP standard form and identify the polytope vertices.
Answer. Standard form: minimize -3x-2y s.t. x+y<=4, x<=3, x,y>=0; optimum at vertex (3,1) with objective value -11 (original max 11).
Worked Example 2
Problem. Solve the LP from Example 1 with SciPy and confirm the corner solution.
Answer. linprog returns x=[3,1], fun=-11, confirming the optimum sits at the polytope vertex (3,1).
Worked Example 3
Problem. Explain why an LP can have infinitely many optimal solutions, and give a condition.
Answer. When the objective gradient is parallel to a constraint face, the optimal set is that entire face (an edge or facet), giving infinitely many optima with the same value.
Problem. Write 'maximize 5x + 4y subject to 6x + 4y <= 24, x + 2y <= 6, x,y >= 0' in LP standard form, then solve it with scipy.optimize.linprog.
Solution. Standard form: minimize -5x - 4y s.t. 6x+4y<=24, x+2y<=6, x,y>=0. In code: from scipy.optimize import linprog; res = linprog([-5,-4], A_ub=[[6,4],[1,2]], b_ub=[24,6], bounds=[(0,None),(0,None)]). The optimum is the vertex where 6x+4y=24 and x+2y=6 meet: solving gives x=3, y=1.5. res.x ~ [3, 1.5], res.fun ~ -21, so the maximum profit is 21 at the corner (3, 1.5).
Two families of algorithms solve LPs: simplex walks the corners, interior-point cuts through the middle.
The simplex method exploits the corner principle: it starts at a feasible vertex and repeatedly moves along an edge to an adjacent vertex that improves the objective, stopping when no neighbor is better — that vertex is globally optimal. Each pivot swaps which constraints are 'active'. Simplex is fast in practice though worst-case exponential. Interior-point methods take a different route: they stay strictly inside the feasible region and follow a smooth 'central path' toward the optimum, solving a sequence of barrier-penalized problems with Newton steps. Interior-point methods have polynomial-time guarantees and scale well to large, sparse LPs and to QPs/conic programs. SciPy's linprog defaults to an interior-point-style 'highs' solver. Knowing both pictures explains solver options and why one may outperform the other on a given problem.
Worked Example 1
Problem. Trace simplex on: maximize 3x + 2y s.t. x + y <= 4, x <= 3, x,y >= 0, starting at vertex (0,0).
Answer. Simplex path (0,0)->(3,0)->(3,1); optimum 11 at (3,1), reached in two pivots.
Worked Example 2
Problem. Solve the same LP with SciPy's interior-point/HiGHS solver and contrast the route.
Answer. Interior-point returns the same optimum x=[3,1], value -11, but approaches it through the feasible interior rather than corner-to-corner.
Problem. For maximize x + y s.t. x <= 2, y <= 3, x,y >= 0, list the simplex vertex path from (0,0) and give the optimum.
Solution. Vertices: (0,0), (2,0), (2,3), (0,3). From (0,0), increase x to its bound -> (2,0), objective 2; then increase y to its bound -> (2,3), objective 5; no neighbor improves, so (2,3) is optimal. Path: (0,0)->(2,0)->(2,3). Optimum value 5 at (2,3). (linprog([-1,-1], bounds=[(0,2),(0,3)]).fun -> -5.)
Every LP has a twin dual LP; its solution reveals shadow prices that tell you the value of relaxing each constraint.
Every LP (the primal) has an associated dual LP built from the same data: a maximization with one dual variable per primal constraint. Strong duality for LPs guarantees their optimal values are equal, so the dual gives a certificate of optimality and a lower bound on the primal at every step. The dual variables are shadow prices: each equals the marginal change in the optimal objective per unit increase of the corresponding constraint's right-hand side. Sensitivity analysis reads these prices to answer 'which resource is worth buying more of?' without re-solving. In ML and operations, duality underlies SVMs (the dual form), optimal transport, and resource pricing. Recognizing the primal-dual pair and interpreting multipliers is what turns an LP solution into actionable insight.
Worked Example 1
Problem. Write the dual of: minimize 4x1 + 3x2 s.t. x1 + x2 >= 2, x1 + 3x2 >= 3, x >= 0.
Answer. Dual: maximize 2y1 + 3y2 s.t. y1 + y2 <= 4, y1 + 3y2 <= 3, y1,y2 >= 0; its optimal value equals the primal's by strong duality.
Worked Example 2
Problem. Read shadow prices from a solved LP using SciPy's marginals.
Answer. The constraint marginals returned by HiGHS are the dual values (shadow prices): each tells how much the optimal cost moves per unit change in that constraint's bound.
Worked Example 3
Problem. A factory's profit LP gives a shadow price of 5 on the labor constraint (100 hours). What does buying 10 more hours do?
Answer. 10 extra labor-hours increase optimal profit by ~50 (price 5 each), so it pays to buy them only if the cost per hour is below 5, and only within the range where the active set is unchanged.
Problem. State the dual of: maximize 3x1 + 5x2 s.t. x1 <= 4, 2x2 <= 12, 3x1 + 2x2 <= 18, x >= 0, and explain what the dual variable on the third constraint means.
Solution. Assign duals y1,y2,y3 >= 0 to the three <= constraints. The dual is: minimize 4 y1 + 12 y2 + 18 y3 s.t. y1 + 3 y3 >= 3 (column x1), 2 y2 + 2 y3 >= 5 (column x2), y >= 0. By strong duality the dual optimum equals the primal optimum (36 for this classic problem). The dual variable y3 on 3x1+2x2<=18 is the shadow price of that resource: it equals the increase in maximum profit per extra unit of the 18-unit budget, valid while the same constraints remain active.
Adding a quadratic objective to linear constraints gives the QP, the workhorse behind SVMs, portfolio optimization, and least squares.
A quadratic program (QP) minimizes (1/2) x^T P x + q^T x subject to linear constraints A x <= b, A_eq x = b_eq. The objective is quadratic, the feasible set still a polytope. The QP is convex exactly when the matrix P is positive semidefinite; then it has a unique optimal value and efficient solvers reach the global optimum. Unlike an LP, the optimum need not be at a vertex — the quadratic bowl can be minimized in the interior of a face or even strictly inside the feasible region if unconstrained there. QPs are central in ML: ridge regression, the soft-margin SVM dual, Markowitz portfolio selection, and model-predictive control are all QPs. Checking that P is PSD is the key step that certifies the problem is convex and solvable.
Worked Example 1
Problem. Identify P, q for the QP: minimize x1^2 + 2 x2^2 + x1 x2 - 3 x1, and confirm convexity.
Answer. P=[[2,1],[1,4]], q=[-3,0]; P is positive definite, so this is a convex QP with a unique minimizer.
Worked Example 2
Problem. Solve the unconstrained convex QP minimize (1/2) x^T P x + q^T x with P=[[2,0],[0,2]], q=[-4,-6].
Answer. Minimizer x = -P^{-1}q = [2, 3]; for a convex QP without active constraints the solution solves P x = -q.
Worked Example 3
Problem. Why is ridge regression a QP? Write min_w ||Xw - y||^2 + lambda ||w||^2 in QP form.
Answer. Ridge regression is a convex QP with P = 2(X^T X + lambda I) (PD for lambda>0) and q = -2 X^T y; its optimum is the ridge normal-equation solution.
Problem. For the QP minimize 2x1^2 + 2x2^2 + 2 x1 x2 - 6 x1 - 4 x2, find P and q, verify convexity, and solve the unconstrained minimum.
Solution. Write as (1/2)x^T P x + q^T x. The x1^2 coefficient 2 needs P11=4, x2^2 needs P22=4, the cross term 2 x1 x2 needs P12=P21=2. So P=[[4,2],[2,4]], q=[-6,-4]. Eigenvalues of P are 2 and 6 (both >0), so P is PD and the QP is convex. Solve P x = -q: [[4,2],[2,4]] x = [6,4]. From 4x1+2x2=6 and 2x1+4x2=4: multiply the second by 2 (4x1+8x2=8), subtract the first to get 6x2=2 -> x2=1/3; then 4x1=6-2/3 -> x1=4/3. Minimizer x=(4/3, 1/3).
The practical skill: recognize when a real decision is linear or quadratic and cast it in solver-ready form.
Modeling means translating a real objective and rules into the LP/QP template. Use an LP when both objective and constraints are linear: production planning, blending/diet, transportation, scheduling, and L1 (absolute-error) fitting after a standard reformulation. Use a QP when the objective has a quadratic term but constraints stay linear: least-squares with bounds, ridge regression, portfolio variance minimization, and the SVM margin. The core moves are: name decision variables, write a linear or quadratic objective, express limits as linear inequalities, and handle absolute values or max terms by introducing auxiliary variables (e.g. minimize t with -t <= expr <= t turns |expr| into an LP). Good modeling exposes the structure so you pick linprog, a QP solver, or CVXPY and get a globally optimal answer.
Worked Example 1
Problem. Model minimizing portfolio risk: minimize variance w^T Sigma w s.t. sum w = 1, w >= 0, given covariance Sigma.
Answer. Minimum-variance portfolio is a convex QP: minimize w^T Sigma w s.t. 1^T w = 1, w >= 0; P=2 Sigma is PSD so it solves globally.
Worked Example 2
Problem. Cast L1 (least-absolute-deviations) regression min_w sum_i |x_i^T w - y_i| as an LP.
Answer. L1 regression becomes an LP by replacing each |r_i| with t_i and the constraints -t_i <= r_i <= t_i, minimizing sum t_i — a classic absolute-value linearization.
Problem. A diet must provide >= 60 protein and >= 40 fiber. Food A: 3 protein, 1 fiber, cost 2. Food B: 1 protein, 2 fiber, cost 3. Model the minimum-cost diet as an LP.
Solution. Variables: a, b >= 0 (servings). Objective (linear): minimize 2a + 3b. Constraints (linear): 3a + b >= 60 (protein), a + 2b >= 40 (fiber), a,b >= 0. This is an LP. In scipy: linprog([2,3], A_ub=[[-3,-1],[-1,-2]], b_ub=[-60,-40], bounds=[(0,None),(0,None)]). The optimum sits at the vertex where both constraints bind: solving 3a+b=60 and a+2b=40 gives a=16, b=12, cost 2*16+3*12=68.
Two tools: scipy.optimize.linprog for LPs and CVXPY for both LPs and QPs with readable, near-mathematical syntax.
SciPy's linprog solves LPs given c, A_ub, b_ub, A_eq, b_eq, and bounds, returning an OptimizeResult with .x, .fun, and constraint marginals (duals). For QPs and richer convex problems, CVXPY lets you declare variables and write the objective and constraints almost as you would on paper; it then compiles the problem, dispatches to an appropriate solver, and returns the optimum. CVXPY enforces disciplined convex programming, so if it accepts your model it is provably convex and the answer is globally optimal. The practical workflow is: write the model, call prob.solve(), then read variable.value and prob.value, and check prob.status == 'optimal'. Mastering these tools is what makes the modeling skills of this unit actually executable for real ML and operations problems.
Worked Example 1
Problem. Solve a small LP with CVXPY: maximize 3x + 2y s.t. x + y <= 4, x <= 3, x,y >= 0.
Answer. CVXPY returns x=3, y=1, objective 11 with status 'optimal' — note CVXPY handles the maximize directly, no manual negation.
Worked Example 2
Problem. Solve a convex QP with CVXPY: minimize (1/2)(x1^2 + x2^2) + x1 s.t. x1 + x2 = 1, x >= 0.
Answer. CVXPY solves the QP to x ~ [0, 1] with optimal value ~0.5; sum_squares keeps the model disciplined-convex.
Worked Example 3
Problem. Solve the minimum-variance portfolio QP in CVXPY for Sigma=[[0.1,0.02],[0.02,0.08]].
Answer. CVXPY's quad_form encodes w^T Sigma w; it returns the fully-invested, long-only weights minimizing portfolio variance, with status 'optimal'.
Problem. Use CVXPY to solve: minimize x^2 + y^2 subject to x + y >= 2, x,y >= 0, and report the optimal point and value.
Solution. import cvxpy as cp; x = cp.Variable(nonneg=True); y = cp.Variable(nonneg=True); prob = cp.Problem(cp.Minimize(x**2 + y**2), [x + y >= 2]); prob.solve(). The constraint binds at x+y=2 and symmetry/convexity gives x=y=1. So x.value ~ 1.0, y.value ~ 1.0, prob.value ~ 2.0, prob.status 'optimal'. (Check: the unconstrained min is (0,0) but it violates x+y>=2, so the optimum lies on the active line x+y=2 at its closest point to the origin, (1,1).)
Formulate a small resource-allocation problem (for example, a diet or production-mix problem) as a linear program in standard form. Solve it with scipy.optimize.linprog and again with CVXPY, confirming the objective values match. Then add a quadratic penalty (turning it into a QP, e.g. least-squares with bounds) and solve it in CVXPY. Use the dual values to do a one-line sensitivity analysis on a binding constraint.
Deliverable · A notebook with the LP and QP formulations, both solver solutions, and a short sensitivity interpretation from the dual values.
1. The optimum of a bounded, feasible linear program is always attained:
Answer B. Because both objective and constraints are linear, an optimum (if it exists) occurs at a vertex of the feasible polytope.
2. A quadratic program differs from a linear program because it has:
Answer B. A QP keeps linear constraints but allows a quadratic (typically convex) objective; LPs have a purely linear objective.
3. Strong duality for a feasible LP means:
Answer A. For linear programs, strong duality holds: when an optimum exists, the primal and dual optimal objective values coincide.
4. The simplex method finds an LP optimum by:
Answer B. Simplex traverses adjacent vertices of the polytope, improving the objective until no neighboring vertex is better.
5. Which SciPy function is intended for solving linear programs?
Answer A. scipy.optimize.linprog solves linear programs in standard form; the others handle linear systems, curve fitting, and distributions.
I can put a linear program in standard form and describe its feasible region as a polytope.
I can model a resource-allocation or fitting problem as an LP or QP.
I can solve LPs and QPs with SciPy or CVXPY and interpret the dual/sensitivity output.
A convex problem is the gold standard of tractability; disciplined convex programming (DCP) is the rule system that keeps your models in that safe zone.
A convex optimization problem minimizes a convex objective over a convex feasible set: minimize f0(x) s.t. fi(x) <= 0 with each fi convex and equalities Ax = b affine. Its great property is that any local optimum is global, so solvers return a certified best answer in polynomial time. Disciplined convex programming (DCP), the ruleset behind CVXPY, builds expressions only from a library of atoms with known curvature (convex, concave, affine) and sign, combined by rules that provably preserve convexity. If a model passes DCP, it is guaranteed convex and solvable; if it fails, CVXPY refuses rather than returning a wrong answer. This discipline matters in ML because it lets you compose losses, norms, and constraints confidently and get globally optimal estimators without proving convexity by hand each time.
Worked Example 1
Problem. Is 'minimize cp.square(x) + cp.abs(y) s.t. x + y == 1' DCP-valid? Explain.
Answer. Yes, it is DCP-valid: a sum of convex atoms minimized over an affine equality, so CVXPY accepts and solves it globally.
Worked Example 2
Problem. Why does 'minimize cp.square(x) * cp.square(y)' fail DCP even though each factor is convex?
Answer. It fails DCP because a product of two nonconstant convex terms is not provably convex; CVXPY returns is_dcp() False rather than risk a wrong solve.
Problem. Decide whether 'minimize cp.norm(A @ x - b, 2) subject to cp.norm(x, 1) <= 1' is a DCP convex problem, and say why.
Solution. cp.norm(A@x-b, 2) is the composition of the convex 2-norm atom with an affine argument A@x-b, so the objective is convex. The constraint uses the convex 1-norm of x bounded above by a constant (cp.norm(x,1) <= 1), which defines a convex sublevel set. Objective convex, constraint set convex -> it is a DCP-valid convex problem (a LASSO-type / norm-ball problem). In code, cp.Problem(cp.Minimize(cp.norm(A@x-b,2)), [cp.norm(x,1) <= 1]).is_dcp() returns True, so CVXPY solves it to a global optimum.
You rarely prove convexity from scratch; instead you build convex functions from convex pieces using a small set of safe operations.
Convexity is preserved under specific operations, and chaining them is how DCP works. Key rules: a nonnegative weighted sum of convex functions is convex; a pointwise maximum (or supremum) of convex functions is convex; composition with an affine map, f(Ax + b), preserves convexity; and certain scalar compositions are convex (e.g. h(g(x)) is convex when h is convex-and-nondecreasing and g is convex). Norms are convex; the max of linear functions is convex (piecewise-linear). Conversely, a pointwise minimum of convex functions is generally not convex. Knowing these rules lets you certify complex objectives — like a regularized hinge loss sum or a max over linear scores — as convex by inspection, which is exactly how losses in SVMs, robust regression, and many ML models are shown solvable.
Worked Example 1
Problem. Show f(x) = max(0, 1 - x) (the hinge) is convex.
Answer. The hinge max(0, 1-x) is convex as a pointwise max of two affine functions; this is why SVM training is a convex problem.
Worked Example 2
Problem. Is g(x) = (sum_i x_i^2)^2 (square of a convex function) convex? Use the composition rule.
Answer. Yes, convex: h(u)=u^2 is convex and nondecreasing on u>=0 and the inner sum-of-squares is convex and nonnegative, so the composition is convex.
Worked Example 3
Problem. Show that the pointwise MINIMUM of two convex functions can fail to be convex.
Answer. min((x+2)^2,(x-2)^2) has two separate minima and a hump between them, so it is nonconvex — the minimum operation does not preserve convexity.
Problem. Use convexity-preserving rules to argue that f(x) = ||Ax - b||^2 + lambda ||x||_1 (lambda >= 0) is convex.
Solution. ||Ax-b|| is the composition of the convex 2-norm with the affine map Ax-b, hence convex; squaring it via h(u)=u^2 (convex, nondecreasing on u>=0) keeps it convex, so ||Ax-b||^2 is convex. ||x||_1 is a norm, hence convex. A nonnegative weighted sum of convex functions is convex, and lambda>=0, so ||Ax-b||^2 + lambda||x||_1 is convex. This is the LASSO objective, certified convex purely by composition rules, so any convex solver (or CVXPY) finds its global optimum.
Norms are the building blocks of regularizers; their geometry explains why L1 gives sparsity and L2 gives smooth shrinkage.
A norm measures size and is always convex; the common ones are the L2 (Euclidean) norm sqrt(sum x_i^2), the L1 norm sum |x_i|, and the L-infinity norm max |x_i|. Used as regularizers added to a loss, they pull solutions toward smaller, simpler parameter vectors. The geometry matters: the L1 ball is a diamond with sharp corners on the axes, so the optimum of loss-plus-L1 tends to land at a corner where some coordinates are exactly zero — that is why the LASSO produces sparse models (feature selection). The L2 ball is a smooth sphere, so ridge regularization shrinks all coordinates smoothly without forcing zeros. Common convex objectives — least squares, ridge, LASSO, logistic loss, hinge loss — are all convex sums of these pieces, which is why they train reliably to a global optimum.
Worked Example 1
Problem. Compute the L1, L2, and L-infinity norms of x = (3, -4, 0).
Answer. L1 = 7, L2 = 5, L-infinity = 4; each norm is convex and emphasizes a different notion of vector size.
Worked Example 2
Problem. Explain geometrically why minimizing loss + lambda||w||_1 produces zeros while loss + lambda||w||_2^2 does not.
Answer. L1's diamond corners sit on the axes, so the optimum is pushed onto a zero coordinate (sparsity); L2's smooth sphere yields uniform shrinkage with no exact zeros.
Worked Example 3
Problem. Set up the LASSO objective in CVXPY and solve a tiny instance.
Answer. CVXPY minimizes sum_squares(Aw-b) + lam*||w||_1; the L1 penalty yields a sparse w, and increasing lam zeros out more coefficients — the LASSO feature-selection effect.
Problem. For w = (0, -2, 1, -1), compute ||w||_1, ||w||_2, and ||w||_inf, and say which regularizer would most encourage exact zeros.
Solution. ||w||_1 = 0 + 2 + 1 + 1 = 4. ||w||_2 = sqrt(0 + 4 + 1 + 1) = sqrt(6) ~ 2.449. ||w||_inf = max(0,2,1,1) = 2. The L1 norm (sum of absolute values) most encourages exact zeros: its diamond-shaped ball has corners on the coordinate axes, so loss-plus-L1 tends to set small coefficients to exactly 0, producing a sparse solution, whereas L2 only shrinks them toward zero without eliminating them.
Duality builds a companion problem whose optimum bounds the original; for convex problems the two values often coincide exactly.
Given minimize f0(x) s.t. fi(x) <= 0, hj(x) = 0, the Lagrangian is L(x, lambda, nu) = f0(x) + sum lambda_i fi(x) + sum nu_j hj(x) with lambda_i >= 0. The Lagrange dual function g(lambda, nu) = inf_x L is the minimum of the Lagrangian over x; it is always concave (an infimum of affine functions of the multipliers) regardless of the primal. The dual problem maximizes g over lambda >= 0, nu. Its optimal value d* is always a lower bound on the primal p* (weak duality). Duality is powerful: it produces certificates of optimality, turns constrained problems into often-simpler dual problems, and reveals structure — the SVM is usually solved in its dual form, and the dual multipliers are the support-vector weights. Building and reading the dual is a core convex-optimization skill.
Worked Example 1
Problem. Form the dual function for minimize x^2 s.t. x >= 1 (i.e. 1 - x <= 0).
Answer. Dual function g(lambda) = lambda - lambda^2/4, maximized at lambda=2 giving d* = 1, which matches the primal optimum x=1, f=1.
Worked Example 2
Problem. Why is the dual function always concave, and what does that buy us?
Answer. Because g is an infimum of affine functions of the multipliers, it is concave; thus the dual is always a convex (maximize-concave) problem, useful even for nonconvex primals.
Problem. Form and solve the Lagrange dual of: minimize x^2 + y^2 subject to x + y = 1.
Solution. Lagrangian L(x,y,nu) = x^2 + y^2 + nu(x + y - 1) (equality multiplier nu is free). Minimize over x,y: dL/dx = 2x + nu = 0 -> x = -nu/2; similarly y = -nu/2. Substitute into L: g(nu) = 2*(nu/2)^2 + nu(-nu - 1) = nu^2/2 - nu^2 - nu = -nu^2/2 - nu. Maximize: g'(nu) = -nu - 1 = 0 -> nu = -1, g(-1) = -0.5 + 1 = 0.5. So d* = 0.5, matching the primal optimum x=y=0.5 with value 0.5 (strong duality holds for this convex problem).
Weak duality always holds; strong duality (no gap) is what makes the dual exactly solve the primal, and Slater's condition guarantees it for convex problems.
Weak duality always holds: the dual optimum d* is a lower bound on the primal optimum p*, so p* - d* = the duality gap >= 0. Strong duality means the gap is zero, p* = d*, so solving the dual solves the primal. Strong duality is not automatic, but for a convex problem it holds under a constraint qualification — most commonly Slater's condition: there exists a strictly feasible point where all inequality constraints hold strictly (fi(x) < 0) and equalities are met. When Slater holds, p* = d* and the optimal multipliers exist, which is the theoretical backbone of KKT-based and interior-point solvers. This is why convex problems are so well-behaved: you can solve whichever of primal or dual is easier and trust the values match — exploited heavily in SVM training and convex ML estimators.
Worked Example 1
Problem. Check Slater's condition for minimize x^2 s.t. x >= 1, and conclude about strong duality.
Answer. Slater holds (x=2 is strictly feasible), so strong duality holds and the dual value d*=1 equals the primal p*=1 — zero duality gap.
Worked Example 2
Problem. Give the duality gap for a problem where p* = 5 and the best dual value found is d* = 3, and interpret it.
Answer. The duality gap is 2; since it is nonzero, strong duality does not hold here (the problem is likely nonconvex or fails a constraint qualification).
Problem. Does Slater's condition hold for minimize x^2 + y^2 subject to x + y <= -1? If so, what does it imply?
Solution. The objective x^2+y^2 is convex and the constraint x+y+1 <= 0 is affine (convex). Slater needs a strictly feasible point: pick (x,y)=(-1,-1), then x+y = -2 < -1, so x+y+1 = -1 < 0 strictly. A strictly feasible point exists, so Slater's condition holds. This implies strong duality: the primal and dual optimal values are equal (zero duality gap) and optimal Lagrange multipliers exist. (The primal optimum is the point on x+y=-1 nearest the origin, (-0.5,-0.5), with value 0.5.)
The capstone tool: express a convex problem in near-mathematical CVXPY syntax, solve it, and read a certified-optimal answer.
CVXPY is a Python modeling language for convex optimization. You declare cp.Variable objects, write a cp.Minimize or cp.Maximize objective from DCP atoms (sum_squares, norm, quad_form, log, entr, etc.), list constraints, build a cp.Problem, and call .solve(). CVXPY verifies the model is DCP-convex, transforms it to a standard conic form, dispatches to a solver (ECOS, OSQP, SCS, Clarabel), and returns the optimum; you read variable.value, prob.value, and check prob.status == 'optimal'. The workflow scales from least squares and LASSO to SVMs, portfolio optimization, and control. Mastering CVXPY ties together the whole unit: norms and regularizers become atoms, convexity-preserving operations become valid compositions, and duality is available via constraint.dual_value. It is the practical bridge from convex theory to working, globally-optimal ML and decision models.
Worked Example 1
Problem. Solve regularized least squares (ridge): minimize ||Ax - b||^2 + ||x||^2 in CVXPY for a small A, b.
Answer. CVXPY returns the ridge estimate x = (A^T A + I)^{-1} A^T b with status 'optimal'; sum_squares keeps the model disciplined-convex.
Worked Example 2
Problem. Model a soft-margin SVM-style objective in CVXPY: minimize (1/2)||w||^2 + C*sum(hinge) for labels y, features X.
Answer. The SVM objective is convex (squared norm plus a sum of hinges); CVXPY's cp.pos encodes the hinge and returns the optimal (w, b) — note SVMs are convex, so the solution is global.
Worked Example 3
Problem. Retrieve a dual value (shadow price) from a solved CVXPY problem.
Answer. CVXPY exposes each constraint's optimal multiplier via constraint.dual_value (here ~2), giving the shadow price directly from the solve.
Problem. Use CVXPY to solve: minimize ||x||_1 subject to A x = b, with A = [[1, 1, 1]], b = [1] (an underdetermined sparse-recovery problem), and describe the expected solution.
Solution. import cvxpy as cp, numpy as np; A = np.array([[1.,1.,1.]]); b = np.array([1.]); x = cp.Variable(3); prob = cp.Problem(cp.Minimize(cp.norm(x,1)), [A@x == b]); prob.solve(). The objective ||x||_1 is convex and the constraint A x = b is affine, so this is a convex (DCP) problem. Minimizing the L1 norm subject to a single equality gives a sparse solution: it places all the mass on one coordinate, e.g. x ~ [1, 0, 0] (any single-coordinate solution achieves ||x||_1 = 1, the minimum). prob.value ~ 1.0, status 'optimal'. This is the basis-pursuit / compressed-sensing principle that L1 minimization recovers sparse vectors.
Pick a convex problem such as L1-regularized (lasso) or L2-regularized least squares, or a robust regression. Express it in CVXPY using DCP-compliant atoms and solve it for several regularization strengths. Verify your model is recognized as convex by CVXPY, plot how the solution changes with the regularizer, and inspect the dual variables of any constraints. Briefly state why each term keeps the problem convex.
Deliverable · A CVXPY notebook with the convex model, a regularization-path plot, the reported dual values, and a short convexity justification.
1. In a convex optimization problem, the objective is convex and the feasible set is:
Answer B. A convex program requires both a convex objective and a convex feasible set, which is what guarantees global optimality of local minima.
2. Which operation preserves convexity?
Answer A. The pointwise maximum of convex functions is convex; negation gives concavity and products/minima need not preserve convexity.
3. Weak duality guarantees that the dual optimal value is:
Answer B. Weak duality always holds: the dual optimum is a lower bound on the primal (minimization) optimum, so the gap is non-negative.
4. Slater's condition is important because it:
Answer A. For convex problems, Slater's constraint qualification (a strictly feasible point) ensures strong duality, so the duality gap is zero.
5. CVXPY enforces disciplined convex programming (DCP) in order to:
Answer B. DCP rules let CVXPY verify convexity by construction, so it can reliably transform and hand the problem to a convex solver.
I can recognize a convex program and use convexity-preserving rules to build one.
I can form the Lagrangian dual and explain the duality gap and when it is zero.
I can express and solve a convex problem in CVXPY using disciplined convex programming.
Training a model is literally an optimization problem — minimize average loss over the data — which is what ties this whole course to machine learning.
Empirical risk minimization (ERM) frames supervised learning as optimization: choose parameters w to minimize the average loss over the training set, R_emp(w) = (1/n) sum_i L(f_w(x_i), y_i). The true goal is to minimize the expected (population) risk, but since the data distribution is unknown we minimize the empirical risk as a surrogate, often adding a regularizer to control overfitting. This makes every learning algorithm an instance of the optimization machinery built earlier: pick a model f_w, a loss L, run gradient-based or convex solvers to drive grad R_emp toward zero. Whether the resulting problem is easy (convex, like linear/logistic regression) or hard (nonconvex, like deep nets) is exactly the convexity question from Unit 1. ERM is the unifying lens: data + loss + regularizer = an optimization problem.
Worked Example 1
Problem. Write the ERM objective for linear regression with MSE loss on data (x_i, y_i), i=1..n.
Answer. ERM objective R(w) = (1/n)||Xw - y||^2; it is convex (Hessian (2/n)X^T X is PSD), so least squares solves it globally.
Worked Example 2
Problem. Add L2 regularization (ridge) to the ERM objective and write the gradient for gradient descent.
Answer. Regularized ERM: R(w) = (1/n)||Xw-y||^2 + lambda||w||^2 with gradient (2/n)X^T(Xw-y) + 2 lambda w; convex, so gradient descent reaches the global ridge solution.
Problem. Write the empirical-risk objective for logistic regression with the log-loss on labels y_i in {0,1}, and state whether it is convex.
Solution. Model probability p_i = sigma(w^T x_i) with sigma the logistic function. Log-loss: L_i = -[y_i log p_i + (1-y_i) log(1-p_i)]. Empirical risk R(w) = (1/n) sum_i L_i. This objective is convex in w: the negative log-likelihood of logistic regression has Hessian X^T D X with D a diagonal of p_i(1-p_i) >= 0, which is positive semidefinite, so R(w) is convex. Therefore gradient descent (or Newton/IRLS) converges to the global minimum, and adding lambda||w||^2 keeps it strictly convex.
The loss you choose decides the optimization landscape and what the model is rewarded for; knowing each shape is essential.
Different tasks use different losses, each with a characteristic shape that drives optimization. Squared error (regression) is a smooth convex parabola that penalizes large residuals quadratically — sensitive to outliers. Absolute error (L1) is convex but kinked at zero, robust to outliers, and yields a non-smooth problem. The Huber loss blends the two: quadratic near zero, linear far out, giving robustness with smoothness. For classification, log-loss (cross-entropy) is smooth and convex, heavily penalizing confident wrong predictions, while hinge loss (SVM) is convex and piecewise-linear, zero once the margin is satisfied. All these losses are convex in the model's score, which is why linear models train reliably; the nonconvexity in deep learning comes from composing them with nonlinear networks. Matching loss shape to the task and to outlier behavior is a core modeling decision.
Worked Example 1
Problem. Compute squared, absolute, and Huber (delta=1) loss for a residual r = 3.
Answer. Squared = 9, absolute = 3, Huber = 2.5; squared loss penalizes the outlier far more, motivating robust losses like Huber/L1.
Worked Example 2
Problem. Compute the hinge loss for a correctly-classified point with margin y*score = 1.5 and for a violated one with y*score = -0.2.
Answer. Hinge loss is 0 for the well-classified point (margin >= 1) and 1.2 for the violated one; only margin violations are penalized.
Worked Example 3
Problem. Compute log-loss for a true label y=1 when the model predicts probability p=0.9 vs. p=0.1.
Answer. Log-loss is ~0.105 for the confident correct prediction and ~2.303 for the confident wrong one; cross-entropy harshly punishes confident mistakes.
Problem. For residuals r = [0.5, 4], compute the total squared loss and total Huber loss (delta=1), and explain the difference.
Solution. Squared: 0.5^2 + 4^2 = 0.25 + 16 = 16.25. Huber (delta=1): for r=0.5, |r| <= delta so loss = 0.5*r^2 = 0.5*0.25 = 0.125; for r=4, |r| > delta so loss = delta*(|r| - 0.5*delta) = 1*(4 - 0.5) = 3.5. Total Huber = 0.125 + 3.5 = 3.625. The squared loss (16.25) is dominated by the single large residual (16 of it), whereas Huber grows only linearly past delta, so the outlier contributes 3.5 instead of 16. Huber is far more robust to the outlier while staying smooth near zero.
The geometry of the loss surface determines whether training is a solved problem or a search — this is the convex/nonconvex divide in action.
A loss landscape is the surface of loss values over the parameter space. For convex models (linear/logistic regression, SVM, LASSO) the landscape is a single convex bowl: one connected set of global minima, no traps, so any descent method finds the best parameters and the answer is essentially unique up to flat directions. Neural networks produce highly nonconvex landscapes: many local minima, saddle points, plateaus, and symmetries (permuting hidden units leaves the loss unchanged). Remarkably, in high dimensions most critical points are saddles rather than bad local minima, and many local minima have similar low loss, so SGD with good initialization and momentum reliably finds a good (not provably global) solution. Understanding which regime you are in tells you whether to trust convergence (convex) or to care about initialization, restarts, and architecture (nonconvex).
Worked Example 1
Problem. Contrast the landscape of L(w) = ||Xw - y||^2 with a two-layer net loss, in terms of minima.
Answer. The least-squares landscape is a single convex bowl (global optimum guaranteed); the neural-net landscape is nonconvex with many minima/saddles, so the outcome depends on initialization.
Worked Example 2
Problem. Why do weight-permutation symmetries create many equivalent minima in a neural net?
Answer. Reordering hidden units leaves the network function (and loss) unchanged, so each minimum has h! symmetric copies, making neural-net minima inherently non-unique.
Problem. You train the same network twice from two random seeds and get two different weight vectors with nearly equal training loss. Explain why this is expected and consistent with the loss-landscape picture.
Solution. Neural-network loss landscapes are nonconvex and riddled with symmetries (e.g. permuting hidden units, or sign flips with odd activations) plus many distinct low-loss basins. Different random initializations start the optimizer in different basins of attraction, so SGD converges to different parameter vectors. Because many of these minima have comparably low loss (a known empirical property of overparameterized nets), the two runs reach nearly equal training loss despite different weights. This is fully consistent with the landscape view: there is no single global optimum but a large set of good solutions, and initialization selects which one you find.
Regularization adds a penalty that trades a little bias for a lot less variance — the lever that controls overfitting.
Regularization adds a penalty to the loss to discourage overly complex models: ridge (L2) adds lambda||w||^2, LASSO (L1) adds lambda||w||_1. This implements the bias-variance tradeoff: an unregularized flexible model has low bias but high variance (it overfits noise), while a heavily regularized model has higher bias but lower variance. The regularization strength lambda tunes this balance — larger lambda shrinks weights more, raising bias and lowering variance. L2 shrinks all coefficients smoothly and stabilizes ill-conditioned problems (it adds lambda to the Hessian's eigenvalues, improving conditioning). L1 drives some coefficients to exactly zero, performing feature selection and yielding sparse, interpretable models. From the optimization view, both keep the convex problem well-posed; choosing lambda by cross-validation is how you minimize the expected (test) error rather than just training error.
Worked Example 1
Problem. Show how ridge (L2) improves conditioning: compare the Hessian of least squares vs. ridge.
Answer. Ridge adds lambda I to X^T X, lifting all eigenvalues by lambda; this guarantees positive definiteness and a smaller condition number, stabilizing the fit.
Worked Example 2
Problem. As lambda increases from 0 to large, describe what happens to bias, variance, and sparsity (for L1).
Answer. Increasing lambda raises bias and lowers variance; an intermediate lambda minimizes test error, and for L1 larger lambda yields more exact zeros (more sparsity).
Worked Example 3
Problem. Select lambda by cross-validation in scikit-learn for ridge regression (sketch the code).
Answer. RidgeCV searches alphas via 5-fold CV and picks model.alpha_ that minimizes validation error — the principled way to set the bias-variance lever.
Problem. A model has near-perfect training accuracy but poor test accuracy. Explain in bias-variance terms and say how L2 regularization helps and how you would choose its strength.
Solution. Near-perfect training accuracy with poor test accuracy is the signature of high variance / overfitting: the model has fit noise in the training data (low bias, high variance). L2 regularization adds lambda||w||^2, shrinking the weights toward zero, which reduces the model's effective complexity and variance at the cost of a small increase in bias. From the optimization side it also adds lambda I to the Hessian, improving conditioning and stability. To choose lambda, use k-fold cross-validation (e.g. RidgeCV over a logspace grid of alphas) and pick the value that minimizes validation error — the lambda that best balances bias and variance for generalization, not the one that minimizes training error (which would be lambda=0).
In high-dimensional deep nets the real obstacle is saddle points, not bad local minima — and overparameterization surprisingly helps.
In nonconvex training the gradient vanishes not only at minima but at saddle points, where the Hessian has both positive and negative eigenvalues. In high dimensions saddles vastly outnumber local minima, and they slow training because the gradient is tiny near them — but they are escapable: a direction of negative curvature exists, and SGD's noise plus momentum push the iterate out. Bad local minima (much worse than global) turn out to be rare in large nets. Overparameterization — using more parameters than data points — reshapes the landscape so that almost all minima achieve near-zero training loss and are connected, making optimization easier rather than harder, and (with implicit regularization from SGD) often generalizing well. Practically this means: don't fear saddles unduly, use stochastic methods with momentum, and large models can be easier to train.
Worked Example 1
Problem. Classify the critical point (0,0) of f(x,y) = x^2 - y^2 and explain why gradient descent stalls there.
Answer. (0,0) is a saddle (Hessian eigenvalues +2, -2); the small gradient near it stalls plain GD, but a negative-curvature escape direction exists, which SGD noise/momentum exploit.
Worked Example 2
Problem. Why does overparameterization tend to make training loss reach (near) zero?
Answer. Overparameterization creates a large, connected set of zero-loss solutions, so descent easily reaches one; implicit regularization from SGD then favors a generalizing member of that set.
Problem. At a critical point of a loss, the Hessian eigenvalues are {3, 0.5, -2, 4}. Is it a minimum, maximum, or saddle, and what does it imply for training?
Solution. The Hessian has both positive eigenvalues (3, 0.5, 4) and a negative one (-2), so it is indefinite -> the point is a saddle point, not a minimum or maximum. The negative eigenvalue -2 indicates a direction of negative curvature along which the loss decreases. For training, the gradient is zero here so plain gradient descent can stall and waste iterations near the saddle, but because an escape direction exists, stochastic gradients (SGD noise) and momentum will perturb the iterate along the negative-curvature direction and let it continue descending. This is why saddles, though they slow training, are not fatal in practice.
Beyond the update rule, practical training is about controlling the learning rate over time and knowing when to stop — read the curves.
Practical training wraps the optimizer in control logic. A learning-rate schedule (step decay, cosine annealing, warmup) takes big early steps then refines, which is essential for SGD's noise to settle. Early stopping monitors validation loss and halts when it stops improving (with a patience window), acting as implicit regularization that prevents overfitting without changing the loss. Diagnostics are how you steer: plot training and validation loss versus epoch — a rising/oscillating curve means the learning rate is too high; a flat curve means it is too low or gradients vanish; a widening train-vs-validation gap means overfitting; both still falling means keep training. Gradient-norm tracking catches vanishing/exploding gradients. Together, schedules + early stopping + curve reading turn the raw optimizer into a reliable training recipe.
Worked Example 1
Problem. Validation loss: epochs [1.0, 0.7, 0.55, 0.54, 0.56, 0.58] with early-stopping patience 2. When does training stop and which weights are kept?
Answer. Training stops after epoch 6 (2 epochs without improvement); the kept weights are from epoch 4, where validation loss was lowest (0.54).
Worked Example 2
Problem. Diagnose: training loss keeps falling but validation loss has been rising for several epochs. What is happening and what do you do?
Answer. It is overfitting (generalization gap widening); apply early stopping at the validation minimum and/or add regularization rather than training further.
Worked Example 3
Problem. Cosine schedule with warmup: linear warmup for 5 steps to eta_max=0.1, then cosine decay over 95 steps. Give eta at steps 0, 5, 100.
Answer. eta = 0 at step 0 (warmup start), 0.1 at step 5 (peak), and 0 at step 100 (end of cosine decay); warmup stabilizes early training, cosine cools it to zero.
Problem. Validation loss over epochs is [0.9, 0.6, 0.5, 0.52, 0.49, 0.51, 0.53] with early-stopping patience 2. State when training stops and which epoch's weights are restored.
Solution. Track the best (lowest) validation loss and a no-improvement counter. Epoch 1:0.9 (best). Epoch 2:0.6 (best). Epoch 3:0.5 (best). Epoch 4:0.52 (>0.5, counter=1). Epoch 5:0.49 (new best, counter resets to 0). Epoch 6:0.51 (>0.49, counter=1). Epoch 7:0.53 (>0.49, counter=2 -> patience exhausted). Training stops after epoch 7, and the restored weights are from epoch 5, where validation loss was the minimum (0.49). The dip at epoch 5 mattered: a naive stop after the epoch-4 uptick would have missed the better epoch-5 model, which is why patience > 0 is used.
The capstone: combine ERM, a loss, an optimizer, regularization, and diagnostics into one end-to-end training-and-tuning workflow.
End-to-end model training ties the whole course together. The workflow: (1) frame the task as ERM — pick a model and a loss; (2) split data into train/validation/test; (3) choose an optimizer (convex solver or SGD/Adam) and a learning-rate schedule; (4) add regularization (L1/L2) and tune its strength plus the learning rate via a validation set or cross-validation; (5) use early stopping and read loss curves to control training; (6) report final performance on the held-out test set only once. Each step draws on earlier units: convexity tells you whether the optimum is guaranteed, gradient methods do the fitting, regularization controls the bias-variance tradeoff, and diagnostics keep training honest. This disciplined loop is how optimization theory becomes a working, well-generalizing model.
Worked Example 1
Problem. Outline an end-to-end logistic-regression training pipeline with hyperparameter tuning in scikit-learn.
Answer. Pipeline: split data, fit L2-regularized logistic regression with C chosen by 5-fold CV on the training set, then report accuracy on the untouched test set — a complete tune-and-evaluate loop.
Worked Example 2
Problem. Why must the test set be touched only once, at the very end?
Answer. Tuning against the test set leaks information and inflates the score; the test set must stay untouched until the final, single evaluation to give an honest estimate of generalization.
Worked Example 3
Problem. Sketch a from-scratch training loop combining mini-batch SGD, L2 regularization, a decaying learning rate, and early stopping.
Answer. The loop fuses mini-batch SGD, an L2 gradient term, a per-epoch learning-rate decay, and validation-based early stopping with best-weight restore — the full practical training recipe in one place.
Problem. You must train and tune a regularized linear classifier. Describe the full workflow from raw data to a reported generalization estimate, naming the role of each optimization concept from this course.
Solution. 1) Frame as ERM: choose a convex loss (logistic/hinge) and a linear model, so by convexity the optimizer reaches a global minimum. 2) Split data into train/validation/test. 3) Standardize features so the loss is well-conditioned (low condition number -> fast, stable gradient descent). 4) Add an L2 (or L1) regularizer to manage the bias-variance tradeoff; this also makes the Hessian PD (well-posed convex problem). 5) Fit with gradient descent / SGD / Adam using a learning-rate schedule (warmup + decay) and monitor training and validation loss curves. 6) Tune the regularization strength lambda and learning rate via k-fold cross-validation, picking values that minimize validation error. 7) Use early stopping at the validation minimum to prevent overfitting. 8) Finally, evaluate the chosen model once on the untouched test set to report an unbiased generalization estimate. Every step maps to a course concept: convexity (guaranteed optimum), conditioning (feature scaling), gradient methods (fitting), regularization (bias-variance), and diagnostics (curves, early stopping).
Train a regularized logistic-regression or linear model on a small dataset by minimizing its loss with gradient-based optimization (your own loop or scikit-learn/CVXPY). Sweep the L2 (and optionally L1) regularization strength, plotting training vs. validation loss to expose the bias-variance tradeoff and any sparsity from L1. Then take a tiny neural net and visualize a 1D or 2D slice of its loss landscape to contrast its nonconvexity with the convex linear model.
Deliverable · A notebook with the regularization-path and train/validation curves, an L1 sparsity comparison, a loss-landscape slice for the neural net, and a paragraph linking regularization to optimization and generalization.
1. Empirical risk minimization trains a model by minimizing:
Answer B. ERM picks parameters that minimize the average (empirical) loss on the training set, a standard optimization problem.
2. Compared with linear/logistic regression, a deep neural network's loss landscape is:
Answer B. Linear models give convex losses, but neural networks produce nonconvex landscapes riddled with saddle points and multiple minima.
3. Adding an L1 penalty to the loss tends to:
Answer A. The L1 (lasso) penalty drives many coefficients exactly to zero, yielding sparse models useful for feature selection.
4. Increasing regularization strength generally:
Answer B. Stronger regularization constrains the model, increasing bias but reducing variance; the sweet spot minimizes validation error.
5. Why are saddle points relevant when training deep networks?
Answer B. Saddle points have zero gradient yet are not optima; they can stall first-order methods, which is why momentum/adaptive optimizers help escape them.
I can frame supervised learning as empirical risk minimization with a chosen loss and regularizer.
I can explain why convex-model loss surfaces differ from neural-network loss landscapes.
I can apply L1/L2 regularization and connect it to the bias-variance tradeoff and optimization behavior.
Where this leads
Part of the open-source Crunch Academy tech-education path. Pair it with the data-science and ML tracks when you're ready.
All Math for Data Science courses Crunch Academy home