Pliska Studia Mathematica Bulgarica
Volume 12, 1998
Proceedings of the 4th International Conference on Mathematical Methods in Operations Research and 6th Workshop on Well-posedness and Stability of Optimization Problems
GUEST EDITORS: P. S. Kenderov, J. P. Revalski
Sofia, 1998
C O N T E N T S
- Andonov, R., Yanev, N. n-dimensional orthogonal tile sizing problem. (pp. 5-20)
- Bednarczuk, E., Song, W. PC points and their application to vector optimization. (pp. 21-30)
- Dontchev, A. The Graves theorem revisited II: Robust convergence of the Newton method. (pp. 31-38)
- Ginchev, I., Guerraggio, A. Second order optimality conditions in nonsmooth unconstrained optimization. (pp. 39-50)
- Khutoretsky, A. Maximization of a linear utility function over the set of the housing market short-term equilibria. (pp. 51-56)
- Lee, H. A fast algorithm for Weber problem on a grid. (pp. 57-70)
- Lemaire, B. Well-posedness, conditioning and regularization of minimization, inclusion and fixed-point problems. (pp. 71-84)
- Ling, M., Lawler, K., McBain, N., Moscardini, A. Optimization of advertising resources over time: a strategic analysis. (pp. 85-96)
- Marco, L., Murillo, J. Viability kernels of higher order. (pp. 97-106)
- Marco, L., Murillo, J. Time-dependent differential inclusions and viability. (pp. 107-118)
- Markov, S. On the algebraic properties of convex bodies. (pp. 119-132)
- Nikonov, O. Financial decisions via methods of guaranteed control theory. (pp. 133-140)
- Penot, J.-P. Well-behavior, well-posedness and nonsmooth analysis. (pp. 141-190)
- Plotnikov, V., Ivanov, R., Kitanov, N. Method of averaging for impulsive differential inclusions. (pp. 191-200)
- Quincampoix, M., Veliov, V. Control systems with constraints and uncertain initial conditions. (pp. 201-212)
- Saint-Pierre, P. Viability, optimality and stability of dynamical systems and estimation of convergence of numerical schemes. (pp. 213-226)
- Tikhomirov, V. Principles of extremum and application to some problems of analysis. (pp. 227-234)
- Timofeeva, G. Efficient control in multistage stochastic optimization problem. (pp. 235-244)
- Vassilev, V., Genova, K., Kirilov, L. A method for solving a class of multiple-criteria analysis problems. (pp. 245-254)
- Zaffaroni, A. Codifferentiable mappings with applications to vector optimality. (pp. 255-266)
- Zolezzi, T. Well-posedness and conditioning of optimization problems. (pp. 267-280)
A B S T R A C T S
n-DIMENSIONAL ORTHOGONAL TILE SIZING PROBLEM
Rumen Andonov Rumen.Andonov@univ-valenciennes.fr
Nicola Yanev choby@math.bas.bg
1991 Mathematics Subject Classification: 68Q22, 90C90.
Key words: coarse grain pipelining, dynamic programming, uniform recurrence
equations, parallelizing compilers, integer non-linear optimization.
We discuss in this paper the problem of generating highly efficient code
when a n+1-dimensional nested loop program is executed on a
n-dimensional torus/grid of distributed-memory general-purpose
machines. We focus on a class of uniform recurrences with non-negative
components of the dependency matrix. Using tiling the iteration space strategy
we show that minimizing the total running time reduces to solving a
non-trivial non-linear integer optimization problem. For the later we present
a mathematical framework that enables us to derive an O(nlog n)
algorithm for finding a good approximate solution. The theoretical evaluations
and the experimental results show that the obtained solution approximates the
original minimum sufficiently well in the context of the considered problem.
Such algorithm is real-time usable for very large values of n and can
be used as optimization techniques in parallelizing compilers as well as in
performance tuning of parallel codes by hand.
PC POINTS AND THEIR APPLICATION TO VECTOR OPTIMIZATION
Ewa Bednarczuk bednarcz@ibis2.ibspan.waw.pl
Wen Song
1991 Mathematics Subject Classification: 90C29, 90C48.
Key
words: PC points, efficient points, density, connectivity,
contractibility, stability, vector optimization.
In this paper we present some results concerning stability under
perturbations and some topological properties of minimal point sets in vector
optimization. A common feature of all these results is that they exploit the
notion of a point of continuity (PC point) of a subset of a topological vector
space. The concept of a PC point plays an important role in investigation of
the geometry of Banach spaces.
THE GRAVES THEOREM REVISITED II: ROBUST CONVERGENCE OF THE NEWTON METHOD
Asen L. Dontchev ald@math.ams.org
1991 Mathematics Subject Classification: 65J15, 47H04, 90C30.
Key words: Newton's method, Aubin property, robust convergence.
Based on the original proof of the Graves theorem [9] we study the
convergence of the Newton method for the solution of the equation f(x) =
y, uniform with respect to the starting point and the parameter y.
We show that the surjectivity of the Jacobian implies the Aubin continuity,
relative to the supremum norm, of the map taking the starting point and the
parameter y to the set of all Newton sequences. These results
complement our previous paper [4].
SECOND ORDER OPTIMALITY CONDITIONS IN NONSMOOTH UNCONSTRAINED OPTIMIZATION
Ivan Ginchev, ginchev@ms3.tu-varna.acad.bg
Angelo Guerraggio angelo.guerraggio@uni-bocconi.it
1991 Mathematics Subject Classification: 49J52, 90C30.
Key
words: second order optimality conditions, nonsmooth optimization, first
and second order directional derivatives, Riemann type derivatives.
Second order sufficient and necessary conditions are given for a nonsmooth
function f defined in a Banach space to attain a minimum at a point in
the interior of its domain. At the beginning sufficient conditions in terms of
Riemann type derivatives are introduced. The considered examples suggest
improvements to gain more efficiency. Consequently second order conditions
based on generalized Riemann type finite difference are proved and their
efficiency is shown. On this ground a generalized second order derivative is
defined.
MAXIMIZATIOM OF A LINEAR UTILITY FUNCTION OVER THE SET OF THE HOUSING MARKET
SHORT-TERM EQUILIBRIA
A. B. Khutoretsky hutor@ieie.nsc.ru
1991 Mathematics Subject Classification: 90C05, 90A14.
Key
words: housing market, quantity constrained equilibrium, linear
programming, unimodularity.
Some generalization of the housing market models published by Herbert and
Stevens [4], Gustafsson et al. [2], and Wiesmeth [7] is suggested. The set of
short-term equilibria in a housing market in the sense of Wiesmeth [7] is
parameterized by Pareto-maximal integral points of some polyhedron. The
problem of maximization of a linear utility function over the set of
short-term equilibriums is studied. The problem is proved to be reducible
(under some natural assumptions) to a linear programming problem (LPP), or to
finite number of the LPPs in general case. The possible applications of the
results and some related problems are pointed out.
A FAST ALGORITHM FOR WEBER PROBLEM ON A GRID
H. Lee hslee@axp1.stm.ntou.edu.tw
1991 Mathematics Subject Classification: 90B80.
Key words:
continued fraction expansions, integer programming, location problem, number
theory.
The Weber problem is to find a supply point in a plane such that total
weighted distance between supply point and a set of demand points is
minimized. No known algorithm finds the exact solution. In this paper, we
consider a restricted case of Weber problem. The solution domain considered
here is confined to grid points (that is, points with integer coordinates).
Given m demand points in a plane and a convex polygon P with
n vertices, we propose an algorithm to find a supply point with integer
coordinates in convex polygon P such that total weighted distance from
the point to these m points is minimized. If P is contained in
U\times U lattice, the worst case running time of the algorithm is
O((n+m)log U+log^{2}U).
Our method works as follows.
Fist, the searching domain polygon P is transformed so that either a
number of horizontal grid lines can cover P or a central grid point in
P can be found. If the first case holds, the supply point with integer
coordinates can be found easily by scanning the grid points on those covering
grid lines. Otherwise, we can prune a way a fixed fraction of the polygon by
drawing a tangent line through the central grid point so that a smaller
searching domain P can be obtained and do the searching recursively.
WELL-POSEDNESS, CONDITIONING AND REGULARIZATION OF MINIMIZATION, INCLUSION
AND FIXED-POINT PROBLEMS
B. Lemaire lemaire@math.univ-montp2.fr
1991 Mathematics Subject Classification: 65K10, 49M07, 90C25, 90C48.
Key words: conditioning, inclusion, maximal monotone,
minimization, fixed-point, well-posed, regularization.
Well-posedness, conditioning and regularization of fixed-point problems
are studied in connexion with well-posedness, conditioning and Tikhonov
regularization of minimization and inclusion problems. Equivalence theorems
are proved. Coupling iteration and well-posedness as well as iteration and
regularization are also considered.
OPTIMIZATION OF ADVERTISING RESOURCES OVER TIME: A STRATEGIC ANALYSIS
M. Ling, Marcus.ling@sunderland.ac.uk
K. Lawler, N. McBain, A. Moscardini
1991 Mathematics Subject Classification: 90B60, 90B50, 90A80.
Key words: Strategic advertising, advertising model, advertising
function, optimisation.
Strategic behaviour has long been a crucial issue for modern corporations.
To maximize potential profits and market share, firms are more than willing to
invest in sales promotion to boost long term manufacturing output. Knowing
that the sales of the firm not only respond to own advertising budgets, but
also depend upon rivals' advertising strategies, oligopolistic firms form
part, therefore of a continuous race with reference to non-price competition.
Efficient use of investment resources is crucial for business operations and
long term strategic success. This paper aims to investigate the key issue of
optimization of strategic advertising outlays. By using mathematical modelling
techniques, strategic linkages between rival companies are identified and
advertising impacts explained. Since advertising influences can persist
through time, our discussion extends to explore this fundamental point by
constructing a more advanced model to examine into the problems of
optimization over time. Empirical data is used to test the predictive power of
these models and assess relative efficiencies. All in all, this paper intends
to highlight the importance of continuous strategic advertising investment and
consequently provides comprehensive insights into the impact of modern
advertising functions over time.
VIABILITY KERNELS OF HIGHER ORDER
Luis Marco, Luis.Marco@uv.es
Jos\'e Alberto
Murillo Alberto.Murillo@uv.es
1991 Mathematics Subject Classification: Primary 34A60, Secondary
49K24.
Key words: Multivalued differential inclusions, viability,
differential inclusions with constraints.
The aim of this article is to establish a definition of the viability
kernel associated with a differential inclusion of high order, which
generalizes this notion for first order differential inclusion. We present a
sufficient condition ensuring the existence of the viability kernel of high
order. Some examples in the second order case are analysed.
TIME-DEPENDENT DIFFERENTIAL INCLUSIONS AND VIABILITY
Luis Marco, Luis.Marco@uv.es
Jos\'e Alberto
Murillo Alberto.Murillo@uv.es
1991 Mathematics Subject Classification: Primary 34A60, Secondary
49J52.
Key words: viable solutions, differential inclusions, high
order, nonautonomous, higher order tangent sets, tangential conditions,
multivalued differential inequalities.
This paper is devoted to study the existence of viable solutions for
nonautonomous higher order differential inclusions. Two cases are considered,
according to the properties of the set-valued maps on the right-hand side.
Firstly, upper semicontinuity is assumed and both necessary and sufficient
conditions are given by means of higher order tangent sets. Later, almost
upper semicontinuous case is investigated, and similar results are stated.
Finally, these results are used to solve a multivalued differential
inequality.
ON THE ALGEBRAIC PROPERTIES OF CONVEX BODIES
S. Markov smarkov@iph.bio.bas.bg
1991 Mathematics Subject Classification: 52A01, 13C99.
Key
words: convex bodies, Minkowski operations, isomorphic embedding,
quasilinear system.
The algebraic properties of the convex bodies are studied. A theorem of
H.Radstrom for embedding of convex bodies in a normed vector space is
generalized by using a natural extension of the multiplication by scalar.
FINANCIAL DECISIONS VIA METHOD OF GUARANTEED CONTROL THEORY
O. I.
Nikonov noi@imm.uran.su
1991 Mathematics Subject Classification: 93C95, 90A09.
Key
words: guaranteed control, financial modelling.
The paper deals with some problems of financial mathematics that can be
studied with the help of the theory of guaranteed control under uncertainty.
From this viewpoint the dynamic portfolio selection problem and the option
pricing models are considered, and the links between guaranteed and stochastic
approaches in financial mathematics are discussed.
WELL-BEHAVIOR, WELL-POSEDNESS AND NONSMOOTH ANALYSIS
Jean-Paul Penot
Jean-Paul.Penot@univ-pau.fr
1991 Mathematics Subject Classification: 90C30, 90C33.
Key
words: Asymptotical well-behavior, conditioning, critical sequence,
error bounds, gage, metrically well-set, minimizing sequence, nice behavior,
Palais-Smale condition, Ptak function, quasi-inverse, stationary sequence,
well-behavior, well-posed problem.
We survey the relationships between well-posedness and well-behavior. The
latter notion means that any critical sequence (x_{n}) of a lower
semicontinuous function f on a Banach space is minimizing. Here
``critical'' means that the remoteness of the subdifferential \partial
f(x_{n}) of f at x_{n} (i.e. the distance of 0 to
\partial f(x_{n})) converges to 0. The objective function f is
not supposed to be convex or smooth and the subdifferential \partial is
not necessarily the usual Fenchel subdifferential. We are thus led to deal
with conditions ensuring that a growth property of the subdifferential (or the
derivative) of a function implies a growth property of the function itself.
Both qualitative questions and quantitative results are considered.
METHOD OF AVERAGING FOR IMPULSIVE DIFFERENTIAL INCLUSIONS
V. A.
Plotnikov, R. P. Ivanov, N. M. Kitanov
1991 Mathematics Subject Classification: Primary 49N25, Secondary
49J24, 49J25.
Key words: method of averaging, differential
inclusion, impulsive differential inclusion, small parameter.
The paper deals with impulsive differential inclusions in the euclidean
space. The main purpose is to justify the method of averaging in the case of
bounded and asymptotically small impulses. The obtained results, which are
based on the condition of an integral continuity, generalize the first
Bogoljubov's theorem for the method of averaging.
CONTROL SYSTEMS WITH CONSTRAINTS AND UNCERTAIN INITIAL CONDITIONS
M.
Quincampoix, Marc.Quincampoix@univ-brest.fr
V. Veliov
1991 Mathematics Subject Classification: 49N55, 93B52, 93C15, 93C10,
26E25.
Key words: viability, uncertainty, set equations.
We study the problem of finding a control such that all solutions of a
control systems, starting from a given set of initial conditions, satisfy a
given constraint. This problem is an extension of the well-known Viability
Problem when the initial condition is a set. The present paper is mainly a
survey of results recently obtained by the authors, but some new results with
proofs are also included.
VIABILITY, OPTIMALITY AND STABILITY OF DYNAMICAL SYSTEMS AND ESTIMATION OF
CONVERGENCE OF NUMERICAL SCHEMES
P. Saint-Pierre saint-pierre@viab.ufrmd.dauphine.fr
1991 Mathematics Subject Classification: 49N35,49N55,65Lxx.
Key
words: Dynamical Systems, Viability Kernel, Approximation.
We present in this paper some recent developments dealing with dynamical
controlled systems with state constraints. After recalling the basic frame of
Viability Theory and it numerical aspects, we estimate the convergence of
numerical schemes for computing the optimal time for target problem. We give
also a relaxation result for decomposable problems. These properties are
enhanced through the study of the Norvegian Fishermen problem arising in
Dynamic of Population. Another interesting application of this approach is
shortly presented when considering the approximation of the so-called the
minimal time of crisis. This appears for problems where some constraints are
``soft'' (reversibility) and others are ``hard'' (irreversibility).
PRINCIPLES OF EXTREMUM AND APPLICATION TO SOME PROBLEMS OF ANALYSIS
V.
M. Tikhomirov tikh@tikhomir.mccme.ru
1991 Mathematics Subject Classification: 41A17, 41A50, 49Kxx, 90C25.
Key words: Lagrange principle, duality, inequalities for
derivatives.
The aim of this paper is to demonstrate applications of a direct approach
to the solution of extremal problems to some concrete problems of classical
analysis, calculus of variations and approximation theory.
EFFICIENT CONTROL IN MULTISTAGE STOCHASTIC OPTIMIZATION PROBLEM
G. A.
Timofeeva tim@ac.usart.ru
1991 Mathematics Subject Classification: 90C31, 90A09, 49K15, 49L20.
Key words: stochastic optimization, bilinear multistage system,
efficient solution, adjoint problem, separation of control and observation.
An efficient control problem for bilinear multistage system with random
perturbations is considered. The efficient solutions are choosen by two
criteria: the first is maximization of a mean value, the second is
minimization of a variance of utility function. Such approach has been
suggested by Markovitz H. [13] to solve one-stage problem of the portfolio
selection in financial analysis.
The existence conditions of the
stationary efficient controls are obtained in case of incomplete information
on the parameters of distributions. The randomization method for unknown
parameters is used to construct a control problem solution. The concept of an
adjoint stochastic optimization problem is introduced. The connection and
separation problems of efficient control and observation are studied by means
of adjoint problem solution.
A METHOD FOR SOLVING A CLASS OF MULTIPLE-CRITERIA ANALYSIS PROBLEMS
V.
Vassilev, K. Genova,
L. Kirilov lkirilov@iinf.acad.bg
1991 Mathematics Subject Classification: 90C29.
Key words:
decision making, discrete multicriteria problems, reference cone.
The paper proposes an interactive method solving the multiple criteria
choice problem (MCCP) with a large number of discrete alternatives and a small
number of quantitative criteria. The decision maker (DM) sets his preferences
in terms of desired directions of improving or relaxing of the criteria. On
this base the so called reference cone is constructed. A small subset of
relatively closed alternatives is defined according to this cone and to the
maximal deterioration of the criteria values at each iteration. This subset is
evaluated by the DM, who selects the most preferred alternative or enters
his/her new preferences.
The method suggested has user-friendly dialog. It
enables the DM to explore the set of alternatives comparatively quickly and
easy. The method is included in a DSS. It is tested by a number of real
multiple criteria choice problems.
CODIFFERENTIABLE MAPPINGS WITH APPLICATIONS TO VECTOR OPMIMALITY
Alberto Zaffaroni alberto.zaffaroni@uni-bocconi.it
1991 Mathematics Subject Classification: Primary 49J52; secondary:
26A27, 90C48, 47N10.
Key words: Nonsmooth analysis, nonsmooth
mappings, codifferentiable functions, vector optimization, optimality
conditions.
Codifferentiable mappings are defined as the ones which can be locally
approximated by a particular type of difference convex mappings, adapting an
analogous notion recently introduced for scalar functions. Some calculus rules
are proved and some applications to vector optimization problems described by
codifferentiable criteria and constraints are given.
WELL-POSEDNESS AND CONDITIONING OF OPTIMIZATION PROBLEMS
T. Zolezzi zolezzi@dima.unige.it
1991 Mathematics Subject Classification: 49K40, 90C31.
Key
words: well-posed optimization problems, conditioning, stability
analysis in optimization.
For a given abstract optimization problem in a Banach space subject to
data perturbations, conditions linking well-posedness to well-conditioning are
obtained. Explicit estimates of the modulus of well-posedness allow to bound
the condition number. Application to mathematical programming problems are
presented.