Solutions for seminars week 9 and 10

A "true/false" question for seminar 10, that we have actually encountered earlier on:

Claim:  "If f is a concave function and A is a constant matrix, then g(x):=f(Ax) is concave". 

The claim is true, which will be shown below. Note: Generally, a concave transformation of a concave need not be concave (it is if the transformation is also nondecreasing). It is the linearity of Ax that makes it work without nondecreasingness of f.

On to the proof: Fix u and v. Consider g(tu+(1-t)v) = f(A(tu + (1-t)v)). Now, A(tu + (1-t)v) = tAu + (1-t)Av. With a=Au and b=Av, concavity of f yields that this is greater than or equal to tf(a) + (1-t)f(b), which equals tg(u)+(1-t)g(v). So the claim is true.

Exam 2015 problems 1 and 2 for seminar 10: see the solution note in the http://www.uio.no/studier/emner/sv/oekonomi/ECON4140/oldexams/ folder.

Exam 2011 problem 3

See the solution note in the http://www.uio.no/studier/emner/sv/oekonomi/ECON4140/oldexams/ folder. Note in particular that "The constraint qualification fails at the optimum" would be a a full-score answer to the last question; it would not be requested to actually compute the gradients and show that they would be proportional. (In fact, the logic dictates that since there is a solution and it cannot satisfy Kuhn--Tucker, the constraint qualification must fail.)

As far as constraint qualifications go at the exam, this is to my knowledge - though I have not checked all postponed exams! - as far-reaching as it has ever been. 
One seminar question below actually asks to check for it, but I would claim that that if there is anything simple about checking constraint qualifications, that question really is simple.

The "pre-knowledge check" consumption-investment problem.

If you just have a look at what is going on: there is no incentive to leave anything at the table in the last period. Consume everything!

This was from exam 2016. Surprisingly many took this power function, differentiated it, put [something] to a NEGATIVE power = 0; that is impossible, but it did not stop them from putting that "[something]" = 0. That is a nasty mistake even before ECON2200. Don't leave common sense at home when going to exams!

The "Also a previous exam problem, but tweaked a little bit" problem

This was also taken from exam 2016. Problem 1, see that solution. Brief notes: 

1. QUESTION: Show that if  qr=0, then either (0,1,0,0)' or (0,0,1,0)'  is an eigenvector of F, and find the corresponding eigenvalue.
   HOW TO SOLVE: The general tip if one is given a suggested eigenvector to verify, is: multiply out!
   So, multiply out F(0,1,0,0)' and F(0,0,1,0)'  and see that if q=0, then one works and if r=0 then the other works.

2. QUESTION: Show that if qr=ps and nonzero, p+s is an eigenvalue of F, and find a corresponding eigenvector of the form (h,k,m,0)'. 
   HOW TO SOLVE: The general tip if an eigenvalue is given, is to do Gaussian elimination. 
   In this case, it would mean to solve (F - (p+s)I)x=0; but, it would be given that the fourth coordinate is zero. And, posing the equations, one sees that - except in particular cases - the first coordinate must be zero. For the second and third coordinate, the equation system reduces to \((\mathbf B-(p+s)\mathbf I)\begin{pmatrix}k\\\ell\end{pmatrix}=\mathbf 0\). We are given that qr=ps, so the coefficient matrix's determinant ps-qr vanishes as it should; also, because qr=ps is nonzero, we can use the following approach:
    * Since we have a degree of freedom - we must have, in order to get eigenvectors! - one of the eq's is superfluous (both iff the coefficient matrix is null).
    * For a 2x2, we can delete any of the two equations except if precisely one of them is a 0=0 equation; then that must be deleted and the other kept. But in this case, the elements are all nonzero (qr=ps is nonzero, and the elements are -s, q, r, -p).
    * So deleting the second, we are left with -s k + q l = 0. Then (k,l)=(q,s) works. (Variable 1 = coefficient 2; variable 2 = the negative of coefficient 1.)

3. QUESTION: Show that for ? to be an eigenvalue of F, then ? must be an eigenvalue of either A or B (or both). 
   Hint: characteristic polynomials? Product of characteristic polynomials?
   NOTE ON NOTATION: It was called "?" in the seminar problem, but lambda in the exam.
   SOLUTION: Calculating det(F-?I) by cofactor expansion and collect terms, we see that it equals det(A-?I)*det(B-?I). Then point out that ? is an eigenvalue of F iff det(F-?I) = 0 iff det(A-?I)=0 or det(B-?I) = 0 iff ? is an eigenvaule of A or an eigenvalue of B.

4. QUESTION: Must F have a (real!) eigenvalue? What about F'F?
   (Hint: there is a short answer to at least one of these!)
   (This was not in the exam.) SOLUTION: By the information given in the previous question, an eigenvalue of F must be an eigenvalue of either A or B (or both), and these are just general 2x2 matrices. Such ones need not have any real eigenvalue (because second-order polynomials need not have real zeroes). But F'F is a symmetric matrix, and those always have real eigenvalues.

5. QUESTION: When does F have full rank?
   (This was not in the exam.) SOLUTION: Full rank means that the rank is as large as could be for the order of the matrix, namely min{#rows, #columns}. For a square matrix, that means that the determinant is nonzero. Since det(F)=det(A)*det(B) (from 3 above!), we have full rank when both A and B are invertible.

Compendium problem 2-01

For (b), (c) and (d): complete solutions given at the end of the compendium. For (a): Recall the fact that a positive, order q homogeneous, quasiconcave function is concave if q is in (0,1]. Notice also that if q>1, then it behaves "like a strictly convex along the main diagonal" (i.e., f(t1) is strictly convex in t), so that it cannot be concave. Then: 

• A log of a Cobb-Douglas is concave, being the sum of concave logs; take exp(ln(Cobb-Douglas)) and get a quasiconcave.
• For f, then q = the sum of exponents is 0.8, so it is concave.
• For g, then q=2>1. It is quasiconcave, but it is not concave. 
• Nitpickery that you will not be required to do on the exam: strictly speaking, the result requires positive functions, so would not be valid on the axes where f and g are zero. But, just take the limits; recall that concavity could be defined in terms of the sign f(?u+(1-?)v)-?f(u)-(1-?)f(v), and since f is continuous we can let v->axis and maintain the inequality.

Compendium problem 2-02

The function is exp(ax+by²) and the answer depends on b. If b is nonnegative, then the exponent is convex; because the exponential function is convex and increasing, convexity is preserved. When b<0, the exponent is concave. Applying exp (which is increasing) will preseve quasiconcavity. It remains to check concavity. Fix x; as a function of y, we have a bell curve, tending to zero when y tends to positive or negative infinity. So by just looking at what happens along vertical lines in the (x,y) plane, we will have concavity violated.

Compendium problem 2-03, 2-06 and 2-07: see the solutions at the end of the compendium.

Compendium problem 3-05

(a) The Kuhn--Tucker-conditions are given at the end of the compendium. Tip for quick differentiation of functions f>0 which "are products, not sums": then \(\nabla f= f\;\nabla[\ln f]\). In this case: \(\nabla f(x,y)=f(x,y)\; \nabla[2\ln x+\ln y-x-y] \)

(b) To find the points that satisfy them: 

• From the constraints, both x and y are strictly positive, so we can rewrite the first two equations as 
  \(x-2=\frac{e^{x+y}}{xy}(\lambda+\sigma)\) (proving that \(x\geq 2\); therefore, \(\lambda=0\))
  \(y-1 = \frac{e^{x+y}}{x^2}(\mu+\sigma)\)
• From the latter equation, we cannot have y>1 and simultaneously x+y>4. (That would yield positive = zero.) So one of these constraints must be active.
• Case y = 1; then all multipliers must be zero, so x=2, but (2,1) is not admissible. So y>1 and \(?=0\).
• So x+y=4. Eliminating \(\sigma\) and solving out, we get the point given. As it satisfies x>2 and y>1, the multiplier has the right sign.

(c) The constraints are linear, and the objective function is quasiconcave. To verify the latter, apply ln (which is OK, as "everything" is positive) to get 2lnx + ln y - (x+y), a concave function. So the objective is exp(a concave) and therefore quasiconcave. Since the candidate point is not stationary for the objective (one multiplier is nonzero!), then by the quasiconcavity-based sufficient conditions, we have found the solution.

Compendium problem 3-13

The seminar question was: "can part (c) be answered "up-front" without doing (a) or (b)?" Yes, it is a concave program, so if a point is found in (b), it must solve.

The BI core course exam problem for seminar 9: 

• Problem 4 from http://www.dr-eriksen.no/teaching/GRA6035/2011/final-2011-12.pdf 
  At http://www.dr-eriksen.no/teaching/GRA6035/2011/ you find the solution as well. Direct link: http://www.dr-eriksen.no/teaching/GRA6035/2011/final-2011-12-sol.pdf

The "Linear algebra drill" for seminar 9. 

• Let A be square, and let V be a matrix whose columns are eigenvectors of A. 
  Calculating AV then each column is the corresponding column of V except scaled by the eigenvalue. Calculating VD - where D is diagonal and has eigenvalues of A on the main diagonal - yield the same. So they are equal.
• Question: When can we write A = VDV^-1?
  Answer: when it is possible to form an invertible V from eigenvectors of A. That is, when V has n linearly independent eigenvectors (where A is nxn).
• Question: If it is so that we can write  A = VDV^-1: What is then the 2018th power of A, and what could be the advantage of calculating it that way? 
  Natural-number powers of A are then formed as putting VDV^-1 VDV^-1VDV^-1VDV^-1...VDV^-1 and V^-1V is the identity and cancels out. So the answer is VD²⁰¹⁸V^-1.The advantage of doing so, is that high powers of diagonal matrices are easily calculated - just take the power of each element! So we have a dirty job first of finding eigenvectors and inverting the matrix, but when the power is high enough, it will be worth it.
• Question: Explain why it is so that if A is positive semidefinite then for each positive rational p we can write, A = VC^pV^-1 where C is diagonal and has the pth roots of the eigenvalues on the main diagonal - and that  A = (VCV^-1)^p. (There is one C for each p, obviously!) Indeed, it is a fact that VCV^-1 is symmetric too, and positive semidefinite.
  Answer for p=2: This was only done for p=2, so let's take that first.
  * A symmetric matrix A is positive semidefinite iff all its eigenvalues are nonnegative, and so we can take square roots (or any rational power!) of the eigenvalues.
  * Thus that construction can be done; let the ith main diagonal element of C be the square root of the ith main diagonal element of D.
  * Then CC = D and  (VCV^-1)² = VCV^-1VCV^-1 = VC²V^-1 = VDV^-1 = A. 
  Answer for p=k/q rational: Let k and q be natural numbers.
  * Form the diagonal elements of C by raising the corresponding (nonnegative!) diagonal element of D to the power k/q.
  * Then (VCV^-1)^q = VC^qV^-1 and the main diagonal elements of C^q are eigenvalues to the kth power. By the above, that was one way to calculate the matrix power A^k.

The "drill" questions for seminar 10. 

• Question: Given a square matrix A with an eigenvalue ?. Suppose for the moment that ? has two linearly independent eigenvectors u and v. This problem is about finding two orthogonal  (don't remember that term? Look it up!) linearly independent eigenvalues corresponding to ?: Find a t such that the two vectors v and w = u-tv do the job. 
  Answer: The dot product between v and w = u-tv is \(\mathbf {u'v}-t\mathbf{v'v}\)which is zero if \(t=\mathbf{u'v}/\mathbf{v'v}\); the fact that v is an eigenvector and thus nonzero, ensures that we are not dividing by zero. It remains to note that w is an eigenvector with the same eigenvalue. For any t we have A(u-tv) = Au-tAv = ?u-t?v = ?w. In order to be an eigenvector, w must be nonzero; but w is a linear combination of the linearly independent vectors u and v, we could not get zero unless both coefficients 1 and -t were both zero.

Supposing that A is symmetric:

• Question: Show that the eigenvectors corresponding to distinct eigenvalues must be orthogonal.
  Hint: Since A is symmetric, x'Av = v'Ax. If both x and v are eigenvectors and the eigenvalues are distinct, what do you get?
  Answer (this is, btw, an exercise in the books): Denote the eigenvalues by \(?, \lambda\). Then \(\mathbf{x'Av} = \mathbf{x'}\mu\mathbf v\) and \(\mathbf{v'Ax}=\mathbf{v'}\lambda \mathbf x\). So \(?\mathbf{x'v}=\lambda\mathbf{x'v}\) and since the eigenvalues are distinct, then \((\mu-\lambda)\mathbf{x'v}=0\) implies orthogonality.
• Question: Earlier on, we had the exercise to show that the largest and smallest eigenvalue determine the definiteness, through the problem max/min x'Ax subject to x'x=1. When that exercise was assigned, the constraint qualification issue was glossed over. Check that the constraint qualification holds for this problem.
  Answer: The CQ fails if there is linear dependence among gradients corresponding to the active constraints. With one constraint, there is only one gradient, and one vector is linearly dependent iff it is zero, that is, when the "g" function is stationary. In this case, x'x has a stationary point at the origin. But that is not admissible!

The "Math 2 review" question.

Question: Consider the differential equation \(\dot x + ax = f(t)\). For what values of the constant a will the effect of the initial state on the long-run solution vanish? 
Answer: The effect of the initial state is only through the Ce^-at part. Vanishes iff a>0.

The "completely optional" quasiconcavity drill: 

We are given a quasiconcave function f such that f(x+c1) = f(x)+c for any vector x and number c, where 1 is the vector of ones, and shall show concavity. Proceeding as in the hints: 

• Why is f(x-f(x)1)=0? 
  Put c=-f(x). Get f(x)+c which is f(x)-f(x).
• Why is f(t(u-f(u)1)+(1-t)(v-f(v)1) = f(tu+(1-t)v) - tf(u)-(1-t)f(v)? And what do you want to show about this? 
  Just identify the 1 coefficient as - tf(u)-(1-t)f(v). We want to show that the expression is nonnegative - that is concavity.
• If you put x=u-f(u)1 and y = v-f(v)1, what does then quasiconcavity tell you about f(tx+(1-t)y)? 
  Then we have  f(t(u-f(u)1)+(1-t)(v-f(v)1)  =  f(tx+(1-t)y). By quasiconcavity, this is greater than or equal to min{f(x),f(y)}. Inserting, we have min{f(u-f(u)1), f(v-f(v)1) }. But from the first bullet item, both of these are zero.

So from the second bullet item, we have f(tu+(1-t)v) - tf(u)-(1-t)f(v) = f(t(u-f(u)1)+(1-t)(v-f(v)1) which by the third is nonnegative. Done!