Optimal solutions and optimal values
Optimal Solutions and Optimal Values
An optimal solution is the best feasible decision.
The optimal value is the objective value achieved by that decision.
Basic Setup
Consider the constrained optimization problem:
\[\min f(x)\]subject to:
\[x\in S\]where:
- $f$ is the objective function
- $S$ is the feasible set
- $x$ is the decision vector
Optimal Solution for Minimization
A feasible point $x^*\in S$ is an optimal solution of a minimization problem if:
\[f(x^*)\le f(x)\]for every feasible point:
\[x\in S\]This means no feasible point has a smaller objective value.
Optimal Solution for Maximization
A feasible point $x^*\in S$ is an optimal solution of a maximization problem if:
\[f(x^*)\ge f(x)\]for every feasible point:
\[x\in S\]This means no feasible point has a larger objective value.
Optimal Value
If $x^*$ is optimal, the optimal value is:
\[z^*=f(x^*)\]The optimal solution is the point:
\[x^*\]The optimal value is the number:
\[z^*\]Solution vs Value
Do not confuse:
\[x^*\]and:
\[z^*\]The vector $x^*$ tells us what decision to make.
The scalar $z^*$ tells us how good that decision is.
Example:
\[x^*=(6,3)\]means produce $6$ units of product 1 and $3$ units of product 2.
If:
\[f(x)=5x_1+12x_2\]then:
\[z^*=f(6,3)=5(6)+12(3)=66\]So the optimal value is $66$.
Unique Optimal Solution
A problem has a unique optimal solution if exactly one feasible point achieves the best objective value.
Example:
\[x^*\]is unique if no other feasible point has the same objective value.
Multiple Optimal Solutions
A problem has multiple optimal solutions if more than one feasible point achieves the same best value.
In linear programming, this often happens when the objective contour line is parallel to an edge of the feasible region.
Then every point on that edge may be optimal.
No Optimal Solution
A problem may have no optimal solution.
Common reasons:
- the feasible set is empty
- the objective is unbounded
- the best value is approached but never attained
In standard linear programming with closed feasible regions, the main cases are usually infeasibility or unboundedness.
Infeasible Problem
If the feasible set is empty:
\[S=\emptyset\]then there is no feasible point.
Therefore, there is no optimal solution.
Unbounded Maximization
A maximization problem is unbounded if the objective can grow without limit while remaining feasible.
Then:
\[z^*=+\infty\]and no finite optimal solution exists.
Unbounded Minimization
A minimization problem is unbounded below if the objective can decrease without limit while remaining feasible.
Then:
\[z^*=-\infty\]and no finite optimal solution exists.
Bounded Feasible Set Does Not Guarantee Feasibility
A bounded feasible set can still be empty.
First check whether feasible points exist.
Then optimize over them.
Unbounded Feasible Set Does Not Always Mean Unbounded Objective
A feasible set may be unbounded, but the objective may still have a finite optimum.
Example:
If the feasible region extends infinitely in a direction that does not improve the objective, an optimum may still exist.
Local and Global Optimality
A local optimum is best only near a point.
A global optimum is best over the entire feasible set.
In general optimization, local optimality does not always imply global optimality.
In linear programming, because the feasible set is convex and the objective is linear, local optimality implies global optimality.
LP Vertex Optimality
In linear programming, if an optimal solution exists, then one can be found at a vertex of the feasible region.
This does not mean every optimal solution must be a vertex.
If there are multiple optima along an edge, the whole edge may be optimal, but its endpoints are vertices.
Graphical Interpretation
For a two-variable LP:
- draw the feasible region
- draw objective contour lines
- move the contour line in the improving direction
- the last feasible point or edge touched gives the optimum
If one point is touched, the optimum is unique.
If an edge is touched, there are multiple optima.
If the line can move forever, the problem is unbounded.
If there is no feasible region, the problem is infeasible.
Optimal Basis
In standard-form minimization:
\[\min c^Tx\]subject to:
\[Ax=b,\qquad x\ge 0\]a basis matrix $B$ is optimal if:
- the basic solution is feasible:
- the reduced costs are nonnegative:
If both conditions hold, the associated basic feasible solution is optimal.
Optimality Check in Simplex
For a minimization problem in standard form:
- if all reduced costs are nonnegative, the current basic feasible solution is optimal
- if some reduced cost is negative, there is a direction of cost decrease
This is the algebraic version of moving to a better neighboring vertex.
Candidate Solution vs Optimal Solution
A feasible solution is only a candidate.
It becomes optimal only if no other feasible point improves the objective.
So the process is:
\[\text{feasible} \ne \text{optimal}\]Feasibility means allowed.
Optimality means best among all allowed points.
Common Mistake
Do not report only the objective value.
A complete answer usually includes both:
\[x^*\]and:
\[z^*=f(x^*)\]Example:
\[x^*=(6,3),\qquad z^*=66\]Checklist
You understand optimal solutions and optimal values if you can:
- define optimal solution for minimization
- define optimal solution for maximization
- distinguish $x^$ from $z^$
- compute the objective value at a solution
- recognize unique and multiple optima
- recognize infeasible problems
- recognize unbounded problems
- explain why LP optima occur at vertices
- connect reduced costs to optimality in simplex
See Also
- Optimization Foundations
- Objective Functions
- Feasible Sets
- Graphical Method
- Vertex Optimality
- Reduced Costs
- Optimality Conditions
- Simplex Method
Exam checkpoint
In exam problems, translate the story into variables, objective, constraints, feasible set, and optimal value. Always state whether the problem is a maximization or minimization and what the units are.