Preface

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

2. Special rule for True/False questions.

(a) If you do not respond or write “I’m not sure”, you receive some marks for each question to which you do not respond.

(b) A wrong conclusion without any explanation or with completely wrong expla- nation leads to zero mark.

(c) If you write “true”, “false”, “yes” or “no” without any explanation, you will not receive more marks than not responding.

No-response credit for True/False question:  1 mark for each part of Questions 1 and 2 and Part 3 of Question 5; 2 marks for Part 4 of Question 4 and Part 2 of Question 5 each.

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 = f(x; y; z) 2 R3  : x is an odd number g and f(x; y; z) = x2 + y4 + exp(z) for all (x; y; z) 2 A. (An odd number is an integer that is not divisible by two.)

2.  [5 marks] (SF) A = f(x; y; z) 2 R3  : x + y + z > 0g and f(x; y; z) = (x2 + y2 + z2)1=2 for (x; y; z) 2 A.

3.  [5 marks] (SF) A = f(x; y) 2 R2  : 0 < x < 3; and y > 0g and f(x; y) = y px(3  x) for (x; y) 2 A.

4.  [5 marks] (SF) A = f(x; y; z) 2 R3  : x4+y4+z4  > 0g and f(x; y; z) = log(x4+y4+z4) for (x; y; z) 2 A.

You may find the following theorem useful.

Theorem 1. Let h1 , h2 , ..., hl  be affine functions on Rn  and g1 , ..., gk , gk+1 , ..., gk+m be quasiconvex functions on Rn .   Then the set fx 2 Rn  : hj(x) = 0 for every j; gi(x)  0 for i = 1; :::; k and gt(x) < 0 for t = k + 1; :::; k + mg is a convex set.

Question 2    [15 marks in total] For each of the following optimization problems, de- termine whether it has a solution; if so determine whether the solution is unique.  You do not need to solve any of the problems, even though solving a problem is one way to determine its number of solutions.

1.  [5 marks] (SF)

maxx;y s:t:

x2 + y2

x4 + y  10;

x  2y  0:

maxx;y;z

s:t:

xyz

x2 + 2y2 + 3z2    1;

x2 + 4y2 + 9z2    15:

maxx;y;z

s:t:

y log x  x log y  z  2;

x > 0;

y > 0;

z > 0;

3x + 5y + 8z  103:

Question 3    [15 marks in total] (SF) A software engineer coded a program with two parts but the parts may contain errors (bugs).  He has a total time budget T > 0 to debug (eliminate errors) of his codes.  If he spends time t1  on Part 1 of the program and t2  on Part 2 of the program, the probability that the program works correctly is (1  1 exp(  t1))(1  2 exp(  t2)) where 1; 2  2 (0; 1) are known constants. The engineer chooses (t1; t2) to maximize the probability that the program works correctly.  Find the optimal (t1; t2) for her.

Question  4    [30 marks in total] Optimization has applications in other branches of mathematics.  The statement of the Corollary below does not involve any optimization, but it can be proved using the theory of optimization.  The trace of a square matrix is defined as the sum of its diagonal entries. For a twice continuously differentiable function f defined on an open subset A of an Euclidean space, the trace of its Hessian at x is called the Laplacian of f at x and denoted by f (x). We wish to prove the following theorem and a corollary.

Theorem 2. Let B  Rn  be a closed and bounded set, which contains a non-empty open set A, and f : Rn  ! R be a twice continuously differentiable function.  If f (x)  0 for every x 2 A, then maxx2B f (x) = maxx2BnA f (x) .

Notice that since both B and B nA are non-empty compact sets, both maxima in the theorem are guaranteed to exist.  The theorem says that in order to find the maximum value of f on B, we only need to search within the smaller set B n A. The conclusion of the theorem can also be rephrased as follows: there is no x 2 A such that f (x) > f () for every  2 B n A.

1.  [5 marks] (SF) We begin by proving a result in linear algebra:  if H is a negative semi-definite matrix, then its trace is non-positive.  (This part has nothing to do with Hessians or open sets.)

2.  [5 marks] (Medium) Prove the theorem under the stronger assumption that f (x) > 0 for every x 2 A.  (Hint: every maximum of f on A is a local maximum of f on Rn.)

3.  [5 marks] (Medium) Indicate why the proof does not immediately generalize to the case where f (x) may equal zero for some x 2 A.

4.  [10 marks] (Challenging) Daniel constructed a “proof” of the theorem assuming that the special case (Part 2) has been proved.

Proof.  Suppose that there exists an x  2  A such that  f (x)  >  f () for every   2 B n A. Let b = f (x)  max2BnA f ()  . Define g : Rn  ! R by g(x) = (x1)2 , where x1 is the first component of the vector x. Let c = maxx2B g(x). Clearly, b > 0 and c  0.  Define h : Rn  ! R by h(x) = f (x) + (c + 1)  1bg(x) for every x 2 Rn .

Then h(x) = f (x)+ > 0 for every x 2 A. By the special case of the theorem,

Evaluate the proof.   If the proof is correct,  explain why b is  “clearly” positive and why that h() < h(x) for every  2 B n A is a contradiction.  If the proof is incorrect but the proof strategy is sound, correct any errors to obtain a correct proof. (You still need to explain why b is positive and the aforementioned inequality is a contradiction if they are indeed so.) If the proof strategy is wrong, explain why it is wrong and you do not need to write a new proof from scratch.

5.  [5 marks] (Challenging) In this part, we assume that the theorem has been fully proved. Now prove the following result.

Corollary 3. Let B  Rn  be a closed and bounded set, which contains a non-empty open set A, and f : Rn  ! R be a twice continuously differentiable function such that f(x) = 0 for every x 2 A.  If f(x) = 0 for every x 2 B n A, then f(x) = 0 for every x 2 B .

Question 5    [20 marks in total] In this question, we consider an “economy” with two consumers and one firm. There is a single physical good in the economy; call it “bread” for simplicity.  Consumer i starts with ei    0 units of the good and i  > 0 units of time available for work, for i = 1 and 2. If the consumers spend a total time z working, f(z) units of bread will be produced where f is a known function.  The consumers can trade bread. For example, if Consumer 1 starts with two units of bread and Consumer 2 starts with one unit, it is physically possible for Consumer 1 to consume one unit and Consumer

2 to consume two units without any production; whether Consumer 1 is willing to accept this arrangement is a story for another day. An allocation is a pair (x; z) where x 2 R2 and z 2 R2, where xi  is the units of bread consumed by Consumer i and zi  is the units of time worked by Consumer i. Consumer i’s utility from an allocation (x; z) is ui(xi; zi). We make the following assumptions throughout the question:

• f is twice continuously differentiable, strictly increasing, weakly concave, and f(0) = 0.

• ui  is well-defined on the entire R2, twice continuously differentiable, strictly in- creasing in its first argument (bread) and strictly decreasing in its second argument (working time), and strictly quasiconcave.

To characterize all the Pareto optimal allocations (whose definition is good to know but not needed for this question), we solve the following problem: for any given v 2 R, we seek for all feasible allocations that maximize Consumer 1’s utility subject to the constraint that Consumer 2’s utility is at least v. Daniel formulates the aforementioned problem as follows.

maxx2R2;z2R2

s:t:

u1 (x1; z1);

x1    0;

x2    0;

z1    0;

z2    0;

u2 (x2; z2)  v;

x1 + x2    e1 + e2 + f(z1 + z2);

z1 + z2    1 + 2 :

Jose read this and has two critiques. First, he argues that zi  should be less than or equal to i  for every i, which is a stronger condition than Daniel’s final constraint.  Secondly, he argues that there is no sense of leaving some bread unconsumed, so the second last constraint should be equality.

1.  [5 marks] (Medium) Formulate the correct optimization problem. This can be done by affirming Daniel’s formulation, correcting any mistakes he made or starting from scratch.

2.  [10 marks] (Medium) Does the problem always have a solution?  If so, prove your assertion; if not, find conditions under which the problem has a solution or prove that the problem never has a solution.