🧠Thinking Like a Mathematician Unit 5 Review

Optimization is about finding the best possible solution from a set of alternatives, given certain goals and limitations. Whether you're maximizing profit, minimizing cost, or finding the most efficient route, optimization gives you a structured way to make the best decision. This section covers the core framework (objective functions, constraints, feasible regions), then moves through the major techniques from linear programming to metaheuristics and their real-world applications.

Fundamentals of Optimization

Every optimization problem has the same basic anatomy: something you want to maximize or minimize, rules you have to follow, and a set of solutions that actually obey those rules. Understanding these building blocks is essential before diving into any specific technique.

Objective Functions

The objective function is the mathematical expression that captures your goal. It's what you're trying to maximize or minimize. You might be maximizing profit, minimizing travel time, or minimizing error in a prediction model.

Typically written as $f(x)$ , where $x$ represents the decision variables (the things you can control)
Can be linear (e.g., $f(x) = 3x_1 + 5x_2$ ) or nonlinear (e.g., $f(x) = x^2 + \sin(x)$ ), depending on the problem
The form of the objective function determines which solving techniques you can use

Constraint Conditions

Constraints are the rules or limitations your solution must satisfy. Without them, optimization would be trivial: just make $x$ infinitely large or small.

Expressed as inequalities like $g(x) \leq 0$ or equalities like $h(x) = 0$
They represent real-world limits: budgets, physical capacities, time windows, regulatory requirements
Together, the constraints define the boundaries of where you're allowed to search for a solution

Feasible Region

The feasible region is the set of all solutions that satisfy every constraint simultaneously. Think of it as the "playing field" for your optimization problem.

Geometrically, it's the intersection of all constraint boundaries
A convex feasible region (shaped so any line between two points in it stays inside it) makes optimization much easier. Non-convex regions can hide multiple peaks and valleys.
The region can be bounded (enclosed) or unbounded (stretching to infinity in some direction). If it's unbounded, an optimal solution might not exist.

Global vs. Local Optima

This distinction matters most in nonlinear problems. A local optimum is the best solution in its immediate neighborhood, but a global optimum is the best solution across the entire feasible region.

In linear problems, any local optimum is automatically a global optimum (a huge advantage of linear programming)
In nonlinear problems, you can get "stuck" at a local optimum that looks great nearby but isn't the best overall
Strategies to find the global optimum include trying multiple random starting points and using global search algorithms like simulated annealing

Linear Programming

Linear programming (LP) handles problems where both the objective function and all constraints are linear. Despite this restriction, LP is remarkably powerful and widely applied in resource allocation, production planning, transportation, and scheduling.

Graphical Method

For problems with just two decision variables, you can solve LP visually:

Plot each constraint as a line on a coordinate plane.
Shade the side of each line that satisfies the inequality.
The overlapping shaded area is the feasible region.
Evaluate the objective function at each vertex (corner point) of the feasible region.
The vertex with the best objective value is your optimal solution.

This works because a key theorem in LP guarantees the optimal solution always occurs at a vertex. The limitation is obvious: you can't plot problems with three or more variables this way.

Simplex Algorithm

The simplex algorithm is the workhorse method for solving LP problems of any size.

It starts at one vertex of the feasible region and moves along edges to adjacent vertices, always improving the objective value
Uses a tableau (a structured table) to perform calculations systematically at each step
Guaranteed to find the optimal solution in a finite number of steps for most problems
Forms the foundation of most commercial LP solvers

The key insight: instead of checking every vertex (which could be enormous in number), simplex efficiently hops between improving vertices until no further improvement is possible.

Duality Theory

Every LP problem (the primal) has a corresponding dual problem. Duality theory connects them in powerful ways.

The weak duality theorem says the dual's objective value always bounds the primal's. If you're minimizing the primal, the dual gives a lower bound (and vice versa).
The strong duality theorem says that at optimality, the primal and dual objective values are equal.
Dual variables have economic interpretations: they tell you the marginal value of relaxing each constraint by one unit (often called shadow prices)
This makes duality essential for sensitivity analysis

Nonlinear Optimization

When the objective function or constraints involve nonlinear terms (squares, products of variables, trigonometric functions, etc.), you need more sophisticated tools. The core challenge: nonlinearity introduces the possibility of multiple local optima.

Unconstrained Optimization

Here you're finding the extrema of a function with no constraints at all. Calculus is your main tool.

First-order condition: At an optimal point, the gradient (vector of partial derivatives) equals zero: $\nabla f(x^*) = 0$
Second-order condition: The Hessian matrix (matrix of second partial derivatives) determines whether that point is a minimum (positive definite), maximum (negative definite), or saddle point (indefinite)
Gradient descent iteratively steps in the direction of steepest decrease: $x_{k+1} = x_k - \alpha \nabla f(x_k)$ , where $\alpha$ is the step size
Newton's method uses second-derivative information for faster convergence but is more expensive per step

Constrained Optimization

When constraints are present, the optimal point usually isn't where the gradient is zero. Instead, it's where the objective function's gradient is balanced against the constraints.

Lagrange multipliers handle equality constraints by introducing new variables (multipliers) that capture the "cost" of each constraint
Penalty methods add a term to the objective function that penalizes constraint violations, converting the problem into an unconstrained one
Barrier methods (also called interior point methods) keep the solution strictly inside the feasible region by adding a term that goes to infinity at constraint boundaries
Sequential quadratic programming (SQP) solves a sequence of simpler quadratic subproblems to handle general nonlinear constraints

Karush-Kuhn-Tucker (KKT) Conditions

The KKT conditions generalize Lagrange multipliers to problems with inequality constraints. They're the necessary conditions for optimality in nonlinear constrained optimization.

The conditions require:

Stationarity: The gradient of the objective, adjusted by the constraint multipliers, equals zero.
Primal feasibility: All constraints are satisfied.
Dual feasibility: Multipliers for inequality constraints are non-negative.
Complementary slackness: For each inequality constraint, either the constraint is active (binding) or its multiplier is zero.

These conditions form the theoretical backbone of most nonlinear optimization algorithms.

Integer Programming

In many real problems, variables must take whole-number values. You can't build 2.7 factories or schedule half a flight. Integer programming (IP) handles these discrete decisions, and it's significantly harder than continuous optimization.

Objective functions, How a Profit-Maximizing Monopoly Chooses Output and Price · Economics

Branch and Bound Method

This is the most common exact method for integer programming:

Relax the integer requirement and solve the resulting LP (the "relaxation").
If the solution happens to be all integers, you're done.
If not, branch: pick a fractional variable and create two subproblems (one forcing the variable up, one forcing it down).
Bound: use the relaxation's objective value to set bounds. If a subproblem's bound is worse than the best known integer solution, prune it.
Repeat until all branches are resolved.

This guarantees a globally optimal solution but can be computationally expensive for large problems since the number of branches can grow exponentially.

Cutting Plane Techniques

Instead of branching, cutting planes tighten the LP relaxation so its solution is closer to being integer-valued.

Valid inequalities (cuts) are added to exclude fractional solutions without removing any integer-feasible solutions
Gomory cuts are derived directly from the simplex tableau of the LP relaxation
In practice, cutting planes are often combined with branch and bound in branch-and-cut algorithms, which is how most modern IP solvers work

Dynamic Programming

Dynamic programming (DP) solves problems by breaking them into overlapping subproblems and building up solutions from smaller pieces.

Based on the principle of optimality: an optimal solution to the whole problem contains optimal solutions to its subproblems
Uses memoization (storing results of subproblems) to avoid redundant computation
Requires two properties: overlapping subproblems (the same subproblem appears multiple times) and optimal substructure (optimal solutions build from optimal sub-solutions)
Common applications: shortest path problems, knapsack problems, scheduling, and sequence alignment

Metaheuristic Algorithms

When problems are too large or too complex for exact methods, metaheuristics offer a practical alternative. These are general-purpose strategies inspired by natural processes that find good (though not guaranteed optimal) solutions in reasonable time.

Genetic Algorithms

Inspired by biological evolution, genetic algorithms maintain a population of candidate solutions that evolve over generations:

Encode each solution as a "chromosome" (e.g., a binary string or permutation).
Evaluate each solution using a fitness function (your objective).
Select the fittest individuals to be parents.
Crossover: combine parts of two parents to create offspring.
Mutate: randomly alter some offspring to maintain diversity.
Repeat for many generations until the population converges.

These work well for combinatorial problems where the search space is huge and poorly understood.

Simulated Annealing

Inspired by the cooling process in metallurgy, simulated annealing uses randomness to escape local optima:

Starts at a "high temperature," accepting both improving and worsening moves freely
Gradually "cools down," making it increasingly unlikely to accept worse solutions
The probability of accepting a worse solution is typically $e^{-\Delta E / T}$ , where $\Delta E$ is the increase in objective value and $T$ is the current temperature
This cooling schedule is what allows the algorithm to explore broadly early on and refine locally later

Particle Swarm Optimization

Inspired by the flocking behavior of birds, particle swarm optimization (PSO) uses a group of candidate solutions ("particles") that move through the search space:

Each particle tracks its own best-known position and the swarm's global best position
Velocity updates pull each particle toward both its personal best and the global best
The balance between following your own experience and following the group creates a mix of exploration and exploitation
Particularly well-suited for continuous optimization problems

Multiobjective Optimization

Real problems often have multiple goals that conflict with each other. Minimizing cost and maximizing quality, for instance, usually pull in opposite directions. Multiobjective optimization provides frameworks for handling these trade-offs.

Pareto Optimality

A solution is Pareto optimal if you can't improve one objective without making at least one other objective worse. There's typically not a single best answer but a whole set of Pareto optimal solutions.

The Pareto front is the set of all Pareto optimal solutions, plotted in objective space
It shows decision-makers the available trade-offs: "If you want 10% better quality, here's how much more it'll cost."
Visualization tools like scatter plots and parallel coordinate plots help compare solutions along the front

Weighted Sum Method

The simplest way to handle multiple objectives: combine them into a single objective using weights.

$\min \sum_{i=1}^{n} w_i f_i(x)$

Each weight $w_i$ reflects the relative importance of objective $i$
By varying the weights and re-solving, you can trace out different points on the Pareto front
The catch: this method can miss Pareto optimal solutions if the Pareto front is non-convex (has "dents" in it)

Goal Programming

Rather than optimizing objectives directly, goal programming sets target values for each objective and minimizes the deviations from those targets.

Introduces deviation variables that measure how far each objective falls from its goal
Preemptive goal programming assigns strict priority levels: satisfy the most important goal first, then the next, and so on
More flexible than the weighted sum method for practical problems where stakeholders have specific targets in mind

Optimization in Machine Learning

Training a machine learning model is fundamentally an optimization problem: you're adjusting model parameters to minimize a loss function that measures prediction error.

Gradient Descent

The most common optimization algorithm in machine learning:

Compute the gradient of the loss function with respect to model parameters.
Update parameters by stepping in the opposite direction of the gradient: $\theta_{k+1} = \theta_k - \alpha \nabla L(\theta_k)$
Repeat until the loss converges.

The learning rate $\alpha$ is critical. Too large and you overshoot the minimum; too small and training takes forever.

Objective functions, Maximizing Profit and the Average Cost Curve | Microeconomics Videos

Stochastic vs. Batch Optimization

The three main variants of gradient descent differ in how much data they use per update:

Batch gradient descent computes the gradient using the entire dataset. Stable updates, but slow for large datasets.
Stochastic gradient descent (SGD) uses a single randomly chosen data point per update. Much faster per step, and the noise can help escape local minima, but updates are noisy.
Mini-batch gradient descent uses a small random subset (e.g., 32 or 64 samples). This is the standard approach in practice because it balances speed and stability.

Regularization Techniques

Regularization prevents overfitting (when a model memorizes training data instead of learning general patterns) by adding a penalty term to the loss function:

L1 regularization (Lasso): Adds $\lambda \sum |w_i|$ to the loss. Tends to push some weights to exactly zero, effectively performing feature selection.
L2 regularization (Ridge): Adds $\lambda \sum w_i^2$ to the loss. Discourages large weights but rarely zeroes them out completely.
Elastic net: Combines L1 and L2 penalties.
Dropout (specific to neural networks): Randomly deactivates neurons during training, forcing the network to learn redundant representations.

Applications of Optimization

Optimization shows up everywhere once you know what to look for. Here are three major application areas.

Operations Research

Operations research uses mathematical optimization to improve decision-making in complex systems:

Scheduling: Assigning jobs to machines, shifts to workers, or gates to aircraft
Transportation: Finding minimum-cost shipping routes across a network (the classic transportation problem is an LP)
Network optimization: Designing supply chains, communication networks, and power grids
Queueing theory: Managing wait times in service systems like call centers or hospital emergency rooms

Financial Portfolio Management

Investors face a fundamental trade-off between risk and return. Optimization helps navigate it.

Markowitz mean-variance optimization finds portfolios that minimize risk (variance) for a given expected return, producing an "efficient frontier" analogous to a Pareto front
The Black-Litterman model blends market equilibrium with an investor's personal views
Risk parity allocates so each asset contributes equally to total portfolio risk
Dynamic models adjust portfolios as market conditions change over time

Supply Chain Optimization

Supply chains involve interconnected decisions that optimization can coordinate:

Facility location: Where to place warehouses and distribution centers to minimize total transportation cost
Inventory optimization: How much stock to hold, balancing the cost of holding inventory against the risk of stockouts
Vehicle routing: Planning delivery routes for a fleet of trucks (a generalization of the traveling salesman problem)
Demand forecasting and production planning: Using time series models and optimization together to match supply with expected demand

Computational Complexity

Not all optimization problems are created equal. Computational complexity theory tells you which problems are tractable and which ones will fight you.

NP-Hard Problems

A problem is NP-hard if no known algorithm can solve every instance of it in polynomial time (i.e., time that grows manageably with problem size).

Many classic optimization problems are NP-hard: the traveling salesman problem, the knapsack problem, graph coloring, and many scheduling problems
NP-hardness is established through polynomial-time reductions: showing that solving your problem would also solve a known NP-hard problem
Knowing a problem is NP-hard tells you to look for approximation algorithms or heuristics rather than expecting an efficient exact solution

Approximation Algorithms

For NP-hard problems, approximation algorithms guarantee solutions within a known factor of optimal:

The approximation ratio measures worst-case quality. A 2-approximation for vertex cover, for example, guarantees a solution at most twice the optimal size.
A polynomial-time approximation scheme (PTAS) lets you choose any $\epsilon > 0$ and get a $(1 + \epsilon)$ -approximation, though runtime increases as $\epsilon$ shrinks
These guarantees distinguish approximation algorithms from heuristics, which offer no formal quality bounds

Heuristics vs. Exact Methods

Choosing between heuristics and exact methods depends on your priorities:

Exact methods (simplex, branch and bound) guarantee the optimal solution but may require exponential time on hard problems
Heuristics find good solutions quickly but with no guarantee of optimality
In practice, heuristics often serve as warm starts for exact methods: the heuristic finds a good initial solution, and the exact method proves optimality or improves from there
Metaheuristics (genetic algorithms, simulated annealing, etc.) provide general frameworks for designing problem-specific heuristics

Sensitivity Analysis

Once you've found an optimal solution, you need to know how fragile it is. Sensitivity analysis answers the question: if the inputs change slightly, does the solution still hold up?

Parameter Perturbation

Small changes in input data can sometimes flip the optimal solution entirely. Sensitivity analysis quantifies this.

Shadow prices (from LP duality) tell you how much the optimal objective value changes per unit increase in a constraint's right-hand side. A shadow price of $5 on a labor constraint means one additional hour of labor is worth $5 to you.
Reduced costs indicate how much an objective coefficient must improve before a currently non-basic variable enters the solution
Parametric programming systematically traces how the optimal solution changes as a parameter varies over a range

Robustness of Solutions

Real-world data is uncertain, so a solution that's optimal for estimated inputs might perform poorly when conditions shift.

Robust optimization builds uncertainty directly into the model, optimizing for the worst case within an uncertainty set
Stochastic programming models uncertainty with probability distributions and optimizes expected performance
Scenario analysis tests the solution against several plausible futures
There's typically a trade-off: more robust solutions sacrifice some optimality under the "expected" scenario

Post-Optimality Analysis

After solving, you can extract additional insights:

Determine the range of parameter values over which the current optimal basis remains optimal (so you know when you'd need to re-solve)
Identify alternative optimal solutions (different solutions with the same objective value), which give decision-makers flexibility
Analyze the impact of structural changes like adding or removing constraints
These insights often matter as much as the optimal solution itself, because they inform how confidently you can act on the results