UUM 526
Optimization Techniques in Engineering
Spring 2018-2019
Problem Set I
Asst. Prof. N. Kemal Ure
Department of Aeronautics
Istanbul Technical University
Due date is March 5th.
Homework Policy:
• All homework should be submitted through Ninova. No hard copy submission are needed/allowed.
• Late homeworks can be submitted by email with a −30 points penalty per day. (Hence after 4 late
days you will not gain any scores by submitting your homework)
• If you type the solution in LATEX, you will get +10 points. There are no extra points for hand-
written/scanned solutions or solutions written in MS Word.
• There is a bonus problem at the end, which is worth extra +10 points. The bonus problem is
significantly more difficult than the rest of the PSet. Only attempt at doing it after you have mastered
the subject and solved all the other problems.
• The full score for this PSet is 100 points. However, you can get a total of 120 points if you type the
solutions in LATEXand solve all the problems correctly along with the bonus problem.
• You can discuss the solution strategies with your classmates, however you must completely type
your solutions on your own. If any cheating is detected, you will get a −100 (yes that is a negative
score) from the PSet.
1
Linear Transformations
• Problem 1 (4 points): Let λ1 , λ2 , . . . , λn be the eigenvalues of the matrix A ∈ Rn×n . Show that
eigenvalues of I − A are 1 − λ1 , 1 − λ2 , . . . , 1 − λn .
• Problem 2 (6 points): For each of the following quadratic forms in R3 , determine if it is positive
definite, negative definite, negative semidefinite, or indefinite.
1. f (x) = x22
2. f (x) = x21 + 2x22 − x1 x3
3. f (x) = x21 + x23 + 2x1 x2 + 2x1 x3 + 2x2 x3
• Problem 3 (20 points): Remember that the 1−norm on Rn is defined by
n
X
kxk = |xi |.
i=1
and the associated induced matrix norm for A ∈ Rm×n is given as:
kAk1 = max kAxk1 .
kxk1 =1
Show that kAk1 = maxj m
P
i=1 |aij | (the maximum absolute column sum of A), where aij is the
element of A that corresponds to ith row and jP th
column. Next, solve the same problem using the
infinity norm, that is show that kAk∞ = maxi nj=1 |aij | (the maximum absolute row sum of A).
Multivariable Calculus
• Problem 4 (15 points): Let A be an n × n matrix.
1. Show that if kAk < 1, then
lim Ak = 0.
k→∞
Here k.k is any matrix norm that satisfy norm conditions, and 0 is the zero matrix. (10 points)
2. Show that for any A,
kAk ≥ max |λi (A)|.
1≤i≤n
Here λi (A) denotes the ith eigenvalue of A . (5 points)
• Problem 5 (15 points): Write down the second order Taylor expansion of the following functions
f : R2 → R around the specified x0 .
2
1. f (x) = x1 e−x2 + x2 + 1, x0 = [1, 0]> (5 points)
2. f (x) = x41 + 2x21 x22 + x42 , x0 = [1, 1]> (5 points)
3. f (x) = ex1 −x2 + ex1 +x2 + x1 + x2 + 1, x0 = [1, 0]> (5 points)
Basics of Optimization
• Problem 6 (20 points): Consider the following minimization problem on R2
minimize f (x1 , x2 ) = 3x1
subject to x1 + x22 ≥ 2
1. Does the point x∗ = [2, 0]> satisfy FONC?
2. Does the point x∗ = [2, 0]> satisfy SONC?
3. Is the point x∗ = [2, 0]> a local minimizer?
• Problem 7 (20 points): Consider the following minimization problem on R2
minimize f (x1 , x2 ) = 4x21 − x22
subject to x21 + 2x1 − x2 ≥ 0
x1 ≥ 0, x2 ≥ 0
1. Does the point x∗ = [0, 0]> satisfy FONC?
2. Does the point x∗ = [0, 0]> satisfy SONC?
3. Is the point x∗ = [0, 0]> a local minimizer?
Bonus Problem (Geometry)
• Problem 8 (10 points): In the class we proved that a linear variety {x : Ax = b} contains all the
lines that pass through any of its two points. Prove the converse of this statement. That is; if a set
contains all the lines that pass through any of its two points, then it is a linear variety.