FlashcardU

Constrained Optimization

Three parts settle every optimization question: the quantities a decision maker sets directly, a function measuring what counts as better, and the set of choices the limits permit. Linear programming is one instance of this shape, and every method in the subject assumes a problem already put into it.

Definition

A constrained optimization problem is a triple: decision variables x ∈ R n , an objective f : R n → R with a direction, and a feasible set F ⊆ R n . It asks for x ⋆ ∈ F optimizing f over F .

Formal statement

min { f ( x ) : x ∈ F } , with F the feasible set and f the objective function.

Assumptions and scope

  • A decision variable is a quantity the decision maker sets directly. A quantity determined by the decisions, such as total cost or total profit, is not a decision variable; it belongs in the objective or a constraint.

  • The feasible set may be empty, in which case no feasible solution exists and the problem is infeasible.

  • The optimal value may fail to exist even when feasible solutions do, if the objective can be improved without limit over the feasible set.

  • The three-part structure is independent of linearity. Linear programming is the case where the objective and constraints are linear.

Worked material

Example

Reading the three parts out of a description

A factory. We make chairs and tables. Each chair takes 2 hours of labour and 1 unit of timber; each table takes 3 hours and 4 units. We have 120 labour hours and 100 units of timber this week. Chairs earn 40, tables earn 90. What should we make?

  • Decision variables: the number of chairs and the number of tables to make.
  • Objective: maximize total earnings.
  • Constraints: labour used cannot exceed 120 hours; timber used cannot exceed 100 units; neither quantity can be negative.

A diet. Find the cheapest daily menu meeting minimum requirements for protein and iron.

  • Decision variables: how much of each food to include.
  • Objective: minimize total cost.
  • Constraints: protein at least the requirement; iron at least the requirement; amounts nonnegative.

Note what is not a decision variable in the factory problem: total earnings. Earnings are determined once the chairs and tables are fixed. A quantity the decision maker computes rather than sets belongs in the objective, not among the variables.

Contrast

Decision variables and computed quantities

Consider the factory again: chairs earn 40, tables earn 90, and we want the most money.

Not a formulation. Let P be the total profit. Maximise P subject to the labour and timber limits.

Nothing here can be chosen. P is not something the factory sets; it is what results once the chairs and tables are fixed. Written this way the constraints have nothing to constrain, and no method can act on the problem.

A formulation. Let x 1 be the number of chairs and x 2 the number of tables. Maximise 40 x 1 + 90 x 2 subject to 2 x 1 + 3 x 2 ≤ 120 , x 1 + 4 x 2 ≤ 100 , x 1 , x 2 ≥ 0 .

Now the variables are the decisions, and profit is what the objective computes from them. The test is one question: could I write this number down before knowing the others? If not, it is derived, and it belongs in the objective or a constraint, never among the variables.

Common errors

Common misconception

A quantity the problem mentions and that matters to the outcome, such as total profit or total cost, is a decision variable.

Related units

Connected

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.