Optimization 1
Problem 14: Traveling salesman problem
A company requires a salesman to visit its N stores (say 50 stores) that are geographically
distributed in different locations. Find the visiting sequence that will require the least amount
of overall travel.
Formulation: The traveling salesman problem is formulated as shortest path problem in an
undirected weighted graph where the stores represent the vertices of the graph. The problem
is then similar to Problem 10.
Classification of Optimization problems
• Nonlinear programming (NP) problems
– Objective function and constraints are nonlinear
• Convex optimization problems
– Feasible region is a convex set, objective function and inequality
constraints are convex, and equality constraints are linear
• Linear programming (LP) problems
– Objective function and constraints are linear
• Mixed integer programming (MIP) problems
– Some of the design variables take on values over a finite set
• Binary integer programming problems
– The design variables take on values over 0,1
The General Optimization Problem
• Let 𝒙 = 𝑥1 , 𝑥2 , … , 𝑥𝑛 denote the vector of design variables; then
the general optimization problem is mathematically defined as:
Objective: min 𝑓 𝒙 , 𝒙 ∈ ℝ𝑛
𝒙
Subject to:
𝑔𝑖 𝒙 ≤ 0, 𝑖 = 1, … , 𝑙 (inequality constraints)
ℎ𝑖 𝒙 = 0, 𝑖 = 𝑙 + 1, … , 𝑚 (equality constraints)
𝑥𝑗 ∈ 𝒮, 𝑗 = 1, … , 𝑘 (discrete variables)
𝑥𝑗𝐿 ≤ 𝑥𝑗 ≤ 𝑥𝑗𝑈 , 𝑗 = 𝑘 + 1, … , 𝑛 (continuous variables)
The feasible region
• Let 𝒙 = 𝑥1 , 𝑥2 , … , 𝑥𝑛 denote the vector of design variables.
Consider the optimization problem:
Objective: min 𝑓 𝒙 , 𝒙 ∈ ℝ𝑛
𝒙
𝑔𝑖 𝒙 ≤ 0, 𝑖 = 1, … , 𝑙;
Subject to ℎ𝑖 𝒙 = 0, 𝑖 = 𝑙 + 1, … , 𝑚;
𝑥𝑗𝐿 ≤ 𝑥𝑗 ≤ 𝑥𝑗𝑈 , 𝑗 = 1, … , 𝑛
• The set Ω = 𝑥: ℎ𝑖 𝒙 = 0, 𝑔𝑗 𝒙 ≤ 0, 𝑥𝑖𝐿 ≤ 𝑥𝑖 ≤ 𝑥𝑖𝑈 is termed
as the feasible region for the problem.
Convex Optimization Problems
• Consider a general optimization problem:
min 𝑓(𝒙)
𝒙
𝑔𝑖 𝒙 ≤ 0𝑖 , 𝑖 = 1, … , 𝑙
Subject to ℎ𝑖 𝒙 = 0, 𝑖 = 𝑙 + 1, … , 𝑚
𝑥𝑗 ∈ 𝑥𝑗𝐿 , 𝑥𝑗𝑈 , 𝑗 = 1, … , 𝑛
• The feasible region is defined by: 𝑆 = {𝒙: 𝑔𝑖 𝒙 ≤ 0, ℎ𝑗 𝒙 = 0}.
• The feasible region is a convex set if the functions: 𝑔𝑖 𝒙 , 𝑖 = 1, … , 𝑙,
are convex and the functions: ℎ𝑖 𝒙 , 𝑖 = 𝑙 + 1, … , 𝑚 are linear.
• If, in addition, 𝑓(𝒙) is a convex function, then the optimization
problem is convex.
Convex Optimization Problems
• Convex sets and convex functions:
– A set is convex if a line joining any two point lies in the set, e.g. a
regular polygon, a circle, a half space, a line, etc.
– A function is convex (downward) if it lies above its tangent line at
every point, or if it lies below its chord line between any two
points, e.g., 𝑓 𝑥1 , 𝑥2 = 𝑥12 + 𝑥22
Convex Optimization Problems
• A convex optimization problem is characterized by the existence of
a single global optimum.
• Establishing convexity property is important in iteratively solving
optimization problems
Convex Optimization Problems
• Examples of convex optimization problems:
– Linear programming problems
– Quadratic programming problems with linear equality constraints
– Unconstrained problems if the feasible region is convex
• NLP problems are generally nonconvex
Optimality
• A point 𝒙∗ is a local minimum of 𝑓(𝒙) if 𝑓 𝒙∗ ≤ 𝑓(𝒙) in the
neighborhood of 𝒙∗
• A point 𝒙∗ is a global minimum of 𝑓(𝒙) if 𝑓 𝒙∗ ≤ 𝑓(𝒙) for all
feasible 𝒙
Optimality Criteria for Single-Variable Functions
• The stationary points of a function 𝑓(𝑥) are characterized by:
𝑑𝑓(𝑥)
= 0.
𝑑𝑥
– The stationary points include the maxima, the minima, and the
points of inflexion
• The curvature condition is used to determine the type of solution:
𝑑 2 𝑓(𝑥 ∗ )
– Minimum: >0
𝑑𝑥 2
𝑑 2 𝑓(𝑥 ∗ )
– Maximum: <0
𝑑𝑥 2
𝑑 2 𝑓(𝑥 ∗ )
– Point of inflexion =0
𝑑𝑥 2
Example: Open box problem
What is the largest volume for an open box that can be constructed
from a given sheet of paper (8.5”x11”) by cutting out squares at the
corners and folding the sides?
Formulation: Let 𝑥 represent the side of the squares to be cut; then
the optimization problem to maximize the volume is formulated as:
max 𝑓 = 𝑥(8.5 − 2𝑥)(11 − 2𝑥)
𝑥
• First order condition:
𝑑𝑓(𝑥)
= 0 → 𝑥 ∗ = 1.585, 4.915
𝑑𝑥
• Second order condition:
𝑑 2 𝑓(1.585) 𝑑 2 𝑓(4.915)
= −39.95; = 39.95
𝑑𝑥 2 𝑑𝑥 2
Example: Open-box Problem
• MATLAB code
f=@(x) x*(8.5-2*x)*(11-2*x)
df=@(x) (8.5-2*x)*(11-2*x)-2*x*(11-2*x)-2*x*(8.5-2*x)
ddf=@(x) -2*(19.5-4*x)-2*(19.5-4*x)+8*x
fzero(df,1)
ans = 1.585
fzero(df,5)
ans = 4.915
f(1.585)
ans = 66.148
f(4.915)
ans = -7.648
ddf(1.585)
ans = -39.95
ddf(4.915)
ans = 39.95
Example: Open box problem
• Objective: max 𝑓 = 𝑥(8.5 − 2𝑥)(11 − 2𝑥)
𝑥
• MATLAB code:
syms x real
fx=x*(8.5-2*x)*(11-2*x);
df=diff(fx);
x=solve(df); vpa(x,4)
df2=diff(df);
eval(df2); vpa(ans,4)
