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 = {(x, y, z) 2 R3   : x is an odd number } 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 = {(x, y, z) 2 R3  : x + y + z > 0} and f(x, y, z) = (x2 + y2 + z2 )1/2 for (x, y, z) 2 A.

3.  [5 marks] (SF) A = {(x, y) 2 R2  : 0 < x < 3, and y > 0} and f(x, y) = y ^x(3 - x) for (x, y) 2 A.

4.  [5 marks] (SF) A = {(x, y, z) 2 R3  : x4 +y4 +z4  > 0} 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 {x 2 Rn  : hj (x) = 0 for every j, gi (x) ≤ 0 for i = 1, ..., k and gt (x) < 0 for t = k + 1, ..., k + m} is a convex set.

1. The set is not convex: (1, 0, 0) and (3, 0, 0) are in it but (1/2)(1, 0, 0)+(1/2)(3, 0, 0)  A.

2. The set is convex by the theorem. Notice that f (v) = |v| for v 2 A, so

f (tv\ +(1   t)v) = |tv\ +(1   t)v| ≤ |tv\ |+|(1   t)v| = t|v\ |+(1   t)|v| = tf (v\ )+(1   t)f (v),

for all v, v\   2  A and t  2  [0, 1].   Therefore, the function is convex.   (Since the function is twice continuously differentiable in its entire domain, the result can also be obtained by checking its Hessian.)

3. The set is convex by the theorem. The Hessian of the matrix at (x, y) has the form  ) for some continuous functions a and b on A, and b  0.  The determinant of this matrix is negative, so the matrix is indefinite. We conclude that f is neither convex nor concave.

4. Notice that x4  + y4  + z4   is always non-negative and equals zero if and only if x = y = z = 0.  Therefore, A = R3  / {(0, 0, 0)}, which is not a convex set.  For example, (   1, 0, 0) and (1, 0, 0) are both in A, but their middle point is not.

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.

maxx,y s.t.

2.  [5 marks] (SF)

maxx,y,z

s.t.

3.  [5 marks] (SF)

maxx,y,z

s.t.

x2 + y2

x4 + y ≤ 10;

x  2y ≤ 0.

xyz

x2 + 2y2 + 3z2    1;

x2 + 4y2 + 9z2  ≤ 15.

y log x    x log y  z  2;

x > 0;

y > 0;

z > 0;

3x + 5y + 8z ≤ 103.

Solution.  The first program has a unique solution; the second has more than one solution; the third has no solution.

1. Clearly, all functions involved are continuous and (0, 0) satisfies both constraints. Adding twice of the first constraint to the second yields that 2x4  + x ≤ 20.  The left hand side approaches infinity when x !    1 and x ! 1.  Therefore, there exists an M 2 R such that |x| ≤ M in order for 2x4  + x to be at most 20.  We have shown that for any (x, y) satisfying both constraints, |x| ≤ M . It follows that y     M/2. The first constraint clearly implies that y ≤ 10. Therefore, the feasible set is bounded. It follows that the problem has a solution.

Without the second constraint, we would send y to    1, violating the second con- straint. Therefore, x    2y = 0 at optimality. The problem is equivalent to choosing x to maximize x2 + (x/2)2  subject to the constraint that x4 + (x/2) ≤ 10. The left hand side of the constraint is a strictly convex function, so the set of x satisfying the constraint is a bounded and closed interval [   L, H] for some positive L and H . Moreover, it is easy to see that L > H . Now it is obvious that the unique solution to the program is (   L,   L/2).

2. Clearly, all functions involved are continuous and (1; 1; 1) satisfies both constraints. Since the left hand side of the first constraint is a positive definite quadratic form, the set of (x; y; z) satisfying the first constraint is bounded. Therefore, the program has a solution. Notice that the value of the objective function at (1; 1; 1) is positive, so all x, y and z are non-zero at optimality.  For any given solution (x ; y  ; z  ), it is then easy to verify that ( —x  ; —y  ; z  ) is a different solution.  Therefore, the program has more than one solution.

3. Consider the candidates (1; y; 1) for some y < 1; the value of the objective function approaches infinity as y ! 0+, implying that the program has no solution.

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.

Solution. The program is as follows:

maxt1 ,t2

s.t.

(1 — α 1 exp( —t1 ))(1 — α2 exp( —t2 ));

t1    0;

t2    0;

t1 + t2  ≤ T.

Clearly, (0, 0) is feasible, 0 ≤ t1   ≤ T and 0 ≤ t2   ≤ T, so the program has a solution. Without the third constraint, we would send t1  to infinity, violating the third constraint. Therefore, the third constraint must be binding. The program is equivalent to the follow- ing:

maxt1       1 — α 1 exp( —t1 ) — α2 exp( —T + t1 ) + α1 α2 exp( —T);

s.t.     —t1  ≤ 0;

t1 — T ≤ 0.

Denote the objective function in the new program by f . Then f is strictly concave and the feasible set is convex, so the program has a unique solution.  f\ (t1 ) = α 1 exp( —t1 ) — α2 exp( —T + t1 ), which vanishes when t1  = (T + log α1 — log α2 )/2. There are three cases.

Case 1  α 1 /α2  ≤ exp( —T). In this case f is strictly decreasing on [0, T], so is maximized at t1  = 0. The solution to the original program is (0, T) in this case.

Case 2 exp( —T)  <  α 1 /α2   <  exp(T).   In this case f  is maximized at (T + log α 1  — log α2 )/2  2  (0, T),  and the solution to the original program is  ((T + log α 1  — log α2 )/2, (T — log α1 + log α2 )/2).

Case 3  α 1 /α2    exp(T). In this case f is strictly increasing on [0, T] so is maximized at t1  = T. The solution to the original program is (T, 0) in this case.

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) = maxx2B/A f (x) .

Notice that since both B and B / A 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 / 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 / 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 / A. Let b = f (x* )  (max2B/A 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,

maxx2B h(x) = maxx2B/A h(x).  However, h() ≤ f () + b < f (x* ) ≤ h(x* ) for

Evaluate the proof.   If the proof is correct, explain why b is “clearly” positive and why that h() < h(x* ) for every  2 B / 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 / A, then f(x) = 0 for every x 2 B .

Solution.

1. Let H be an m  m negative semi-definite matrix and ej be the m-dimensional vector whose jth entry is one and other entries are zero, for j = 1, 2, ..., m. It is easy to verify that ej(T)Hej is the jth diagonal entry of H , and is thus non-positive. Therefore, every diagonal entry of H is non-positive and thus their sum is non-positive too.

2. Suppose that the theorem is not true. Then there exists an x  2 A the maximizes f on B . Then x  is a local maximum of f, and the second-order condition implies that the Hessian of f at x  is negative semi-definite.  By Part 1, this means that f(x ) ≤ 0, contradicting the assumption.

3. It is possible that the Hessian of f is the zero matrix at some x 2 A and we cannot immediately rule out the possibility that this x is a local maximum of f .

4. The proof is correct.   Since B / A is non-empty and compact,  (max2B/A f()) is well-defined, and it is less than f(x ) by assumption.  The special case of the theorem applies to h, so max北2B h(x) = max北2B/A h(x), and thus an x  2 A with h(x ) > h() for every  2 B / A cannot exist.

5. The theorem implies that f(x) ≤ 0 for every x 2 A. Notice that (   f)(x) = 0 for every x 2 A, so the theorem implies that    f(x) ≤ 0 for every x 2 A.  Combining the two results yields the desired conclusion.

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.

3.  [5 marks] (Challenging) Can the problem have more than one solutions? If so, give a concrete example of (u1 , u2 , f, e1 , e2 , 1 , 2 , v) for which the problem has at least two solutions; otherwise, prove that the problem has at most one solution.  (You automatically receive full credit for this part if you prove in the previous part that the correctly formulated problem never has a solution.)

1. Jose’s first critique is right: Consumer i cannot work for more than time i . His sec- ond critique is not technically wrong, but we will see that leaving it as an inequality constraint facilitates the analysis later.

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  ≤ 1 ;

z2  ≤ 2 .