Optimization — Introduction
Mathematical Optimization - Introduction
Introductory Undergraduate LevelGoals of this introduction
- Understand how to formulate an optimization problem (objective function, constraints, feasible region)
- Solve extremum problems for single-variable functions using differentiation
- Understand critical points of multivariable functions and their classification via the Hessian matrix
- Understand the geometric meaning of the gradient vector and the optimality conditions
- Solve equality-constrained optimization problems using the method of Lagrange multipliers
- Understand the definitions of convex sets and convex functions, and why convexity matters in optimization
Prerequisites
- Calculus (single- and multi-variable differentiation)
- Basic linear algebra (matrices, systems of equations)
- Basics of functions (definition, graphs, continuity)
Chapter structure
Formulating Optimization Problems
What an objective function is and what constraints are. Maximization versus minimization and the feasible region, through concrete examples.
Single-Variable Optimization
The definition of extrema, the first-derivative test, the second-derivative test, and finding maxima and minima on a closed interval.
Multivariable Optimization
Partial derivatives and the gradient vector, classification of critical points, the Hessian matrix and second-order conditions, with concrete examples.
Gradients and Optimality Conditions
The geometric meaning of the gradient, first-order necessary conditions, second-order sufficient conditions, and the relationship between level curves and the gradient.
The Method of Lagrange Multipliers
Solving equality-constrained optimization problems. The meaning of the Lagrange multipliers and the extension to multiple constraints.
Convex Sets and Convex Functions
The definitions and properties of convex sets and functions. Testing convexity via the Hessian matrix, and why convexity matters in optimization.
Exercises
A set of practice problems to check your understanding at the introductory level.
Overview
Optimization is a mathematical method for finding the "best" solution under given conditions. It is used in every field, from everyday life to engineering, economics, and machine learning.
For example:
- Make a box of maximum volume from a given amount of material
- Produce a product while minimizing cost
- Minimize the error of a machine learning model
All of these can be formulated as optimization problems: maximizing or minimizing some function (the objective function).
In this introduction, we first learn the basic formulation of optimization problems, then start with optimization of single-variable functions using differentiation, and proceed to multivariable functions and constrained optimization. Building on the differentiation you learned in high school, let's master the foundations of optimization.
Frequently asked questions
What do you learn in an introduction to optimization theory?
You learn the basic formulation of optimization problems (objective function, constraints, feasible region), optimization of single- and multi-variable functions using differentiation, gradients and optimality conditions, the method of Lagrange multipliers, and the concepts of convex sets and convex functions. This is the stage where you master the essence of optimization: expressing the quantity you want to minimize as a formula and finding its minimum systematically.
What kind of problem is an optimization problem?
It is the problem of finding a variable $x^*$ that minimizes (or maximizes) an objective function $f(x)$ subject to a constraint $x\in\mathcal{X}$. Most real-world decision problems can be formulated as optimization: engineering design, machine learning (loss minimization), operations research (cost minimization, profit maximization), control (optimal control), and statistics (maximum likelihood estimation).
Why is convex optimization important?
In convex optimization, a local minimum is guaranteed to coincide with the global minimum, and efficient algorithms (interior-point methods, cutting-plane methods) are available. Important problems such as linear programming, quadratic programming, and semidefinite programming are special cases of convex optimization. Non-convex problems are also often solved via convex approximation or convex relaxation, so understanding convex optimization is an essential foundation.