Concave Programming

Lecture notes based on
Foundations of Mathematical Economics
c 2001 Michael Carter
All rights reserved
Concave programming
1 Introduction
Concave programming is another special case of the general constrained optimization problem
max (x)
x
subject to g(x) 0
in which the objective function is concave and the constraint functions
are convex. For such problems, an alternative derivation of the Kuhn-Tucker
conditions is possible, providing yet another perspective on the Lagrangean
method.
2 Derivation
Consider the family of optimization problems
max (x)
x
subject to g(x) c
where the parameter c measures the available resources. The value function
(c) = max{ (x) : (x) c }
x
summarizes what can be achieved with dierent amounts of resource c. The

set of attainable outcomes is given by its hypograph
= { (c, ) : (c) }
Since v is concave (Theorem 3.1), its hypograph is convex (Exercise 3.125).
Let = (0) and dene
= { (c, ) : c 0, }
is convex, and its interior is nonempty and disjoint from .
All rights reserved

(c)
There exists a hyperplane separating and (Corollary 3.2.1), the equation

of which is
= + c
or
c =
(1)
with
= 0 c for every (c, )
(2)
That is, (0, ) maximizes the linear functional c on . By denition,

for every (c, ) , there exists some x such that (x) = and
(x) c. Let x be such that (x) 0 and (x ) = . Substituting in (2)
(x ) (x) (x) for every x
The right-hand side of this inequality is precisely the Lagrangean of the
constrained optimization problem. At the optimal solution (0, ), the Lagrangean is maximized over . In particular, x and therefore
(x ) (x ) (x )
which implies that (x ) 0. But 0 (Exercise 1) and g(x ) 0, and
therefore we must have
(x ) = 0 for every = 1, 2, . . .
2.1 Concave programming theorem 5.6
for
Suppose that is concave and are convex and there exists an x
which g(
x) < 0. Then x is a global solution of
max (x) subject to g(x) 0
if and only if there exist multipliers

= (1 , 2 , . . . , ) 0 such that the
Lagrangean (x, ) = (x) (x) is maximized on and (x ) = 0

for every .
2
All rights reserved

3 Net benet approach

An economic approach to constrained maximization would be to assign a
price to each constraint and maximize the net benet
(x, ) = (x)
(x)
where (x) measures the resources used and the (x) the total benet attained. If is concave and convex, the Lagrangean is concave, and the
Kuhn-Tucker conditions identify those policies which maximize the net benet. This is the fundamental economic insight of the Lagrangean method.
Example An electricity company operates generating plants. At each
plant , it costs ( ) to produce units of electricity. If the company aims
to meet electricity demand at minimum cost, its optimization problem is
min
( ) subject to
=
x
=1
=1
The Lagrangean is
(, ) =
=1
( )
=1
(
( ) +
=1
(3)
=1
Suppose that the company has the option of purchasing electricity from outside suppliers at a price . Then, the Lagrangean (3) represents the sum of
the costs of producing electricity at its own plants and purchasing electricity
from outside. For any arbitrary price , the company will choose an optimal
mix of its own production and outside purchase to minimize the total costs.
The rst-order conditions for a minimum of (3) are
= = 0
(4)
Optimality requires that the company utilize each plant to the level at which
its marginal cost is equal to the alternative price . As the price increases, the
proportion of demand which it satises from its own resources will increase.
At some price , the company will be induced to ll total demand from
its own production. This is the shadow price which arises from the solution
of (4) together with the constraint
=1
and is the marginal cost of producing the total demand from its own
plants.
3
All rights reserved

4 Summary of necessary and sucient conditions

Necessary
Sucient
x0
Unconstrained
= 0
0, x = 0
pseudoconcave
Equality constraints
= 0
0, x = 0
pseudoconcave
g(x) = 0
Inequality constraints
g(x) 0
Concave programming
quasiconvex
= 0
0, x = 0
pseudoconcave
0, g(x ) = 0
0, g(x ) = 0
quasiconvex
max
max
concave
convex
5 Homework
1. In general, the equation of the separating hyperplane in (1) is
c =
Show that 0 and 0. [Hint: Consider the point (0, +1) .
]
2. The constraints g satises the Slater constraint qualication condition
with (
if there exist x
x) < 0. Show that this implies that > 0.
Therefore, without loss of generality, we can set = 1 as in (1) (see
Remark 5.8).
3. Show how the shadow price can be used to decentralize the running of
the power company, leaving the production level at each plant to be
determined locally.
4. (Pareto optimality) Suppose that there are agents each of which has
preferences over a set . The preferences of agent can be presented
by the concave function : . A choice is Pareto
optimal if it impossible to make any agent better o without making
another agent worse o. Show that is Pareto optimal if and only
All rights reserved

if it maximizes a weighted average of the individual utility functions,

that is
()
arg max
=1
for some weights 1 , 2 , . . . , .

5. (Peak load pricing) Suppose a public utility supplies a service, the
demand for which varies with the time of day. For simplicity, assume
that demand in each period is independent of the price in other periods.
The inverse demand function for each period is ( ). Assume that
marginal production costs are constant, independent of capacity and
independent across periods. Further assume that the marginal cost of
capacity 0 is constant. With these assumptions, the total cost function
is
+ 0
(, ) =
=1
The objective is to determine outputs (and hence prices ) and

production capacity to maximize social welfare, as measured by total
consumer and producer surplus.
In any period , total surplus is measured by the area between the
demand and cost curves, that is

( ( ) )
(, ) =
0
and so total surplus is

(, ) =
=1
( ( ) ) 0
(5)
The optimization problem is to choose nonnegative and so as to

maximize (5) subject to the constraints

= 1, 2, . . . ,
Show that it is optimal to price at marginal cost during o-peak periods,

and extract a premium during peak periods, where the total premium
is equal to the marginal cost of capacity 0 . Furthermore, under this
pricing rule, the enterprise will break even. Note that

( ( ) ) = ( )
(, ) =
0
All rights reserved

Solutions 6
1 The point (0, + 1) belongs to , and therefore
( + 1) 0 = 0
which implies that 0. Similarly, let { e1 , e2 , . . . , e } denote the standard
basis for (Example 1.79). For any = 1, 2, . . . , , the point (0 e , )
(which corresponds to decreasing resource by one unit) belongs to and
therefore (from (75))
(0 e ) = + 0 =
which implies that 0.
2 Let
c = g(
x) < 0 and = (
x)
Suppose = 0. Then, at least one component of must be nonzero. That

is, 0 and therefore
< 0
(1)
But (c, ) and (2) implies
c 0
and therefore = 0 implies
contradicting (1). Therefore, we conclude that > 0.

3 The Lagrangean
(x, ) =
(
( ) +
=1
(2)
=1
can be rewritten as
(x, ) =
)
( ) +
(3)
=1
The th term in the sum is the net prot of plant if its output is valued at
. Therefore, if the company undertakes to buy electricity from its plants at
the price and instructs each plant manager to produce so as to maximize
the plants net prot, each manager will be induced to choose an output
1
All rights reserved

level which maximizes the prot of the company as a whole. This is the
case whether the price is the market price at which the company can buy
electricity from external suppliers or the shadow price determined by the
need to satisfy the total demand . In this way, the shadow price can be
used to decentralize the production decision.
4 is Pareto optimal if and only if it solves the problem
max 1 ()
subject to () ( )
= 2, 3, . . . ,
which can be written in standard form as

max 1 ()
subject to () = ( ) () 0
= 2, 3, . . . ,
Since is concave, is convex for every . Assuming the qualication condition is satised (see below), the problem satises the conditions of the concave programming theorem (Theorem 5.6). Therefore, is Pareto optimal
if and only if there
exist multipliers 2 , 3 , . . . , such that the Lagrangean
(, ) = () =2 () is maximized on , that is
(
(
)
)
( , ) = 1 ( )
( ) ( ) 1()
( ) () = (, )
=2
=2
for every which implies that
1 ( ) +
( ) 1 () +
=2
() for every
=2
Letting 1 = 1 gives the desired result.

The constraint qualication condition requires that there exists such
that
(
) < 0 or (
) > ( ) for every = 2, 3, . . . ,
Suppose this is satised for only a subset of agents. Without loss of generality,
suppose that there exists such that
) < 0 or (
) > ( ) for every = 2, 3, . . . , <
(
If is Pareto optimal with respect to agents 1, 2, . . . , , it solves the problem
max 1 ()
subject to () ( )
2
= 2, 3, . . . ,
All rights reserved

which can be written in standard form as
max 1 ()
subject to () = ( ) () 0
= 2, 3, . . . ,
This problem satises the conditions of the concave programming theorem

(Theorem 5.6), including the constraint qualication condition. Therefore,
there exist
multipliers 2 , 3 , . . . , such that the Lagrangean (, ) =
() =2 () is maximized on , that is
(
(
)
)
( , ) = 1 ( )
( ) ( ) 1()
( ) () = (, )
=2
=2
for every which implies that
1 ( ) +
( ) 1 () +
=2
() for every
=2
Letting 1 = 1 and = 0 for every > gives the desired result, namely
arg max
()
(4)
=1
Conversely, suppose satises (4) for some weights 1 , 2 , . . . , . Assume

to the contrary that is not Pareto optimal. That is, there exists
such that
() ( ) for every = 1, 2, . . . ,
with
and () > ( ) for at least one
Adding, this implies that
() >
=1
=1
contradicting (4).
( )
All rights reserved

5 The utilitys optimization problem is

max (, ) =
( ( ) ) 0
, 0
=1
subject to (y, ) = 0
= 1, 2, . . . ,
The demand independence assumption ensures that the objective function

is concave, since its Hessian
0 0
1 0 . . .
0
2 . . . 0 0
=
0
. . . 0
0
...
0 0
is nonpositive denite (Exercise 3.96). The constraints are linear and hence
convex. Moreover, there exists a point (0, 1) such that for every = 1, 2, . . . ,
(0, 1) = 0 1 < 0
Therefore the problem satises the conditions of Theorem 5.6. The optimal
solution (y , ) satises the Kuhn-Tucker conditions, that is there exist
multipliers 1 , 2 , . . . , such that for every period = 1, 2, . . . ,
= ( ) 0

0
0
( ( ) ) = 0
( ) = 0
(5)
and that capacity be chosen such that

= 0
(
0
=1
=0
(6)
=1
where is the Lagrangean

(, , ) =
=1
( ( ) ) 0
( )
=1
In o-peak periods ( < ), complementary slackness requires that = 0

and therefore from (5)
( ) =
assuming > 0. In peak periods ( = )
( ) = +
4
All rights reserved

We conclude that it is optimal to price at marginal cost in o-peak periods

and charge a premium during peak periods. Furthermore, (6) implies that
the total premium is equal to the marginal capacity cost
= 0
=1
Furthermore, note that
=1
Peak
=
=
O-peak
=0

= 0
=1
Therefore, the utilitys total revenue is

(, ) =
( )
=1
=
=
=
=1
=1
( + )
+
=1
+ 0 = (, )
=1
Under the optimal pricing policy, revenue equals cost and the utility breaks
even.

Concave Programming

Uploaded by

Copyright:

Available Formats

Concave Programming

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Concave Programming

Uploaded by

Copyright:

Available Formats

Lecture notes based on

Foundations of Mathematical Economics

c 2001 Michael Carter

All rights reserved

summarizes what can be achieved with dierent amounts of resource c. The

c 2001 Michael Carter

All rights reserved

Lecture notes based on

There exists a hyperplane separating and (Corollary 3.2.1), the equation

= 0 c for every (c, )

That is, (0, ) maximizes the linear functional c on . By denition,

if and only if there exist multipliers

Lagrangean (x, ) = (x) (x) is maximized on and (x ) = 0

c 2001 Michael Carter

All rights reserved

Lecture notes based on

3 Net benet approach

c 2001 Michael Carter

All rights reserved

Lecture notes based on

4 Summary of necessary and sucient conditions

c 2001 Michael Carter

All rights reserved

Lecture notes based on

if it maximizes a weighted average of the individual utility functions,

for some weights 1 , 2 , . . . , .

The objective is to determine outputs (and hence prices ) and

and so total surplus is

The optimization problem is to choose nonnegative and so as to

Show that it is optimal to price at marginal cost during o-peak periods,

c 2001 Michael Carter

All rights reserved

Lecture notes based on

Suppose = 0. Then, at least one component of must be nonzero. That

contradicting (1). Therefore, we conclude that > 0.

c 2001 Michael Carter

All rights reserved

Lecture notes based on

which can be written in standard form as

for every which implies that

Letting 1 = 1 gives the desired result.

c 2001 Michael Carter

All rights reserved

Lecture notes based on

This problem satises the conditions of the concave programming theorem

for every which implies that

Conversely, suppose satises (4) for some weights 1 , 2 , . . . , . Assume

c 2001 Michael Carter

All rights reserved

Lecture notes based on

5 The utilitys optimization problem is

The demand independence assumption ensures that the objective function

and that capacity be chosen such that

where is the Lagrangean

In o-peak periods ( < ), complementary slackness requires that = 0

c 2001 Michael Carter

All rights reserved

Lecture notes based on

We conclude that it is optimal to price at marginal cost in o-peak periods