ENGINEERING OPTIMIZATION (CIE-312)

Complete Exam-Oriented Notes — GGSIPU [Link]

One-Day Revision + Concept Book

HOW TO USE THIS BOOK

• Read the Theory for understanding, memorise the Formula Boxes (marked ★ ).
• Practice every Worked Example with pen and paper.
• Before the exam, read only the Revision Notes and Mind Maps at the end of each unit.
• [!] COMMON MISTAKE boxes show where students lose marks.
• [TRICK] MEMORY TRICK boxes help you recall in the exam hall.

Standard reference: S. S. Rao, Engineering Optimization: Theory and Practice; Kalyanmoy

Deb, Optimization for Engineering Design.

Engineering Optimization (CIE-312) — GGSIPU Exam Notes • Page 1

UNIT 1 — INTRODUCTION TO OPTIMIZATION
Learning Objectives

After this unit you should be able to: 1. Define optimization and explain why engineers need it.
2. Write the standard mathematical statement of an optimization problem. 3. Identify design
variables, objective function, constraints and parameters. 4. Formulate a real engineering
problem as an optimization problem. 5. Classify any optimization problem into the correct
category. 6. Distinguish global vs local optima and apply optimality criteria.

1.1 Introduction to Optimization

Optimization means finding the best possible solution to a problem out of all available
(feasible) solutions, subject to certain limitations called constraints.

In engineering, "best" usually means: - Minimum cost, weight, time, energy, error, or -
Maximum profit, strength, efficiency, output, reliability.

★ DEFINITION (write this in exam): Optimization is the process of finding the values of
the design variables that make an objective function maximum or minimum while satisfying
all the given constraints.

Mathematically, maximizing f(X) is the same as minimizing −f(X). So in optimization theory we

usually treat everything as a minimization problem (standard form).

[TRICK] MEMORY TRICK: Optimization = "best out of feasible." Two words: Best +
Feasible.

1.2 Need for Optimization

Engineers cannot use trial-and-error for modern problems because resources (money, material,
time) are limited and competition is high. Optimization is needed to:

1. Reduce cost of design and manufacturing.

2. Save material and weight (very important in aerospace, automobile).
3. Improve performance and efficiency of machines and processes.
4. Use limited resources wisely (men, money, machines).
5. Increase profit and competitiveness.
6. Meet safety and quality standards while still being economical.
7. Take fast, scientific decisions instead of guesswork.

1.3 Historical Background

Period Contribution

1700s Newton, Leibniz develop calculus → basis of derivative-based optimization.

Engineering Optimization (CIE-312) — GGSIPU Exam Notes • Page 2

Period Contribution

1750s Lagrange gives the method of Lagrange multipliers for constrained problems.

1800s Cauchy proposes the Steepest Descent method (1847).

1939–1947 Kantorovich & Dantzig develop Linear Programming and the Simplex method.

1951 Kuhn–Tucker (KKT) conditions for nonlinear constrained optimization.

1960s Development of nonlinear, dynamic and geometric programming.

1975 John Holland introduces Genetic Algorithms.

1983 Kirkpatrick introduces Simulated Annealing.

1992 Dorigo introduces Ant Colony Optimization.

[TRICK] MEMORY TRICK (order of methods): "Cauchy → LP → KKT → GA → SA → ACO" =

C-L-K-G-S-A.

1.4 Engineering Applications of Optimization

Field Example application

Civil / Structural Minimum-weight design of trusses, beams, frames.

Mechanical Optimum design of gears, springs, shafts, machine tools.

Aerospace Minimum-weight aircraft wing, optimal flight trajectory.

Electrical Optimal power flow, network design, control systems.

Production Production planning, scheduling, inventory control.

Chemical Optimal operating conditions of reactors, plant layout.

Transportation Shortest route, vehicle routing, transportation problem.

Management Resource allocation, assignment, portfolio selection.

1.5 Statement of an Optimization Problem

★ STANDARD FORM OF AN OPTIMIZATION PROBLEM

Find the design vector X = [x₁, x₂, …, xₙ]ᵀ
which minimizes f(X)
subject to: - gⱼ(X) ≤ 0, j = 1, 2, …, m (inequality constraints) - hₖ(X) = 0, k = 1, 2, …, p
(equality constraints) - xᵢ⁽ˡ⁾ ≤ xᵢ ≤ xᵢ⁽ᵘ⁾ (side / bound constraints)

Here: - X = vector of design variables (the unknowns we control). - f(X) = objective function
(what we want to make best). - gⱼ, hₖ = constraints (limitations to be satisfied).

[!] COMMON MISTAKE: Students forget to convert "≥" constraints to "≤" form. Always
rewrite g(X) ≥ 0 as −g(X) ≤ 0 before applying standard methods.

Engineering Optimization (CIE-312) — GGSIPU Exam Notes • Page 3

1.6 Components of an Optimization Problem

(a) Design Variables

The quantities that the designer is free to change to get the best design. Example: in a beam,
the breadth b and depth d are design variables. They form the design vector X. An n-variable
problem → n-dimensional design space.

(b) Objective Function

The criterion (a function of the design variables) used to compare designs and decide which is
best. Also called the cost function / merit function. - Single objective → ordinary
optimization. - More than one objective → multi-objective optimization.

(c) Constraints

The restrictions that any acceptable design must satisfy. - Behaviour / functional
constraints: based on performance (stress ≤ allowable stress). - Geometric / side
constraints: physical limits on variables (b ≥ 0). - A design satisfying all constraints is a
feasible design; otherwise it is infeasible.

(d) Parameters (Pre-assigned / Design Constants)

Quantities that are fixed for a given problem and not changed during optimization (e.g.,
material density, modulus of elasticity, allowable stress, loads).

Term Controlled by designer? Example

Design variable [+] Yes beam depth d

Parameter [-] No (fixed) Young's modulus E

Objective — minimize weight

Constraint — stress ≤ σ_allow

1.7 Mathematical Formulation of Optimization Problems

To put any problem into mathematical form: 1. Identify the design variables and call them x₁,
x₂, … 2. Write the objective function f(X) in terms of these variables. 3. Write all constraints
as gⱼ(X) ≤ 0 and hₖ(X) = 0. 4. Add side constraints (lower/upper bounds).

The set of all feasible points is called the feasible region (S).

1.8 Optimal Problem Formulation (Step-by-Step Procedure)

★ THE 5 STEPS OF FORMULATION (very important — often asked): 1. Choose

design variables. 2. Formulate constraints. 3. Formulate the objective function. 4.
Set up variable bounds (side constraints). 5. Choose / identify a suitable
optimization method to solve.

Engineering Optimization (CIE-312) — GGSIPU Exam Notes • Page 4

[TRICK] MEMORY TRICK: V-C-O-B-M → "Very Clever Optimizers Build Models."

Engineering Example — Soda Can Design

Design a cylindrical can of minimum material to hold 300 mL of liquid. - Variables: radius r,
height h. - Objective: minimize surface area f = 2πr² + 2πrh. - Constraint: volume πr²h = 300
(equality), r, h ≥ 0.

1.9 Classification of Optimization Problems

Basis Types

Nature of equations Linear (LP) vs Nonlinear (NLP)

Presence of constraints Constrained vs Unconstrained

Number of variables Single-variable vs Multi-variable

Nature of variables/data Deterministic vs Stochastic

Variation with time Static vs Dynamic

Type of variables Continuous, Integer, Discrete, Mixed

Definitions to write in exam: - Linear optimization: objective and all constraints are linear
functions of variables (solved by Simplex / LP). - Nonlinear optimization: objective or any
constraint is nonlinear. - Constrained: at least one constraint present. - Unconstrained: no
constraints; optimum found by setting derivatives to zero. - Single-variable: one design
variable; Multi-variable: more than one. - Deterministic: all data known with certainty. -
Stochastic: some parameters are random / probabilistic. - Static: parameters do not change
with time; Dynamic: decisions taken in stages over time (Dynamic Programming).

1.10–1.12 Global and Local Optimum

★ DEFINITIONS - A point X* is a GLOBAL minimum if f(X*) ≤ f(X) for all feasible X. - A

point X* is a LOCAL minimum if f(X*) ≤ f(X) for all X in a small neighbourhood of X*.

Feature Local Optimum Global Optimum

Region Best in a small region Best in the entire feasible region

Number Many can exist Only one best value

Guarantee Easier to find Harder to find

Methods Gradient methods may stop here Modern methods (GA, SA) aim for this

[TRICK] MEMORY TRICK: Local = "best near me", Global = "best of all".

For a convex function, any local minimum is the global minimum — this is why convex
problems are "easy."

Engineering Optimization (CIE-312) — GGSIPU Exam Notes • Page 5

1.13 Optimality Criteria (Single Variable)

For an unconstrained single-variable function f(x):

★ NECESSARY CONDITION (First Derivative Test): At a minimum or maximum (a

stationary point), f′(x*) = 0.
★ SUFFICIENT CONDITION (Second Derivative Test): - If f′(x*) = 0 and f″(x*) > 0 →
x* is a MINIMUM. - If f′(x*) = 0 and f″(x*) < 0 → x* is a MAXIMUM. - If f″(x*) = 0 → test
fails; check higher derivatives.

Higher-order test: if the first non-zero derivative at x* is of order n: - n even & positive →
minimum; even & negative → maximum. - n odd → point of inflection (neither).

For multi-variable functions: - Necessary: ∇f(X*) = 0 (gradient vector = 0). - Sufficient:

Hessian matrix H at X* is positive definite → minimum; negative definite → maximum;
indefinite → saddle point.

[!] COMMON MISTAKE: Forgetting to do the second-derivative test. f′(x)=0 only tells you it is
a stationary point, not whether it is max/min.

1.14 Graphical Interpretation

For two variables, the objective function gives contour lines (lines of equal f). The optimum
(for a minimization) lies at the innermost contour inside the feasible region. For LP problems,
the optimum lies at a corner (vertex) of the feasible polygon.

x2 | feasible region bounded by constraints

| ___________
| / *optimum *| <- innermost contour touching region
| / ( ( ) ) |
|___/_____________ |________ x1

1.15 — TEN SOLVED EXAMPLES (UNIT 1)

Example 1.1 Find the minimum of f(x) = x² − 4x + 4. - f′(x) = 2x − 4 = 0 → x* = 2. - f″(x) = 2 >

0 → minimum. f(2) = 0. ✔

Example 1.2 Optimize f(x) = x³ − 3x. - f′ = 3x² − 3 = 0 → x = ±1. - f″ = 6x. At x = 1: f″ = 6 > 0

→ min, f(1) = −2. At x = −1: f″ = −6 < 0 → max, f(−1) = 2.

Example 1.3 Test f(x) = x⁴ at x = 0. - f′ = 4x³ = 0 → x = 0. f″ = 12x² = 0 at 0 (test fails). f‴ =

24x = 0; f⁗ = 24 > 0 (first non-zero is 4th order, even, positive) → minimum.

Example 1.4 Classify the stationary point of f(x₁,x₂) = x₁² + x₂² − 2x₁ − 4x₂. - ∇f = [2x₁−2,
2x₂−4] = 0 → x₁ = 1, x₂ = 2. - H = [[2,0],[0,2]] → positive definite → minimum at (1,2), f = −5.

Example 1.5 Formulate: minimum surface-area open-top box of volume 32 m³, square base
side a, height h. - Variables a, h. Objective: minimize S = a² + 4ah. Constraint: a²h = 32.
Substitute h = 32/a² → S = a² + 128/a; dS/da = 2a − 128/a² = 0 → a³ = 64 → a = 4, h = 2.

Engineering Optimization (CIE-312) — GGSIPU Exam Notes • Page 6

Example 1.6 Find optima of f(x) = 2x³ − 15x² + 36x + 1 in [0,5]. - f′ = 6x² − 30x + 36 = 0 → x²
− 5x + 6 = 0 → x = 2, 3. f″ = 12x − 30. At x=2: −6<0 → local max f=29. At x=3: +6>0 → local
min f=28. Check ends: f(0)=1, f(5)=56 → global max at x=5, global min at x=0.

Example 1.7 Is f(x₁,x₂) = x₁² − x₂² a min, max or saddle at (0,0)? - ∇f = [2x₁, −2x₂] = 0 at
origin. H = [[2,0],[0,−2]] → indefinite → saddle point.

Example 1.8 Formulate (LP): A factory makes A (profit ₹40) and B (profit ₹30). A needs 2h
machine, B needs 1h; 40h available. Max profit. - Maximize Z = 40x₁ + 30x₂ s.t. 2x₁ + x₂ ≤ 40,
x₁,x₂ ≥ 0.

Example 1.9 Convert to standard (min) form: Maximize Z = 5x₁ + 3x₂ s.t. x₁ + x₂ ≥ 4. -
Minimize (−Z) = −5x₁ − 3x₂ s.t. −(x₁+x₂) + 4 ≤ 0, i.e. 4 − x₁ − x₂ ≤ 0.

Example 1.10 Check convexity of f(x) = x² + 3x + 2. - f″ = 2 > 0 for all x → convex → its single
stationary point is the global minimum (x = −1.5).

1.16 — UNIVERSITY QUESTIONS (UNIT 1)

2-mark: 1. Define optimization. 2. What is a design variable? 3. Define feasible region. 4. State
the necessary condition for a minimum. 5. Differentiate parameter and design variable.

5-mark: 6. Explain the components of an optimization problem. 7. State and explain the
standard form of an optimization problem. 8. Differentiate local and global optimum with a
diagram. 9. Explain optimality criteria for single-variable functions. 10. List and define any five
classifications of optimization problems.

10-mark: 11. Explain the step-by-step procedure for optimal problem formulation with an
engineering example. 12. Explain the classification of optimization problems in detail. 13.
Derive and explain first and second order optimality conditions (single and multi-variable). 14.
Formulate the can / beam design as an optimization problem and identify all components.

15-mark: 15. Explain in detail the need, applications, and historical background of
optimization, with examples. 16. (a) Formulate the open-box problem (8). (b) Classify it and
solve it fully (7). 17. Explain convexity and its role; show why a local optimum of a convex
function is global. 18. Solve any three single-variable problems using first and second
derivative tests with full classification. 19. Discuss design variables, objective, constraints,
parameters with one detailed mechanical example. 20. Explain graphical interpretation of
optimization for LP and NLP problems.

1.17 — REVISION NOTES (UNIT 1)

• Optimization = best feasible solution (min/max f subject to constraints).

• Standard form: minimize f(X), s.t. gⱼ ≤ 0, hₖ = 0, bounds.
• Components: Design variables, Objective, Constraints, Parameters.
• Formulation steps: V-C-O-B-M.
• Necessary: f′ = 0 / ∇f = 0. Sufficient: f″ > 0 (min) / Hessian positive definite (min).
• Local = near; Global = overall. Convex ⇒ local is global.

Engineering Optimization (CIE-312) — GGSIPU Exam Notes • Page 7

UNIT 2 — UNCONSTRAINED OPTIMIZATION
ALGORITHMS
Learning Objectives

1. Understand gradient-based search for multi-variable functions.

2. Apply Cauchy's Steepest Descent, Newton's, and Conjugate Gradient methods.
3. Write algorithms, pseudocode and flowcharts for each.
4. Solve numerical problems and compare the methods.

2.1 Introduction to Unconstrained Optimization

An unconstrained problem has no constraints — we only minimize f(X). The optimum is

where ∇f(X) = 0 and the Hessian is positive definite.

These methods are iterative: starting from a point X₁, we repeatedly compute a search
direction Sₖ and a step length λₖ and move:

★ GENERAL ITERATIVE FORMULA X_{k+1} = Xₖ + λₖ · Sₖ

where Sₖ = search direction, λₖ = optimum step length (found by line search).

Gradient vector: ∇f = [∂f/∂x₁, ∂f/∂x₂, …, ∂f/∂xₙ]ᵀ — points in the direction of maximum

increase of f.

Hessian matrix: H = [∂²f/∂xᵢ∂xⱼ] — matrix of second partial derivatives.

Exact line search for quadratics (very useful in exams):

★ λ* = − (∇fₖᵀ Sₖ) / (Sₖᵀ H Sₖ)

[TRICK] MEMORY TRICK: Direction first, then step. Every method differs only in how it
picks the direction S.

2.2 Gradient-Based Methods — Working Principle

1. Start at X₁, set k = 1.

2. Compute gradient ∇fₖ.
3. Choose a descent direction Sₖ (one along which f decreases, i.e. ∇fₖᵀSₖ < 0).
4. Find step length λₖ by line search.
5. Update X_{k+1} = Xₖ + λₖSₖ.
6. Check convergence (‖∇f‖ ≈ 0). If not converged, k = k+1, go to step 2.

Engineering Optimization (CIE-312) — GGSIPU Exam Notes • Page 8

2.3 Cauchy's Steepest Descent Method

Theory

The function decreases fastest along the negative gradient direction. So Steepest Descent
always chooses:

★ Sₖ = − ∇f(Xₖ)

Derivation (why negative gradient?)

The rate of change of f along a unit direction u is the directional derivative ∇fᵀu, which is
minimized (most negative) when u is opposite to ∇f. Hence the steepest descent direction is
−∇f.

Algorithm (write in exam)

1. Start with X₁, set k = 1, choose tolerance ε.

2. Compute ∇f(Xₖ). If ‖∇f(Xₖ)‖ ≤ ε → STOP, Xₖ is optimum.
3. Set search direction Sₖ = −∇f(Xₖ).
4. Find λₖ that minimizes f(Xₖ + λSₖ) (line search).
5. Update X_{k+1} = Xₖ + λₖSₖ.
6. k = k + 1; go to step 2.

Pseudocode

k = 1; X = X1
while ||grad_f(X)|| > eps:
S = -grad_f(X)
lambda = argmin_lambda f(X + lambda*S)
X = X + lambda*S
k = k + 1
return X

Flowchart

START → choose X1, eps, k=1

│
▼
Compute grad f(Xk)
│
▼
||grad|| <= eps ? ──Yes──► OUTPUT Xk → STOP
│No
▼
S = -grad f(Xk)
│
▼
Line search: find lambda minimizing f(Xk+lambda S)
│
▼
X(k+1) = Xk + lambda*S ; k = k+1 ──► (loop back)

Engineering Optimization (CIE-312) — GGSIPU Exam Notes • Page 9

Numerical Example 2.1 (most-asked)

Minimize f = x₁ − x₂ + 2x₁² + 2x₁x₂ + x₂², start X₁ = (0, 0).

∇f = [1 + 4x₁ + 2x₂ , −1 + 2x₁ + 2x₂], H = [[4, 2],[2, 2]].

Iteration 1: - ∇f(0,0) = [1, −1]; S₁ = [−1, 1]. - λ = −(∇fᵀS)/(SᵀHS) = −((1)(−1)+(−1)(1)) /

([−1,1]·H·[−1,1]ᵀ) = −(−2)/(2) = 1. - X₂ = (0,0) + 1·(−1,1) = (−1, 1), f = −1.0.

Iteration 2: - ∇f(−1,1) = [−1, −1]; S₂ = [1, 1]. - λ = −((−1)(1)+(−1)(1))/( [1,1]·H·[1,1]ᵀ ) = −

(−2)/(10) = 0.2. - X₃ = (−1,1) + 0.2(1,1) = (−0.8, 1.2), f = −1.2.

Iteration 3: X₄ = (−1, 1.4), f = −1.24 … converging to the true optimum X* = (−1, 1.5), f* =
−1.25.

[!] COMMON MISTAKE: Using a wrong sign for λ. For a quadratic, the formula gives λ
directly; it must be positive for descent. If you get negative λ, recheck your gradient.

Advantages

• Very simple, easy to program, low memory.

• Always reduces f at each step (guaranteed descent).
• Good starting method (far from optimum it works well).

Disadvantages

• Slow (zig-zag) convergence near the optimum, especially for elongated (ill-conditioned)
contours.
• Successive directions are perpendicular (∇f_{k+1} ⊥ Sₖ) → inefficient.
• Linear convergence rate only.

Applications

Neural network training (basic gradient descent), curve fitting, structural weight minimization,
initial iterations of larger solvers.

2.4 Newton's Method

Theory

Newton's method uses second-order (curvature) information via the Hessian, giving very
fast convergence near the optimum.

Taylor Series Derivation

Expand f around Xₖ to second order: f(X) ≈ f(Xₖ) + ∇fₖᵀ(X − Xₖ) + ½ (X − Xₖ)ᵀ H (X − Xₖ). Set the
gradient of this approximation to zero: ∇fₖ + H(X − Xₖ) = 0 ⇒ X − Xₖ = −H⁻¹∇fₖ.

★ NEWTON UPDATE FORMULA X_{k+1} = Xₖ − Hₖ⁻¹ ∇f(Xₖ)

Search direction Sₖ = −Hₖ⁻¹∇fₖ ("Newton direction"). For a pure quadratic, it reaches the
optimum in ONE step.

Engineering Optimization (CIE-312) — GGSIPU Exam Notes • Page 10

Algorithm

1. Start X₁, k = 1, tolerance ε.

2. Compute ∇fₖ and Hₖ. If ‖∇fₖ‖ ≤ ε → STOP.
3. Compute Hₖ⁻¹. Search direction Sₖ = −Hₖ⁻¹∇fₖ.
4. X_{k+1} = Xₖ + Sₖ (or Xₖ + λₖSₖ for modified Newton).
5. k = k+1; go to step 2.

Pseudocode

k = 1; X = X1
while ||grad_f(X)|| > eps:
H = hessian(X); g = grad_f(X)
X = X - inverse(H) * g
k = k + 1
return X

Numerical Example 2.2

Same f = x₁ − x₂ + 2x₁² + 2x₁x₂ + x₂², start (0,0). - ∇f(0,0) = [1, −1]; H = [[4,2],[2,2]]; H⁻¹ =
[[0.5, −0.5],[−0.5, 1]]. - X₂ = (0,0) − H⁻¹[1,−1]ᵀ = (0,0) − [0.5(1)+(−0.5)(−1), −0.5(1)+1(−1)]
= (0,0) − [1, −1.5] = (−1, 1.5). - This is the exact optimum in ONE step (f = −1.25). ✔

Advantages

• Quadratic convergence (very fast near optimum); exact for quadratics in one step.
• Uses curvature → no zig-zag.

Disadvantages

• Needs Hessian and its inverse each step → costly (O(n³)) and memory-heavy.
• Hessian may be singular or not positive definite → may diverge or move to a saddle/max.
• Sensitive to the starting point.

Applications

Final-stage refinement in optimization, logistic regression (Newton–Raphson), control &

estimation problems.

2.5 Conjugate Gradient Method (Fletcher–Reeves)

Theory

Combines the simplicity of steepest descent with much faster convergence by using conjugate
directions (directions that are "H-orthogonal": SᵢᵀHSⱼ = 0). For an n-variable quadratic it
converges in at most n steps — no Hessian inverse needed.

Mathematical Derivation / Update

• First direction: S₁ = −∇f₁.

• Subsequent directions:

Engineering Optimization (CIE-312) — GGSIPU Exam Notes • Page 11

 ★ Sₖ₊₁ = −∇f_{k+1} + βₖ Sₖ, where βₖ = ‖∇f_{k+1}‖² / ‖∇fₖ‖² (Fletcher–Reeves).

• Step length λₖ by exact line search (same formula as before).

Algorithm

1. Start X₁; compute ∇f₁; set S₁ = −∇f₁; k = 1.

2. Line search: λₖ minimizing f(Xₖ + λSₖ).
3. X_{k+1} = Xₖ + λₖSₖ; compute ∇f_{k+1}. If ‖∇f_{k+1}‖ ≤ ε → STOP.
4. βₖ = ‖∇f_{k+1}‖² / ‖∇fₖ‖².
5. S_{k+1} = −∇f_{k+1} + βₖSₖ. k = k+1; go to step 2.

Pseudocode

X=X1; g=grad(X); S=-g; k=1

while ||g||>eps:
lam = argmin f(X+lam*S)
Xnew = X + lam*S
gnew = grad(Xnew)
beta = (gnew·gnew)/(g·g) # Fletcher-Reeves
S = -gnew + beta*S
X, g = Xnew, gnew
return X

Numerical Example 2.3

Same quadratic, start (0,0): - Iter 1: S₁ = [−1,1], λ = 1 → X₂ = (−1,1), ∇f₂ = [−1,−1]. - β₁ =

(‖[−1,−1]‖²)/(‖[1,−1]‖²) = 2/2 = 1. S₂ = −[−1,−1] + 1·[−1,1] = [1,1] + [−1,1] = [0, 2]. - Iter 2:
λ = −(∇f₂ᵀS₂)/(S₂ᵀHS₂). ∇f₂ᵀS₂ = (−1)(0)+(−1)(2) = −2; S₂ᵀHS₂ = [0,2]·H·[0,2]ᵀ = 8. λ = 2/8 =
0.25 → X₃ = (−1,1)+0.25[0,2] = (−1, 1.5) = optimum in 2 steps (= n). ✔

Engineering Applications

Large-scale problems (FEM, structural analysis), machine learning (CG for least-squares),
solving large linear systems Ax = b.

2.6 COMPARISON TABLES (UNIT 2)

Steepest Descent vs Newton's Method

Feature Steepest Descent Newton's Method

Direction −∇f −H⁻¹∇f

Order First-order Second-order

Convergence Slow (linear), zig-zag Fast (quadratic)

Needs Hessian? No Yes (and its inverse)

Cost per step Low High (O(n³))

Quadratic problem Many iterations 1 iteration

Reliability far from optimum Good May diverge

Engineering Optimization (CIE-312) — GGSIPU Exam Notes • Page 12

Newton vs Conjugate Gradient

Feature Newton Conjugate Gradient

Hessian needed Yes No

Memory High Low

Steps for n-var quadratic 1 ≤n

Cost per step High Low

Best for Small problems, final refinement Large-scale problems

All-Methods Summary

Method Direction Hessian Speed Memory Use

Steepest Descent −∇f No Slow Low Start / simple

Newton −H⁻¹∇f Yes Fast High Small / final

Conjugate Gradient −∇f + βS No Medium-Fast Low Large problems

2.7 — FIFTEEN NUMERICAL PROBLEMS (UNIT 2)

For practice (functions; do one full iteration of each method unless stated): 1. f = x₁² + x₂², start
(1,1). (SD) → optimum (0,0). 2. f = x₁² + 2x₂², start (2,1). (SD, 2 iter) 3. f = (x₁−2)² + (x₂−3)²,
start (0,0). (Newton, 1 step → (2,3)) 4. f = x₁² + x₂² − 2x₁ − 4x₂, start (0,0). (any method → (1,2))
5. f = x₁ − x₂ + 2x₁² + 2x₁x₂ + x₂², start (0,0). (SD/Newton/CG) 6. f = 4x₁² + 3x₂² − 5x₁x₂ − 8x₁,
start (0,0). (SD) 7. f = x₁² + x₂² + x₃², start (1,1,1). (SD → origin) 8. f = 100(x₂−x₁²)² + (1−x₁)²
(Rosenbrock), start (−1,1). (observe slow SD) 9. f = 2x₁² + 2x₁x₂ + 5x₂² , start (1,1). (CG, ≤2
steps) 10. f = x₁²+ 25x₂², start (1,1). (SD zig-zag vs Newton 1-step) 11. f = (x₁−1)² + (x₂−1)² +
(x₁x₂−1)², start (0,0). (Newton, 2 iters) 12. f = x₁⁴ − 2x₁²x₂ + x₁² + x₂² − 2x₁ + 1, start (1,1).
(SD) 13. f = 3x₁² + 2x₂² − 6x₁ − 8x₂ + 10, start (0,0). (Newton, optimum (1,2)) 14. f = x₁² + x₁x₂
+ x₂², start (1,2). (CG) 15. f = 5x₁² + 5x₂² − x₁x₂ − 11x₁ + 11x₂ + 11, start (0,0). (SD vs Newton)

(Answers: each converges to the point where ∇f = 0; e.g. Q13 optimum (1,2), f=2.)

2.8 — EXAM QUESTIONS (UNIT 2)

2-mark (8): 1. Define gradient vector. 2. Define Hessian. 3. State Newton's update. 4. Why is
−∇f the steepest-descent direction? 5. What are conjugate directions? 6. State Fletcher–Reeves
β. 7. What is a line search? 8. Convergence rate of Newton's method?

5-mark (10): 9. Explain steepest descent with algorithm. 10. Derive Newton's method from
Taylor series. 11. Write the conjugate gradient algorithm. 12. Compare SD and Newton. 13.
Disadvantages of Newton & remedies. 14. Explain the role of step length. 15. Draw flowchart of
steepest descent. 16. Why does steepest descent zig-zag? 17. State advantages of CG over
Newton. 18. Define positive-definite Hessian and its meaning.

10-mark (8): 19. Solve Example 2.1 by steepest descent (2 iterations). 20. Solve by Newton's
method, show 1-step convergence. 21. Derive and apply the conjugate gradient method on a
quadratic. 22. Full comparison of all three methods with table. 23. Explain gradient-based

Engineering Optimization (CIE-312) — GGSIPU Exam Notes • Page 13

methods, working principle and convergence. 24. Solve a 2-variable problem by all three
methods and compare. 25. Explain modified Newton method and need for it. 26. Flowchart +
algorithm of CG with one numerical.

15-mark (4): 27. Complete theory + derivation + numerical of steepest descent. 28. Newton's
method: derivation, algorithm, numerical, merits/demerits. 29. Conjugate gradient: full
derivation, algorithm, numerical, applications. 30. Compare and solve one common function by
SD, Newton and CG; comment on convergence.

2.9 — VIVA QUESTIONS (UNIT 2)

• Q: Why is steepest descent slow? A: Consecutive search directions are orthogonal, causing
zig-zag near elongated contours.
• Q: Why is Newton fast? A: It uses curvature (Hessian) and solves the quadratic model
exactly.
• Q: When does Newton fail? A: When the Hessian is singular or not positive definite, or the
start is far away.
• Q: Why is CG popular for large problems? A: It gives near-Newton speed without computing
the Hessian inverse, using little memory.
• Q: What does ∇f = 0 mean physically? A: The slope is zero in every direction — a stationary
(candidate optimum) point.

2.10 — FORMULA SHEET (UNIT 2)

Quantity Formula

Iteration X_{k+1} = Xₖ + λₖSₖ

Steepest descent dir. Sₖ = −∇f(Xₖ)

Newton update X_{k+1} = Xₖ − Hₖ⁻¹∇fₖ

CG direction S_{k+1} = −∇f_{k+1} + βₖSₖ

β (Fletcher–Reeves) ‖∇f_{k+1}‖² / ‖∇fₖ‖²

Optimal step (quadratic) λ* = −(∇fₖᵀSₖ)/(SₖᵀHSₖ)

Engineering Optimization (CIE-312) — GGSIPU Exam Notes • Page 14

UNIT 3 — CONSTRAINED OPTIMIZATION
ALGORITHMS
Learning Objectives

1. Understand equality/inequality constraints and the feasible region.

2. Apply Lagrange multipliers and the KKT conditions.
3. Solve problems by penalty (exterior/interior) methods.
4. Apply gradient projection / constrained steepest descent ideas.
5. Formulate engineering design problems with constraints.

3.1 Introduction to Constrained Optimization

Most real engineering problems have constraints (limits on stress, cost, space, resources).
The general problem: minimize f(X) s.t. gⱼ(X) ≤ 0 (j=1..m), hₖ(X) = 0 (k=1..p).

The optimum may lie inside the feasible region (constraints inactive — behaves like
unconstrained) or on a boundary (one or more constraints active, gⱼ = 0).

[TRICK] MEMORY TRICK: Active constraint = "touching the wall"; the optimum often sits on
the wall.

3.2 Types of Constraints

Type Form Meaning

Equality hₖ(X) = 0 Must hold exactly (e.g. volume = fixed)

Inequality gⱼ(X) ≤ 0 Limit / bound (e.g. stress ≤ allowable)

Active gⱼ(X) = 0 Satisfied as equality at optimum

Inactive gⱼ(X) < 0 Slack; not limiting at optimum

Side/bound xᵢˡ ≤ xᵢ ≤ xᵢᵘ Range of variable

3.3 Lagrange Multipliers (Equality Constraints)

★ LAGRANGE METHOD To minimize f(X) s.t. h(X) = 0, form the Lagrangian: L(X, λ) =
f(X) + λ·h(X) Set ∂L/∂xᵢ = 0 and ∂L/∂λ = 0 (= h(X) = 0). Solve together. λ = Lagrange
multiplier (sensitivity of optimum to the constraint).

Worked Example 3.1

Minimize f = x₁² + x₂² s.t. x₁ + x₂ = 4. - L = x₁² + x₂² + λ(x₁ + x₂ − 4). - ∂L/∂x₁ = 2x₁ + λ = 0; ∂L/
∂x₂ = 2x₂ + λ = 0 → x₁ = x₂ = −λ/2. - Constraint: 2(−λ/2) = 4 → λ = −4 → x₁ = x₂ = 2, f = 8. ✔

Engineering Optimization (CIE-312) — GGSIPU Exam Notes • Page 15

3.4 KKT Conditions (Inequality Constraints) — VERY
IMPORTANT

★ KARUSH–KUHN–TUCKER (KKT) NECESSARY CONDITIONS For min f(X) s.t. gⱼ(X)

≤ 0: 1. Stationarity: ∇f + Σ μⱼ ∇gⱼ = 0 2. Primal feasibility: gⱼ(X) ≤ 0 3. Dual feasibility:
μⱼ ≥ 0 4. Complementary slackness: μⱼ · gⱼ(X) = 0
(μⱼ = 0 ⇒ constraint inactive; gⱼ = 0 ⇒ constraint active.)

[!] COMMON MISTAKE: Forgetting complementary slackness (μⱼgⱼ = 0). It tells you which
constraints are active. Test both cases: constraint active vs inactive.

Worked Example 3.2

Minimize f = (x₁−2)² + (x₂−2)² s.t. x₁ + x₂ ≤ 1. - Unconstrained optimum (2,2) violates the

constraint, so the constraint is active (x₁+x₂ = 1). - L = f + μ(x₁+x₂−1). ∂/∂x₁: 2(x₁−2)+μ = 0; ∂/
∂x₂: 2(x₂−2)+μ = 0 → x₁ = x₂. - Active: 2x₁ = 1 → x₁ = x₂ = 0.5, μ = 2(2−0.5) = 3 ≥ 0 ✔. f =
2(1.5²) = 4.5.

3.5 Direct Methods (Constrained)

Direct methods search within the feasible region without converting to unconstrained form.
Examples: gradient projection, feasible directions, Zoutendijk's method.

Method of Feasible Directions — idea: 1. Start at a feasible point. 2. Find a direction S that
is both usable (∇fᵀS < 0, reduces f) and feasible (∇gⱼᵀS ≤ 0 for active constraints, stays
inside). 3. Move along S by a step that does not violate constraints. 4. Repeat until no further
usable-feasible direction exists (KKT satisfied).

Gradient Projection (Rosen) — idea: Project the negative gradient onto the surface of the
active constraints so each step stays feasible:

★ S = −P∇f, where P = projection matrix = I − Nᵀ(NNᵀ)⁻¹N, N = matrix of active-

constraint gradients.

Engineering Applications (direct methods)

Structural shape optimization, trajectory optimization, any problem where staying feasible
every step is important (safety-critical designs).

3.6 Penalty Function Methods (Indirect Methods)

Idea: Convert a constrained problem into a sequence of unconstrained problems by adding

a penalty for violating constraints. Solved by SUMT (Sequential Unconstrained Minimization
Technique).

Engineering Optimization (CIE-312) — GGSIPU Exam Notes • Page 16

(a) Exterior Penalty Method

Penalizes violation of constraints; the search approaches the optimum from outside
(infeasible side).

★ EXTERIOR PENALTY Φ(X, r) = f(X) + r · Σ [max(0, gⱼ(X))]² + r · Σ [hₖ(X)]² Start with

small r, increase r → ∞ in stages.

(b) Interior Penalty (Barrier) Method

Adds a barrier that blows up near the boundary, keeping the search inside the feasible region.

★ INTERIOR PENALTY (barrier) Φ(X, r) = f(X) − r · Σ 1/gⱼ(X) or f(X) − r · Σ ln(−gⱼ(X))

Start with large r, decrease r → 0 in stages. Needs a feasible start point.

Numerical Example 3.3 (Exterior)

Minimize f = (x−1)² s.t. x ≥ 2 (i.e. g = 2 − x ≤ 0). - Φ = (x−1)² + r·[max(0, 2−x)]². For x < 2 the
bracket = (2−x). - dΦ/dx = 2(x−1) − 2r(2−x) = 0 → x(1+r) = 1 + 2r → x*(r) = (1+2r)/(1+r).

r x*(r)

1 1.500

10 1.909

100 1.990

1000 1.999

As r → ∞, x* → 2 (constraint boundary). ✔

Numerical Example 3.4 (Interior)

Minimize f = x s.t. x ≥ 1 (g = 1 − x ≤ 0). Barrier: Φ = x − r·ln(x − 1). - dΦ/dx = 1 − r/(x−1) = 0

→ x − 1 = r → x*(r) = 1 + r. - r = 1 → 2; r = 0.1 → 1.1; r = 0.01 → 1.01. As r → 0, x* → 1. ✔

Advantages & Disadvantages

Method Advantages Disadvantages

Exterior Any start point (even infeasible); handles Intermediate points infeasible; ill-conditioning as
equality constraints r→∞

Interior Always feasible; good for inequality Needs feasible start; fails on equality constraints;
constraints ill-conditioning as r→0

[!] COMMON MISTAKE: Using the interior (barrier) method for equality constraints — it
cannot handle them (the barrier needs a strict interior). Use exterior penalty for equalities.

Engineering Optimization (CIE-312) — GGSIPU Exam Notes • Page 17

3.7 Steepest Descent for Constrained Problems (Projected
Gradient)

1. Start at a feasible point X.

2. Compute −∇f. If a constraint is active, project −∇f onto the active constraint surface: S =
−P∇f.
3. Line search along S, limited so constraints are not violated.
4. If a new constraint becomes active, add it to the active set; repeat.
5. Stop when projected gradient ≈ 0 (KKT satisfied).

3.8 Engineering Applications of Constrained Optimization

Area Objective Typical constraints

Structural design Min weight of truss/beam Stress ≤ σ_allow, deflection ≤ limit

Machine design Min cost of gear/shaft Bending/torsion strength, geometry

Manufacturing Min machining cost Tool life, surface finish, power

Resource allocation Max profit Limited men/machine/material hours

Transportation Min transport cost Supply ≤ capacity, demand met

Production planning Max output / min cost Capacity, demand, storage limits

Detailed Solved Problem 3.5 (Resource Allocation, LP-type, KKT)

Maximize Z = 3x₁ + 2x₂ s.t. x₁ + x₂ ≤ 4, x₁ ≤ 3, x₁,x₂ ≥ 0. - Convert: min −Z. Try corner points
of feasible polygon: (0,0)→0, (3,0)→9, (3,1)→11, (0,4)→8. - Optimum: x₁ = 3, x₂ = 1, Z = 11.
(Both x₁≤3 and x₁+x₂≤4 active.)

3.9 — UNIVERSITY QUESTIONS (UNIT 3)

2-mark: 1. Define active constraint. 2. What is a Lagrange multiplier? 3. State complementary

slackness. 4. Difference: equality vs inequality constraint. 5. What is SUMT?

5-mark: 6. Explain Lagrange multiplier method with example. 7. State and explain KKT
conditions. 8. Exterior vs interior penalty (table). 9. Explain method of feasible directions. 10.
Gradient projection idea with the projection matrix.

10-mark: 11. Derive and solve a problem by Lagrange multipliers. 12. Solve a 2-variable
inequality problem using KKT. 13. Solve Example 3.3 by exterior penalty for several r and show
convergence. 14. Explain penalty methods (both) with formulation, merits, demerits. 15.
Explain engineering applications with one full structural/resource example.

15-mark: 16. Full theory + formulation + numerical of penalty function methods. 17. State,
derive and apply KKT conditions on a detailed example. 18. Compare direct and indirect
methods; solve one problem by penalty method. 19. Formulate and solve a constrained
machine/structural design problem. 20. Explain projected/constrained steepest descent with
algorithm and example.

Engineering Optimization (CIE-312) — GGSIPU Exam Notes • Page 18

3.10 — VIVA + REVISION (UNIT 3)

• Q: Why penalty methods? A: They turn a hard constrained problem into easy unconstrained
ones.
• Q: Exterior vs interior? A: Exterior approaches from outside (r→∞); interior stays inside
(r→0).
• Q: Meaning of μⱼ ≥ 0? A: Multipliers for ≤ constraints must be non-negative for a minimum.
• Q: What is an active constraint? A: One satisfied as equality at the optimum (gⱼ = 0).

Revision: Lagrangian L = f + λh; KKT = Stationarity + Feasibility + μ≥0 + μg=0; Exterior

penalty r↑∞ (square of violation); Interior barrier r↓0 (1/g or −ln). Optimum usually on active
constraints.

Engineering Optimization (CIE-312) — GGSIPU Exam Notes • Page 19

UNIT 4 — MODERN METHODS OF
OPTIMIZATION
Learning Objectives

1. Understand why classical methods fail on complex, multimodal problems.

2. Explain Genetic Algorithms, Simulated Annealing, Ant Colony, Tabu Search.
3. Describe neural-network-based and fuzzy optimization.
4. Compare all modern methods.

4.1 Introduction to Modern Optimization

Classical (gradient) methods need differentiable functions, may get trapped in local optima,
and struggle with discrete / non-smooth / multimodal problems. Modern (metaheuristic)
methods are: - Nature-inspired (biology, physics). - Derivative-free (only need function
values). - Stochastic (use randomness) → good at escaping local optima → aim for the global
optimum.

[TRICK] MEMORY TRICK: Modern methods are "GSATN-F" → Genetic, Simulated annealing,
Ant colony, Tabu, Neural, Fuzzy.

4.2 Genetic Algorithms (GA)

Biological Inspiration

Based on Darwin's "survival of the fittest" and natural genetics. Better solutions ("fitter")
survive and reproduce; over generations the population improves.

Key Terms

GA term Meaning

Chromosome / String One candidate solution (often binary coded)

Gene One variable / bit of a chromosome

Population Set of chromosomes in one generation

Fitness function Measures how good a solution is (∝ objective)

Selection Choose parents based on fitness

Crossover Combine two parents to make offspring

Mutation Randomly flip a gene (maintains diversity)

Elitism Carry the best solution unchanged to next generation

Operators

• Selection: Roulette wheel (probability ∝ fitness), Tournament, Rank.

• Crossover: Single-point, two-point, uniform. (Probability p_c ≈ 0.6–0.9.)

Engineering Optimization (CIE-312) — GGSIPU Exam Notes • Page 20

 • Mutation: Flip a bit with small probability (p_m ≈ 0.01–0.1).
• Elitism: Keep best chromosome(s) to avoid losing good solutions.

Algorithm

1. Initialize random population of N chromosomes; set generation g = 0.

2. Evaluate fitness of each chromosome.
3. Selection of parents based on fitness.
4. Crossover parents → offspring (prob p_c).
5. Mutation of offspring (prob p_m).
6. Elitism: retain best; form new population.
7. g = g+1. If termination (max generations / converged) → STOP, else go to step 2.

Pseudocode

initialize population P (random)

evaluate fitness(P)
while not stop:
parents = select(P)
offspring = crossover(parents, pc)
offspring = mutate(offspring, pm)
P = elitism(P) + offspring
evaluate fitness(P)
return best chromosome

Flowchart

START → Initialize population → Evaluate fitness

→ Termination? --Yes--> Output best → STOP
|No
→ Selection → Crossover → Mutation → Elitism → (loop)

Numerical Example 4.1 (maximize f(x)=x² on x∈[0,31], 5-bit)

• Random population (binary): 01101(13), 11000(24), 01000(8), 10011(19).

• Fitness = x²: 169, 576, 64, 361. Total = 1170.
• Selection probabilities: 0.14, 0.49, 0.06, 0.31 → fitter strings (24, 19) get more copies.
• Apply single-point crossover + mutation → next generation moves toward x = 31 (max f =
961).

Applications

Structural & shape optimization, machine learning hyper-parameters, scheduling, travelling

salesman, antenna & circuit design, neural network training.

Advantages / Disadvantages

• [+] Global search, derivative-free, handles discrete/nonlinear/multimodal, parallelizable.

• [-] Many function evaluations (slow), tuning of p_c, p_m, population size; no guaranteed
optimum.

Engineering Optimization (CIE-312) — GGSIPU Exam Notes • Page 21

4.3 Simulated Annealing (SA)

Metallurgical Background

Inspired by annealing of metals: heat a metal then cool it slowly so atoms settle into a
minimum-energy (defect-free) crystal. In SA, "energy" = objective function; "temperature" T
controls acceptance of worse moves.

Acceptance Probability (Metropolis criterion)

★ A worse move (Δf > 0 for minimization) is accepted with probability P = exp(−Δf / T). A
better move (Δf ≤ 0) is always accepted. High T → accept many worse moves (explore).
Low T → accept few (exploit).

Cooling Schedule

T is reduced over time, commonly geometric: T_{new} = α·T_old, with α ≈ 0.8–0.99.

Algorithm

1. Choose initial solution X, high initial temperature T₀.

2. Repeat at each T (inner loop): a. Generate a neighbour X′. b. Δf = f(X′) − f(X). c. If Δf ≤ 0
accept X′; else accept with P = exp(−Δf/T).
3. Cool: T = α·T.
4. Stop when T is very low or no improvement; output best found.

Pseudocode

X = X0; T = T0
while T > Tmin:
repeat L times:
Xnew = neighbour(X)
d = f(Xnew) - f(X)
if d <= 0 or random() < exp(-d/T):
X = Xnew
T = alpha * T
return best X

Numerical idea 4.2

Minimizing f, at T=100 a worse move with Δf=10 is accepted with

P=exp(−10/100)=exp(−0.1)=0.905 (likely accepted). At T=1 the same move:
P=exp(−10)=0.000045 (almost never). This shows cooling reduces acceptance of bad moves.

Applications

VLSI layout, TSP, job scheduling, image processing, network design. - [+] Escapes local optima,
simple, derivative-free. [-] Slow, sensitive to cooling schedule, no optimum guarantee.

Engineering Optimization (CIE-312) — GGSIPU Exam Notes • Page 22

4.4 Ant Colony Optimization (ACO)

Biological Inspiration

Real ants find the shortest path to food by depositing pheromone; shorter paths get
reinforced faster and attract more ants (positive feedback / stigmergy).

Pheromone Concept

• Ants choose paths probabilistically, biased toward higher pheromone τ and better
heuristic η (e.g. 1/distance).
• Probability of choosing edge (i,j):

★ p_{ij} = (τ_{ij}^α · η_{ij}^β) / Σ (τ^α · η^β)

• Pheromone update: evaporation + deposit:

★ τ_{ij} ← (1−ρ)·τ_{ij} + Σ Δτ_{ij}, where ρ = evaporation rate, Δτ ∝ 1/(path length).

Algorithm

1. Initialize pheromone on all edges, place ants.

2. Each ant builds a solution using probability p_{ij}.
3. Evaluate all tours; update pheromones (evaporate then deposit, more on shorter tours).
4. Repeat for many iterations; output the best tour.

Flowchart

START → Init pheromones → Place ants

→ Each ant builds tour (prob. rule)
→ Evaporate + deposit pheromone
→ Stop? --No--> (loop) ; --Yes--> Best tour → STOP

Numerical idea 4.3

On a small TSP, edges on shorter tours accumulate more pheromone each iteration, so after
several iterations almost all ants follow the shortest route.

Applications

Travelling salesman, vehicle routing, network routing, scheduling, telecom. - [+] Good for
discrete/combinatorial & routing, parallel, adaptive. [-] Slow convergence, many parameters (α,
β, ρ), theoretical analysis hard.

4.5 Tabu Search (TS)

Idea

A local search that uses memory to avoid cycling back to recently visited solutions. Recent
moves are stored in a Tabu List (forbidden) for a number of iterations (tabu tenure).

Engineering Optimization (CIE-312) — GGSIPU Exam Notes • Page 23

Memory Structures

• Short-term (tabu list): recently visited moves/solutions — forbidden.

• Intermediate-term: intensification — focus search near good solutions.
• Long-term: diversification — push search into unexplored regions.
• Aspiration criterion: allow a tabu move if it gives a better solution than the best so far.

Algorithm

1. Start with an initial solution; best = current; empty tabu list.

2. Generate neighbours; pick the best non-tabu neighbour (or tabu but meeting aspiration).
3. Move there; update tabu list (add the move, remove expired ones).
4. Update best if improved. Repeat until stopping criterion.

Applications

Scheduling, routing, assignment, graph colouring, TSP. - [+] Escapes local optima via memory,
efficient. [-] Memory and parameter tuning (tenure, list size).

4.6 Neural-Network-Based Optimization

Introduction

Artificial Neural Networks (ANN) mimic the brain: neurons connected by weighted links.
Some networks (e.g. Hopfield networks) settle into a minimum-energy state and can be used
to solve optimization problems (the energy function = the objective).

Architecture

• Layers: input, hidden, output. Each connection has a weight w; each neuron applies an
activation function (sigmoid, ReLU, tanh).

Learning / Optimization Process

• Training = optimization: adjust weights to minimize an error (loss) function, typically

by gradient descent / backpropagation.
• Hopfield/energy networks: the network dynamics minimize an energy function E = −½ ΣΣ
wᵢⱼvᵢvⱼ − Σ θᵢvᵢ, mapping a problem (e.g. TSP) onto E.

Applications

Function approximation, pattern recognition, control, combinatorial optimization (Hopfield

TSP), parameter estimation.

Engineering Optimization (CIE-312) — GGSIPU Exam Notes • Page 24

4.7 Fuzzy Optimization

Fuzzy Sets

Classical sets: an element is in or out (membership 0 or 1). Fuzzy sets allow partial
membership between 0 and 1 — useful when goals/constraints are vague ("cost should be
low", "strength high").

Membership Function μ(x)

A function μ: X → [0,1] giving the degree of membership. Common shapes: triangular,

trapezoidal, Gaussian.

Fuzzy Logic

Reasoning with linguistic variables (low, medium, high) and IF–THEN rules, using fuzzy
AND (min), OR (max), NOT (1−μ).

Fuzzy Optimization

Objective and/or constraints are fuzzy. A common approach (Bellman–Zadeh): the fuzzy
decision is the intersection of fuzzy goal and fuzzy constraints; maximize the minimum
membership:

★ maximize λ, s.t. λ ≤ μ_goal(X), λ ≤ μ_constraint(X) (max–min principle).

Engineering Applications

Control systems (washing machines, AC, cameras), decision-making under uncertainty,

resource allocation with vague limits, structural design with imprecise data.

4.8 — MASTER COMPARISON TABLE (UNIT 4)

Method Inspiration Speed Accuracy Complexity Memory Global search Typical

use

Genetic Evolution/ Slow– High Medium Medium Excellent Design,

Algorithm genetics Medium (population) ML,
scheduling

Simulated Metal Slow Medium– Low Low (single Good TSP, VLSI
Annealing annealing High soln)

Ant Colony Ant Slow High High Medium Good Routing,

foraging (combinatorial) TSP

Tabu Search Memory- Medium High Medium High Good Scheduling,

based (memory assignment
search lists)

Neural Brain Fast High High High Local-ish Pattern,

Network neurons (after (weights) control,
training) Hopfield

Engineering Optimization (CIE-312) — GGSIPU Exam Notes • Page 25

 Method Inspiration Speed Accuracy Complexity Memory Global search Typical
use

Fuzzy Human Fast Depends Low– Low N/A (handles Control,

Optimization reasoning Medium vagueness) vague
problems

4.9 — UNIVERSITY + VIVA QUESTIONS (UNIT 4)

2-mark: 1. Define chromosome & gene. 2. What is mutation? 3. State SA acceptance

probability. 4. What is a pheromone? 5. Define tabu list. 6. What is a membership function? 7.
What is elitism?

5-mark: 8. Explain GA operators (selection, crossover, mutation). 9. Explain SA with cooling

schedule. 10. Explain ACO probability & pheromone update. 11. Explain Tabu Search memory
structures. 12. Explain fuzzy sets & membership functions. 13. NN-based optimization
(Hopfield idea).

10-mark: 14. Full GA algorithm + flowchart + numerical (f=x²). 15. SA algorithm, acceptance
rule, applications, merits/demerits. 16. ACO algorithm + flowchart + applications. 17. Compare
all modern methods (table) on speed/accuracy/memory/global search.

15-mark: 18. Explain GA in detail with biological basis, operators, algorithm, example,
applications. 19. Explain SA & ACO with theory, algorithm, example, applications and compare.
20. Explain fuzzy optimization (sets, membership, logic, max–min) and NN optimization with
applications.

Viva: - Why are GA/SA called global methods? They use randomness to escape local optima. -
Role of temperature in SA? Controls probability of accepting worse moves (exploration vs
exploitation). - Why pheromone evaporation in ACO? Prevents premature convergence to a sub-
optimal path. - Purpose of tabu list? To avoid revisiting recent solutions (no cycling). -
Crossover vs mutation? Crossover combines good genes; mutation maintains diversity.

4.10 — REVISION NOTES (UNIT 4)

• GA: population → select → crossover → mutate → elitism (fitness-driven evolution).

• SA: accept worse with P = exp(−Δf/T); cool slowly (T = αT).
• ACO: probability ∝ τ^α η^β; τ updated by evaporation + deposit.
• TS: local search + memory (tabu list) + aspiration.
• NN: training = minimize loss via gradient/backprop; Hopfield minimizes energy.
• Fuzzy: partial membership [0,1]; max–min decision for vague goals/constraints.

---

Engineering Optimization (CIE-312) — GGSIPU Exam Notes • Page 26

FINAL REVISION SECTION

A. COMPLETE FORMULA HANDBOOK

# Topic Formula

1 Standard form min f(X), gⱼ(X)≤0, hₖ(X)=0

2 Necessary (1-var) f′(x*)=0

3 Sufficient (1-var) f″>0 min, f″<0 max

4 Multi-var necessary ∇f(X*)=0

5 Multi-var sufficient Hessian positive definite → min

6 Iteration X_{k+1}=Xₖ+λₖSₖ

7 Steepest descent Sₖ=−∇fₖ

8 Newton X_{k+1}=Xₖ−Hₖ⁻¹∇fₖ

9 Conjugate gradient S_{k+1}=−∇f_{k+1}+βₖSₖ

10 β (Fletcher–Reeves) ‖∇f_{k+1}‖²/‖∇fₖ‖²

11 Optimal step (quad) λ*=−(∇fᵀS)/(SᵀHS)

12 Lagrangian L=f+Σλₖhₖ

13 KKT stationarity ∇f+Σμⱼ∇gⱼ=0, μⱼ≥0, μⱼgⱼ=0

14 Exterior penalty Φ=f+rΣ[max(0,gⱼ)]²+rΣhₖ²

15 Interior penalty Φ=f−rΣ1/gⱼ or f−rΣln(−gⱼ)

16 Projection matrix P=I−Nᵀ(NNᵀ)⁻¹N

17 SA acceptance P=exp(−Δf/T)

18 SA cooling T_{new}=αT

19 ACO probability p_{ij}=τ^α η^β / Σ(τ^α η^β)

20 ACO pheromone τ←(1−ρ)τ+Στ

21 Fuzzy decision max λ s.t. λ≤μ_goal, λ≤μ_constraint

B. ONE-DAY REVISION (read this last)

• U1: definitions, components (variables/objective/constraints/parameters), formulation steps

V-C-O-B-M, optimality (f′=0, f″ test, Hessian), local vs global, convexity.
• U2: three methods + their directions; λ* formula; SD slow/zig-zag, Newton 1-step for
quadratic, CG ≤ n steps; comparison table.
• U3: Lagrange, KKT (4 conditions), exterior (r↑∞) vs interior (r↓0) penalty, active
constraints, engineering examples.
• U4: GA/SA/ACO/TS/NN/Fuzzy — one line each + master comparison table + key formulas
(P=exp(−Δf/T), p_ij).

Engineering Optimization (CIE-312) — GGSIPU Exam Notes • Page 27

C. 50 IMPORTANT DEFINITIONS (one-liners)

Optimization, design variable, objective function, constraint, parameter, feasible region,

feasible/infeasible point, equality constraint, inequality constraint, active constraint, inactive
constraint, side constraint, design vector, design space, global optimum, local optimum,
stationary point, saddle point, convex function, convex set, gradient, Hessian, positive-definite
matrix, directional derivative, descent direction, line search, step length, search direction,
steepest descent, Newton's method, conjugate gradient, conjugate directions, quadratic
convergence, linear programming, nonlinear programming, deterministic, stochastic, static,
dynamic optimization, Lagrange multiplier, Lagrangian, KKT conditions, complementary
slackness, penalty function, exterior/interior penalty, barrier function, SUMT, metaheuristic,
genetic algorithm, chromosome, fitness function, crossover, mutation, elitism, simulated
annealing, cooling schedule, acceptance probability, ant colony optimization, pheromone, tabu
search, tabu list, aspiration criterion, neural network, membership function, fuzzy set.

D. 50 MOST IMPORTANT VIVA QUESTIONS (themes)

Definition & need of optimization; difference parameter vs variable; standard form; convexity &
why it matters; meaning of ∇f=0; Hessian test; local vs global; why SD is slow; why Newton is
fast; when Newton fails; what are conjugate directions; CG vs Newton; meaning of λ*; what is
line search; Lagrange multiplier meaning; KKT four conditions; complementary slackness;
active vs inactive constraint; exterior vs interior penalty; why barrier fails for equality; what is
SUMT; why metaheuristics; GA operators; roulette selection; crossover vs mutation; elitism; SA
acceptance rule; role of temperature; cooling schedule; ACO pheromone & evaporation; ACO
probability rule; tabu list purpose; aspiration criterion; intensification vs diversification; NN
training as optimization; Hopfield energy; fuzzy set vs crisp set; membership function; max–min
fuzzy decision; deterministic vs stochastic; single vs multi-objective; static vs dynamic; integer/
discrete optimization; penalty parameter behaviour; feasible direction; gradient projection;
saddle point; positive-definite meaning; why convex problems are easy; difference LP vs NLP.

E. 100 UNIVERSITY EXAM QUESTIONS

Use the 20 per unit above (U1: 20, U2: 30, U3: 20, U4: 20) plus these 10 mixed: 1. Differentiate
classical and modern optimization. 2. Explain SUMT. 3. Compare SD, Newton, CG with a
common numerical. 4. Derive KKT and solve a 2-var inequality problem. 5. Solve a penalty-
method numerical for 3 values of r. 6. Explain GA with a maximize-x² example. 7. Compare GA,
SA, ACO. 8. Formulate and classify a beam/can design problem. 9. Explain convexity with
diagrams. 10. Write algorithms + flowcharts of any three methods.

F. EXPECTED QUESTIONS FOR EXAMINATION (high probability)

• Steepest descent numerical (2 iterations) ★ ★ ★

• Newton's method derivation + 1-step numerical ★ ★ ★
• KKT conditions: state + apply ★ ★ ★
• Exterior/Interior penalty: formulation + numerical ★ ★ ★
• GA: operators + flowchart + example ★ ★ ★
• SA: acceptance probability + algorithm ★ ★
• Comparison tables (U2 methods; U4 modern methods) ★ ★ ★

Engineering Optimization (CIE-312) — GGSIPU Exam Notes • Page 28

• Problem formulation + classification ★ ★

G. IMPORTANT NUMERICAL PROBLEMS (must practice)

1. f = x₁−x₂+2x₁²+2x₁x₂+x₂² by SD, Newton, CG (start (0,0)).

2. min x₁²+x₂² s.t. x₁+x₂=4 (Lagrange).
3. (x₁−2)²+(x₂−2)² s.t. x₁+x₂≤1 (KKT).
4. (x−1)² s.t. x≥2 by exterior penalty (r=1,10,100,1000).
5. min x s.t. x≥1 by interior penalty.
6. maximize f=x² (5-bit GA), one generation.
7. LP corner-point: max 3x₁+2x₂ s.t. x₁+x₂≤4, x₁≤3.

H. UNIT-WISE MIND MAPS

OPTIMIZATION
├─ U1 Basics: variables·objective·constraints·params | formulation | optimality | local/
global
├─ U2 Unconstrained: Steepest Descent | Newton | Conjugate Gradient (dir → step → update)
├─ U3 Constrained: Lagrange | KKT | Penalty(ext/int) | Projected gradient | applications
└─ U4 Modern: GA | SA | ACO | Tabu | Neural | Fuzzy (nature-inspired, global, derivative-
free)

I. FREQUENTLY ASKED DERIVATIONS

1. Steepest-descent direction = −∇f (from directional derivative).

2. Newton update from 2nd-order Taylor series.
3. Optimal step λ* for a quadratic.
4. Conjugate gradient β (Fletcher–Reeves).
5. KKT conditions from the Lagrangian.
6. Penalty/barrier limiting behaviour (r→∞ / r→0).

J. LAST-MINUTE REVISION CHARTS

If question is about… Remember

"best feasible solution" definition of optimization

f′=0 only stationary point, still test f″

zig-zag / slow steepest descent

1-step for quadratic Newton

≤ n steps, no Hessian conjugate gradient

λ multiplier Lagrange / KKT

r→∞, square of violation exterior penalty

r→0, 1/g or −ln interior penalty

exp(−Δf/T) simulated annealing

pheromone, ants ACO

Engineering Optimization (CIE-312) — GGSIPU Exam Notes • Page 29

If question is about… Remember

chromosome, crossover genetic algorithm

memory, forbidden moves tabu search

membership 0–1 fuzzy optimization

FINAL EXAM TIPS

1. Always write the standard form at the start of a numerical — examiners give marks for it.
2. For numericals, show the gradient/Hessian explicitly before plugging numbers.
3. Draw the flowchart even if not asked in algorithm questions — it earns extra marks.
4. State advantages/disadvantages in 2–3 bullet points for every method.
5. Memorise the comparison tables — they answer 10-mark questions quickly.
6. Manage time: 2-mark in ≤3 min, 5-mark in ~7 min, 10/15-mark in 15–20 min.

**ALL THE BEST! **

Engineering Optimization (CIE-312) — GGSIPU Exam Notes • Page 30