Mathematical methods for economic theory

Martin J. Osborne
Previous section Previous page Contents Text Exercises Search Next page Next section

7.4 Exercises on optimization with inequality constraints: nonnegativity conditions

  1. Solve the problem
    maxx,yx2y2 subject to 2x + y ≤ 2, x ≥ 0, and y ≥ 0.
    [You may use without proof the fact that x2y2 is quasiconcave for x ≥ 0 and y ≥ 0.]

    Solution

    The constraints are concave, so the KT conditions are necessary. The objective function is quasiconcave, and the constraint is quasiconvex. So if ∇f(x*, y*) ≠ (0, ..., 0) and (x*, y*, λ*) satisfies the KT conditions, then (x*, y*) is a solution of the problem.

    Let M(x, y) = x2y2 − λ(2x + y − 2). The KT conditions are

    2xy2 − 2λ ≤ 0, x ≥ 0, and x[2xy2 − 2λ]  =  0
    2x2y − λ ≤ 0, y ≥ 0, and y[2x2y − λ]  =  0
    λ ≥ 0, 2x + y ≤ 2, and λ(2x + y − 2)  =  0
    Consider each possibility for the solutions of the first two sets of conditions:
    • x = 0, y = 0: in this case we need λ = 0 from the third set of conditions
    • x = 0, y > 0: from the second set of conditions we have λ = 0.
    • x > 0, y = 0: from the first set of conditions we have λ = 0
    • x > 0, y > 0: from the first two sets of conditions we have xy2 = λ and 2x2y = λ, so that 2x = y and λ > 0. From the third set of conditions we thus have y = 1, and hence x = 1/2.
    The value of the objective function at solutions in the first three cases is 0, and the value in the last case is 1/4. Thus the solution of the problem is (x, y) = (1/2, 1).
  2. Consider the problem
    maxxf(x) subject to gj(x) ≤ cj for j = 1, ..., m and xi ≥ 0 for i = 1, ..., n.
    1. Write down the Kuhn-Tucker conditions for this problem when it is written in the form
      maxxf(x) subject to gj(x) ≤ cj for j = 1, ..., m+n
      where gm+i(x) = −xi for i = 1, ..., n. (Write the derivative of the Lagrangean explicitly in terms of the derivatives of f and gj for j = 1, ..., m, using the notation (∂gj/∂xi)(x) for the derivative of gj with respect to xi at x. Denote the Lagrange multiplier associated with the constraint gk(x) ≤ cj by λj for j = 1, ..., m and the multiplier associated with the constraint gm+i(x) ≤ 0 by λm+i for i = 1, ..., n.)
    2. Write down the Kuhn-Tucker conditions tailored to problems with nonnegativity constraints.
    3. Show that if (x, (λ1, ..., λm+n)) satisfies the conditions in (a) then (x, (λ1, ..., λm)) satisfies the conditions in (b), and if (x, (λ1, ..., λm)) satisfies the conditions in (b) then there exist numbers λm+1, ..., λm+n such that (x, (λ1, ..., λm+n)) satisfies the conditions in (a).

    Solution

    1. The Kuhn-Tucker conditions are
      f'i(x) − ∑m
      j=1      λj(∂gj/∂xi)(x) + λm+i = 0 for i       		 = 1, ..., n
      λj ≥ 0, gj(x) ≤ cj, λj[gj(x) − cj] = 0 for j  = 1, ..., m
      λm+i ≥ 0, xi ≥ 0, λm+ixi = 0 for i  = 1, ..., n.
    2. The Kuhn-Tucker conditions are
      f'i(x) − ∑m
      j=1       λj(∂gj/∂xi)(x) ≤ 0, xi ≥ 0, xi·[f'i(x) − ∑m
      j=1      λj(∂gj/∂xi)(x)] = 0 for i       		 = 1,...,n
      λj ≥ 0, gj(x) ≤ cj, and λj·[cj − gj(x)] = 0 for j  = 1,...,m.
    3. First suppose that (x, (λ1, ..., λm+n)) satisfies the conditions in (a). Then since λj ≥ 0 for all j we have
      f'i(x) − ∑m
      j=1       λj(∂gj/∂xi)(x) ≤ 0
      from the first condition. Further, if xi > 0 then by the last condition we have λm+i = 0, so that from the first condition we have
      f'i(x) − ∑m
      j=1      λj(∂gj/∂xi)(x) = 0.
      Hence we have
      xi·[f'i(x) − ∑m
      j=1      λj(∂gj/∂xi)(x)] = 0.
      Thus the conditions in (b) are satisfied.

      Now suppose that (x, (λ1, ..., λm)) satisfies the conditions in (b). Define

      λm+i = −[f'i(x) − ∑m
      j=1      λj(∂gj/∂xi)(x)] for all i = 1, ..., n.
      By the second condition in (b) we have xi = 0 if λm+i > 0, so λm+ixi = 0 for all i. Hence (x, (λ1, ..., λm+n)) satisfies the conditions in (a).
  3. Consider the following problem.
    maxx−(x1−c1)2 − (x2 − c2)2 subject to (x1 + 1)2 + x2
    2     ≤ 4, x1 ≥ 0, and x2 ≥ 0,
    where c1 and c2 are constants.
    1. Are the Kuhn-Tucker conditions necessary for a solution of this problem?
    2. Are the Kuhn-Tucker conditions sufficient for a solution of this problem?
    3. If possible, use the Kuhn-Tucker conditions to find the solution(s) of the problem for c1 = −1 and c2 = 3.
    4. If possible, use the Kuhn-Tucker conditions to find the solution(s) of the problem for c1 = c2 = 0.
    5. If possible, use the Kuhn-Tucker conditions to find the solution(s) of the problem for c1 = 2 and c2 = 0.

    Solution

    1. The function g1 is convex; the remaining two constraints are also convex (and concave). Finally, there exists a point that satisfies all the constraints strictly (e.g. (1/2, 1/2)). Thus the Kuhn-Tucker conditions are necessary for a solution to the problem.
    2. Since f is concave and each gj is convex, the Kuhn-Tucker conditions are sufficient for a solution of the problem.
    3. The Lagrangean is
      M(x1, x2) = −(x1−c1)2 − (x2 − c2)2 − λ[(x1 + 1)2 + x2
      2       − 4].
      The Kuhn-Tucker conditions are
      −2(x1 + 1) − 2λ(x1 + 1)  ≤ 0, x1 ≥ 0, and x1·[−2(x1 + 1) − 2λ(x1 + 1)] = 0
      −2(x2 − 3) − 2λx2  ≤ 0, x2 ≥ 0, and x2·[−2(x2 − 3) − 2λx2] = 0
      (x1 + 1)2 + x2
      2             		 ≤ 4, λ ≥ 0, and λ·[4 − (x1 + 1)2 − x2
      2      ] = 0
      The unique solution of these conditions is x1 = 0, x2 = √3, λ = √3 − 1. Thus a solution of the problem (in fact the only solution, as one can see from a diagram) is (x1, x2) = (0, √3).
    4. In this case the unique solution of the Kuhn-Tucker conditions has (x1, x2) = (0, 0), so this is a solution of the problem. (λ is zero in this case.)
    5. In this case the unique solution of the Kuhn-Tucker conditions has (x1, x2) = (1, 0), so this is a solution of the problem. (λ is positive in this case.)
  4. Let u be a quasiconcave, increasing function of n variables. (Increasing means u'i(x) > 0 for all i.) Let w > 0 be a number and let p = (p1, ..., pn) be a vector with pi > 0 for all i. Consider the problem
    maxxu(x) subject to ∑n
    i=1    pixi ≤ w and x ≥ 0.
    1. Write down the Kuhn-Tucker conditions for this problem.
    2. Suppose that x* solves the problem. Is there necessarily a value of λ* such that (x*,λ*) satisfies the Kuhn-Tucker conditions?
    3. Suppose that (x*,λ*) satisfies the Kuhn-Tucker conditions. Does x* necessarily solve the problem?
    4. Suppose that x* solves the problem. What can you say about the relationship between pi/pj and the value of u'i(x*)/u'j(x*) when
      1. x*i > 0 and x*j > 0?
      2. x*i = 0 and x*j > 0?
      3. x*i = 0 and x*j = 0?

    Solution

    1. The Kuhn-Tucker conditions are
      u'i(x*) − λ*pi  ≤ 0, x*i ≥ 0, and xi·(u'i(x*) − λ*pi) = 0, i = 1,...,n
      ∑n
      i=1      pix*i ≤ w       		 ≤ 0, λ* ≥ 0, and λ*·(w − ∑n
      i=1      pix*i) = 0

    2. The constraint function is linear, hence concave. Thus if x* solves the problem then there is a number λ* such that (x*, λ*) solves the Kuhn-Tucker conditions.
    3. The objective function is quasiconcave and increasing (so that there is no point at which ∇u(x) = (0,...,0)) and the constraint function is linear, hence quasiconvex. Thus if (x*, λ*) satisfies the Kuhn-Tucker conditions then x* solves the problem.
      1. If x*i > 0 and x*j > 0 then from the Kuhn-Tucker conditions we have
        u'i(x*)/u'j(x*) = pi/pj.
      2. If x*i = 0 and x*j > 0 then from the Kuhn-Tucker conditions we have u'i(x*) ≤ λ*pi and u'j(x*) = λ*pj, so
        u'i(x*)/u'j(x*) ≤ pi/pj.
      3. If x*i = 0 and x*j = 0 then from the Kuhn-Tucker conditions we have u'i(x*) ≤ λ*pi and u'j(x*) ≤ λ*pj, so we can say nothing about the relationship of the ratio of the partials of u and pi/pj.
  5. Consider the problem
    maxx,y3x + y subject to (x + 1)2 + (y + 1)2 ≤ 5, x ≥ 0, and y ≥ 0.
    1. Suppose that (x*, y*) solves this problem. Is there necessarily a value of λ* such that (x*, y*, λ*) satisfies the Kuhn-Tucker conditions?
    2. Now suppose that (x*, y*, λ*) satisfies the Kuhn-Tucker conditions. Does (x*, y*) necessarily solve the problem?
    3. Given the information in your answers to (a) and (b), use the Kuhn-Tucker method to solve the problem. (You may use a graph to get some idea of what the solution might be; but use the Kuhn-Tucker conditions to find the solution exactly and justify it.)

    Solution

    1. The constraint function is convex (its Hessian is
      left parenthesis 2 0 right parenthesis
      0 2
      		)
      and there exists (x, y) ≥ (0, 0) such that g(x, y) < c, so the Kuhn-Tucker conditions are necessary.
    2. The objective function is concave and the constraint function is convex, so the Kuhn-Tucker conditions are sufficient.
    3. The Kuhn-Tucker conditions are
      3 − 2(x + 1)λ ≤ 0, with equality if x > 0
      1 − 2(y + 1)λ ≤ 0, with equality if y > 0
      (x + 1)2 + (y + 1)2 ≤ 5 and λ(5 − (x + 1)2 − (y + 1)2) = 0
      The unique solution of these conditions is (x,y,λ) = (1, 0, 3/4). Thus (x, y) = (1, 0) is the solution of the problem.
  6. A firm produces in each of n periods. In any period i its output is xi and the price of output is pi (which is fixed, but varies between periods). If it chooses the capacity k, then its output in each period is at most k. The cost of maintaining the capacity k is D(k), where D is convex, and the cost of producing the vector of outputs x = (x1, ..., xn) is C(x), where C is convex. Thus the firm's problem is
    maxx,k(∑n
    i=1    pixi − C(x1, ..., xn) − D(k)) subject to 0 ≤ xi ≤ k for i = 1, ..., n.
    (Note that the firm chooses both the vector x and the number k, and that one constraint is k ≥ 0.)
    1. Write down the Kuhn-Tucker conditions (either variety) for this problem.
    2. What is the relation between the solutions of the Kuhn-Tucker conditions and the solutions of the problem? (You may use the result in a previous problem.)
    3. Consider the case in which C(x1, x2) = x2
      1       + x2
      2      , D(k) = k2 (both of which are convex), p1 = 1, and p2 = 3.

      Is there a solution in which x1 = x2 = k > 0?

      Is there a solution in which 0 < x1 < k = x2?

    Solution

    1. You write the Lagrangean either as
      M(x,k) = ∑n
      i=1      pixi − C(x1, ..., xn) − D(k) − ∑n
      i=1      λi(xi − k),
      in which case the Kuhn-Tucker conditions are
      pi − C'i(x1, ..., xn) − λi ≤ 0, xi ≥ 0, and
            xi(pi − C'i(x1, ..., xn) − λi) = 0 for i = 1,...,n
      −D'(k) + ∑n
      i=1      λi ≤ 0, k ≥ 0, and k(−D'(k) + ∑n
      i=1      λi) = 0
      λi ≥ 0, xi ≤ k, and λi(xi − k) = 0 for i = 1,...,n
      or as
      L(x,k) = ∑n
      i=1      pixi − C(x1, ..., xn) − D(k) − ∑n
      i=1      λi(xi − k) − ∑n
      i=1      μixi − ηk,
      in which case the Kuhn-Tucker conditions are
      pi − C'i(x1, ..., xn) − λi − μi = 0
      −D'(k) + ∑n
      i=1      λi − η = 0
      λi ≥ 0, μi ≥ 0, η ≥ 0 for i = 1,...,n
      λi(xi − k) = 0, μixi = 0, and ηk = 0 for i = 1,...,n
    2. Each constraint function is concave, so the Kuhn-Tucker conditions are necessary. Each constraint function is convex and the objective function is concave (by the result of question 2), so the Kuhn-Tucker conditions are sufficient. That is, (x*, k*) solves the problem if and only if there exist λ1, ..., λn such that ((x*, k*), λ1, ..., λn) solves the Kuhn-Tucker conditions.
    3. If x1 = x2 = k > 0 then from the Kuhn-Tucker conditions we have
      1 − 2k − λ1  = 0
      3 − 2k − λ2  = 0
      −2k + λ1 + λ2  = 0.
      From the third equation we have −2k = −λ1 − λ2, so the first two equations are
      1 − 2λ1 − λ2  = 0
      3 − λ1 − 2λ2  = 0
      which imply that 3λ1 = −1, contradicting λ1 ≥ 0. Thus there is no solution in which x1 = x2 = k > 0.

      If 0 < x1 < k = x2 then from the Kuhn-Tucker conditions we have λ1 = 0 and

      1 − 2x1  = 0
      3 − 2k − λ2  = 0
      −2k + λ2  = 0.
      From the first equation we have x1 = 1/2. From the second and third equations we have k = 3/4 and λ2 = 3/2. Since λ2 ≥ 0, these values satisfy all the conditions. Thus a solution to the problem is (x1, x2, k) = (1/2, 3/4, 3/4).
  7. Consider the problem
    maxx1,x2f(x1, x2) subject to p1x1 + p2x2 ≤ c, x1 ≥ 0, and x2 ≥ 0,
    where the function f is differentiable and quasiconcave, pi > 0 for i = 1, 2, and c > 0.
    1. Write down the Kuhn-Tucker conditions (either variety) for (x*1, x*2) to solve this problem.
    2. If (x*1, x*2) solves the problem does it necessarily satisfy the Kuhn-Tucker conditions?
    3. If (x*1, x*2) satisfies the Kuhn-Tucker conditions and the constraint does it necessarily solve the problem?
    4. Let (x*1(p1, p2,c), x*2(p1, p2,c)) be the solution of the problem, as a function of the parameters; assume that at this solution the values of xi* are both positive and the constraint is satisfied with equality. Let the value of the Lagrange multiplier be λ*(p1, p2, c). Define the function f* by F(p1, p2, c) = f(x*1(p1, p2, c), x*2(p1, p2, c)). Use the envelope theorem to find F'1(p1, p2,c) in terms of the parameters and functions of these parameters.
    5. For f(x1, x2) = x1x2
      2      , which is quasiconcave (you do not need to show this), find the solution of the problem.

    Solution

    1. The Kuhn-Tucker conditions are
      f'i(x*) − λ*pi  ≤ 0, xi* ≥ 0, and xi·(f'i(x*) − λ*pi) = 0, i = 1,2
      p1x*1 + p2x*2  ≤ c, λ* ≥ 0, and λ*·(c − (p1x*1 + p2x*2)) = 0
      Or, alternatively,
      f'i(x*) − λ*pi + μ*i  = 0, i = 1,2
      μ*i ≥ 0, x*i  ≥ 0, and μ*ix*i = 0 for i = 1, 2
      p1x*1 + p2x*2  ≤ c, λ* ≥ 0, and λ*·(p1x*1 + p2x*2 − c) = 0
    2. Each constraint function is concave (in fact, linear), so the Kuhn-Tucker conditions are necessary.
    3. The objective function is quasiconcave and each constraint function is quasiconvex, so if ∇f(x*) ≠ (0,0) and (x*1, x*2) satisfies the Kuhn-Tucker conditions then x* solves the problem.
    4. By the envelope theorem, F'1(p1, p2,c) is the partial derivative of the Lagrangean with respect to p1 evaluated at (x*1, x*2,λ*). Thus F'1(p1, p2,c) = −λ*(p1, p2,c)x*1(p1, p2,c).
    5. In this case the Kuhn-Tucker conditions are
      x2
      2       − λp1       		 ≤ 0, x1 ≥ 0, and x1·(x2
      2       − λp1) = 0
      2x1x2 − λp2  ≤ 0, x2 ≥ 0, and x2·(2x1x2 − λp2) = 0
      p1x1 + p2x2  ≤ c, λ ≥ 0, and λ·(p1x1 + p2x2 − c) = 0

      If λ = 0 then from the first condition we have x2 = 0. But ∇f(x1, x2) = (x2
      2      ,2x1x2), which is (0,0) for x2 = 0. Thus there is no solution of this type.

      If λ > 0 then p1x1 + p2x2 = c. If x2 = 0 then ∇f(x1, x2) = (0,0), as above. If x1 = 0 then x2 = 0 by the second set of conditions. Thus x1 > 0 and x2 > 0, so that by the first two conditions we have x2
      2       = λp1 and 2x1x2 = λp2, so that x2
      2      /p1 = 2x1x2/p2, or p2x2 = 2p1x1. Substituting into the constraint p1x1 + p2x2 = c we get x1 = c/(3p1), x2 = 2c/(3p2), and λ = 4c2/(9p1p2
      2      ).

      Thus the solution of the problem is (x1, x2) = (c/(3p1), 2c/(3p2)).