Scribd
Upload
6 views14 pages

Chapter 2 Basis Math

The document provides an overview of optimization fundamentals, including the definition of optimization problems, notations for decision variables and objective functions, and the concept of convex sets and functions. It explains the conditions for convexity, examples of convex functions, and introduces the notion of norms and Taylor approximations. The content serves as a mathematical foundation for understanding optimization techniques.

Uploaded by

nguyenquangtrunghieu2k7
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views14 pages

Chapter 2 Basis Math

The document provides an overview of optimization fundamentals, including the definition of optimization problems, notations for decision variables and objective functions, and the concept of convex sets and functions. It explains the conditions for convexity, examples of convex functions, and introduces the notion of norms and Taylor approximations. The content serves as a mathematical foundation for understanding optimization techniques.

Uploaded by

nguyenquangtrunghieu2k7
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

FUNDAMENTALS OF

OPTIMIZATION
Mathematical foundation
Optimization problems
• Maximize or minimize some function relative to some set (range of
choices)
• The function represents the quality of the choice, indicating which is the
“best”
• Example
• A shipper need to find the shortest route to deliver packages to
customers 1, 2, …, N
Notations
• x  Rn : vector of decision variables xj, j = 1, 2, …, n
• f : Rn → R is the objective function (dom f = Rn)
• gi : Rn → R is the constraint function defining restriction on x, i = 1, 2, …,
m

minimize f(x) over x = (x1, x2,…, xn) X  Rn satisfying a property P:

gi(x) ≤ bi, i = 1, 2, …, s
gi(x) = di, i = s + 1, 2, …, m
Convex sets
• S is called a convex set if:  u1, u2, …, uk in S,  non-negative numbers
1, 2, …, k such that σ𝑘𝑖=1 i = 1, then σ𝑘𝑖=1 𝑢𝑖i is in S

Convex set Non Convex set


Convex functions
• Linear function: f(x) = Ax
• Affine function: f(x) = Ax + b
• Convex function
• f is called convex if x1, x2 and  [0,1]:
f(x1 + (1 - )x2) ≤ f(x1) + (1 - )f(x2)
• f is called strictly convex if x1 ≠ x2 and  (0,1):
f(x1 + (1 - )x2) < f(x1) + (1 - )f(x2)
Convex functions
• Example: f(x) = 2x + 3
• f(x1 + (1- )x2) = 2(x1 + (1- )x2) + 3
= (2x1 + 3) + (2(1- )x2) + (1- )3)
=  f(x1) + (1- )f(x2)
Convex functions
• Examples
• f(x) = x2
• f(x) = xn, n is a constant is convex on x > 0
• Is convex if n  1 or n  0
• Is concave is 0  n  1
• f(x) = eax, a is a constant
• f(x) = xlnx
Basis
• f(x1,x2,…, xn) is a multivariable function
𝑓
(𝑥)
𝑥1
𝑓
(𝑥)
𝑥2
f(x) (or f ’(x)) =
…

𝑓
(𝑥)
𝑥𝑛

2𝑓
2f(x) (or f ’’(x)) = (𝑥) called Hessian matrix
𝑥𝑖𝑥𝑗
Convex functions
• First-order condition
• Suppose f is differentiable (i.e., its gradient exists at all points in
dom f, which is open). f is convex if and only if dom f is convex and
f(x) + f(x)T (y-x) ≤ f(y), x,y dom f

f(y)

f(x) f(x) + f(x)T (y-x)

x y
Basis
• If f(x) = 0, then f(y)  f(x), y dom f → x is global minimizer of the
function f

f(y)

f(x) f(x) + f(x)T (y-x)

x y
Norms

• Norm: A real-valued function f(x) on Rn is called a norm, if


• f(x)  0
• f(x) = f(x)
• f(x + y) ≤ f(x) + f(y) (triangle inequality)
• Examples
• ||x||p = (|x1|p + |x2|p + . . . + |xn|p)1/p
• ||x||1 = (|x1| + |x2| + . . . + |xn|)
• ||x|| = max{|x1|, |x2|, . . . , |xn|}
Taylor approximation

• Single variable Taylor series


𝑓′ 𝑎 𝑓′′ 𝑎 2
f(x) = f(a) + (𝑥 − 𝑎) + 𝑥−𝑎 +⋯
1! 2!
• First-order Taylor approximation
f(x + h )  f(x) + hT (x)
• Second-order Taylor approximation
1
f(x+h)  f(x) + hTf(x) + hT2f(x)h
2
Thank you
for your
attentions!

You might also like