Mathematical Optimization Fundamentals Cheat Sheet

Updated 2026-05-19

Next Topic: Mathematical Proof Techniques Cheat Sheet

Mathematical optimization is the branch of applied mathematics concerned with finding the best element from a feasible set according to a defined criterion. It underpins machine learning, operations research, economics, and engineering — any domain where resources must be allocated or decisions must be made under constraints. The key mental model is the interplay between the objective function (what you want to minimize or maximize), the feasible region (what's allowed), and the structure of the problem (convex or not, continuous or integer) — because structure determines which algorithms are guaranteed to find a global optimum and which may only find a local one.

What This Cheat Sheet Covers

This topic spans 15 focused tables and 137 indexed concepts. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.

Table 1: Linear Programming FormulationTable 2: Simplex MethodTable 3: LP DualityTable 4: Convex Sets and Convex FunctionsTable 5: Lagrange Multipliers and KKT ConditionsTable 6: Gradient-Based Optimization MethodsTable 7: Newton's Method and Quasi-Newton MethodsTable 8: Line Search MethodsTable 9: Integer ProgrammingTable 10: Interior Point MethodsTable 11: Augmented Lagrangian and ADMMTable 12: Sequential Quadratic Programming and Nonlinear Constrained OptimizationTable 13: Second-Order Optimality ConditionsTable 14: Dynamic ProgrammingTable 15: Advanced Formulations and Special Problem Classes

Table 1: Linear Programming Formulation

Linear programming (LP) provides the foundational language for optimization problems where both the objective and all constraints are linear functions of the decision variables. Understanding standard form, canonical form, and slack variables is prerequisite to every solver and algorithm that follows.

Method	Example	Description
Standard Form (LP)	$\max\ \mathbf{c}^\top \mathbf{x}$ s.t. $A\mathbf{x} \leq \mathbf{b},\ \mathbf{x} \geq 0$	LP form with $\leq$ inequality constraints and non-negative variables; most solvers convert to this before processing.
Canonical / Equality Form	$\max\ \mathbf{c}^\top \mathbf{x}$ s.t. $A\mathbf{x} = \mathbf{b},\ \mathbf{x} \geq 0$	Each $\leq$ constraint is converted to equality by adding a slack variable $s_i \geq 0$ ; required by the simplex method.
Slack Variable	$a_1 x_1 + a_2 x_2 + s = b,\ s \geq 0$	Non-negative variable added to a $\leq$ constraint to convert it to equality; $s = 0$ at the constraint boundary.
Surplus Variable	$a_1 x_1 + a_2 x_2 - s = b,\ s \geq 0$	Non-negative variable subtracted from a $\geq$ constraint to convert it to equality; used in Phase I / Big M.
Objective Function	$z = 3x_1 + 5x_2$	The linear expression to be maximized or minimized; coefficients $\mathbf{c}$ encode the value of each variable.

Table 1: Linear Programming Formulation

Method	Example	Description
Standard Form (LP)	$\max\ \mathbf{c}^\top \mathbf{x}$ s.t. $A\mathbf{x} \leq \mathbf{b},\ \mathbf{x} \geq 0$	LP form with $\leq$ inequality constraints and non-negative variables; most solvers convert to this before processing.
Canonical / Equality Form	$\max\ \mathbf{c}^\top \mathbf{x}$ s.t. $A\mathbf{x} = \mathbf{b},\ \mathbf{x} \geq 0$	Each $\leq$ constraint is converted to equality by adding a slack variable $s_i \geq 0$ ; required by the simplex method.
Slack Variable	$a_1 x_1 + a_2 x_2 + s = b,\ s \geq 0$	Non-negative variable added to a $\leq$ constraint to convert it to equality; $s = 0$ at the constraint boundary.
Surplus Variable	$a_1 x_1 + a_2 x_2 - s = b,\ s \geq 0$	Non-negative variable subtracted from a $\geq$ constraint to convert it to equality; used in Phase I / Big M.
Objective Function	$z = 3x_1 + 5x_2$	The linear expression to be maximized or minimized; coefficients $\mathbf{c}$ encode the value of each variable.