Optimality and Lagrangian regularity in vector optimization

Ph.D. Thesis in Mathematics

Giancarlo Bigi


Life involves decision making constantly. Whenever a decision is taken rationally, the possible alternatives are compared to select the ''most suitable'' one; such a judgement generally requires the understanding of what is ''better'' and ''worse'' and thus it can be aided taking into account a performance criterion. Hence, many real world problems have been often modeled as optimization problems, whose objective function gives a numerical measure of the performance of the different alternatives, according to the considered criterion. Obviously, building an appropriate and accurate optimization model is a very important and difficult task; one of the main difficulties to overcome is to identify the right criterion and sometimes it may be even impossible. Infact, there is a wide range of real world decision making problems, which involve a certain number of reasonable performance criteria and not just a single one. These criteria often happen to be independent so that selecting just one of them as objective function appears arbitrary and inadequate; moreover, they are very often also conflicting: there is no chance to achieve the best for all the criteria with the same choice. Clearly, decision making problems with these features can not be efficiently modeled as optimization problems: composing somehow the different criteria into a single one may seem an unavoidable necessity but in this way the very nature of the problem often gets lost. To preserve it within an optimization framework, some idea of optimality with respect to many criteria is needed and it can be achieved through some kind of compromise between the criteria. At the beginning of the last century the famous italian economist Vilfredo Pareto wrote in his Manual of Political Economy:

''We will say that the members of a collectivity enjoy the maximum ophelimity in a certain position when it is impossible to move even slightly away from that position without producing benefits or causing disadvantages to all the members of the collectivity; any minimum change from that position necessarily benefit some members and trouble others.''

Though it does not explicitly refer to any optimization context, this sentence is widely recognized as the very root of what nowadays is known as multiobjective or vector optimization. Actually, Pareto's interests were mainly about welfare economics and economic equilibrium and he was not really concerned with optimization. He didn't even give a precise mathematical formulation of his concept; however, it follows from his qualitative description, just considering members as criteria and positions as alternatives: a choice is ''optimal'' if any other choice improving the value of one criterion does worsen the value of at least another one; in his honor, these ''optimal'' choices are often called Pareto optima. However, these ideas had very little impact on mathematicians for a long time (a detailed account on historical developments of vector otimization can be found in the survey paper by Stadler). Some interest arose at the beginning of the fifties with Koopmans' paper on a multiobjective optimization model for the analysis of production activities and the pioneering paper by Kuhn and Tucker on nonlinear programming, in which the term vector optimization problem was introduced for the first time and some optimality conditions were discussed; only starting from the late sixties an increasing number of reaserchers devoted their efforts to study vector optimization.

The core of this dissertation is devoted to the discussion of optimality conditions for nonlinear vector optimization problems. Much work has been done on this topic, starting from the pioneering papers of Da Cuna and Polak, Borwein, Lin, Censor, Ben-Israel et al. and many others followed. The main focus has generally been on first order optimality conditions both for problems with smooth and nonsmooth functions or on saddlepoint type criteria; on the contrary, just a few papers developed a second order analysis. Another issue that seems to have not been deeply investigated is Lagrangian regularity, that deals with those conditions which guarantee multipliers rules to hold with nonzero multipliers corresponding to all or at least one of the objective functions. In the case of classical nonlinear optimization such conditions generally involve just the constraint and therefore they are usually referred to as constraint qualifications; on the contrary, conditions involving also the objective functions are often needed in the case of vector optimization.
A large part of Chapter 2 is devoted to the analysis of regularity conditions both for first and second order multipliers rules. In particular, not only very weak ones are presented but also those regularity conditions, which guarantee additional properties of multipliers such as boundedness and uniquess, are analysed. It is worth stressing that the focus of that chapter is on first and second order optimality criteria both for the classical problems, where the constraint is described by inequalities and equalities, and for those problems where the constraint is given just as a set. Actually, necessary optimality criteria are first developed for the latter case, exploiting suitable approximations of the constraint; these results allow to deduce multipliers rules and analyse regularity conditions for the former case quite easily. This procedure does not work for sufficient criteria and the relationships between the criteria developed for the two cases are investigated: quite surprisingly, the second order ones are completely unrelated.
Since the results of Chapter 2 require that functions are smooth, precisely differentiable or twice differentiable, Chapter 3 is devoted to optimality criteria for problems involving nonsmooth functions. Two different approaches are considered and compared: the first one relies on the components of vector functions so that well-known nonsmooth analysis tools for the real--valued case can be exploited; the second one is based on set--valued directional derivatives, which can be introduced considering suitable limits of vector incremental ratios without relying on components. The latter allows also to recover tools for vector functions such as generalized Jacobians and Hessians as particular cases and furthermore it provides sharper results than the former.
Finally, Chapter 4 deals with optimality criteria based on the saddlepoints of suitable Lagrangian functions. Though this issue has been deeply investigated, vector Lagrangians with multipliers associated to the objective functions have generally been disregarded. On the contrary, they allow to achieve stronger results and to recover those based on the saddlepoint of real Lagrangians as particular cases.

The thesis was sent out for evaluation on October, 2002. The referees have been Prof. Angelo Guerraggio (Università dell'Insubria) and Prof. Kathrin Klamroth (Universität Erlangen-Nürnberg). The thesis has been successfully defended on September 19, 2003. The committee was chaired by Prof. Franco Giannessi (Università di Pisa) and composed by Prof. Massimo Pappalardo (Thesis advisor), Prof. Fioravante Patrone (Università di Genova), Proff. Angelo Guerraggio and Kathrin Klamroth.

Download the .pdf file (1.2M) of the thesis:

Optimality and Lagrangian regularity in vector optimization

My Home Page