Skip to content
Tutorials Center
My learning

Topics

Lesson 2 of 38 · Getting Started

Anatomy of an Optimization Problem

Learn the standard form of an optimization problem: objective, feasible set, minimizers, minimum values and what happens when no solution exists.

In the previous lesson you met variables, objectives and constraints informally. Now we give them precise names, because the rest of this track uses them constantly. Precise language lets you say exactly what an algorithm promises, and it helps you spot problems that have no answer at all.

The standard form

Mathematicians write almost every optimization problem in one template:

Text
minimize    f(x)
subject to  g_i(x) ≤ 0    for i = 1, ..., m
            h_j(x) = 0    for j = 1, ..., p
  • x is a vector of decision variables, for example x = (x₁, x₂).
  • f is the objective function. It maps a vector to one real number.
  • Each g_i gives an inequality constraint. Each h_j gives an equality constraint.

A rule like "x₁ ≥ 3" fits the template after rewriting: 3 - x₁ ≤ 0. A rule like "x₁ + x₂ = 10" becomes x₁ + x₂ - 10 = 0. So the template is not limiting.

Feasible set, optimal value, minimizer

  • The feasible set is the collection of all x that satisfy every constraint. A point in it is feasible.
  • The optimal value p* is the smallest value of f over the feasible set (more precisely the infimum, the greatest lower bound).
  • A minimizer (or optimal point) x* is a feasible point with f(x*) = p*.

Two things to keep apart: x* is a place, p* is a number. Many different places can share the same optimal value, so a minimizer need not be unique.

Let us test feasibility in code. The problem is: minimize (x₁ - 3)² + (x₂ - 2)² subject to x₁ + x₂ ≤ 4 and x₁ ≥ 0, x₂ ≥ 0.

Python Feasible or not?

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The point (3, 2) is the best place for the objective (distance zero), but it breaks x₁ + x₂ ≤ 4. The constraint changes the answer: the true minimizer sits on the boundary line x₁ + x₂ = 4.

Finding the constrained minimizer by sampling

We can sample many feasible points and keep the best. This brute-force check helps you build intuition before we learn real methods.

Python Random search inside the feasible set

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The exact minimizer is (2.5, 1.5). You can see why: the closest point to (3, 2) on the line x₁ + x₂ = 4 is found by moving perpendicular to the line, by 0.5 in each coordinate. The optimal value is 0.5² + 0.5² = 0.5.

When there is no solution

Not every problem has a minimizer. Three things can go wrong.

Situation Example What happens
Infeasible x ≤ 1 and x ≥ 2 The feasible set is empty, so there is no answer.
Unbounded minimize x over all real x f goes to -∞; no smallest value.
Not attained minimize 1/x over x > 0 The infimum is 0, but no x reaches it, so no minimizer exists.

Good practice is to ask three questions before running an algorithm: Is the feasible set non-empty? Is the objective bounded below on it? Is the minimum actually reached? Closed, bounded feasible sets with a continuous objective always attain their minimum (the extreme value theorem).

Active and inactive constraints

At a solution, an inequality g_i(x*) ≤ 0 is active if it holds with equality, g_i(x*) = 0, and inactive if g_i(x*) < 0. In our example the line constraint is active at (2.5, 1.5) (it equals 4), while x₁ ≥ 0 and x₂ ≥ 0 are inactive. If you removed an inactive constraint, the solution would not change. Active constraints are the ones that "push back". They will matter a lot in the KKT conditions later in the track.

flowchart TD
    A["Is the feasible set empty?"] -->|yes| B["Infeasible: no solution"]
    A -->|no| C["Is f bounded below on it?"]
    C -->|no| D["Unbounded: no minimum"]
    C -->|yes| E["Minimizer exists (if attained)"]

A short checklist to run before trusting a solver.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Which standard-form inequality represents the rule x₁ ≥ 3?

    x₁ ≥ 3 is the same as 3 - x₁ ≤ 0, since the standard form needs the left side to be at most zero.
  2. 2. What is the difference between a minimizer and the optimal value?

    x* is where the minimum happens; p* = f(x*) is how small the objective gets.
  3. 3. The problem 'minimize x over all real x' is

    You can make x as negative as you like, so there is no smallest value.
  4. 4. An inequality constraint is active at x* when

    Active means the constraint holds with equality, so the solution sits on its boundary.

Summary

  • Standard form: minimize f(x) subject to g_i(x) ≤ 0 and h_j(x) = 0.
  • The feasible set holds all points that obey the constraints; the minimizer is a point, the optimal value is a number.
  • A problem can be infeasible, unbounded or have an infimum that is never reached.
  • Active constraints hold with equality at the solution; inactive ones do not affect it.

Next: Local and Global Minima