HW4
ISE 530: Optimization for Analytics
Andre´s Go´mez
March 2021
Question 1
Solve using the KKT conditions the optimization problems
min
x,y
− ln(x + 1)− y
s.t. 2x + y ≤ 3
x, y ≥ 0.
Question 2
Solve using the KKT conditions the optimization problems
min
x,y
x2 + y2
s.t. x2 + y2 ≤ 5
x + 2y = 4
x, y ≥ 0.
1
Question 3
Solve using the KKT conditions the optimization problems
min
x,y
(x− 0.5)2 + (y − 1)2
s.t. y ≤ x
x ≤ 1
x, y ≥ 0.
2
Question 4
Consider a discrete random variable X taking one of n values, x1, . . . , xn. The probability
associated with value xi is pi, this is, P (X = xi) = pi. Since the vector p ∈ Rn is a
probability distribution, it satisfies
∑n
i=1 pi = 1 and pi ≥ 0 for all i = 1, . . . , n.
The entropy of this distribution is given by
ε = −
n∑
i=1
pi log(pi).
The maximum entropy distribution supported on x1, . . . , xn can be found by solving the
optimization problem
min
p∈Rn
n∑
i=1
pi log(pi) (1a)
s.t.
n∑
i=1
pi = 1 (1b)
pi ≥ 0 i = 1, . . . , n. (1c)
You can assume that strong duality holds for (1). Show that the maximum entropy
distribution in this case is a uniform distribution, this is, pi = 1/n.
Question 5
Given a point x and function f , consider the problem of finding the a direction d with
unit norm that results in the fastest decrease of f(x + d), given by
min
d
n∑
i=1
∂f(x)
∂xi
di
s.t
n∑
i=1
d2i = 1.
Show that d = ∇f(x) is a KKT point for the above optimization problem.
3