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.