Preface

1. There are 55 marks of questions deemed straight forward, 25 marks deemed medium and 20 marks deemed challenging.

2. In Questions 1 and 2, if you do not respond to one part or state“I’m not sure”, you receive 2 marks for that part. The same rule applies to Part 2 of Question 7.

3. In Questions 4 and 5, you may use results of earlier parts even if you fail to prove them. For example, even if you cannot prove the result of Part 1, you may receive full credit from Part 2 using the result of Part 1.

Question 1 [20 marks in total] Each part defines a non-empty set A and a function f on A. First determine whether A is a convex set; if so, determine whether f is concave, convex or neither. (You do not need to determine whether f is strictly concave or strictly convex.)

1.  [5 marks] (SF) A = R2  and f(x, y) = exp(x + y) for every (x, y) e R2 .

2.  [5 marks] (SF) A = {(x, y, z) e R3  : x2 + 2y2 + 5z4  < 10 and x + 3y - 4z > -105}, and f(x, y, z) = x2 + exp(y) - 35z .

3.  [5 marks] (SF) A = {(x, y) e R2  : x > y}, and f(x, y) = log(x - y) - ex(1)一y .

4.  [5 marks] (Medium) A = R3  and f(x, y, z) = (xyz)1/3  (the cubic root of xyz) for (x, y, z) e R3 .

Solution.

1. Clearly, A is a convex set. The Hessian of f at (x, y) is 、, which is positive semidefinite by the leading-principal-minor test. Therefore, f is a convex function.

2. The Hessian of g(x, y, z) = x2 + 2y2 + 5z4  is positive semidefinite everywhere, so g is a convex function. Therefore, A is a convex set. The Hessian of f at (x, y, z) is．(╱) ex(y) ．(、) , which is positive semidefinite by the eigenvalue test.  Therefore, f is a convex function.

3. For (x1 , y1 ), (x2 , y2 ) e A and t e [0, 1], tx2 +(1 - t)x1  > ty2 +(1 - t)y1 , so t(x2 , y2 )+ (1 -t)(x1 , y1 ) = (tx2 +(1 -t)x1 , ty2 +(1 -t)y1 ) e A. Therefore, A is a convex set. The Hessian of f at (x, y) is )一2(一))一5(一)一)2一(34一)5一、, which is negative semidefinite by the leading-principal-minor test. Therefore, f is a concave function.

4. Clearly, A is a convex set.  Put (x1 , y1 , z1 ) =  (1, 1, 1), (x2 , y2 , z2 ) =  (2, 1, 1) and (x3 , y3 , z3 ) = (-2, 1, 1). Then

f ╱ (x1 , y1 , z1 ) + (x2 , y2 , z2 )、 =   (3/2)1/3  s 1.14 > f (x1 , y1 , z1 ) + f (x2 , y2 , z2 );      f ╱ (x1 , y1 , z1 ) + (x3 , y3 , z3 )、 =   (-1/2)1/3  s -0.79 < f (x1 , y1 , z1 ) + f (x3 , y3 , z3 ).

The first inequality shows that f is not convex and the second inequality shows that f is not concave.

Question 2 [15 marks in total] For each of the following optimization problems, deter- mine whether it has a solution; if so determine whether the solution is unique.  You do not need to solve any of the problems.

1.  [5 marks] (SF)

minx,y     x2 - y4

s.t.     cos x + cos(y2 + 3) < ;

x6 + y6  < 28.

2.  [5 marks] (SF)

maxx,y,z     log x - - exp(-z);

s.t.       x > 0;

y > 0;

z > 0;

x8 + y28 + z18  < 251.

3.  [5 marks] (SF)

maxx,y,z     x + y - z;

s.t.       2x - y + z < 10;

x3 + y3 + z3  < 15.

Solution.

1. All functions are continuous and there are no implicit strict inequality constraints. It is easy to verify that (0, 0) satisfies both constraints. Finally, the second constraint implies that |x| < (28)1/6 and |y| < (28)1/6. Therefore, the feasible set is bounded. To sum up, the program has a solution. Clearly, (0, 0) is not a solution since (0, 1) is feasible and strictly better. As all functions are invariant upon changing the signs of x and y, whenever (x* , y* ) is a solution, (-x* , -y* ) is also a solution. Since (x* , y* ) (0, 0), (-x* , -y* ) (x* , y* ). This shows that the solution is not unique.

2. All function are continuous. When x - 0+ or y - 0+, the value of the objective function approaches -o.  Therefore, the strict inequality constraints can be re- placed with weak inequality constraints that x > x and y > y for some positive and sufficiently small x and y .  Clearly, (1, 1, 0) is feasible.  The last constraint implies that |x| < (251)1/8 , |y| < (251)1/28 and |z| < (251)1/18. Therefore, the feasible set is bounded. To sum up, the program has a solution. The feasible set is convex since g(x, y, z) = x8 + y28 + z18 is a convex function. The Hessian of the objective function at (x, y, z) is  ．(╱) -一2     -2 一3     - ex(-z)．(、) , which is negative definite by

the eigenvalue test. Therefore, the objective function is strictly concave. Therefore, the program has a unique solution.

3. Fix x = y = 0 and send z - -o; then (x, y, z) satisfies both constraints, while the value of the objective function approaches +o.  Therefore, the program does not have a solution.

Question 3 [10 marks] (SF) Solve the following consumer’s problem, where b > 0:

maxx í,xà       - - ;

s.t.       x1  > 0;

x2  > 0;

p1 x1 + p2 x2  < y.

Solution. Since the objective function approaches -o as x1  - 0+, the program has a solution. Clearly, the budget constraint must be binding and the first constraint cannot be binding.

Case 1 The second constraint is not binding.

Let λ be the Lagrange multiplier of the budget constraint.  Then the first-order conditions are

x 1(一)2     =   λp1 ;

(x2 + b)一2     =   λp2 .

Therefore, x1  = (λp1 )一1/2 and x2  = (λp2 )一1/2 - b. Substituting these into the budget constraint yields that λ 一1/2  = (y + p2 b)/(p1(1)/2 + p2(1)/2). Therefore, x1  = p í and x2  = ep(y一)p(à)à(b) . That x2  > 0 requires that y > ′p1p2 b.

Case 2 The second constraint is binding.

Let λ be the Lagrange multiplier of the budget constraint and µ be the Lagrange multiplier of the constraint that -x2  < 0. Then the first-order conditions are

x 1(一)2     =   λp1 ;

(x2 + b)一2     =   λp2 - µ.

Clearly, x2  = 0 and thus x1  = y/p1 .  From the first equation, λ = p1 y一2  and then

from the second equation, µ = p1p2 y一2 - b一2 . That µ > 0 requires that y < ′p1p2 b.

To sum up, the solution is as follows:

x 1(*)     = , ,

,0,

if y < ′p1p2 b;

if y > ′p1p2 b.

if y < ′p1p2 b;

if y > ′p1p2 b.

Question 4 [20 marks in total] In this question, we consider a monopoly’s pricing problem of a durable good (such as a smart phone). For simplicity, assume that the good is sold only on two dates, Date 1 and Date 2. Implicitly, the good becomes obsolete (or is replaced by the next generation) and nobody would buy it after Date 2. The result we obtain here sheds lights on what would happen if we allow for more dates.

Let p1   be the price of the good on Date 1 and p2   be the price of the good on Date

2. Crucially, the monopoly announces p1  and p2  at the beginning of Date 1 (and cannot adjust p2  on Date 2).  Since this is not a course in industrial organization, we do not pursue the economics behind this assumption.  There are some consumers present from Date 1 and some more consumers enter the market on Date 2. Each consumer has a value

v of the product and has three options if present from Date 1:  buying the product on Date 1 yields “payoff”(happiness) v - p1 , buying the product on Date 2 yields payoff δ(v - p2 ) and not buying yields payoff 0.  Here δ e (0, 1) is a parameter capturing the discount of future value. Consumers who enter the market on Date 2 only has the latter two options. Each consumer chooses the option that maximizes his “payoff”(happiness).

1.  [4 marks] (SF) Clearly, a consumer who enters the market on Date 2 buys the product if and only if his valuation is above p2 .  Assuming that p2   > p1 , show that no consumer present from Date 1 buys the product on Date 2. Assuming that p2  < p1 , show that consumer (present from Date 1) buys the product on Date 1 if and only if v > (1 - δ)一1 (p1  - δp2 ) and buys the product on Date 2 if and only if p2  < v < (1 - δ)一1 (p1  - δp2 ).  (Ignore the cases where v = (1 - δ)一1 (p1  - δp2 ) or v = p2 .)

Assume that consumers who enter the market on Date 2 has the same distribution of

values as those who are present from Date 1. For both groups of consumers, the fraction of

consumers with value at most v is F (v) where F : [0, o) - R is a function assumed to be continuous, continuously differentiable on (0, o) and strictly increasing. Also, F (0) = 0 and limv →o F (v) =  1.  The population sizes of consumers present from Date 1 and of consumers entering on Date 2 are N1  and N2 , respectively.  The result of Part 1 implies

that the demand for the monopoly’s product on Date 1 is

D1 (p1 , p2 )   = 一1 (p1 - δp2 ))),

if p2  < p1 ;

if p2  > p1 .

D2 (p1 , p2 )   = 一),1 (p1 - δp2 )) - F (p2 )) + N2 (1 - F (p2 )),

if p2  < p1 ; if p2 > p1 .

You do not need to prove the expressions of D1  and D2 . The monopoly chooses (p1 , p2 ) to maximize the discounted total profit

s(p1 , p2 ) = (p1 - c)D1 (p1 , p2 ) + δ(p2 - c)D2 (p1 , p2 ),

where c > 0 is a constant marginal cost of production.

2.  [3 marks] (Medium) First, consider the benchmark case where p1  = p2 , in which case the monopoly solves

maxp←R     (N1 + δN2 )(1 - F (p))(p - c),

s.t.      p > 0.

(1)

(2)

Assume that limp→o (1 - F (p))p = 0. Show that the above problem has a solution for every c > 0.

For the rest of the question, assume that the benchmark problem Eqs. (1)-(2) has a unique solution p* .  Now consider the general case where p1  and p2  may be different.  Since D1 and D2  may not be differentiable when p1  = p2 , we use the following strategy for solving the monopoly’s problem: first analyze the case where p2  > p1  by inserting that p2  > p1 as a constraint, then analyze the opposite case by inserting that p2  < p1 as a constraint, and finally compare the two cases. For example, if (hypothetically) the first case yielded optimal price (15, 102) with profit 105 and the second case yielded optimal price (20, 1) with profit 99, we would conclude that the optimal price is (15, 102). (Of course, these numbers are probably wrong.)

3.  [3 marks] (SF) Solve the monopoly’s problem under the assumption that p2  > p1 .

4.  [10 marks] (Challenging) Solve the monopoly’s problem under the assumption that p2  < p1 . Compare with the previous part and determine the monopoly’s optimal pricing policy.

Solution.

1. A consumer buys the product on Date 2 if and only if δ(v - p2 ) > max{0, v - p1 }, which means that p2  < v < (1-δ)一1 (p1 -δp2 ). When p2  > p1 , (1-δ)一1 (p1 -δp2 ) < p2 and thus the range of v for a consumer to buy on Date 2 is essentially empty as we ignore the boundary cases. When p2 < p1 , this range is non-empty. A consumer buys the product on Date 1 if and only if v - p1 > max{0, δ(v - p2 )}, which means that v > p1  when p2  > p1  and v > (1 - δ)一1 (p1 - δp2 ) when p2  < p1 .

2. All functions are continuous.  The value of the objective function is positive when p = c + 1, but is negative when p < c. Therefore, it is never optimal to choose p < c. As p - o, (1 - F (p))(p - c) < (1 - F (p))p, while the latter approaches zero, so (1 - F (p))(p - c) - 0. This shows that all p too high are worse than c + 1. Therefore, the program has a solution.

3. The program becomes

maxp í,pà       N1 (1 - F (p1 ))(p1 - c) + δN2 (1 - F (p2 ))(p2 - c);

s.t.      p1  > 0;

p2  > 0;

p2  > p1 .

The objective function is the sum of a function of p1  with a unique maximum p* and a function of p2  with a unique maximum p* . Therefore, the unique solution of the above program is (p* , p* ).

4. The program becomes

maxp í,pà       N1 (1 - F ((1 - δ)一1 (p1 - δp2 )))(p1 - c) +

+δN1 (F ((1 - δ)一1 (p1 - δp2 )) - F (p2 ))(p2 - c) + δN2 (1 - F (p2 ))(p2 - c); s.t.      p1  > 0;

p2  > 0;

p2  < p1 .

Notice that the first constraint is implied by the second and the third and thus can be ignored.  Let r1  = (1 - δ)一1 (p1  - δp2 ). Then that p2  < p1 is equivalent to that r1 > p2 . Therefore, the above program can be rewritten as follows:

maxrí,pà       N1 (1 - F (r1 ))((1 - δ)r1 + δp2 - c) +

+δN1 (F (r1 ) - F (p2 ))(p2 - c) + δN2 (1 - F (p2 ))(p2 - c); s.t.      p2  > 0;

r1  > p2 .

The objective function can be further rewritten as (1 - δ)N1 (1 - F (r1 ))(r1  - c) + δ(N1  + N2 )(1 - F (p2 ))(p2  - c).  This is the sum of a function of r1  with a unique maximum p* and a function of p2 with a unique maximum p* . Therefore, the unique solution to the new program is r1  = p2  = p* . Now p1  = (1 - δ)r1 + δp2  = p*  when r1  = p2  = p* . Therefore, the second case also yields that p1  = p2  = p* . To sum up, the monopoly’s optimal pricing policy is p1  = p2  = p* .

Remark. This is a classical model in industrial organization showing that a monopoly seller of durable good will not lower her price if she can commit to future prices. In real life, sellers like Apple almost never lower her prices until a new generation is put on sale.

Question 5 [15 marks in total] Consider the econometric problem of estimating an unknown n-dimensional parameter β. The true value β* satisfies a system of m equations:

Aβ *  = b* ,                                                                                                                (3)

where A is an m x n matrix and b*  is an m-dimensional vector. Unfortunately, the true A and b*  are not observed.  Since the main source of error is from error in estimating b* , we assume in this question that A is known for simplicity. The data, consisting of N observations (data points), provide an approximation b to b* . In classical econometrics, b* is a fixed (non-random) vector, while each component of b is treated as a random variable. The expectation of b - b* is 0 and the covariance matrix of ′N(b - b* ) is W . Throughout this question, assume that W is positive definite.

In this question, we consider what happens when we only use part of the system Eq. (3) to estimate β* . More specifically, let A1 be the submatrix of A consisting of its first m1 rows, where m1  < m, and b1 and b 1(*) be the vector consisting of the first m1 components of b and b* , respectively. Intuitively, instead of using all the m equations in Eq. (3), we will try using only the first m1  equations. Let W1  be the covariance matrix of ′N(b1 - b 1(*)), which is the submatrix of W consisting of its first m1  rows and first m1  columns. Throughout this question, assume that the columns of A1  are linearly independent.  In econometric terms, this assumption means that the first m1  equations in Eq. (3) identify β .

1.  [4 marks] (SF) Show that for every positive definite m1 xm1 matrix C1 , the following problem has a unique solution:

min(A1 β - b1 )T C1 (A1 β - b1 ).                                                                          (4)

β←R亢

2.  [4 marks] (SF) Find the unique solution of Eq. (4) and show that it equals β * when b1  is replaced with b 1(*) .

3.  [2 marks] (Medium) Show that W1  is positive definite.

4.  [5 marks] (Challenging) The covariance matrix of the estimator produced by Eq. (4) using the optimal weighting matrix C1  = (W1 )一1  turns out to be N一1/2V1  with V1  = (A1(T)(W1 )一1 A1 )一1 . The covariance matrix of the estimator using all equations in Eq.  (3) and the optimal weighting matrix is N一1/2V2  with V2  = (AT W一1 A)一1 . Show that V1 - V2  is positive definite. Therefore, using only the first m1  equations produces a good estimator (as long as the columns of A1  are linearly independent) but using all equations is strictly better.

Solution.

1. We first show that (A1 )T C1 A1  is a positive definite matrix.  Clearly, the matrix is symmetric.  Fix a w  e Rn  \ {0}.   Since the columns of A1   are linearly inde- pendent, A1w 0.   Therefore, wT (A1(T)C1 A1 )w  =  (A1w)T C1 (A1w)  >  0 as C1   is positive definite. This shows that A1(T)C1 A1  is positive definite. The Hessian of the objective function is 2A1(T)C1 A1 , so the objective function is strictly convex. The gra- dient of the objective function, 2A1(T)C1 b1  - 2A1(T)C1 A1 β, vanishes at a unique point (A1(T)C1 A1 )一1 A1(T)C1 b1 , and thus this is the unique minimum of the objective function.

2. We showed in the previous part that the unique minimum is (A1(T)C1 A1 )一1 A1(T)C1 b1 . When b = b* , b1  = A1 β * , so (A1(T)C1 A1 )一1 A1(T)C1 b1  = β * .

3. The leading principal minors of W1  are the first m1  leading principal minors of W , which are known to be positive.

4. Let be the m x m matrix whose top left m1 x m1 block is (W1 )一1 and other entries (those in the last (m - m1 ) rows and the last (m - m1 ) columns) are zero.  Then (A1(T)W一11 A1 )一1 A1(T)W一11 b1  = (AT A)一1 AT b. Let = A(AT A)一1 . Consider the following optimization problem for every w e Rm \ {0}:

minv←R亢

s.t.

vT Wv

AT v = w.

This program minimizes a strictly convex function on a convex set, so it has a unique minimum. We show in Tutorial 8 that this minimum is D*w = W一1 A(AT W一1 A)一1w . Since for every w e Rm \{0}, v = w satisfies the constraint. The unique optimality D*w implies that

wT T W w > wT (D* )T WD*w, with strict inequality when w D*w.

It is straight forward to verify that T W = V1  and (D* )T WD*  = V2 . The above inequality thus shows that V1  - V2  is positive semidefinite.  Since W一1  and thus D* , there exists a w e Rm \ {0} such that w D*w, and thus above inequality is strict.  (You receive full credit as long as you show that V1  - V2  is positive semidefinite.)

Question 6 [10 marks in total] Let C be an n x n positive definite matrix, v and w be n-dimensional vectors, and r be a positive number.   For x  e Rn , a, b  e R, let u(x, a, b) = aw . x - xT Cx - ra2 + b. Denote the gradient of u with respect to its first argument (x) by ux : ux (x, a, b) = aw - Cx. Consider the following program:

maxx←R亢 ,(a,b)←Rà

s.t.

v . x - aw . x - b;

ux (x, a, b) = 0;

u(x, a, b) > 0.

(5)

(6)

(7)

1.  [5 marks] (Medium) It may appear difficult to establish existence of solution di- rectly, so we first attempt to simplify the program before considering the problem of existence.  Show that Eq.  (7) must be binding at optimality.  Then use Eqs. (6) and (7) to eliminate x and b, thus reducing the program Eqs.  (5)-(7) to an unconstrained program with only one choice variable, a.

2.  [5 marks] (Medium) In the simplified program obtained from the previous part, show that the objective function is strictly concave and solve the program.

Solution.

1. Since b does not appear in ux (x, a, b), without the second constraint the decision maker would send b to -o, violating the second constraint.  Therefore, the sec- ond constraint must be binding.  Now x = aC一1w and b = ra2  - a w2T C一1w . Therefore, the program can be simplified to the following:

max avT C一1 w - 1 a w2T C一1 w - 1 ra2 .

a←R                                      2                          2

2. The objective function is a quadratic function, whose second derivative is -wT C一1 w -

r.   Since  C  is  a  positive  definite  matrix,  C一1   is  also  positive  definite  and thus

wT C一1 w + r  > 0.  Therefore, the program maximizes a strictly concave function.

The derivative of the objective function vanishes at a unique point, , which