Global Optimization of Marginal Functions with Applications to Economic Equilibrium.
We discuss the applicability of the cutting angle method to global minimization of marginal functions. The search of equilibrium prices in the exchange model can be reduced to the global minimization of certain functions, which include marginal functions. This problem has been approximately solved by the cutting angle method. Results of numerical experiments are presented and discussed.
Introduction
Marginal functions, that is, functions of the form
where a is a set-valued mapping, have been intensively studied by many researches, (see,
for example, [11, 16, 14] and references therein).
Note, that the so-called max function:
is the simplest example of a marginal function. Here Y can be considered as the image
of a constant mapping a. We assume that the set Y in (1.2) is nite dimensional, innite
and compact.
Marginal functions arise in the study of many problems of mathematical economics.
Global minimization of marginal functions (in particular, max functions) is a very
complicated problem. Indeed, almost all known methods of global minimization require
This research was supported by the Australian Research Council
to compute values of the objective function many times. However, the value of marginal
function of (1.1) at a point p can be found only by solving the optimization problem
subject to y 2 a(p);
so the calculation of the value of is very time consuming.
Recently the so-called cutting angle method for global optimization of Lipschitz function
has been developed (see [2, 23, 6, 7]). We need to compute only a few values of the
objective function at each iteration of the cutting angle method, so we can hope that this
method is suitable for minimizing some marginal functions.
In this paper we apply the cutting angle method to solving some problems of global
optimization, which arise in the theory of economic equilibrium. The objective functions
of these problems are not always Lipschitz, so we need to transform objective functions in
order to obtain Lipschitz continuity. Note that the data in models of economic equilibrium
often is not very precise. Thus, we can restrict ourselves to the search of approximate
solutions of corresponding problems of global optimization. We show that the cutting
angle method, which can nd an approximate solution fairly quickly, can serve for solving
these problems.
Consider a market economy with m consumers (agents) and n goods. The consumer j
has a utility function U j and a vector of initial endowments ! j . It has been shown in [20]
that, under some natural assumptions, a vector of equilibrium prices of this model can be
found as a solution of the following problem:
subject to p 2 ri
with are special marginal functions (see
Section 5). Problem (1.3) has been studied from various points of view in [1] and [5]. The
similar approach for Arrow-Debreu equilibrium model was proposed in [21].
The equilibrium exists if and only if the value of problem (1.3) is equal to zero. It is
well known that the equilibrium does exist if the utility function U j is quasiconcave and
j is a strictly positive vector for all j. If these conditions hold, we need to solve problem
(1.3) with the known value of global minimum. If at least one of these conditions is not
valid, problem (1.3) can serve for recognition of the existence of the equilibrium.
The structure of this paper is as follows. In Section 2 we discuss problems, which arise
under minimization of marginal functions. In Section 3 we recall brie
y the cutting angle
method and in Section 4 we recall the exchange model of economic equilibrium. Section 5
provides a discussion of a reformulation of an equilibrium problem as a special optimization
problem. In Section 6, we study Lipschitz continuity of the objective function of this
optimization problem. Section 7 provides a discussion of the calculation of equilibrium
prices by the cutting angle method. We record results of numerical experiments in this
section. Appendix contains data, which were used for numerical experiments.
2 Minimization of marginal functions
Let a be a set-valued mapping transforming a set P into the set of all non-empty subsets
of a set Y . Consider a function function dened on P by
is called a marginal function. In this paper we assume that P and Y are closed subsets
of nite-dimensional spaces and images of the mapping a are compact sets. Assume also
that the function y 7! f(p; y) is upper semicontinuous for all . Then the supremum
in (2.1) is attained. Continuity, Lipschitz continuity and directional dierentiability of
marginal functions have been intensively studied (see, for example, [4, 11, 14, 16] and
references therein).
A well-known example of marginal functions is delivered by a parametric problem of
mathematical programming:
subject to g i (p; y)  0 (i 2 I); h j (p;
Here J)g. It is assumed that the set
a(p) is nonempty and compact for all
Marginal functions arise in the study of many problems of mathematical economics.
Assume, for example, that a is a production mapping of a producer, that is, a(x) is the
set of all outputs, which can be produced by the producer from an input x. Let p be a
price vector (that is a vector with positive coordinates). Then the maximal prot (x),
which can be obtained by the producer, is equal to (max y2a(x) [p; y]) [p; x], where [u; v]
is the inner product of vectors u and v. The marginal function max y2a(x) [p; y] describes
the revenues of the producer. A dierent kind of marginal functions arises in the study
of a consumer behaviour. Assume that a consumer has a utility function U . Then the
maximal utility, which can be obtained by the consumer is
where B(p) is the set of vectors of goods, which are available for the consumer, if there is
a price vector p at the market.
are marginal
functions and let P be a compact set. Consider the following problem of global optimization

subject to p 2 P: (2.2)
Many problems from various elds of mathematics and its applications can be represented
in form (2.2). We mention here only bilevel programming (see for example [24] and
references therein) and problems of economic equilibrium (see [20]).
Consider the simplest version of (2.2), namely the problem
subject to p 2
where is a marginal function dened by (2.1). A very special case of problem (2.3),
where the mapping a in (2.1) is constant: known as a minimax
problem. Thus the minimax problem has a form: to nd a point (~p; ~
Y such that
If Y is nite, we have a discrete minimax problem, if Y is a compact innite set, we have
a continuous minimax problem.
Discrete minimax problems have been studied by many authors (see, for example
[10, 17] and references therein). We consider here only continuous minimax problems,
which are much more complicated.
We mention three numerical methods, which were proposed for solving continuous minimax
problems in the seventies and earlier: Arrow - Hurwicz method (see [3, 15]), the net
method (see [10]); and the method of extremal basis (see [9]). Modern approaches to solving
these problems can be found in the book [17] by E. Polak. The main attention in this
book is paid to the minimization of convex functions of the form
The net method and the method of consistent approximation [17] can be applied for the
search for local minima of , when this function is non-convex. These methods are based
on an approximation of the given set Y by a nite set Y 0 . Having such an approximation
we can substitute a continuous minimax problem for a sequence of discrete minimax problems
and then solve these problems by known algorithms (see, for example [10, 17]. These
methods require to use large nite sets Y 0 , hence we need to minimize the maximum of a
large number of functions.
The calculation of local minima of a non-convex marginal function is very time-
consuming. Indeed, the application of a majority of known numerical methods for local
optimization is based on the calculation of the objective function and its subgradients (in
a certain sense) in many dierent points. Sometimes it is possible to use only approximate
values of the function and its subgraients, however, in order to nd an approximate value
of the function  at a point
p we need to nd an approximate solution of the problem
subject to y 2 a(p): (2.5)
Thus the search for a local minimum of the function  requires to solve (approximately)
problem (2.5) very often.
Note that as a rule the calculation of subgradients of a non-convex marginal function is
more complicated than the calculation of a value of this function. It leads to the following
conclusion: optimization methods, which are based on the calculation both functions
and its subgradients, as a rule are not applicable for the local minimization of non-convex
marginal functions. Methods, which are based only on calculation of values of the objective
function (so-called derivative-free methods), are more preferable.
any convexity assumptions a marginal function may have a lot of local mini-
mizers, so we need to use methods of global optimization for solving problem (2.2). How-
ever, the majority of these methods (branch-and-bound, random search etc) require very
many objective function evaluations. So, these methods are not applicable for minimization
of marginal functions (and even for solving minimax problems) if the dimension of the
problem is suciently high. For global optimization of marginal functions we need to nd
methods, which require a small amount of objective functions evaluations. One of such
methods is the so-called cutting angle method, which uses only few function evaluations
at each iteration. So we can propose that the cutting angle method is applicable for the
global minimization of marginal functions.
Cutting angle method
ng. Consider the space IR n of all vectors We shall use the following
notations.
is the i-th coordinate of a vector x 2
is the inner product of vectors l and x.
A function f dened on the cone IR n
of all n-vectors with nonnegative coordinates is called
an IPH function if f is increasing (x  y =) f(x)  f(y)) and positively homogeneous
of the rst degree 0). The following result holds
(see [23]).
Theorem 3.1 Let f be a Lipschitz function dened on the unit simplex
1g. Then there exists a constant c > 0 such that for all c 0  c the function
is the restriction of a certain IPH function g to S.
Thus the minimization of a Lipschitz function f over S is reduced to the minimization
of an IPH function g over S. The minimization of a Lipschitz function subject to linear
constraints can be transformed to the minimization of another Lipschitz function over the
simplex (see [23] for details), hence the minimization of a Lipschitz function subject to
linear constraints is reduced to the minimization of an IPH function over the simplex.
The cutting angle method was proposed (see [2] and also [22]) for the minimization of
a so-called ICAR (increasing convex-along-rays) function dened on IR n
over a compact
subset of IR n
. We consider here only a version of this method, which is suitable for the
minimization of an IPH (increasing positively homogeneous of degree one) function over
the unit simplex. This version has been proposed and discussed in detail in [6, 7]. It
follows from monotonicity of an IPH function f that f(x)
. We
assume in the sequel that f(x) > 0 for all x 6= 0. For x 2 IR n
we shall use the following
c=x is the vector with the following coordinates:
x
The cutting angle method is based on the following result (see [22] and references therein).
Theorem 3.2
! IR be a function such that f(x) > 0 for all x 6= 0. Then
f is IPH if and only if there exists U  IR n
f0g such that
l2U
min
l
min
l
and min
l
be the unit vector such that I(e k
First we present the simplest version of the cutting angle method.
The cutting angle method for minimizing an IPH function
over the unit simplex
Dene the function h
kn
min
l k
kn
l k
and set
Step 1. Find a solution x  of the problem
subject to x 2 S: (3.1)
Step 2. Set
Step 3. Compute dene the function
l j
min
l k
and go to Step 1.
The convergence of the cutting angle method has been proved under very mild assumptions
(see [16], where the convergence of much a more general method was established,
and also [22]).
Remark 3.1 The solution of the auxiliary problem (3.1) is the most dicult part of
the algorithm. The special method for the solution of this problem has been developed
in [6, 7]. We do not discuss this method here. Dierent approaches are possible in lower
dimensions ([2, 23]): in particular, the auxiliary problem can be reduced to a mixed-integer
linear programming problem, which can be solved by standard optimization packages (for
example, CPLEX).
Remark 3.2 Only one value of the objective function f should be calculated at each
iteration.
Remark 3.3 A more advanced version of the cutting angle method was proposed in [7].
All approximate solutions of the problem (3.1) are considered in this version. We shall
use the advanced version in this paper, since it allows us to fasten the search for a global
minimizer (see [7] for details). The advanced version may require a few calculation of the
objective function at each iteration.
Remark 3.4 Let
It follows from Theorem 3.2 that h j (x)  f(x) for all x 2 S. Hence
Thus  j is a lower estimate of the global minimum of f over S. Let  It can
be shown (see, for example [22] and references therein) that  j is an increasing sequence
and  j  we have a stopping criterion, which enables us (at least
theoretically) to obtain an approximate solution with an arbitrary given tolerance.
Remark 3.5 The cutting angle method can be considered as a special case of many well-known
algorithms (see [22] for a short survey of some of these algorithms). However, the
numerical implementation of the cutting angle method has demonstrated that it works
much better than many other versions of these algorithms.
4 The equilibrium model
We study the so-called exchange models of economic equilibrium. First we consider a
classical version of this model. The classical exchange model describes a market, where n
goods are circulated. Let I ng. There is a nite number, say m, of economical
agents, which are called consumers, at the market. Let
is described by a pair (U is a utility function (objective function) of the
consumer
is a vector of her initial endowments.
A state of economy is a vector
. A state X is called feasible
if it belongs to the
set
where
is the vector of all products available on the market.
A vector p 2 IR n
n f0g is called a price vector. Having a price vector p, the consumer
can sell her initial endowment ! j and can buy a vector x j from the set
This set is called the budget set of the consumer j.
Note that B j so we can assume without loss of generality
that the mapping B j is dened only on the unit simplex
1g. We
shall denote the model under consideration by M:
A semi-equilibrium of the model M is a pair (p;
X), where  p is a price vector and
is a feasible state, such that
x j is a solution of the consumer problem:
subject to x
The vector
p is called equilibrium prices and the vector  x j is called an equilibrium state of
the agent j.
It is well known that a semi-equilibrium exists if functions U j are quasiconcave and
vectors ! j are strictly positive (see, for example, [13] and references therein). We assume
in the rest of this paper that
We shall consider both models with quasiconcave U j and without quasiconcave U j .
Let (p;
X) be a semi-equilibrium of the model M. Since
X is a feasible state, the
inequality
is dened by (4.2). A semi-equilibrium (p;
X) is
called an equilibrium if
It is well-known (and easy to check), that each semi-
X) with
is an equilibrium.
We accept the following
Assumption 4.1 There exists j 2 J such that the utility function U j is non-satiated
in the following sense: for each x 2 IR n
and each i 2 I there exists  i > 0 such that
is the i-th unit vector.
Then each vector of equilibrium prices
p is strictly positive. Indeed, assume that
Let
x j be an equilibrium state of the consumer j. Then the budget set B
of this consumer contains the ray fx there exists
(p) such that U j which contradicts the denition of
the semi-equilibrium. Thus Assumption 4.1 allows us to consider only strictly positive
equilibrium prices (therefore, an equilibrium is guaranteed to exist by the above).
We also consider one more type of exchange models, namely a model of exchange with
xed budgets. In contrast with the classical version, it is assumed that each agent j has a
xed budget, that is, a special sum of money d j , which does not depend on market prices
. The budget mapping B j (p) should be replaced for the mapping
~
Having mappings ~
(p), we can dene the semi-equilibrium and equilibrium in this model
in the same way as in the classical case. Note that in contrast with the classical model,
~
so we need to consider mappings ~
on the cone IR n
f0g.
The existence results for the model with xed budgets are similar to those for the classical
model. If Assumption 4.1 holds then equilibrium prices are strictly positive.
Remark 4.1 It is known [18, 13] that an equilibrium for a model with xed budgets and
positively homogeneous utility functions can be found by solving a convex programming
problem. However this does not hold if utility functions are not positively homogeneous. In
this paper we consider a search for an economical equilibrium as an example of application
of the cutting angle method. From this point of view models with xed budget is of a
special interest since they can be reduced to a problem of global optimization, which is
dierent from that for classical exchange models.
5 Equilibrium prices as a solution of a special optimization
problem
It is not hard to formulate a bilevel problem such that its solution set coincides with the
set of equilibrium prices. Let Assumption 4.1 hold. Consider the set ri
++ . Assume for the sake of simplicity that the utility functions U
are strictly concave. Then the consumer's problem
subject to x
has a unique solution for each p 2 ri S. Denote this solution by x j (p). Consider a function


only if p is a vector of equilibrium prices. Thus
equilibrium prices can be found as a solution of the following bilevel problem:


min subject to p 2 ri S (5.2)
where x j (p) is a solution of problem (5.1). The optimal value of problem (5.2) is known
(and equal to zero). However, this problem is very complicated. Note that the set-valued
mapping B j is not Lipschitz on ri S. (See, for example, [4] for the denition of Lipschitz
set-valued mappings.) So we cannot hope that the mappings x j (p) (j 2 J) and the
function
(p) are Lipschitz for an arbitrary functions U j . Hence we cannot guarantee that
problem (5.2) can be solved by the cutting angle method.
We now consider a certain dierent type of optimization problems, which can serve
for the search of economic equilibrium. Such problems were suggested in [20]. For each
ri S consider sets
A
Y
and
Both sets A  (p) and A(p) are compact for p 2 ri S, so the following functions are well
ri S (5.5)
and
ri S: (5.6)
0: The following assertion holds (see [20]).
Lemma 5.1 Let Assumption 4.1 holds. and let
ri S. The equality
if and only if  p is a vector of equilibrium prices.
Thus in order to nd a vector of equilibrium prices we need to solve the following problem
of global optimization:
subject to p 2 ri S: (5.7)
The objective function of this problem is the dierence of two marginal functions H 1 and
. If the equilibrium exists then the minimal value of this problem is known and equal
to zero.
We accept the following assumption.
Assumption 5.1 (1) For each j 2 J there exists a point a j  0 such that the utility
function U j is twice continuously dierentiable on the set a
++ and
++ and y j 6= 0: (5.8)
(2) The utility function U j (j 2 J) is increasing in the following sense: if x 1  x 2 then
It follows from (5.8) that U j is a strictly concave function. If Assumption 5.1 holds then
for each p  0 and each j 2 J the consumer's problem
subject to x
has a unique solution x Hence, the problem
subject to
which serves for the denition of the function H 1 , has a unique solution
The problem X
subject to
which serves for the denition of H 2 also has a unique solution ~
It has been proved in [21] that the function H 1 is Frechet dierentiable with the piece-wise
mapping rH 1 . We have

is an arbitrary index belonging to I j (p) :=
0g. The function
H 2 is directionally dierentiable and, under some additional assumptions, also Frechet
dierentiable with the piece-wise C 1 gradient mapping. Assume that there exist
I and a sequence p (k) 2 ri S such that
It follows from (5.11) that
So we cannot hope that H(p) is a Lipschitz function on the set ri
all quasiconcave utility functions U j and we cannot guarantee that the global minimizer
of H over the simplex S can be found by the cutting angle method.
In order to get a Lipschitz function we shall slightly change the denition of the function
H. First we note that the function H 2 is bounded on ri S. Indeed, let p 2 ri S and let
Since the utility
functions U j are increasing, we have
where
However the function H 1 can be unbounded on S. Since we are interested in the global
minimum of the function points where the function H 1 is
very large. For this purpose we consider the function
where d is an arbitrary positive number, which is bigger than a global minimum of the
function H. Clearly global minimizers of functions H and L coincide so if the equilibrium
exists, then a point p 2 ri S is an equilibrium prices if and only if
Thus a vector of equilibrium prices can be found as a solution of the following problem:
subject to p 2 ri S: (5.14)
6 Lipschitz continuity of the function L.
In this section we shall check that the function L is Lipschitz. Let dg.
It is sucient to verify that L is Lipschitz on the set E. First we prove the following simple
Proposition.
Proposition 6.1 The function H 1 is bounded on the set E.
Proof: If dened by (5.12). 2
Corollary 6.1 There exists a vector a 2 IR n
++ such that x j (p)  a for all
Indeed, U j (x(p))  H 1 (p). So Proposition 6.1 and Assumption 5.1(3) imply the boundness
of the set fx Jg.
We need the following theorem which is a special case of a general result from [19].
(This special case and its relation with the mentioned general result were discussed in
Theorem 6.1 Let P  be an open subset of a nite dimensional space and
x  (p) be a solution of the following parametric convex programming problem:
subject to
where K and R are nite sets, a k (k 2 K); h r (r 2 R) are vectors and A r (r 2 R) are
matrices. Assume that T is a twice continuously dierentiable concave function dened
on an open
set
such that
Assume also that the Mangasarian-Fromovitz constraint qualication holds at the point
x  (p), that is, there exists y 2 IR n such that
where
Then the function x  (p) is piece-wise continuously dierentiable near the point p. In
particular, x  (p) is a locally Lipschitz function near the point p.
In order to apply this theorem, we need to consider an open set P   S such that
for all Such a set exists since ! j  0 for all j 2 J . For
the following two optimization problems.
Problem
subject to [p; x]
where a is a vector from Corollary 6.1. Problem P 1 has a unique solution x
(p).
Problem
subject to
This problem has a unique solution ~
(p)) j2J .
Proposition 6.2 1) For each p 2 P  the Mangasarian-Fromovitz constraint qualication
holds for problem P 1 at the point x j
(p).
2)For each p 2 P  the Mangasarian-Fromovitz constraint qualication holds for problem
P 2 at the point ~
We leave the simple but cumbersome proof of this proposition to the reader.
Proposition 6.3 Let
Then the function H  is locally Lipschitz on the set P  .
Proof: It follows from Theorem 6.1 and Proposition 6.2 a that functions x
(p) and ~ x j
(p)
are locally Lipschitz. Functions U j are locally Lipschitz as well. Hence H  (p) is locally
Corollary 6.2 The function H  (p) is Lipschitz on the compact set S.
Theorem 6.2 The function L dened by (5.13) is Lipschitz on the simplex S.
Proof: It is sucient to prove that the function H is Lipschitz on the set
H(p)  dg. Since x j (p)  a for
(p) for
(p) for all p 2 S. Hence
The result follows from Corollary 6.2. 2
7 The calculation of equilibrium prices by the cutting angle
method
In this section we discuss results of numerical experiments, which were carried out in order
to nd an approximate equilibrium prices or to verify that the equilibrium does not exist.
The problem (5.14):
subject to p 2 ri S
has been solved by the cutting angle method.
First we give some remarks.
1. We consider a search of an economical equilibrium as an example of applications of the
cutting angle method to approximate global optimization of a complicated function, which
is the dierence of two marginal functions. Currently the developed approach can mainly
be used for research purposes. We hope that the further development of the cutting angle
method will allow one to use this approach for many real problems of economic equilibrium.
2. Assume that the equilibrium exists. We have actually we are
looking for a global minimum of the function H, which is equal to zero. We also use the
function H for determining the precision of results of calculations. This function is dened
with the help of utility functions U j , which describe the preferences of agents. Note that
the function  j U j with  j > 0 and function U j describes the same preferences (see [20] for
a corresponding discussion). Thus if we replace the function H for the function H with
arbitrary , we obtained the same approximate global minimizers, however the measure
of the precision will be changed. In order to avoid this situation, we need to consider only
functions U j , which are normalized in a certain sense.
All numerical experiments were carried out with utility functions of the form
are dened by maximization of the sum
we consider the following normalization of function H:
3. The cutting angle method is suitable for the search of approximate solution of a global
optimization problem. If there exists the equilibrium of the model under consideration,
then the optimal value of the normalized function H is equal to zero. We search for
vectors p such that H(p)  0:0010:003. Assume that we consider a model, for which the
existence of the equilibrium are not proved and we want to learn whether the equilibrium
exists. Recall (see Section 3) that the cutting angle method produces the lower estimates
j of the global minimum. If  j > 0 for some j, then the equilibrium does not exist.
4. We used the exact penalty method for solving internal problems, which are problems of
convex programming (maximization of a concave function subject to linear constraints).
Thus, the exact penalty functions have been constructed; for their minimization we used
the so-called discrete gradient method ([5]). Since the precision of the results obtained by
the cutting angle method is approximately 0:001  0:003, internal problems were solved
with the precision 10 4 .
5. We used a computer IBM Pentium-S CPU 150 MHz. Problems with
were mainly considered. It takes approximately 15-18 minutes to nd a solution of such
a problem with the precision 0:001  0:003. Results of numerical experiments show that
the solution of internal problems takes the main part of CPU time.
Our aim is to show that the cutting angle method can be successfully applied for
solving the problem (5.14). Using more eective methods of convex optimization for
solving internal problems and more iterations of the cutting angle method we can nd a
more precise solution of problem (5.14).
Classical exchange models with concave utility functions
First we consider a classical exchange model such that Assumption 4.1 and Assumption
5.1 hold. Then the equilibrium does exist, so the value of problem (5.14) is known and
equal to zero. Since the function L is Lipschitz over the unit simplex, the cutting angle
method can be applied.
Example 7.1 Consider the economical system with 8 consumers and 4 goods. The utility
functions are dened as follows:
Vectors
are the rows of the matrices
are rows of
matrix
1 . Coecients
are coordinates of the vector c 1 . Matrices A
1 and vector c 1 can be
found in Appendix.
Numerical results for Example 7.1. The point
with found by the cutting angle method after iterations. It takes
22 objective function evaluations.
Example 7.2 We again consider the same economical system. Utility functions have
the same form with the same vector of coecients c 1 and the same matrix B 1 . However
coecients  j
are dened in dierent way. We assume now thatX
Vectors
are the rows of the matrix A 0
1 , which is in


Appendix

.
Numerical results for Example 7.2. The point
with found by the cutting angle method after 17 iterations. It takes
objective function evaluations.
Exchange model with xed budgets and concave utility functions
Consider a model with xed budgets such that Assumption 4.1 and Assumption 5.1
hold. We now use the approach similar to that for the classical model. Let p 2 IR n
++ .
Consider set-valued mappings
~
A
~
where ~
dened by (4.5). Let ~
~
Further, let ~
d), where d is an arbitrary positive number. The same
argument as in Section 5 demonstrates that a vector of equilibrium prices can be found as
a solution of the problem:
~
subject to p 2 IR n
In order to apply the cutting angle method we need to transform this problem to a problem
with a simplicial constraint. For this purpose we introduce constraints p i  M where M
is a suciently large number. (It is assumed that there exist a vector
p of equilibrium
prices such that
Consider the set
i2I
Clearly this set contains the set fp Adding a
new variable p n+1 and replacing p i =t by q i we transform the set D to the unit simplex
.
Example 7.3 Consider the economical system of Example 7.2. It is assumed now that
each consumer j has the xed budget d j and her budget set ~
(p) has the following form
~
Vector can be found in Appendix.
Numerical results for Example 7.3. The point
with found by the cutting angle method after 5 iterations. It takes 24
objective function evaluations. Note that
3. Classical exchange model with not necessarily concave utility functions
The existence of the equilibrium in classical model can be proved if utility functions U
are quasiconcave. If at least one of these functions is not quasiconcave we cannot guarantee
that the equilibrium exists. However, we also cannot guarantee that the equilibrium does
not exist. In order to check the existence of the equilibrium we can solve problem (5.14).
If the value of this problem is equal to zero then the equilibrium exists and a global
minimizer of the function L is a vector of equilibrium prices. Otherwise, the equilibrium
does not exist. Some numerical experiments have been carried out in order to check the
existence of equilibrium. We consider utility functions, which can be represented as the
maximum of two concave functions. (Functions of such structure arise when indivisible
goods are considered.)
We now describe numerical experiments which were carried out.
1. A number of models with two goods and two consumers has been examined. Each
consumer has a utility functions, which is the maximum of two functions of the form
(*). Coecients c j and b i were chosen at random. Coecients  j
were chosen also at
random, however it is assumed that either
0:8. A model with three
goods and three consumers, which have utility functions of the same form with chosen
at random coecients, also has been examined. Numerical experiments showed that all
models under consideration possess equilibrium. These results allow us to consider the
following conjecture: if the number of goods is equal to the number of consumers and a
utility function of each consumer is the maximum of two functions, for which Assumption
4.1 and Assumption 5.1 hold, then the classical exchange model has an equilibrium. This
conjecture was discussed with Professor J.-M. Bonnisseau, who suggested the following
counter-example.
Example 7.4 (J.-M. Bonnisseau, [8] Consider a classical exchange model with two goods
and two consumers. Utility functions U j and vectors ! j (J =1,2) of consumers have the
following
The demand of the consumers can be explicitly calculated. This calculations showed that
an equilibrium does nor exist.
Numerical experiments, based on the approach suggested in this paper, also conrmed
that the model under consideration and also some similar models have no equilibrium.
Nevertheless our numerical experiments which were performed by a random choice of
coecients show that there exists many models, which have the described above form and
possess an equilibrium.
2 A model with two products and three consumers has been examined. Each consumer
has a utility function, which is the maximum of two functions of the form (*) with chosen
at random coecients. This model has no equilibrium, however each its submodel with
two consumers possesses an equilibrium.
We now present one of the corresponding examples.
Example 7.5 Consider two economical systems, one of them has 3 consumers and 2
goods, the other has 3 consumers and 3 goods. Assume the consumer j has a utility
function
where
U jk
Y
jk
2:
For the rst system vectors
are the rows of matrices A 3
and
respectively, which can be found in Ap-
pendix. Coecients (c 1
3 are coordinates of the vector c 2 (see Appendix).
For the second system vectors
and are the rows of matrices A 3
and
3 , respectively (see Appendix).
Coecients
3 are coordinates of the vector c 2 .
First we describe our approach for solving internal problems.
Note that the function H 1 has the form
ri S:
Hence, we can nd the value H 1 (p) of the function H 1 at a point p by solving the
convex programming problems:
U ji
We also have for p 2 ri S:
In order to nd the value H 2 (p) of the function H 2 at the point p we consider all possible
combinations:
2:
Then we solve the convex programming problems :
and calculate H 2 (p) by (7.4).
Solving problems (5.14) for the described models, we found that the rst economic
system does not possesses the equilibrium. However, all its subsystems consisting of 2
consumers and 2 goods have the equilibrium. The second system also has the equilibrium.

Appendix


In this Appendix we report the data, which were used for numerical experiments.
Examples 8.1 { 8.3
0:05205 0:35366 0:24230 0:15199
0:23562 0:08699 0:30802 0:16937
0:25335 0:17358 0:10888 0:26420
0:09515 0:33689 0:18525 0:18271
0:21114 0:13245 0:32138 0:13503
0:25861 0:14220 0:14025 0:25893
0:13280 0:32224 0:13540 0:20955
0:18448 0:18196 0:33593 0:09763C C C C C C C C C C C C A
0:06506 0:44207 0:30288 0:18999
0:29452 0:10874 0:38502 0:21171
0:31668 0:21697 0:13610 0:33025
0:11893 0:42112 0:23156 0:22839
0:26393 0:16556 0:40172 0:16879
0:32326 0:17775 0:17532 0:32367
0:16601 0:40281 0:16925 0:26194
0:28793 0:06658 0:23274 0:20954
0:24972 0:22317 0:10869 0:29905
0:12910 0:22351 0:19709 0:20271
0:28129 0:05614 0:27284 0:17613
0:26395 0:16693 0:16528 0:28286
0:09218 0:19242 0:20010 0:20564
0:25339 0:06827 0:29563 0:12479
0:22732 0:17509 0:41652 0:27501
0:03812 0:02936 0:06985 0:04612
0:20445 0:15747 0:37461 0:24734
0:25905 0:19953 0:47466 0:31340
0:07548 0:05814 0:13831 0:09132
0:26728 0:20586 0:48973 0:32334C C C C C C C C C C C C A
Example 8.4
0:12829 0:87171 0:73035 0:26965
0:59343 0:40657 0:22022 0:77978
0:61452 0:38548 0:64521 0:35479C A
0:28793 0:06658 0:24972 0:22317
0:12910 0:22351 0:28129 0:05614
0:26395 0:16693 0:09218 0:19242C A
0:22732 0:17509
0:03812 0:02936C A
A 3 =B @
0:08032 0:54576 0:37392 0:37362 0:13794 0:48843
0:47284 0:32395 0:20321 0:15414 0:54576 0:30010
0:31752 0:19918 0:48330 0:47796 0:26282 0:25922C A
C A

Acknowledgement

The authors wish to thank Professor J.-M. Bonnisseau for very useful discussions and
two anonymous referees for valuable comments.



--R

A parametric approach to global optimization problems of a special kind
Cutting angle method in global opti- mization
Studies in Linear and Nonlinear Program- ming

Global optimization of increasing positively homogeneous functions over the unit simplex


Method of extremal basis

Constructive nonsmooth analysis
Mathematical Theory of Economic Dynamic and Equilibria


Numerical Methods for Deterministic and Stochastic Minimax Prob- lems
Foundation of Mathematical Optimization

Economic equilibrium and optimum
Directional derivatives of the solution of a parametric nonlinear program
On some problems of non-smooth optimization in economic theory
Reformulation of a problem of economic equilib- rium
Kluwer Academic Pub- lishers

Bilevel and multilevel programming: a bibliography review
--TR

--CTR
A. M. Bagirov , A. M. Rubinov, Cutting Angle Method and a Local Search, Journal of Global Optimization, v.27 n.2-3, p.193-213, November
global optimization;exchange model;cutting angle method;marginal function;economic equilibrium