FlashcardU

Optimal Solutions and Optimal Values

An optimization problem yields two different objects: the choice that achieves the best outcome, and the number that outcome is worth. Several choices may tie for best, so the first can be plural while the second never is, and a problem can have feasible points yet attain neither.

Definition

For min x ∈ F f ( x ) : an optimal solution is a point x ⋆ ∈ F with f ( x ⋆ ) ≤ f ( x ) for all x ∈ F ; the optimal value is the number f ( x ⋆ ) . The optimal set is the collection of all optimal solutions.

Formal statement

x ⋆ ∈ arg ⁡ min x ∈ F f ( x ) , and the optimal value is f ( x ⋆ ) = min x ∈ F f ( x ) .

Assumptions and scope

  • The optimal value is unique whenever it exists, because two optimal solutions must score equally by the definition of optimality.

  • The optimal set may contain many points. Reporting one of them answers what to do, but does not report that alternatives exist.

  • Feasible points can exist without any optimal solution, when the objective approaches a bound it never attains over the feasible set.

  • The optimal value of a maximization and of its negated minimization differ by sign, while the optimal set is unchanged.

Worked material

Example

Reporting the right object

One optimal solution. Minimise x subject to x ≥ 2 . The optimal solution is x = 2 ; the optimal value is 2. Here they happen to be the same number, which is exactly why this case teaches the distinction badly on its own.

Many optimal solutions, one optimal value. Maximise x + y subject to x + y ≤ 4 , x , y ≥ 0 . Every point on the segment from ( 4 , 0 ) to ( 0 , 4 ) is optimal, infinitely many optimal solutions. The optimal value is 4 for all of them.

No optimal solution, though feasible points exist. Minimise x subject to x > 0 . Every feasible point has a smaller feasible point below it, so no choice attains a minimum. The greatest lower bound is 0, but 0 is not feasible: there is no optimal solution and no optimal value.

How to report. What should we produce? answers with a point: 4 chairs and 0 tables. What is the maximum profit? answers with a number: 160. Giving a point where a number was asked, or a number where a point was asked, does not answer the question.

Contrast

Two answers that look alike

Maximise 3 x 1 + 3 x 2 subject to x 1 + x 2 ≤ 10 , x 1 , x 2 ≥ 0 .

Not a complete answer. The optimum is 30.

This gives the value and calls it the optimum. If the question asked what to produce, it has not been answered, and it hides that the answer is not a single choice.

Not a correct answer. The optimal solution is 30.

30 is a number, not a point. No choice of x 1 and x 2 has been named.

A complete answer. Every point with x 1 + x 2 = 10 and x 1 , x 2 ≥ 0 is an optimal solution, for instance ( 10 , 0 ) , ( 0 , 10 ) , or ( 5 , 5 ) . The optimal value is 30.

The test: a solution is something you could act on, and a value is something you could put in a budget. If your answer to what should we do is a number, you have reported the wrong object.

Common errors

Common misconception

The optimal solution is the best value the objective can take.

Related units

Requires

Learn this topic

Used in

Sources

Type to search.

Settings

Appearance

Interface density

Your record

Your progress is stored in this browser and nowhere else: an identifier, the answers you have given, the mastery states and review schedule derived from them, and the lesson you last opened. Clearing it makes you a new learner on this device. It cannot be undone, and it will not affect your appearance or density settings.

Focus timer

Focus--minutes remaining

Phase

Kept in this browser only, and used to label the session in your own history.

Today

Nothing recorded yet. Finish a focus session and it will appear here.

Settings

Focus sessions between long breaks.

Sessions you are aiming for in a day.

Notifications

Your history

Sessions are stored in this browser and nowhere else. They are not evidence and never reach your mastery record.