Blog · Collection

Optimization for decision-making

Linear and convex optimization, duality and KKT conditions, conic and semidefinite programs, first-order algorithms, and contextual predict-then-optimize decisions.

Linear programming and duality

Every linear program has a dual, and strong duality makes their optimal values equal. The dual variables have a concrete meaning as shadow prices: how much the optimal value would change if a constraint were relaxed slightly, which is the basis of sensitivity analysis. Many problems that do not look linear can be rewritten as linear programs, including minimizing a piecewise-linear convex function, least absolute deviations regression, maximum flow, and robust linear optimization, where the constraints must hold for every value of some uncertain coefficients.

Convex optimization

Convex problems are the ones we can reliably solve, because every local minimum is a global one. Lagrangian duality gives lower bounds on the optimal value, and under a mild condition (Slater’s condition) the bound is tight. The Karush–Kuhn–Tucker conditions, namely stationarity, primal and dual feasibility, and complementary slackness, then characterize the optimal solutions. Conic programs, and semidefinite programs in particular, extend linear programming to cones of matrices and cover a remarkable range of problems.

First-order methods

For large problems, methods that use only gradients win. Gradient descent on a convex function with LL-Lipschitz gradient, using step size 1/L1/L, satisfies

f(xk)−f⋆≤L ∥x0−x⋆∥22k,f(x_k) - f^\star \le \frac{L\,\lVert x_0 - x^\star \rVert^2}{2k},

and strong convexity upgrades this to linear convergence. Projected subgradient methods handle constraints and nonsmooth objectives. The Frank–Wolfe method avoids projections by solving a linear subproblem at each step. Mirror descent adapts the geometry of each update to the constraint set, for example becoming multiplicative updates on the probability simplex.

Predict, then optimize

In contextual linear optimization, decisions such as routing or inventory depend on costs that must first be predicted from features. Training the predictor for accuracy alone ignores how its errors affect the decision. The “smart predict-then-optimize” framework trains for decision quality instead, through a convex surrogate called the SPO+ loss, which can be minimized with stochastic mirror descent.

← All collections