Description
youtube link 1: https://youtu.be/deFMue9YtVk?feature=shared youtube link 2: https://youtu.be/e_khtYmf21k?feature=shared
Unformatted Attachment Preview
p 50 111
1 4 39
1 43 -72
1 44 -99
1 49 -57
2 7 78
2 14 -28
2 32 15
3 11 -84
3 44 86
4 11 -77
4 22 43
4 27 -12
4 38 -86
4 39 -81
4 49 -48
5 9 -51
5 16 -75
5 20 -53
6 7 2
6 14 -68
6 15 -3
6 16 -66
6 21 89
6 24 -90
6 31 -76
7 17 -97
7 18 -65
7 32 -50
7 48 2
7 50 -22
8 42 -91
8 49 -19
9 29 -22
9 31 -7
9 45 22
9 48 -10
10 20 -77
10 30 42
10 41 40
11 18 35
11 41 -86
11 42 -62
11 47 75
12 20 94
12 25 -95
12 46 25
12 47 25
13 30 -14
13 40 45
13 43 48
13 47 -25
14 19 -24
14 23 -31
14 30 -78
14 36 59
15 19 -72
15 21 45
15 26 -38
15 27 55
15 36 -53
16 35 40
16 37 -55
17 20 -78
17 23 -65
17 24 -16
17 25 30
18 33 -49
19 19 99
19 22 -60
19 48 78
21 31 -28
21 38 17
22 25 -43
22 29 70
22 35 98
22 46 81
22 50 -87
23 27 70
23 34 -10
23 43 -43
23 48 -90
24 33 -9
24 36 31
25 48 -24
26 39 -50
27 47 3
27 49 65
28 39 -84
28 44 12
29 34 62
29 39 -91
29 50 23
30 50 98
31 33 12
31 35 14
32 35 -48
32 48 -49
34 39 66
35 40 -18
36 41 -88
37 41 -77
37 50 44
38 48 -71
39 47 9
39 50 -36
40 40 -48
40 43 -67
42 45 -64
44 44 58
46 48 -12
47 48 35
Convex optimization
Yu Du
Affine set
line through x 1 , x 2 : all points
x = θx 1 + (1 − θ)x 2
(θ ∈ R)
x1
θ = 1.2
θ= 1
θ = 0.6
x2
θ= 0
θ = −0.2
affine set: contains the line through any two distinct points in the set
example: solution set of linear equations { x | A x = b}
(conversely, every affine set can be expressed as solution set of system of
linear equations)
Convex sets
2–2
Convex set
line segment between x 1 and x 2 : all points
x = θx 1 + (1 − θ)x 2
with 0 ≤ θ ≤ 1
convex set: contains line segment between any two points in the set
x 1 , x 2 ∈ C,
0≤ θ≤ 1
=⇒
θx 1 + (1 − θ)x 2 ∈ C
examples (one convex, two nonconvex sets)
Convex sets
2–3
Convex combination and convex hull
convex combination of x 1 ,. . . , x k : any point x of the form
x = θ1×1 + θ2×2 + · · · + θ k x k
with θ1 + · · · + θ k = 1, θi ≥ 0
convex hull conv S: set of all convex combinations of points in S
Convex sets
2–4
Convex cone
conic (nonnegative) combination of x 1 and x 2 : any point of the form
x = θ1×1 + θ2×2
with θ1 ≥ 0, θ2 ≥ 0
x1
x2
0
convex cone: set that contains all conic combinationsof points in the set
Convex sets
2–5
Hyperplanes and halfspaces
hyperplane: set of the form { x | a T x = b} (a / = 0)
a
x0
x
aT x = b
halfspace: set of the form { x | a T x ≤ b} (a / = 0)
a
x0
aT x ≥ b
aT x ≤ b
• a is the normal vector
• hyperplanes are affine and convex; halfspaces are convex
Convex sets
2–6
Generalized inequalities
a convex cone K ⊆ R n is a proper cone if
• K is closed (contains its boundary)
• K is solid (has nonempty interior)
• K is pointed (contains no line)
examples
• nonnegative orthant K = R+n = { x ∈ R n | x i ≥ 0, i = 1, . . . , n }
+
• nonnegative polynomials on [0, 1]:
K = { x ∈ R n | x 1 + x 2 t + x 3 t 2 + · · · + x n t n − 1 ≥ 0 for t ∈ [0, 1]}
Convex sets
2–7
Separating hyperplane theorem
if C and D are nonempty disjoint convex sets, there exist a / = 0, bs.t.
a T x ≤ b for x ∈ C,
a T x ≥ b for x ∈ D
aT x ≥ b
aT x ≤ b
D
C
a
the hyperplane { x | a T x = b} separates C and D
strict separation requires additional assumptions (e.g., C is closed, D is a
singleton)
Convex sets
2–8
Supporting hyperplane theorem
supporting hyperplane to set C at boundary point x 0 :
{ x | aT x = aT x 0 }
where a / = 0 and a T x ≤ a T x 0 for all x ∈ C
a
x0
C
supporting hyperplane theorem: if C is convex, then there exists a
supporting hyperplane at every boundary point of C
Convex sets
2–9
Convex functions
3–1
Definition
f : R n → R is convex if d o m f is a convex set and
f (θx + (1 − θ)y) ≤ θ f (x) + (1 − θ)f (y)
for all x, y ∈ d o m f , 0 ≤ θ ≤ 1
( y, f ( y ) )
(x, f (x))
• f is concave if − f isconvex
• f is strictly convex if d o m f is convex and
f (θx + (1 − θ)y) < θ f (x) + (1 − θ)f (y)
for x, y ∈ d o m f , x / = y, 0 < θ < 1
Convex
functions
3–
11
Examples on R
convex:
• affine: ax + b on R, for any a, b ∈ R
ax
• exponential: e , for any a ∈ R
α
• powers: x on R + + , for α ≥ 1 or α ≤ 0
p
• powers of absolutevalue: |x| on R, for p ≥ 1
• negative entropy: x log x on R + +
concave:
• affine: ax + b on R, for any a, b ∈ R
α
• powers: x on R + + , for 0 ≤ α ≤ 1
• logarithm: log x onR - -
Convex
functions
3–
12
First-order condition
f is differentiable if d o m f is open and the gradient
/
∇ f (x) =
∂ f (x) ∂ f (x)
∂f (x)
,
,...,
∂x 1
∂x 2
∂x n
exists at each x ∈ d o m f
1st-order condition: differentiable f with convex domain is convex iff
f (y) ≥ f (x) + ∇ f (x) T (y − x)
for all x, y ∈ d o m f
f (y)
f (x) + ∇ f (x)T (y − x)
(x, f (x))
first-order approximation of f is global underestimator
Convex
functions
3–
13
Second-order conditions
f is t wice differentiable if d om f
n
2
is open and the Hessian ∇ f (x ) ∈ S ,
∂ 2 f (x)
∇ f (x) i j =
,
∂ x i∂ x j
2
i, j = 1, . . . , n,
exists at each x ∈ d o m f
2nd-order conditions: for twice differentiable f with convex domain
• f is convex if and only if
2
∇ f (x) ≻ = 0 for all x ∈ d o m f
2
• if ∇ f (x) ≻ 0 for all x ∈ d o m f , then f is strictly convex
Convex
functions
3–
14
Jensen’s inequality
basic inequality: if f is convex, then for 0 ≤ θ ≤ 1,
f (θx + (1 − θ)y) ≤ θ f (x) + (1 − θ)f (y)
extension: if f is convex,then
f (E z) ≤ E f (z)
Convex
functions
3–
15
Positive weighted sum & composition with affine function
nonnegative multiple: α f is convex if f is convex, α ≥ 0
sum: f 1 + f 2 convex if f 1 , f 2 convex (extends to infinite sums, integrals)
composition with affine function: f ( A x + b) is convex if f is convex
examples
• log barrier for linear inequalities
• (any) norm of affine function: f (x) = l A x + b l
Convex
functions
3–
16
Pointwise maximum
examples
Convex
functions
3–
17
A convex optimization example
Find the extreme points of the function
f ( x1 , x2 ) = x13 + x23 + 2 x12 + 4 x22 + 6
18
Find the extreme points of the function
f ( x1 , x2 ) = x13 + x23 + 2 x12 + 4 x22 + 6
Solution: The necessary conditions for the existence of an extreme point
are:
f
= 3 x12 + 4 x1 = x1 (3 x1 + 4) = 0
x1
f
= 3 x22 + 8 x2 = x2 (3 x2 + 8) = 0
x2
These equations are satisfied at the points: (0,0), (0,-8/3), (-4/3,0), and (4/3,-8/3)
19
Example
Solution cont’d: To find the nature of these extreme points,
we have to use the sufficiency conditions. The second order
partial derivatives of f are given by:
2 f
= 6 x1 + 4
2
x1
2 f
= 6 x2 + 8
2
x2
2 f
=0
x1x2
The Hessian matrix of f is given by:
0
6 x1 + 4
J=
0
6
x
+
8
2
20
Example
Solution cont’d:
If J1=(6x1+4) and
J2 =
6 x1 + 4
0
0
6 x2 + 8 , the values of J1 and J2 and
the nature of the extreme point are as given in the next slide:
21
Point X
J1
J2
Nature of J Nature of
X
f (X)
(0,0)
+4
(4 0
08)
Positive
definite
Relative
minimum
6
(0,-8/3)
+4
(4 0
0 -8)
Indefinite
Saddle
point
418/27
(-4/3,0)
-4
(-4 0
0 8)
Indefinite
Saddle
point
194/27
(-4/3,-8/3)
-4
(-4 0
0 -8)
Negative
definite
Relative
maximum
50/3
22
Methods for unconstrained convex optimization
• Steepest Descent
• Newton's Method
Methods for constrained convex optimization
• Penalty Method
• Augmented Lagrangian Method
Examples of using scipy or cvxpy to solve linear/nonlinear programing
(1)
# min x^2 + 1
# s.t. (x-2)(x-4) ≤ 0
# var x
#%%
# CVXPY
import cvxpy as cp
import numpy as np
import time
print('nSOLVING USING CVXPYn')
# Create two scalar optimization variables.
x = cp.Variable(1, name='x')
# Form objective.
f0 = x**2 + 1
obj = cp.Minimize(f0)
# Constraints
f1 = x**2 - 6*x + 8 # (x - 2)*(x - 4)
constraints = [f1= 1,
x1+3*x2>=1,
x1>=0,
x2>=0]
#Create objective
obj1 = cp.Minimize(x1+x2)
print(“Problem a”)
problem1 = cp.Problem(obj1, constraints)
print(“optimal value”, problem1.solve())
print(“status:”, problem1.status)
print(“optimal var”, x1.value, x2.value)
obj2 = cp.Minimize(-x1-x2)
print(“Problem b”)
problem2 = cp.Problem(obj2, constraints)
print(“optimal value”, problem2.solve())
print(“status:”, problem2.status)
print(“optimal var”, x1.value, x2.value)
obj3 = cp.Minimize(x1)
print(“Problem c”)
problem3 = cp.Problem(obj3, constraints)
print(“optimal value”, problem3.solve())
print(“status:”, problem3.status)
print(“optimal var”, x1.value, x2.value)
obj4 = cp.Minimize(cp.maximum(x1,x2))
print(“Problem d”)
problem4 = cp.Problem(obj4, constraints)
print(“optimal value”, problem4.solve())
print(“status:”, problem4.status)
print(“optimal var”, x1.value, x2.value)
obj5 = cp.Minimize(x1**2+9*x2**2)
print(“Problem e”)
problem5 = cp.Problem(obj5,constraints)
print(“optimal value”, problem5.solve())
print(“status:”, problem5.status)
print(“optimal var”, x1.value, x2.value)
→ Answer
Problem a
optimal value 0.5999999999116253
status: optimal
optimal var 0.3999999999724491 0.1999999999391762
Problem b
optimal value -inf
status: unbounded
optimal var None None
Problem c
optimal value -2.2491441767693299e-10
status: optimal
optimal var -2.2491441767693299e-10 1.5537158969947242
Problem d
optimal value 0.3333333334080862
status: optimal
optimal var 0.3333333334080862 0.33333333286259564
Problem e
optimal value 0.5000000000000002
status: optimal
optimal var 0.5000000000000001 0.1666666666666667
Homework 5
Question 1.
A stockbroker, Richard Smith, has just received a call from his most important client, Ann
Hardy. Ann has $50,000 to invest and wants to use it to purchase two stocks. Stock 1 is a solid
blue-chip security with a respectable growth potential and little risk involved. Stock 2 is much
more speculative. It is being touted in two investment newsletters as having outstanding growth
potential but also is considered very risky. Ann would like a large return on her investment but
also has considerable aversion to risk. Therefore, she has instructed Richard to analyze what mix
of investments in the two stocks would be appropriate for her.
Ann is used to talking in units of thousands of dollars and 1,000-share blocks of stocks. Using
these units, the price per block is 20 for stock 1 and 30 for stock 2. After doing some re- search,
Richard has made the following estimates. The expected return per block is 5 for stock 1 and 10
for stock 2. The variance of the return on each block is 4 for stock 1 and 100 for stock 2. The
covariance of the return on one block each of the two stocks is 5.
Without yet assigning a specific numerical value to the minimum acceptable expected return,
formulate a nonlinear programming model for this problem. (No need to solve)
Question 2
Solve the QUBO problem using python Gurobi:
max xTQx, x is binary.
The input file Q is defined in the bqp50.txt file.
Question 3
Use nonlinear programming solvers (such as scipy.optimize, or cvxpy, or cvxopt, or gurobi) to
solve following optimization problems.
(1)
(2)
(3)
Question 4
Use optimality conditions to find all local optimal and global optimal.
(1) ( ) = 48 − 60 2 + 3
(2) ( ) = 3 1 + 2 12 + 4 2 + 22 − 2 1 2 − 29
1. Convex function
Convex programming additional notes
2. Optimality condition for convex problems
3. Steepest(gradient) descent method and Newton method for convex optimization
1) Gradient descent
2) Newton method
3)
Purchase answer to see full
attachment
