Introduction to Optimization Techniques
Almost every engineering decision — the lightest beam that still holds the load, the cheapest schedule that still meets demand, the controller gains that settle fastest — is secretly a search for the best choice among many. Before any algorithm, we need the central idea: name the things you may choose, write down what "best" means, list what you must respect, and then hunt for the winner. This chapter builds that vocabulary — variables, objective, and constraints — and the standard form the rest of the course rests on.
- What an optimization problem is, and the three pieces inside every one: decision variables, an objective function, and constraints.
- The standard form of a problem, \( \min f(x)\ \text{s.t.}\ g_i(x)\le 0,\ h_j(x)=0 \), and why every problem can be written this way.
- Why maximizing \(f\) is the same as minimizing \(-f\), so one set of tools covers both.
- The difference between a local and a global optimum, and why that difference is the hardest part of the subject.
- What the feasible region is, and how to test whether a candidate point is feasible.
- How optimization problems are classified: constrained/unconstrained, linear/nonlinear, continuous/discrete, single/multi-objective, deterministic/stochastic — and which chapters each class needs.
What Is Optimization?
Optimization is the process of finding the best choice from a set of possible choices, where "best" is measured by a quantity we care about and the choices are limited by rules we must obey. Three ingredients appear every time. The decision variables \(x = (x_1, x_2, \dots, x_n)\) are the quantities we are free to set — dimensions, quantities to produce, gains to tune. The objective function \(f(x)\) is the single number that tells us how good a choice is — a cost to minimize or a profit to maximize. The constraints are the conditions any acceptable choice must satisfy — budgets, physical limits, demand, non-negativity.
Put together, optimization asks: which values of the decision variables make the objective as good as possible, without breaking any constraint? The winning choice is written \(x^\star\) and called the optimal solution (or optimizer); the value \(f(x^\star)\) is the optimal value.
The engineering goal is always the same: turn a fuzzy real-world wish ("make it cheap but strong") into three crisp mathematical objects — variables, an objective, and constraints — and then let a method find \(x^\star\). The rest of this book is a toolbox for building and solving exactly that.
Name the variables, state the objective, list the constraints. If you cannot write down all three, the problem is not yet ready to solve — and getting them right is half the work.
The Standard Form of an Optimization Problem
To let one set of algorithms attack many different problems, we agree on a single standard form. By convention we minimize, we push every inequality into the "\(\le 0\)" shape, and we write equalities as "\(=0\)":
Here \(f\) is the objective, the \(g_i\) are the inequality constraints, and the \(h_j\) are the equality constraints. The set of all points that satisfy every constraint is the feasible region \(\mathcal{F}\); the search for \(x^\star\) happens only inside it. A point outside \(\mathcal{F}\) is infeasible and is never a valid answer, no matter how good its objective value looks.
Maximization needs no separate theory. Because the location of the best point does not move if we flip the sign of the objective, maximizing \(f\) is identical to minimizing \(-f\) — the optimizer \(x^\star\) is the same and only the optimal value changes sign. Likewise a "\(\ge\)" constraint becomes "\(\le\)" by multiplying through by \(-1\). So the single standard form above covers every case.
Optimization lives entirely inside \(\mathcal{F}\). Any method you learn for minimizing a cost also maximizes a profit — just minimize its negative. This is why textbooks state everything as a minimization and never lose generality.
Local vs Global Optima
Not every "best nearby" point is the true best. A global minimum \(x^\star\) has the smallest objective value anywhere in the feasible region. A local minimum only has the smallest value within a small neighbourhood of itself — step far enough away and you may find something better. The gap between these two ideas is the single hardest fact in optimization: most algorithms are good at rolling downhill to a local optimum, but proving a point is global is generally hard.
A global optimum is always a local optimum, but not the reverse. There is one blessed case — a convex problem (Chapter 3) — where every local minimum is automatically global. Recognising convexity is worth a great deal, because it turns a hard search into a solvable one.
Terminology & Notation
The words and symbols below recur on every page of this book. Learn them once here and the later chapters read smoothly.
| Symbol | Name | Meaning |
|---|---|---|
| \(x=(x_1,\dots,x_n)\) | Decision / design variables | The quantities we are free to choose |
| \(f(x)\) | Objective (cost) function | The single number measuring "how good" |
| \(g_i(x)\le 0\) | Inequality constraints | Limits that may or may not be tight |
| \(h_j(x)=0\) | Equality constraints | Balances that must hold exactly |
| \(\mathcal{F}\) | Feasible region / set | All points satisfying every constraint |
| \(x^\star\) | Optimal solution (optimizer) | The best feasible choice |
| \(f(x^\star)\) | Optimal value | The objective at the optimum |
| active / binding | Active constraint | A \(g_i\) that holds with equality at \(x^\star\) |
Before you ever compare objective values, check feasibility. A point that violates even one constraint is disqualified, however attractive its cost. This simple filter settles a surprising number of exam questions.
Optimization Around Us
Once you look for the three ingredients, optimization is everywhere in engineering. A structural engineer chooses member sizes to minimize weight subject to stress limits; a power engineer schedules generators for economic dispatch, minimizing fuel cost subject to meeting demand; a logistics planner routes vehicles to minimize distance subject to delivery windows; a machine-learning model tunes weights to minimize a loss; and a control engineer picks gains to minimize settling time while keeping the loop stable. Same three ingredients, different dress.
Turning any of these into a solvable problem follows one repeatable loop: understand the real situation, build a mathematical model of it, solve the model with a suitable algorithm, then interpret the answer and check it against reality — refining the model when it disagrees.
Classification of Optimization Problems
Optimization problems are sorted along a few independent axes. Knowing where a problem sits tells you which method applies — and which chapters of this book you will need.
An unconstrained problem optimizes \(f(x)\) over all of \(\mathbb{R}^n\); a constrained one restricts \(x\) to \(\mathcal{F}\). Lagrange multipliers and the KKT conditions (Chapter 5) handle the constrained case.
If \(f\) and all constraints are linear, it is a linear program (Part 2); otherwise it is a nonlinear program (Part 5). Linearity buys the simplex method and guaranteed global optima.
Continuous variables take any real value; discrete/integer variables take whole numbers (how many machines to buy). Integer problems (Part 4) are far harder than they look.
One objective gives a single best point; multiple, competing objectives (cost and weight) give a set of trade-off solutions — the Pareto front of Chapter 27.
Deterministic data are known exactly; stochastic problems involve randomness or uncertainty, calling for probabilistic formulations (Chapter 28).
A static problem is solved once; a dynamic one chooses a sequence of decisions over stages, which is the domain of dynamic programming (Chapter 17).
The Three Method Families
The thirty chapters ahead draw on three broad families of solution methods, and this course is organised around them. Knowing which family a problem belongs to is the first design decision you will make.
The classical (analytical) methods use calculus — setting derivatives to zero, Lagrange multipliers, and the KKT conditions — to characterise optima exactly. They are the foundation (Part 1) and are unbeatable when the problem is small and smooth. The mathematical-programming methods — the simplex method, transportation and assignment algorithms, branch-and-bound, and gradient-based nonlinear solvers (Parts 2–5) — are systematic procedures that scale to large, structured problems and often guarantee a global optimum. The metaheuristic (nature-inspired) methods — genetic algorithms, particle-swarm and ant-colony optimization, and simulated annealing (Part 6) — trade guarantees for reach: they search rugged, non-smooth, or combinatorial landscapes where gradients fail, returning very good (if not provably optimal) solutions.
Worked Examples
Problem. A farmer has \(100\) m of fencing to enclose a rectangular pen against a straight wall (so only three sides are fenced). What dimensions maximize the enclosed area?
Solution. Let the two sides perpendicular to the wall be \(x\) and the side parallel to it be \(y\). Variables: \(x,y\ge 0\). Objective: maximize area \(A = xy\). Constraint: the fence used is \(2x + y = 100\). Substitute \(y = 100 - 2x\):
Then \(y = 100 - 50 = 50\) m and \(A = 25 \times 50 = 1250\ \text{m}^2\). Since \(A''(x) = -4 < 0\), this is a maximum. Notice all three ingredients were needed before any calculus began.
Problem. A firm wants to maximize profit \(P = 5x_1 + 4x_2\). Rewrite this in standard (minimization) form and state what changes.
Solution. Minimize the negative objective:
The optimal point \(x^\star\) is exactly the same; only the reported optimal value flips sign. This is why every solver in the book can be written to minimize and still handle profit problems.
Problem. The feasible region is \(x_1 + x_2 \le 4,\ x_1 \ge 0,\ x_2 \ge 0\). Are the points \((3,2)\) and \((1,2)\) feasible?
Solution. Check every constraint. For \((3,2)\): \(3 + 2 = 5 \not\le 4\) — the first constraint is violated, so the point is infeasible. For \((1,2)\): \(1 + 2 = 3 \le 4\), and both coordinates are non-negative, so it is feasible. Feasibility is decided before objective values are ever compared.
Problem. Find and classify the stationary points of \(f(x) = x^4 - 8x^2\).
Solution. Set the derivative to zero:
The second derivative is \(f''(x) = 12x^2 - 16\). At \(x = 0\), \(f'' = -16 < 0\) — a local maximum with \(f = 0\). At \(x = \pm 2\), \(f'' = 32 > 0\) — minima with \(f(\pm 2) = 16 - 32 = -16\). Both are global minima (the function is symmetric). A single function can thus have two global optima at once — a first hint that "the" optimum need not be unique.
Problem. A workshop makes tables (profit ₹60 each) and chairs (profit ₹30 each). Each table needs 4 h of carpentry and 2 units of wood; each chair needs 2 h and 4 units. There are 40 h of carpentry and 32 units of wood available. Write the optimization model.
Solution. Let \(x_1\) = tables, \(x_2\) = chairs.
All expressions are linear, so this is a linear program; the graphical and simplex methods of Part 2 will find its optimum at a corner of the feasible region — exactly the picture in Section 1-2.
Problem. A utility must decide how many of three generator units (whole numbers) to commit to minimize fuel cost, where cost rises with the square of each unit's output and total output must exactly meet a fixed demand. Classify it.
Solution. Quadratic cost ⇒ nonlinear; whole-number unit counts ⇒ integer / discrete; a demand-balance "\(=\)" ⇒ constrained with an equality; one cost to minimize ⇒ single-objective; fixed known data ⇒ deterministic; decided once ⇒ static. It is therefore a constrained, single-objective, deterministic integer nonlinear program — a genuinely hard class that often calls for the branch-and-bound (Part 4) or metaheuristic (Part 6) methods.
Chapter Summary
Every problem has decision variables, an objective function, and constraints.
\(\min f(x)\) s.t. \(g_i(x)\le0,\ h_j(x)=0\); every problem can be cast this way.
Maximizing \(f\) equals minimizing \(-f\); the optimizer is unchanged, the value flips sign.
\(\mathcal{F}\) is the set of points satisfying all constraints; the search happens only inside it.
A local optimum is best only nearby; a global optimum is best everywhere. Convexity makes them coincide.
Constrained/unconstrained, linear/nonlinear, continuous/discrete, single/multi-objective, deterministic/stochastic.
Problems
For each item, first identify the decision variables, objective, and constraints, then answer what is asked. Difficulty rises down the list.
- State the three ingredients of an optimization problem and give a one-line real example of each for a smartphone battery design.
- Rewrite in standard minimization form: maximize \(f = 8x_1 + 3x_2\) subject to \(x_1 + x_2 \ge 5\), \(x_1,x_2 \ge 0\). (Flip both the objective and the "\(\ge\)".)
- A rectangular field of fixed area \(600\ \text{m}^2\) is to be fenced. Formulate the problem of minimizing the perimeter, and identify the objective and constraint.
- Given \(2x_1 + x_2 \le 10,\ x_1 + 3x_2 \le 15,\ x_1,x_2 \ge 0\), test whether \((4,3)\) and \((3,2)\) are feasible.
- Find and classify all stationary points of \(f(x) = x^3 - 3x\). Which, if any, is a global minimum over all real \(x\)?
- Classify each on every axis (constrained?, linear?, continuous?, single-objective?): (a) shortest route through 20 cities, (b) least-squares line fit, (c) choosing pipe diameters to minimize pumping cost with a pressure limit.
- Explain in words why a global optimum is always a local optimum but not the reverse, and draw a 1-D sketch that shows the difference.
- A factory maximizes profit \(40x_1 + 30x_2\) subject to \(x_1 + x_2 \le 12\), \(2x_1 + x_2 \le 16\), \(x_1,x_2\ge 0\). Write the model in standard form and state which method family (Section 1-7) you would use.
- For \(f(x,y) = (x-1)^2 + (y+2)^2\), find the unconstrained minimum by inspection and state its optimal value. Is the problem convex?
- A company must buy an integer number of trucks to meet a delivery target at minimum cost. Explain why rounding the answer to a continuous (LP) relaxation may give a wrong or infeasible solution.
- Give one engineering example each of a single-objective and a multi-objective problem, and describe what "the optimum" means in the multi-objective case.
- A wind-farm layout must place turbines to maximize annual energy while keeping wakes below a limit; the terrain makes the objective jagged and computable only by simulation. Classify the problem on every axis and argue which method family from Section 1-7 is most appropriate, and why the classical calculus approach fails.