The Central Idea
An optimization problem asks us to choose values that make some quantity as favorable as possible.
That quantity is represented by an objective function.
In its simplest form, we might write
\[ y=f(x), \]and then ask for the value of \(x\) that makes \(f(x)\) as large or as small as possible.
Symbolically, the goal might be written
\[ \boxed{\text{maximize } f(x)} \]or
\[ \boxed{\text{minimize } f(x)}. \]The function tells us how the quality of a choice is measured.
What Is Optimization?
Optimization is the mathematical process of finding the best available value of a quantity according to a specified objective.
Depending on the problem, we may want to:
- maximize profit;
- maximize production;
- maximize efficiency;
- maximize area or volume;
- maximize reliability;
- minimize cost;
- minimize travel time;
- minimize material use;
- minimize energy consumption;
- minimize error;
- minimize risk.
The mathematics changes from problem to problem, but the underlying structure remains similar: identify the choices, measure their outcomes, and determine which allowable choice performs best.
What Is an Objective Function?
An objective function is a mathematical function whose value represents the quantity being optimized.
If profit depends on the number of units produced, for example, we might write
\[ P(x)=R(x)-C(x), \]where
- \(x\) is the number of units produced;
- \(R(x)\) is revenue;
- \(C(x)\) is cost;
- \(P(x)\) is profit.
If the goal is to obtain the greatest possible profit, then \(P(x)\) is the objective function and the problem is
\[ \boxed{\text{maximize } P(x)}. \]Decision Variables
The inputs that we are allowed to choose are called decision variables.
In
\[ P(x)=50x-0.02x^2-5000, \]the variable \(x\) might represent the number of units produced.
The decision is therefore a choice of \(x\).
In a problem involving several choices, we may have several decision variables:
\[ f(x_1,x_2,\ldots,x_n). \]The Objective Value
Once the decision variables are chosen, the objective function produces an objective value.
Suppose
\[ P(x)=40x-0.01x^2-2000. \]If \(x=1000\), then
\[ P(1000) = 40(1000)-0.01(1000)^2-2000. \]Therefore,
\[ P(1000) = 40000-10000-2000 = 28000. \]So the decision \(x=1000\) gives the objective value
\[ \boxed{P(1000)=28000}. \]Maximization Problems
A maximization problem seeks the greatest attainable value of an objective function.
\[ \boxed{\text{maximize } f(x)}. \]Common maximization objectives include profit, revenue, output, area, volume, efficiency, coverage, utility, and performance.
Minimization Problems
A minimization problem seeks the smallest attainable value of an objective function.
\[ \boxed{\text{minimize } f(x)}. \]Common minimization objectives include cost, distance, travel time, energy consumption, material usage, error, risk, waste, and deviation from a target.
Maximization and Minimization Are Closely Related
Maximizing a function is equivalent to minimizing its negative.
\[ \boxed{ \text{maximize } f \quad\Longleftrightarrow\quad \text{minimize }(-f) }. \]The Decision Is Not the Objective
It is important to distinguish the variable being chosen from the quantity being optimized.
Suppose
\[ A(x)=x(20-x). \]Here \(x\) is a decision variable, while \(A(x)\) is the objective value. We are not necessarily trying to make \(x\) as large as possible. Instead, we want to choose \(x\) so that \(A(x)\) is as large as possible.
Comparing Choices Directly
Consider the objective
\[ f(x)=12x-x^2. \]| \(x\) | \(f(x)=12x-x^2\) |
|---|---|
| 2 | 20 |
| 4 | 32 |
| 6 | 36 |
| 8 | 32 |
| 10 | 20 |
Among these choices, \(x=6\) gives the largest objective value:
\[ \boxed{f(6)=36}. \]The Domain Is Part of the Problem
An objective function cannot be optimized meaningfully without knowing which input values are permitted.
The function may remain unchanged while the allowable choices change, producing a different optimum.
Feasible Choices
A choice that satisfies all requirements of an optimization problem is called a feasible solution or feasible choice.
The collection of all feasible choices forms the feasible region or feasible set.
The next lesson develops constraints and feasible regions in detail.
What Is an Optimal Solution?
An optimal solution is a feasible choice that gives the best attainable objective value.
If we seek to maximize \(f(x)\), an optimal solution \(x^*\) satisfies
\[ f(x^*)\ge f(x) \]for every feasible \(x\).
For minimization,
\[ f(x^*)\le f(x) \]for every feasible \(x\).
Optimal Point Versus Optimal Value
The optimal point is the decision \(x^*\). The optimal value is the corresponding objective value \(f(x^*)\).
Objective Functions of One Variable
Some optimization problems involve only one independent decision variable.
\[ C(x)=500+8x+0.01x^2, \] \[ P(x)=120x-0.02x^2-10000, \] \[ A(x)=x(50-x). \]Objective Functions of Several Variables
Many realistic decisions involve several variables simultaneously.
\[ f(x,y)=40x+60y. \]More generally,
\[ f:\mathbb{R}^n\rightarrow\mathbb{R} \]assigns a numerical objective value to each decision vector \(\mathbf{x}\).
Linear Objective Functions
\[ f(x_1,\ldots,x_n)=c_1x_1+\cdots+c_nx_n. \]Linear objectives are central to linear programming, which will appear later in this optimization sequence.
Quadratic Objective Functions
\[ f(x)=100x-x^2 \]is a quadratic objective. A multivariable quadratic objective might be
\[ f(x,y)=x^2+2xy+3y^2. \]Nonlinear Objective Functions
Examples include
\[ f(x)=xe^{-x}, \qquad f(x,y)=xy, \qquad f(x,y)=\sqrt{x^2+y^2}. \]Discrete Decisions
Decision variables do not always vary continuously. If \(x\) represents the number of trucks purchased, then \(x\) may be restricted to
\[ x\in\mathbb{Z}. \]Optimization over discrete and continuous choices will be treated later as a separate topic.
Example: A Profit Objective
Suppose
\[ R(x)=80x \]and
\[ C(x)=12000+20x+0.01x^2. \]Then
\[ P(x)=R(x)-C(x) \]gives
\[ \boxed{ P(x)=-0.01x^2+60x-12000 }. \]If the business objective is maximum profit, the optimization problem is
\[ \boxed{ \text{maximize } P(x) }. \]Revenue Is Not the Same as Profit
Selecting the correct objective is part of modeling.
\[ \boxed{P(x)=R(x)-C(x)}. \]Maximizing revenue and maximizing profit are not generally the same problem.
Example: Minimizing Cost
\[ C(x)=0.5x^2-20x+700. \]If the goal is to select the production rate with the lowest operating cost, then
\[ \boxed{ \text{minimize } C(x) }. \]Example: Minimizing Distance
Suppose a point \((x,0)\) should be as close as possible to \((4,3)\).
\[ D(x)=\sqrt{(x-4)^2+9}. \]The problem is to minimize \(D(x)\).
Equivalent Objective Functions
Because the square-root function is increasing, minimizing
\[ D(x)=\sqrt{(x-4)^2+9} \]is equivalent to minimizing
\[ \boxed{ Q(x)=(x-4)^2+9 }. \]Monotonic Transformations of an Objective
If \(g\) is strictly increasing, then maximizing \(f(x)\) and maximizing \(g(f(x))\) preserve the same ordering of feasible choices. The analogous statement holds for minimization.
Example: Maximizing Area
Suppose a rectangle has perimeter \(40\). If one side is \(x\), then the other side is \(20-x\), so
\[ \boxed{ A(x)=x(20-x)=20x-x^2 }. \]The optimization problem is to maximize \(A(x)\).
Using Relationships to Reduce the Number of Variables
- write the quantity to be optimized;
- identify relationships among the variables;
- use those relationships to eliminate unnecessary variables;
- optimize the resulting function.
Building an Objective Function from a Verbal Problem
- identify the quantity that should become best;
- decide whether it should be maximized or minimized;
- define the decision variables;
- translate the objective quantity into mathematics;
- identify relationships connecting the variables;
- identify the allowable values;
- check the units and interpretation.
Words That Often Signal the Objective
| Phrase | Likely Objective |
|---|---|
| greatest profit | maximize profit |
| largest volume | maximize volume |
| highest output | maximize production |
| lowest cost | minimize cost |
| shortest route | minimize distance |
| least material | minimize material use |
| smallest error | minimize an error measure |
| closest approximation | minimize deviation or distance |
Units of an Objective Function
The units of an objective function should match the physical or practical quantity it represents. Unit analysis is an important way to check whether the objective has been modeled correctly.
Units of Objective Coefficients
In
\[ P(x,y)=40x+70y, \]if \(x\) and \(y\) are product counts and \(P\) is measured in dollars, then \(40\) and \(70\) naturally carry units of dollars per unit.
Graphical Interpretation of an Objective Function
For a one-variable objective \(y=f(x)\), a maximum corresponds to a high point of the graph and a minimum corresponds to a low point, subject to feasibility.
Objective Surfaces
For \(z=f(x,y)\), the graph may be viewed as a surface in three-dimensional space. This connects optimization with multivariable calculus, gradients, tangent planes, and level sets.
Level Sets of an Objective Function
A level set consists of all decisions that produce the same objective value.
\[ f(x,y)=x^2+y^2, \qquad f(x,y)=c \]gives
\[ x^2+y^2=c. \]Level Sets of a Linear Objective
\[ f(x,y)=3x+2y \]and
\[ 3x+2y=c \]describe parallel level lines. This becomes important in graphical linear programming.
Objective Contours
Level sets of a multivariable objective are often called contours. Moving from one contour to another corresponds to changing the objective value.
Connection with Derivatives
For a differentiable one-variable function, \(f'(x)\) measures the local rate of change of the objective. Many interior local maxima or minima satisfy
\[ f'(x)=0. \]Such points are candidates requiring further analysis.
Connection with the Gradient
\[ \nabla f = \begin{bmatrix} \frac{\partial f}{\partial x_1}\\ \frac{\partial f}{\partial x_2}\\ \vdots\\ \frac{\partial f}{\partial x_n} \end{bmatrix}. \]The gradient points in the direction of greatest local increase, while \(-\nabla f\) points in the direction of greatest local decrease.
Local and Global Objectives
A point may be better than nearby choices without being the best choice everywhere. This leads to the distinction between local and global optimality.
The Best Value May Occur at a Boundary
Optimization does not consist only of finding interior critical points. Endpoints and boundaries can also contain maxima or minima.
The Objective Function Does Not Describe Every Requirement
The objective tells us what quantity we want to improve. Other mathematical statements tell us which choices are allowed.
\[ \text{maximize }P(x,y)=40x+70y \]might be accompanied by constraints such as
\[ 2x+3y\le120, \qquad x+y\le50, \qquad x\ge0, \qquad y\ge0. \]Why the Objective Alone May Not Have a Solution
Without a bounded feasible set, a function may fail to attain a maximum or minimum. Constraints can determine whether an optimum exists at all.
Scaling an Objective Function
Multiplying an objective by a positive constant does not change which decision maximizes or minimizes it.
Adding a Constant to the Objective
Adding the same constant to every objective value preserves the ranking of choices and therefore preserves the optimizing decision.
Argmax and Argmin
\[ \operatorname*{arg\,max}_x f(x) \]identifies the maximizing inputs, while
\[ \operatorname*{arg\,min}_x f(x) \]identifies the minimizing inputs.
There May Be More Than One Optimal Solution
An optimization problem need not have a unique optimizer. Several feasible points can produce the same best objective value.
Every Feasible Point Can Sometimes Be Optimal
If the objective is constant over the feasible set, every feasible point is both a maximizer and a minimizer.
An Objective Function Encodes Preference
Mathematically, the objective function tells us how to rank decisions. A poorly chosen objective can therefore lead to a mathematically correct solution to the wrong practical problem.
Sometimes the Objective Is a Proxy
When the true goal is difficult to measure directly, a model may optimize a measurable proxy such as waiting time, completion rate, response time, retention rate, or a weighted performance score.
Weighted Objective Functions
\[ J(x)=w_1C(x)+w_2T(x). \]The weights represent the relative importance assigned to different criteria. Changing them can change the optimal decision.
Be Careful When Combining Different Units
Weighted objectives should be constructed so that units, scaling, and interpretation remain meaningful.
When There Is More Than One Objective
Real decisions often involve competing goals. Such problems lead to multiobjective optimization, where tradeoffs among several legitimate objectives must be considered.
Loss Functions
In statistics, machine learning, estimation, and control, an objective being minimized is often called a loss function, cost function, or error function.
\[ L(\theta) = \sum_{i=1}^{n} \left( y_i-\widehat{y}_i(\theta) \right)^2. \]Energy as an Objective
In physical systems, equilibrium configurations can sometimes be characterized by minimizing an energy function
\[ \boxed{ \min_{\mathbf{x}} E(\mathbf{x}) }. \]Objectives Based on Distance from a Target
\[ E(x)=|g(x)-T| \]or
\[ E(x)=[g(x)-T]^2 \]can measure deviation from a desired target.
Why Squared Error Is Common
- It is never negative.
- It equals zero exactly when the target is reached.
- Large deviations receive greater penalties.
- It is differentiable in many common settings.
Objectives as Scores
\[ S=0.4R+0.35Q+0.25E. \]A model may construct a numerical score to evaluate alternatives, but the validity of the result depends on whether the score meaningfully represents the intended decision criteria.
Decision Variables Versus Parameters
\[ P(x)=px-C(x). \]Here \(x\) may be the decision variable and \(p\) a fixed model parameter. Changing parameters can change the objective and therefore the optimal decision.
The Objective Can Depend on Model Parameters
\[ f(x;a)=ax-x^2. \]Studying how an optimal solution responds to changes in assumptions is part of sensitivity analysis.
Optimization Under Uncertainty
A solution that is optimal under one precise set of assumptions may perform poorly when those assumptions change. This motivates robust optimization.
Common Error: Optimizing the Wrong Quantity
A business problem asking for maximum profit generally requires
\[ P(x)=R(x)-C(x), \]not simply a revenue objective.
Common Error: Confusing the Decision Variable with the Objective
In
\[ A(x)=x(20-x), \]\(x\) is the decision variable and \(A(x)\) is the quantity being optimized.
Common Error: Ignoring Feasibility
A calculated optimizer that violates the original restrictions cannot be accepted as an optimal solution.
Common Error: Ignoring Units
An objective should have interpretable and dimensionally consistent units.
Common Error: Assuming Every Critical Point Is Optimal
Solving \(f'(x)=0\) identifies candidates, not guaranteed optima. Boundaries and other feasible candidates may also need to be checked.
Common Error: Assuming an Optimum Must Exist
Not every optimization problem possesses a maximum or minimum. Existence must be established rather than assumed.
A Reliable Objective-Function Workflow
- Read the problem and identify the desired outcome.
- Decide whether the outcome should be maximized or minimized.
- Define the decision variable or decision variables.
- Write the quantity being optimized as a mathematical function.
- Use relationships among variables to simplify the objective when appropriate.
- Identify the allowable domain and all constraints.
- Check the units of the objective.
- Determine whether the variables are continuous, discrete, or mixed.
- Select an appropriate optimization method.
- Verify that the resulting solution is feasible.
- Evaluate the objective at the candidate solution.
- Interpret the optimal point and optimal value in context.
The Basic Structure of an Optimization Model
\[ \boxed{ \begin{aligned} \text{maximize or minimize}\quad &f(\mathbf{x})\\ \text{subject to}\quad &\mathbf{x}\in\mathcal{F}. \end{aligned} } \]Here \(\mathbf{x}\) is the decision vector, \(f(\mathbf{x})\) is the objective function, and \(\mathcal{F}\) is the feasible set.
Optimization as a Function-Mapping Problem
\[ f:\mathcal{F}\rightarrow\mathbb{R}. \]Optimization compares the numerical scores assigned to feasible choices.
Why Objective Functions Matter
Without an objective function, a model may describe what can happen but provide no criterion for choosing among the possibilities. The objective turns a feasibility model into a decision model.
Practice 1: Identify the Objective
A manufacturer wants to choose the number \(x\) of units produced in order to obtain the greatest possible profit.
\[ R(x)=75x, \qquad C(x)=8000+25x. \]Write the objective function and state whether it should be maximized or minimized.
Practice 2: Cost Objective
\[ C(x)=0.2x^2-16x+900. \]State the optimization objective.
Practice 3: Decision Variable and Objective Value
\[ P(x)=100x-0.05x^2-5000. \]Identify the decision variable and compute the objective value when \(x=500\).
Practice 4: Maximize or Minimize?
- Find the shortest transportation route.
- Find the largest possible storage volume.
- Find the least expensive production plan.
- Find the greatest expected return.
- Find the smallest prediction error.
Practice 5: Construct an Area Objective
A rectangle has perimeter \(60\). Let one side have length \(x\). Write the area as an objective function involving only \(x\).
Practice 6: Identify Objective and Constraints
\[ \text{maximize }40x+60y \]subject to
\[ 2x+y\le80, \qquad x+3y\le90, \qquad x\ge0, \qquad y\ge0. \]Practice 7: Equivalent Objective
\[ D(x)=\sqrt{x^2-6x+13}. \]Give a simpler objective function with the same minimizing value of \(x\).
Practice 8: Optimal Point Versus Optimal Value
\[ f(x)=20x-x^2. \]Suppose its maximum occurs at \(x=10\). Find the optimal value and distinguish it from the optimal point.
Practice 9: Multiple Optimizers
\[ f(x)=x^2, \qquad -4\le x\le4. \]Find the maximum objective value and all maximizing values of \(x\).
Practice 10: Identify the Modeling Error
A company wants to maximize profit. A student writes
\[ \text{maximize }R(x), \]where \(R(x)\) is revenue. Explain why this may not represent the requested objective.
Practice Answers
Practice 1
\[ P(x)=R(x)-C(x)=75x-(8000+25x)=\boxed{50x-8000}. \]The objective is to maximize \(P(x)\).
Practice 2
\[ \boxed{\text{minimize }C(x)}. \]Practice 3
The decision variable is \(x\). At \(x=500\),
\[ P(500)=100(500)-0.05(500)^2-5000=\boxed{32500}. \]Practice 4
- Minimize route length.
- Maximize storage volume.
- Minimize production cost.
- Maximize expected return.
- Minimize prediction error.
Practice 5
Since \(x+y=30\), we have \(y=30-x\), so
\[ \boxed{A(x)=x(30-x)}. \]Practice 6
The objective function is
\[ \boxed{f(x,y)=40x+60y}. \]The remaining inequalities are the constraints.
Practice 7
\[ \boxed{Q(x)=x^2-6x+13}. \]Practice 8
\[ \boxed{x^*=10} \]and
\[ f(10)=20(10)-10^2=\boxed{100}. \]Practice 9
\[ \boxed{\max f=16} \]at
\[ \boxed{x=-4\text{ and }x=4}. \]Practice 10
Revenue is not generally the same as profit. The requested objective is
\[ \boxed{\text{maximize }P(x)=R(x)-C(x)}. \]What to Remember
An objective function assigns a numerical measure of performance to a decision.
\[ \boxed{ \begin{aligned} \text{maximize or minimize}\quad &f(\mathbf{x})\\ \text{subject to}\quad &\mathbf{x}\in\mathcal{F}. \end{aligned} } \]- decision variables are the quantities being chosen;
- the objective function measures performance;
- the feasible set contains allowable choices;
- an optimal solution is a feasible decision producing the best attainable objective value;
- the optimal value is the objective value at an optimal solution.
The most important modeling question is: What quantity are we actually trying to make best?
Where We Go Next
An objective function tells us how to evaluate a decision, but most real optimization problems do not permit every mathematically possible input.
The next lesson, Constraints and Feasible Regions, develops the mathematical language used to describe those allowable choices and the regions they form.