Description
Problem 1 (25pts). Suppose that f : R → R is convex, and a, b ∈ dom f with a < b, where dom
denotes the domain of the function. More specifically, f : Rp → Rq means that f is an Rp
-valued
function on some subset of Rp
, and this subset of Rp
is the domain of the function f. Show that
(a)
f(x) ≤
b − x
b − a
f(a) + x − a
b − a
f(b), for all x ∈ (a, b)
Hint: (Jensen’s Inequality) If p1, …, pn are positive numbers which sum to 1 and f is a real
continuous function that is convex, then
f
Xn
i=1
pixi
!
≤
Xn
i=1
pif (xi)
(b)
f(x) − f(a)
x − a
≤
f(b) − f(a)
b − a
≤
f(b) − f(x)
b − x
for all x ∈ (a, b). Draw a sketch that illustrates this inequality.
(c) Suppose f is differentiable. Use the result in (b) to show that:
f
′
(a) ≤
f(b) − f(a)
b − a
≤ f
′
(b)
Note that these inequalities also follow form:
f(b) ≥ f(a) + f
′
(a)(b − a), f(a) ≥ f(b) + f
′
(b)(a − b)
(d) Suppose f is twice differentiable. Use the result in (c) to show that f
′′(a) ≥ 0 and f
′′(b) ≥ 0.
Problem 2 (30pts) Show that the following functions are convex:
(a) f(x) = − log
− log Pm
i=1 e
a
T
i
x+bi
on dom f =
n
x |
Pm
i=1 e
a
T
i
x+bi < 1
o
. You can use the
fact that log (Pn
i=1 e
yi ) is convex.
(b)
f(x, u, v) = − log
uv − x
T x
on dom f =
(x, u, v) | uv > xT x, u, v > 0
(c) Let T(x, ω) denote the trigonometric polynomial
T(x, ω) = x1 + x2 cos ω + x3 cos 2ω + · · · + xn cos(n − 1)ω
Show that the function
f(x) = −
Z 2π
0
log T(x, ω)dω
is convex on {x ∈ Rn
| T(x, ω) > 0, 0 ≤ ω ≤ 2π}.
Hint: Nonnegative weighted sum of convex functions is still convex. Let this property extend
to infinite sums and integrals. Assume that f(x, y) is convex in x for each y ∈ A and w(y) ≥ 0
for each y ∈ A and integral exists. Then the function g defined as
g(x) = Z
A
w(y)f(x, y)dy
is convex in x.
Problem 3 (20pts). Consider the following function:
minimize −x1 − x2 + max {x3, x4}
s.t. (x1 − x2)
2 + (x3 + 2×4)
4 ≤ 5
x1 + 2×2 + x3 + 2×4 ≤ 6
x1, x2, x3, x4 ≥ 0
(a) Verify this is a convex optimization problem.
(b) Use CVX to solve the problem.
Problem 4 (25pts). To model the influence of price on customer purchase probability, the
following logit model is often used:
λ(p) = e
−p
1 + e−p
where p is the price, λ(p) is the purchase probability.
Assume the variable cost of the product is 0 (e.g., iPhone Apps). As the seller, you want to
maximize the expected revenue by choosing the optimal price. That is, you want to solve:
maximizep pλ(p)
(a) Draw a picture of r(p) = pλ(p) (for p from 0 to 10) and use the picture to show that r(p) is
not concave (thus maximize r(p) is not a convex optimization problem)
(b) Write down p as a function of λ (the inverse function of λ(p) ). Show that you can write the
objective function as a function of λ : ˜r(λ), where ˜r(λ) is concave in λ.
(c) From part 2, write the KKT condition for the optimal λ. Then transform it back to an optimal
condition in p.