5ème CONGRES FRANCO-LATINOAMERICAIN DE MATHEMATIQUES APPLIQUEES

ABSTRACTS Existence and Uniqueness of the Competitive Equilibrium for Infinite Dimensional Economies

Elvio Accinelli

Instituto de Matemática, Universidad de la República Montevideo, Uruguay

                             elvio@fing.edu.uy

Abstract. In this paper we prove an existence of equilibrium theorem and we obtain a condition for the uniqueness of equilibrium in infinite dimensional economies using the excess utility function.

Classical versus homogenized minimizers in some optimal design problems

Grégoire Allaire

Université Paris 6, Laboratoire d’Analyse Numérique 75252 Paris Cedex 05, France

                           allaire@ann.jussieu.fr

Abstract. This talk will describe some joint works with Gilles Francfort and Véronique Lods concerning the existence of minimizers to some functionals, arising from optimal design problems in electrostatics and elasticity, with affine boundary conditions. More precisely, the motivation is to find the best possible arrangement of two phases that minimizes an energy criterion. These functionals are non quasiconvex, and therefore existence of minimizers is, in general, guaranteed only for their quasi-convex envelopes. Such a quasiconvexification can be computed by using homogenization theory. A careful analysis of its structure allows to give necessary and sufficient conditions on the affine boundary conditions for the existence of classical minimizers, i.e., minimizers for the original, non quasiconvex, functional.

Keywords. Optimal design, homogenization, quasiconvexity.

L^{p} approximation of variational problems in L^{1} or L^{∞} Selection of particular solutions

Hedy Attouch

Université Montpellier II, Département des Sciences Mathématiques Place E. Bataillon, 34095 Montpellier Cedex 05, France

                        attouch@math.univ-montp2.fr

Abstract. We shall describe two recent results related to the L^{p} approximation:

1. The Plateau problem (non parametric minimal surface problem) involves a functional with a linear growth at infinity, like an L^{1} functional, with, as a corollary, relaxation and non uniqueness phenomena. Classicaly, one uses a viscosity regularization method to approach it, but it is still an open problem to know if the sequence of solutions of the regularized problems converges. We propose an alternative regularization method based on the L^{p} approximation (as p goes to one) for which we can prove that the solutions of the approximate problems converge to a particular solution which can be characterized thanks to an entropy selection criteria. The method has some similarity with the theory of the natural median in statistics, as developped by Landers and Rogge.

2. Following a recent result of T. Champion, we show an example of a closed convex set in the three dimensional space for which the sequence of the projection of the origin for the L^{p} norm do not converge as p goes to infinity. Of course this is quite a pathological situation, we show too large classes of convex sets for which the sequence of the L^{p} projections do converge.

Monotone properties of the normal cone to the sublevel sets of quasiconvex functions.

Didier Aussel^{a} and Aris Daniilidis^{b}

a Lab. MANO, Université de PERPIGNAN 52 Avenue de Villeneuve, F-66860 PERPIGNAN Cedex, France

b Lab. Math. Appliquées, Université de Pau et des pays de l’Adour

Abstract. We explore the concept of the normal cone to the sublevel sets of a function. By slightly modifying the original definition of Borde & Crouzeix, we obtain a new notion of normal operator. This technique turns out to be an appropriate tool in quasiconvex analysis since it allows us to reveal characterizations of various classes of quasiconvex functions (namely quasiconvex, semistrictly quasiconvex and strictly quasiconvex) in terms of the generalized quasimonotonicity of their normal multifunction.

Keywords. Normal cone, quasiconvexity, quasimonotone map

A General Decrease Principle for Lower Semicontinuous Functions with Applications

D. Azé^{a}, J.-N. Corvellec^{a} and R.E. Lucchetti^{b}

aUniversité de Perpignan, Mathématiques 52 Avenue de Villeneuve, 66860 Perpignan CEDEX, France

                             aze@univ-perp.fr

bUniversità di Milano, Dipartimento di Matematica via Saldini 50, 20133 Milano, Italia.

Abstract. We give a general decrease principle for lower semicontinuous functions defined on complete metric spaces based on a quantitative version of Ekeland’s principle. Application are given to the good asymptotic behaviour of functions in the framework of general metric spaces, to parametric inverse function theorems and to the stability of a feasible set defined by a finite number of equalities and inequalities.

AMS subject classification. 49J52, 90C31.

Keywords. Decrase principle, good asymtotic behaviour, inversion theorems, multifunctions, feasible set.

Primal-Dual Convergence of the Steepest Descent Trajectory Associated with the Exponential Penalty

in Linear Programming^{1}

Jean-Bernard Baillon^{a} and Roberto Cominetti^{b}

aUniversité de Lyon I 43 bd du 11 Nov 1918, 69622 Villeurbanne Cedex,France

                      baillon@desargues.univ-lyon1.fr

bUniversidad de Chile, Departamento de Ingeniería Matemática Casilla 170/3, Correo 3, Santiago, Chile.

                           rcominet@dim.uchile.cl

Abstract. We study the asymptotic behavior of the evolution equation

u̇(t) = −∇f(u(t), r(t)),

where for r > 0, f(x, r) := c^{T}x + r ∑ exp[(A_{i}x − b_{i})/r] is the exponential penalty approximation of the linear program min{c^{T}x : Ax ≤ b}. We prove that for every function r(t) decreasing to 0, the solution u(t) converges towards an optimal point u^{∞} of the linear program. We also establish convergence of the associated dual trajectory μ_{i}(t) := exp[(A_{i}u(t) − b_{i})/r(t)] towards an optimal solution μ^{∞} of the dual of the linear program.

AMS subject classification. 34C35, 34D05, 49M10, 49M30, 90C25.

Keywords. Steepest descent, exponential penalty, linear programming.

1Supported by ECOS-Conicyt

University Admissions and Extensions The Admissions Polytope

Mourad Baïou and Michel Balinski

Universidad de Chile, Departamento de Ingeniería Matemática Casilla 170/3 Correo 3, Santiago, Chile.

                            baiou@dim.uchile.cl

Abstract. An admissions problem or admissions game (Γ, q) is specified by a directed graph Γ defined over a grid, and positive integers q, as follows. There are two distinct, finite sets of players, U = {u_{1}, u_{2}, …, u_{|U|}} (the “universities”) and A = {a_{1}, a_{2}, …, a_{|A|}} (the “applicants”), each player has a strict preference order over those players of the opposite set whom it, she or he considers to be acceptable, and each university u has a quota q_{u} of applicants it may accept.

The solutions of interest are the stable assignments: those feasible assignments having the property that no pair of agents u ∈ U, a ∈ A not matched can both improve their situations by being matched.

A new graphical characterization of stability leads to a description of the stable admissions polytope, the convex hull of the stable assignments expressed in terms of linear inequalities.

AMS subject classification. 90C27, 05C90, 52B10, 90D40

Keywords. stable assignment, stable marriage, two-sided market, polytopes, graphs, manyto-one matching.

University Admissions and Extensions Structure and Optimal Mechanisms

Michel Balinski and Mourad Baïou

CNRS et Laboratoire d’Econometrie, Ecole Polytechnique 1 rue Descartes, 75005 Paris, France

                       balinski@poly.polytechnique.fr

Abstract. An admissions problem or admissions game (Γ, q) is specified by directed graph Γ defined over a grid, and positive integers q, as follows. There are two distinct, finite sets of players, U = {u_{1}, u_{2}, …, u_{|U|}} (the “universities”) and A = {a_{1}, a_{2}, …, a_{|A|}} (the “applicants”), each player has a strict preference order over those players of the opposite set whom it, she or he considers to be acceptable, and each university u has a quota q_{u} of applicants it may accept.

The solutions of interest are the stable assignments: those feasible assignments having the property that no pair of agents u ∈ U, a ∈ A not matched can both improve their situations by being matched.

A graphical algorithm finds a reduced graph, containing all stable assignments, in which the applicant-optimal μ_{A} and university-optimal μ_{U} stable assignments are immediate. The fine structure of stable assignments shows that, contrary to current belief, the admissions problem is virtually equivalent to the marriage problem: there is a symmetry in the qualitative properties of the optimal stable assignments μ_{A} and μ_{U}. Each is characterized as the unique mechanism that is either “monotone,” “strategy-proof” or “Pareto optimal” on one side of the market.

AMS subject classification. 90C27, 05C90, 52B10, 90D40

Keywords. stable matching, college admissions, stable marriage, two-sided market, manyto-one matching,mechanism design, polytope.

A Global Quadratic Approach for Solving 0-1 Knapsack Problems^{1}

Oscar Barrientos^{a} and Martín Matamala^{b}

aSubgerencia de Planificación Nacional, ENDESA Santa Rosa 76, Santiago, CHILE.

                           obarrien@dim.uchile.cl

bUniversidad de Chile, Departamento de Ingeniería Matemática Casilla 170/3, Correo 3, Santiago, Chile.

                           mmatamal@dim.uchile.cl

Abstract. In this work, we show a method for solving the 0-1 knapsack problem based on the idea of (globally) minimizing a concave quadratic function. For solving the last problem, we use a branch and bound algorithm which uses Lagrangian duality for obtaining lower and upper bounds on each region of the branch. Moreover, we presente a technique for reducing the duality gap for a 0-1 concave quadratic linearly contrained problem.

From complexity viewpoint, we show that the algorithm developed for solving the global concave (continuous) problem runs out at the most 3 · 2^{n−2} − 1 iterations and we establishe that if the data are (partially) superincreasing then this complexity is exponentially reduced. Moreover, it is important to note that the number of regions stoked always is bounded by the dimension of the problem.

On the other hand, the implementation of the algorithm developed becomes very simple and we note that it may be accomplished on integer arithmetic. From the numerical results, we conclude that the proposed method is, on average, efficient.

Finally, we are working in showing that the method have polynomial average complexity and that it may be used for solving any 0-1 quadratic linearly constrained problem.

Keywords. Knapsack problems, NP-hard, concave quadratic programs, branch and bound methods, Lagrangian duality, complexity.

References.

[1] O. Barrientos and R. Correa, “An algorithm for global minimization of linearly constrained quadratic functions”, send to Journal of Global Optimization, 1996.

[2] A. Ben-Tal, G. Eiger and V. Gershovitz, “Global minimization by reducing the duality gap”, Mathematical Programming 63, pp. 193-212, 1994.

1This research was supported in part by FONDECYT-Chile, DIIT-CIMM and ECOS.

[3] J.J. Moré and S.A. Vavasis, “On the solution of concave knapsack problems”, Mathematical Programming 49, pp. 397-411, 1991.

[4] C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization, Prentice-Hall, Englewood Cliffs, NJ, 1982.

[5] S. Sahni, “Computationally related problems”, SIAM Journal on Computing 3, pp. 262-279, 1974.

Optimal Control of Problems Governed by Obstacle Type Variational Inequalities: a Dual Regularization-Penalization Approach

Maïtine Bergounioux^{a} and Helmut Dietrich^{b}

a Département de Mathématiques, Université d’Orléans B.P. 6759 - 45067 Orléans Cedex 2, France

                Maitine.Bergounioux@labomath.univ-orleans.fr

b Institute of Optimization and Stochastics, Martin-Luther-University of Halle-Wittenberg D-06099 Halle, Germany

Abstract. We investigate optimal control problems governed by variational inequalities of obstacle type that we can write in an abstract form :

(P)  min J(y, v) , ⟨T (y, v), z − y⟩ ≥ 0 ∀z ∈ K, y ∈ K, v ∈ U_{ad}

where V and U are Hilbert spaces, K and U_{ad} are non empty closed convex subsets of V and U respectively and T is an operator from V × U to V′. In addition J : V × U → IR ∪ {+∞} is a proper, convex and lower semicontinuous functional, supposed to be bounded below and Gâteaux-differentiable.

Introducing the dual regularized functional h_{α} : V × U → IR as

h_{α}(y, v) = sup_{z∈K} [⟨−αT (y, v), z − y⟩ − \frac{1}{2}∥z − y∥_{V}^{2} ] ,

which is C^{1} (but not convex), with α > 0, we prove that the original problem (P) is equivalent to

(P_{α})  min J(y, v) , h_{α}(y, v) = 0 , y ∈ K, v ∈ U_{ad}

Then, using penalization techniques and Ekeland’s variational principle we get optimality conditions. These first-order conditions are given in a weak form where no interior assumption on the set of constraints is required and a strong form under some additional conditions (which are satisfied for example in the finite-dimensional case.)

Lift and Project index relations on the Matching Polytope Problem

Aguilera, Nestor (1), Bianchi, Silvia (2), Nasini, Graciela (2)

(1) CONICET- Universidad Nacional del Litoral (Argentina) (2) Universidad Nacional de Rosario (Argentina)

(1) Guemes 3450 - 3000 Santa Fe - Argentina (2) Pellegrini 250 - 2000 Rosario - Argentina

                         sbianchi@fceia.unr.edu.ar

Abstract. We work on Lift and Project relaxations of combinatorial problems defined by Ceria-Balas-Cornuejols operator (BCC) and Lovasz-Schrijver operators (N and N^{+}). We explore the different Matching Polytope relaxations and we obtain a comparison for the complete graph of 2k + 1 vertices by showing that the N^{+}-index is k, whereas the BCC and N indeces are both k^{2}.

AMS subject classification. 90C35, 90C10, 90C27

Keywords. matching polytope, lift and project

Existence of Marginal Cost Pricing Equilibria in Economies with Externalities and non Convexities

Jean-Marc Bonnisseau

Université de Paris I, CERMSEM, Maison des Sciences Economiques 106-112 boulevard de l’Hopital, 75647 Paris Cedex 13, France

Abstract. We consider a model of an economy with production. To take into account the possibility of external effects, the consumption sets, the preferences and the production sets are represented by set-valued mappings which depend on the environment that is on the choices of the others agents. There is no convexity assumption on the production sets.

We define a concept of marginal cost pricing equilibria for which the firms follow a pricing rule which is defined with the Clarke’s normal cone. We prove the existence of an equilibrium. Contrary to the case without externalities, we need an additional assumption on the production set in order to obtain a pricing rule with a closed graph.

This result generalizes previous works on economies with externalities and convex production sets and on economies without externalities.

Parallel Algorithms for M-Huber Estimation

M.L. Bougeard

Université de Lyon 1, UFR Mathématiques 43 bd 11 Novembre 1918, 69622 Villeurbanne cedex, France

and

URA 1125 CNRS/IERS, Paris Observatory, 75014 Paris, France

                          bougeard@hpvlbi.obspm.fr

Abstract. In this paper, we are presenting highly parallel algorithms for robust M-HUBER estimation. The efficient implementation on a parallel computer architecture is described. Remnedies are introduced to ensure efficency in case of models with less than full ranks. A variety of linear and non-linear restrictions is discussed. Numerical simulations are reported.

AMS subject classification. 47H05,49M27, 49N15, 62F12, 62F35,62J07, 90C25

Keywords. Huber-M estimator, parallel processing, proximal decomposition

Un algoritmo de optimización basado en ε-gradientes

Manuel Bustos^{a}, Víctor Alvarado^{a} y Raúl Aguila^{b}

aU. Austral de Chile, Facultad de Ciencias, Instituto de Matemáticas

                        mbustos@valdivia.uca.uach.cl

bU. Católica de Valparaiso, Instituto de Matemáticas

Abstract. En esta comunicación los autores presentan un algoritmo de optimización para programas no lineales con datos semisuaves. Este algoritmo, que genera una sucesión convergente a un punto ε-optimal del problema, se basa en gradientes aproximados para funciones localmente lipschitzianas. Se exponen los resultados de convergencia para el caso irrestricto como también resultados computacionales.

Referencias.

[1] Bustos M., Epsilon-gradients pour les fonctions locallement lipschitziennes. Num. Funct. Anal. and Optimiz., 15 (3 & 4), 435-453 (1994).

[2] Lemaréchal C., Bundle methods in Nonsmooth Optimization. Nonsmooth Optimization, Proc.of IIASA Workshop, 79-102. C.Lemaréchal, R. Mifflin Editors, Pergamon Press (1977).

[3] Mifflin R., An algorithm for Unconstrained Optimization with Semismooth Functions. Math.of Oper. Research, vol.2, 191-207 (1977).

[4] Wolfe P., A Method of Conjugated Subgradients for Minimizing Nondifferentiable Functions. Nondifferentiable Optimization, Math.Progr. Study 3, 145-173 (1985)

Some reformulations for some lot-sizing problems

Miguel Constantino^{a} and Luis Gouveia^{b}

aDepartamento de Ingeniería Industrial, Universidad de Chile and Centro de Investigaçao Operacional, Universidade de Lisboa

                mconstan@dii.uchile.cl, miguel@deio.fc.ul.pt

bCentro de Investigaçao Operacional, Universidade de Lisboa

                             lgouveia@fc.ul.pt

Abstract. The linear relaxation of a mixed integer program P is the problem P̄ obtained by dropping the integrality constraints from P. P̄ can be used to obtain bounds for the optimal value of P, but in many cases these bounds are too far from this optimal value to be useful. One way to strengthen the bounds is to reformulate the problem by adding a new set of variables.

Here we consider the following reformulation: for each continuous variable x taking values in some set V, define new variables as x^{p} = 1 if x = p and x^{p} = 0 otherwise, for p ∈ V. In general, this reformulation has too many variables and does not give better bounds than the original one.

In this talk we show how to reduce the number of variables and strengthen the bounds for some lot-sizing problems, using some well known extreme point properties for these problems.

Keywords. Mixed integer programming, reformulation, lot-sizing, extreme point, valid inequality, lot-sizing.

Proximal solutions of some generalized minmax locations problems

Oscar Cornejo^{a} and Christian Michelot^{b}

aDepartamento de Ingeniería de Sistemas, Universidad de Talca, Chile

bLaboratoire de Analyse Apliquée et Optimisation, Dijon, France.

Abstract. The aim in this paper is to study the proximal solution of continuous location problems. Here we consider the minmax location problem. This problem has a convex set of non-linear constraints which can be split up in two sets, but the constraints in the two sets remain linked. Thus, the problem may be written in term of the indicator function on the epigraph of the distance function.

In order to obtain the optimality conditions, we use Fenchel’s duality, and thus write the original problem in terms of the normal cone on the epigraph. To solve the optimality conditions and then to explicit an optimal solution, is necessary to find a vectors set in the intersection of two sets, one of them is the graph of operator T and the other one is a subspace. However as the graph of operator T is not a convex, hence it is not posssible to use a method like successives projections. So, we shall use the partial inverse method developed by J. E. Spingarn, in order to avoid that projection, thus, we replace the projection by a proximal step. On the other hand, we shall show that the projection onto a vector subspace is easily calculable.

Numerical experiences will be developed using this algorithm. Here, the problem considered is that of finding the location of a facility in the plane so that the maxi-mum weighted rectilinear round-trip distance between the facility and N pairs of existing facilities is minimized.

Variational Inequalities Problems Linear Complementarity

Jean-Pierre Crouzeix

CUST, Université Blaise Pascal BP 206, 63174 Aubière cedex, France

                     crouzeix@ucfma.univ-bpclermont.fr

Abstract. We are concerned with the VIP problem:

Find x ∈ C and x^{∗} ∈ F (x) such that ⟨x^{∗}, y − x⟩ ≥ 0 for all y ∈ C.

Here we assume that C is convex and closed, F is a point-to-set map. Classical existence theorems require some continuity on the map F and some compactness (coercivity) assumption on C and F. In fact, these results do not require any monotonicity on the map.

We present here new results when F presents mononicity-type conditions. These conditions are related, in some way, to the famous inf-compactness condition 0 ∈ int(domf^{⋆}) for the problem of minimizing a closed convex function. Thus, they can be considered as of dual type.

In a second part, we present new results on the linear complementarity problem.

AMS subject classification. 90C

Keywords. Variational Inequalities Problems, Existence of Solutions, (Generalized) Monotonicity, Linear complementarity Problems

Approximating the Network Loading Problem by Trees

Rafael Epstein^{a} and Thomas L. Magnanti^{b}

aUniversidad de Chile, Departamento de Ingeniería Industrial Santiago, Chile

bMassachussets Institute of Technology, U.S.A.

Abstract. The Network Loading Problem (NLP), a particular case of a broad class of combinatorial problems known as Network Design problems, arises in many application contexts in telecommunication, transportation, and other industries. The NLP seeks a minimum cost network design that is capable of simultaneously routing prescribed demands between pairs of nodes. A feasible network can use any integer combination of different capacitated facilities. Each installed facility has an edge-dependent cost. There is no routing cost. We consider special cases with only one and two facilities: SF LP and T F LP.

We present a family of heuristic algorithms, called Cut-Tree algorithms, that generate tree solutions for the NLP. We show that a special Greedy-Cut-Tree version of the algorithm, which loads an approximately cheapest edge on an approximately most violated cut, generates a tree solution with an O(n) performance guarantee for problems with n nodes.

Using a relaxation of the SF LP that incorporates known cutset and aggregate capacity demand inequalities from the literature, we develop a primal-dual algorithm, which we call the Large-Cut-Primal-Dual algorithm, that generates a tree solution with an O(n) performance guarantee. In selected examples, this primal-dual algorithm and the Greedy-Cut-Tree algorithm exhibit complementary behavior: the Large-Cut-Primal-Dual algorithm achieves its worst performance when the Greedy-Cut-Tree algorithm finds the optimal solution and conversely. We extend the Large-Cut-Primal-Dual algorithm for the T F LP case with the same performance guarantee. We also present another primal-dual algorithm, that routes the demand on a minimum spanning tree, and provide another lower bound for the SF LP.

Optimal solutions to some variational problems arising in Economics

Fabian Flores-Bazán

Universidad de Concepción Departamento de Ingenieria Matemática

                          fflores@ing-mat.idec.cl

Abstract. Some variational problems arising in Economics are studied. The first problem refers to an allocation process for a continuum of traders in an economy with production in the absence of the convexity condition. The second problem regards a contnuius-time allocation process related to a consumption program without the concavity condition. In both cases some economic parameters are considered. We add to the usual constraint one of “unilateral-type”. We prove existence of optimal planning for the two problems. This is carried out by applying a result recently established in a previous work. Part of these results is joint work with Jean Pierre Raymond.

Mécanique et Mathématiques des Collisions de Solides Rigides

C. Cholet and M. Frémond

Ecole Nationale des Ponts et Chaussées Laboratoire des Matériaux et des Structures du Génie Civil Cité Descartes, 2 allée Kepler, 77420 Champs sur Marne, France

Abstract. Considérons un solide rigide, par exemple un rocher qui se meut au dessus d’un plan fixe. Bien que les éléments constituant le système solide-plan soient rigides, le système est déformable puisque la position du solide par rapport au plan change. Cette idée est développée. Elle conduit à introduire des efforts intérieurs nouveaux: des percussions qui décrivent ce qui se passe lors d’une collision entre le solide rigide et le plan.

La théorie donne une solution au problème complexe des chocs multiples. Ces chocs sont des collisions simultanées, par example collisions en deux points différents du solide rigide avec le plan ou collisions de billes alignées.

Les équations du mouvement du solide rigide sont bien posées dans des espaces de fonctions à variation bornées. Un théorème d’existence peut être démontré dans certaines circonstances. Des méthodes d’approximation numériques convenables sont mises en œuvre.

Solving box constraint problems without computing derivatives: A survey and a new proposal

Ubaldo Garcia-Palomares

Universidad Simon Bolivar, Departamento de Procesos y Sistemas Apartado 89000, Caracas 1081-A, Venezuela

                              garciap@usb.ve

Abstract. Box constraint optimization problems are found many times in real applications. Lagrangian techniques transform a constrained problem in an unconstrained problem (or in a box constraint problem). Nonetheless, the algorithmic process can become intractable. No differentiability, inaccuracy of the function values, unavailability of function/gradient values can render useless many algorithms that need an exact computation of first derivatives. It is therefore convenient to have at hand free derivative optimization algorithms. In this work we give an oveview of existing methods pointing out their advantages and drawbacks. We end with a new proposal that tries to take into account the main features of known algorithms. Quadratic interpolation, polytope (simplex) method and multidimensional techniques are put together with a modification of the Armijo rule to ensure convergence to an almoststationary point.

Strong Duality for Inexact Linear Programming^{1}

Jorge Amaya^{a} and Juan A. Gómez^{b}

aUniversidad de Chile, Departamento de Ingeniería Matemática Casilla 170/3, Santiago, Chile

                           jamaya@dim.uchile.cl

bInstituto de Cibernética, Matemática y Física, CIMAT Calle E, 309, Vedado, Ciudad Habana, Cuba

                         jagomez@cidet.icmf.inf.cu

Abstract. In this work, we apply the Dubovitskii-Milyutin approach to derive strong duality theorems for inexact linear programming problems. Inexact linear programming deals with the standard linear problem in which the data is not well known and it is supposed to lie in certain given convex sets. The case of parametric dependence of the data is particularly analyzed and relations with semi-infinite and semi-definite programming are also commented.

AMS subject classification. Primary: 90C08, 90C05. Secondary: 90C31.

Keywords. Inexact Linear Programming, Parametrized Data, Strong Duality, Dubovitskii-Milyutin approach.

1This research has been partially supported by DID-Universidad de Chile and CONICYT, through FON-DAP en Matemáticas Aplicadas and Programa de Cooperación Científica Internacional. The second named author is partially supported by UMALCA.

New Optimization Formulations for Computing Eigenelements of Symmetric Matrices

Jean-Baptiste Hiriart-Urruty, M. Mongeau and M. Torki

Université Paul Sabatier Laboratoire “Approximation et Optimisation” Toulouse, France

                               jbhu@cict.fr

Abstract. In certain circumstances, it is more advantageous to use an optimization approach in order to solve the generalized eigenproblem Ax = λBx, where A and B are real symmetric matrices and B is positive definite. This is the case namely when the matrices A and B are very large and the computational cost of solving systems of equation involving these matrices is prohibitive. The optimization approach involves usually optimizing the Rayleigh quotient.

We propose alternative objective functions to solve the generalized eigenproblem via (unconstrained) optimization. We describe the variational properties of these functions and we motivate the use of these functions with comparative numerical experiments emphasizing the fact that they yield results superior to those obtained with the Rayleigh quotient. We also introduce variational principles that can be used in order to compute the condition number and the width of the spectrum of a real symmetric matrix via (unconstrained) optimization.

Règles du premier ordre en optimisation non lisse avec contraintes

Marc Lassonde

Université des Antilles et de la Guyane, Département de Mathématiques 97159 Pointe-à-Pitre Cedex, Guadeloupe, France.

                          Marc.Lassonde@univ-ag.fr

Abstract. We consider first-order necessary conditions for minimizing sums of lower semicontinuous functions. We first show that rules of this type are equivalent to several basic principles of subdifferential calculus, in the line of recent works of Zhu and Ioffe. We next prove that such rules hold in large classes of spaces having appropriate smoothness properties with respect to the given subdifferential. Our considerations do not depend on any specific subdifferential.

Résumé. Dans ce qui suit, X désigne un espace de Banach réel, X^{∗} son dual topologique, et ⟨·, ·⟩ le crochet de dualité. Les lettres f, g, f_{i} dénotent des fonctions semi-continues inférieurement de X dans IR ∪ {+∞} tandis que φ dénote des fonctions plus régulières de X dans IR. Étant donné un sous-différentiel ∂, on pose ∂f = {(x, x^{∗}) ∈ X × X^{∗} | x^{∗} ∈ ∂f(x)}.

La condition nécessaire du premier ordre pour un minimum local sans contrainte :

(UR0) Si f admet un minimum local fini en x_{0} ∈ X, alors 0 ∈ ∂f(x_{0}),

est vérifiée de façon banale dans tout espace de Banach et pour tout sous-différentiel. La version approchée de cette règle :

(UR1) Si inf_{X} f est fini et si (x_{n})_{n} est une suite dans X telle que f(x_{n}) → inf_{X} f, alors il existe une suite (x̄_{n}, x̄_{n}^{∗})_{n} ⊂ ∂f telle que

∥x̄_{n} − x_{n}∥ → 0, f(x̄_{n}) → inf_{X} f, et x̄_{n}^{∗} → 0 ,

n’est, elle, pas banale (elle résulte d’un principe variationnel) et n’est vraie que dans les Banach ayant des propriétés de lissité par rapport au sous-différentiel considéré.

Qu’en est-il des règles concernant les problèmes de minimisation avec contraintes, ou, de façon équivalente, des règles concernant des sommes de fonctions? Dans ce contexte, il est connu que même la condition nécessaire du premier ordre pour un minimum local ne peut (en général) avoir qu’une forme approchée (“fuzzy”) et, de plus, ne peut avoir cours que dans les Banach ayant des propriétés de lissité par rapport au sous-différentiel considéré. Une de ces règles, parmi les plus simples, dit ceci :

(R1) Si f + φ atteint un minimum local fini en x_{0} et φ est convexe Lipschitz, alors il existe des suites (x̄_{n}, x̄_{n}^{∗})_{n} ⊂ ∂f et (ȳ_{n}, ȳ_{n}^{∗})_{n} ⊂ ∂φ telles que

x̄_{n} → x_{0}, ȳ_{n} → x_{0}, f(x̄_{n}) → f(x_{0}), φ(ȳ_{n}) → φ(x_{0}),

x̄_{n}^{∗} + ȳ_{n}^{∗} → 0 .

On sait que cette règle est vérifiée dans tout Banach, pour le sous-différentiel approché de Ioffe, et dans les Banach ayant une fonction bosse β-lisse, pour le β-sous-différentiel. Bien sûr, cette règle ne recouvre pas la règle familière (UR0) : on a déjà dit que c’est sans espoir. Mais elle ne recouvre pas non plus sa version approchée (UR1), bien que leurs formulations soient similaires et que toutes deux soient vraies dans le même type d’espaces.

Notre objectif est de formuler des règles qui contiennent (R1) et (UR1) et qui sont vérifiées dans de vastes classes d’espaces incluant les exemples ci-dessus. Pour exprimer proprement de telles règles, il est particulièrement commode d’utiliser la quantité suivante, appelée borne inférieure uniforme de la famille {f_{1}, …, f_{k}},

r_{X}(f_{1}, …, f_{k}) := lim_{δ→0} inf{ ∑_{i=1}^{k} f_{i}(x_{i}) | diam(x_{1}, …, x_{k}) ≤ δ },

plutôt que la borne inférieure algébrique usuelle. Dans notre contexte, une condition de qualification reviendrait à supposer a priori que les bornes inférieures uniformes et algébriques coïncident; il s’avère cependant que ceci n’est pas nécessaire.

Nous étudions sept règles du premier-ordre incluant (R1) et des généralisations de règles dues à Deville-El Haddad, Borwein-Zhu, Clarke-Ledyaev, etc. La plus frappante est certainement celle-ci :

(R5) Si r_{X}(f_{1}, …, f_{k}) est fini et si (x_{i,n})_{n} ⊂ X, i = 1, …, k, sont k suites telles que diam(x_{1,n}, …, x_{k,n}) → 0 et ∑_{i=1}^{k} f_{i}(x_{i,n}) → r_{X}(f_{1}, …, f_{k}), alors il existe k suites (x̄_{i,n}, x̄_{i,n}^{∗})_{n} ⊂ ∂f_{i}, i = 1, …, k, telles que

(i) ∥x̄_{i,n} − x_{i,n}∥ → 0, |f_{i}(x̄_{i,n}) − f_{i}(x_{i,n})| → 0, pour i = 1, …, k;
(ii) ∑_{i=1}^{k} x̄_{i,n}^{∗} → 0 ;

(iii) diam(x̄_{1,n}, …, x̄_{k,n}) ∑_{i=1}^{k} ∥x̄_{i,n}^{∗}∥ → 0.

Nous montrons que ces règles sont équivalentes dans le sens suivant : si une règle est vraie dans X^{N} pour tout naturel N, alors les autres aussi. Ce résultat est motivé par des travaux récents de Zhu et Ioffe sur l’équivalence de divers principes sous-différentiels. Nous ajoutons sept nouvelles règles à leur liste d’équivalences et nous montrons que toutes ces règles ont effectivement cours dans les Banach ayant une renorme ∂-lisse, lorsque ∂ est un sous-différentiel arbitraire, et dans les Banach ayant une fonction bosse β-lisse, lorsque ∂ est le β-sous-différentiel. Ainsi, notre but est atteint : la règle (R5) contient à la fois (R1) et (UR1) et est valide pour des sous-différentiels et des classes d’espaces plus vastes que ceux mentionnés ci-dessus.

Dynamical approach to some variational problems

Bernard Lemaire

Université Montpellier Place E. Bataillon, 34095 Montpellier Cedex 05, France

                    lemaire@darboux.math.univ-montp2.fr

Abstract. The talk proceeds into two main parts.

The first part is concerned with a variant of the theorem of Bruck on the asymptotic convergence of a nonlinear contraction semigroup in a Hilbert space. Namely, let H be a real Hilbert space and {A(λ)} be a family of uniformly cocoercive operators on H depending pointwise continuously upon λ on the compact space Λ and such that every A(λ) has the same zero set S. Let u be the solution to the differential equation

−\frac{du}{dt}(t) = A(λ(t)) u(t), t > 0, u(0) ∈ H

where λ(t) is a continuous parametrization. If S is nonempty then the weak asymptotic limit of u(t) exists and belongs to S.

The second part is devoted to a variant of the Attouch-Cominetti’s approach. Let {A, A_{n}}, n = 1, 2, ... be maximal monotone operators on H such that, for every n, A_{n} is β_{n}-strongly monotone and {D(A_{n})} is nondecreasing. Let {α_{n}} be a sequence of positive reals. For every n = 1, 2, ..., let u_{n} be the solution to the differential inclusion

−\frac{du_{n}}{dt} (t) ∈ A_{n}u_{n}(t), t_{n−1} ≤ t ≤ t_{n}, u_{n}(t_{n−1}) := u_{n−1}(t_{n−1})

where t_{n} is determined iteratively (with t_{0} := 0 and u_{0}(0) ∈ D(A_{1})) so that

∥u_{n}(t_{n}) − u_{n}∥ ≤ α_{n}/β_{n}

where u_{n} is the zero of A_{n}. As t_{n} is nondecreasing, t_{n} converges to some t̄ ≤ +∞. So, denoting by u the trajectory which coincides with u_{n} on the interval [t_{n−1}, t_{n}], if α_{n}/β_{n} → 0 and if u_{n} → u^{⋆} a particular zero of A, then lim_{t→t̄}u(t) = u^{⋆}.

In the two parts applications to finding a zero of a maximal monotone operator or a fixed point of a nonexpansive mapping via regularization techniques as well as connexions with discrete versions are considered.

AMS subject classification. 65K10, 49J40, 49M10.

Keywords. Approximation, dynamical system, fixed point, iteration, monotone, nonexpansive, regularization, staircase iteration, variational inequality.

Bicriteria optimization with quasimonotonic objectives

C. Malivert and N. Popovici

Université de Limoges, LACO-Optimisation ESA-CNRS 6090 123, avenue Albert Thomas, 87060 Limoges, France

                            malivert@unilim.fr

Abstract. We introduce the class of quasimonotonic functions, which contains in particular all fractional linear functionals. The elements in this class enjoy good properties as quasiconvexity, quasiconcavity and their level sets are hyperplans. It follows that every optimization problem of such a function over a polytope admits at least a vertex as a solution. Then we consider a bicriteria problem with quasimonotonic objectives and linear constraints. In general such a problem has solutions which belong to the interior of the polytope. However it turns out that the efficient outcome can be obtained by simply considering the edges of the polytope. Using this fact we present a method for finding all efficient values of the problem.

AMS sbject classification. 90C31, 90C32

Keywords. Multiple objectives, Efficient sets.

On Some Basic Principles in Variational Analysis

Boris S. Mordukhovich

Wayne State University, Department of Mathematics Detroit, Michigan 48202

                           boris@math.wayne.edu

Abstract. We study relationships between certain basic principles in variational analysis and its applications to nonsmooth calculus and optimization. In the case of Banach spaces admitting Lipschitzian and Fréchet differentiable bump functions, we establish the equivalence between useful versions of the smooth variational principle for lower semicontinuous functions, the extremal principle for nonconvex sets, and the fuzzy sum rule for subdifferentials. Under some modifications, this result is extended to the case of smooth bornological spaces in terms of viscosity normal cones and subdifferentials with controlled rank. We present also new characterizations of Asplund spaces in the framework of variational analysis and discuss some applications.

Interior Point Algorithms for Decomposition of Dantzig-Wolfe

P. R. Oliveira^{a} and M. A. dos Santos^{b}

aUniversidade Federal do Rio de Janeiro, COPPE/SISTEMAS CP 68511, 21945-970 Rio de Janeiro, Brazil

                           poliveir@cos.ufrj.br

bUniversidade Federal de Minas Gerais - DCC - ICEx

Abstract. The Dantzig-Wolfe’s decomposition principle gave rise to a family of algorithms in which the efficient solution of large scale problems was expected. Although having an attractive idea of distribution and a decentralization schema, it has poor convergence; most of the effort gained on solving easy sub-problems is wasted due to a high number of iterations between the master program and the parts. Moreover, in the case of linear programming problems, the simplex, until now an important technique for solving the sub-problems, casually produces high computational times. Nevertheless, for some families of problems, the later drawback could be substantially reduced by using interior point algorithms (IPA). But this substitution does not solve the possibly large number of external iterations. In order to attack those difficulties, an interesting approach is the using of sub-optimal solutions in the sub-problems. In this paper we propose a new algorithm where IPA is used in both decomposition levels, and sub-optimal solutions are produced, depending on a certain improvement test. One major class of IPA is the analytic center method. It closely adapts to the cutting plane method which plays a central role in decomposition schemes. We apply a partial analytic center method to the problems originated from the Dantzig-Wolfe’s decomposition principle to linear programming. We present two algorithms; one of them demands optimal solutions of the sub-problems and the other admits sub-optimal solutions. Both solve partially the master problem at each iteration.

Keywords. Decomposition of Dantzig-Wolfe. Analytic Center Method. Nonsmooth Optimization.

Equilibrium with Default and Endogenous Collateral

Aloisio Araujo^{a}, Jaime José Orrillo^{a} and Mario Páscoa

a Instituto de Matemática Pura e Aplicada Estrada Dona Castorina 110, 22460-320 Rio de Janeiro, RJ BRAZIL

b Faculdade de Economia, Universidade Nova de Lisboa Travessa Estevão Pinto, 1070, Lisboa, PORTUGAL

Abstract. We study a general equilibrium model with incomplete asset markets and default. We make collateral endogenous by allowing each seller of assets to fix the level of collateral. We prove that equilibrium always exists if sellers are required to provide collateral whose value, per unit of asset, exceeds the asset price, by an arbitrarily small amount. We use a spread that penalizes the borrowers( sellers of assets) who incur in default and benefits the lenders ( buyers of assets) who suffer default. The spread we consider is a linear function on the portfolio.

Keywords. Incomplete Markets; Asset Promises; Collateral; Spread.

On the Uncapacitated Fixed Charge Network Flow Problem.

Francisco Ortega and Laurence A. Wolsey

CORE- Université Catholique de Louvain 34, Voie du Roman Pays, B-1348 Louvain-La-Neuve, Belgium.

                           ortega@core.ucl.ac.be

Abstract. In this talk we will present a study concerning the polyhedral structure of the Fixed Charge Network Flow Problem. In particular, we will explain how the Path Inequalities and the Cut set inequalities work and we present some fractional solutions that can not be “cutted off” using these inequalities. Additionally, we present a review on valid inequalities and strong formulations related to this problem.

Keywords. Fixed charge networks, mixed integer programming, cutting planes, network design.

Nonconvex Dualities and Hamilton-Jacobi Equations

Jean-Paul Penot

Université de Pau et Pays de l’Adour, Pau, France

                        Jean-Paul.Penot@univ-pau.fr

Abstract. We consider various dualities which play a role in what can be called “quasiconvex analysis”. Using classical convergence notions we use these dualities to get regularization processes for functions. In particular, we focus our attention to a regularization procedure via a sub-level convolution. This operation has been extensively used during the last few years. It is particularly adapted to quasiconvex functions. We evoke its use for solving Hamilton-Jacobi equations.

[1] D. Azé and M. Volle, A stability result in quasi-convex programming, J. Optim. Th. Appl. 67 (1) (1990), 175-184.

[2] A. Barbara, J.-P. Crouzeix, Concave gauge functions and applications, Zeitschrift für Operations Research, 40 (1994), 43–74.

[3] E.J. Balder, An extension of duality-stability relations to non-convex optimization problems, SIAM J. Control Opt. 15 (1977), 329-343.

[4] E.N. Barron and W. Liu, Calculus of variations in L^{∞}, Applied Math. Opt. 35 (1997), 237-243.

[5] E.N. Barron, R. Jensen and W. Liu, Hopf-Lax formula for u_{t}+ H(u, Du) = 0. J. Differ. Eq. 126 (1996), 48-61.

[6] E.N. Barron, R. Jensen and W. Liu, Hopf-Lax formula for u_{t}+ H(u, Du) = 0 II, to appear in Comm. P.D.E.

[7] E.N. Barron, R. Jensen and W. Liu, Applications of Hopf-Lax formula for u_{t}+ H(u, Du) = 0, to appear in SIAM J. Math. Anal.

[8] J.-E. Martinez-Legaz and I. Singer, Subdifferentials with respect to dualities, ZOR- Math. Methods Oper. Res. 42 (1995), 109-125.

[9] J.-P. Penot, Are generalized derivatives useful for generalized convex functions?, in “Generalized convexity and generalized monotonicity”, J.-P. Crouzeix et al. eds., Kluwer, Dordrecht (1998), 3-59.

[10] J.-P. Penot, What is quasiconvex analysis?, in preparation

[11] J.-P. Penot and C. Zălinescu, Regularization of quasiconvex functions, in preparation.

[12] A. Seeger, M. Volle, On a convolution operation obtained by adding level sets: classical and new results, Recherche Opérationnelle 29 (1995), 131-154.

[13] S. Traore and M. Volle, Quasi-convex conjugation and Mosco convergence, Richerche di Mat. 44 (2) (1995), 369-388.

[14] S. Traore and M. Volle, Dualité pour la minimization du maximum de deux fonctions convexes: applications à la somme en niveaux des fonctions convexes, preprint, Univ. of Avignon, (1996).

[15] M. Volle, Duality for the level sum of quasiconvex functions and applications, ESAIM: Control, Optimisation and Calculus of Variations, URL: http://www.emath.fr/cocv/

[16] C. Zălinescu, Mathematical programming in infinite dimensional normed linear spaces (Rumanian) Editura Academiei, Bucharest (1998), French translation to appear.

Dynamical adjustment of the penalization parameter in the variable metric proximal bundle method

Pablo Andrés Rey

Depto. de Engenharia Eletrica, PUC-Rio R. Marques de Sao Vicente 225, Caixa Postal 38063 22452-970 Rio de Janeiro, Brazil

Abstract. To minimize a convex function, we combine Moreau-Yosida regularizations, quasi-Newton “poor-man” matrices and bundling mechanisms as in C. Lemarechal and C. Sagastizabal, Variable metric bundle methods: From conceptual to implementable forms, Mathematical Programming 76(1997) 393-410.

At every iteration, to compute a candidate to become a serious step we solve the following prox-subproblem

argmin_{y∈IR^{N}} \{f̌_{k}(y) + \frac{1}{2}μ_{n}(y − x)^{⊤}(y − x)\} ,

When the cutting plane model f̌_{k} is rich enough, a serious step is x_{n+1} declared To update the metric, i.e., the prox-parameter μ_{n}, after each serious step, we use a

“reversal” quasi-Newton formulæ. More precisely, instead of making the standard choice (fix u, then compute v), we first fix the difference of gradients v and then we invert the proxoperator to deduce the corresponding u. Having defined v as any difference of subgradients of f at x_{n} and x_{n+1}, because ξ = x_{n+1} − x_{n} , we directly have

u = ξ + μ_{n}^{−1}v .

This results in following the quasi-Newton update for the prox-parameter

\frac{1}{μ_{n+1}} = \frac{v^{⊤}ξ}{|v|^{2}} + \frac{v^{⊤}(μ_{n}^{−1}v)}{|v|^{2}} = \frac{v^{⊤}ξ}{|v|^{2}} + \frac{1}{μ_{n}} .

The formula has many advantages, first of all, it is explicit and requires no extra proxcomputation. Also, a wide variety is available for v. Indeed, when the n^{th} iteration of an algorithm is completed, we always have on hand g(x_{n}) ∈ ∂f(x_{n}) and g(x_{n+1}) ∈ ∂f(x_{n+1}); but we also have the subgradients G_{n−1} ∈ ∂f(x_{n}) and G_{n} ∈ ∂f(x_{n+1}). Thus, we can take

v := γ = g(x_{n+1}) − g(x_{n}) ,

or

v := G_{n} − G_{n−1} ,

or any convex combination. Among the infinitely many other choices using convex sums, we choose the one giving the smaller μ_{n+1}.

To assess our approach, we report some numerical illustrations.

Improved Tabu Search for the Steiner Problem in Graphs

Celso C. Ribeiro and Maurício C. de Souza

Department of Computer Science Catholic University of Rio de Janeiro Rio de Janeiro, RJ 22453-900, Brazil

                           celso@inf.puc-rio.br

Abstract. Given an undirected graph with weights associated with its nodes, the Steiner tree problem consists in finding a minimum weight subgraph spanning a given subset of nodes (terminals) of the original graph. In this work, we describe an improved tabu search algorithm for the Steiner problem in graphs, based on a neighborhood defined by insertions and eliminations of Steiner nodes. Move estimations, elimination tests, and neighborhood reduction techniques are used to speedup the local search, leading to a very fast algorithm with very good results in terms of solution quality. Computational experiments on benchmark problems are reported, comparing the behavior of the improved tabu search with that of other heuristics from the literature. The improved tabu search algorithm clearly outperforms other heuristics in terms of computation times, obtaining better or comparably good solutions.

Keywords. Combinatorial optimization, Steiner problem, graphs, local search, metaheuristics, tabu search.

The equilibrium manifold with boundary constraints on the consumption sets

Jean-Marc Bonnisseau^{a} and Jorge Rivera^{b}

aUniversité de Paris I, CERMSEM

bDepartamento de Ingeniería Matemática, Universidad de Chile

Abstract. In this paper we study the equilibrium manifold in a pure exchange economy with a finite number of consumers and commodities, where there exists an initial restriction for the consumption of each agent. We show that the demand function is a locally Lipschitzian and almost everywhere continuously differentiable mapping. Using an adapted definition of regularity, we show the following results : the set of regular economies is open and of full measure; for each regular economy, there exists a finite odd number of equilibria; for each given regular economy and equilibrium price, there exists a local differentiable selection of the equilibrium price correspondence which associates the given price vector to the economy.

In other words, the presence of boundary constraints does not change the properties of the exchange economies.

AMS subject classification.

Keywords: demand functions, equilibrium manifold, critical equilibriums.

Second-Order Nonsmooth Analysis

R.T. Rockafellar

University of Washington, Department of Mathematics Seattle, Washington, U.S.A.

                          rtr@math.washington.edu

Abstract. In first-order nonsmooth analysis, the key concepts on the geometric level have been those of tangent cone and normal cone, along with the full or partial duality relations between them. On the level of functions, everything has revolved analogously around subderivatives and subgradients, whereas for set-valued mappings it has been graphical derivatives and coderivatives. In second-order nonsmooth analysis, however, the picture is less settled and the search for fundamental patterns is still going on.

One idea has been to investigate various kinds of generalized second-order directional derivatives, along curves as well as along lines. This has uncovered second-order Lipschitz properties and, in the study of limits of difference quotients, led to the consideration not only of pointwise limits but also of epigraphical limits. Another idea has been to generate second derivatives of a function through first derivatives of its subgradient mapping, with these being taken in the graphical sense. The two approaches have turned out more than just complementary; they have deep and important connections with each other.

The use of second-order concepts is further being explored in optimality conditions and the stability of solutions under perturbations. Much has been learned, but many open questions remain.

A note on level-continuity of functions^{1}

Heriberto Román-Flores^{a} and Marko Rojas-Medar^{b}

aUniversidad de Tarapacá, Departamento de Matemática Casilla 7D, Arica, Chile

                          hroman@vitor.faci.uta.cl

bIMECC-UNICAMP, CP6065, 13081-970, Campinas-SP, Brasil.

Abstract. In this work, we study the concepts of level-continuity and proper local maximum points of functions defined on a regular topological space X and, on the one hand we stablish that, under adequate conditions, f is level-continuous iff f is without proper local maximum points and, on the other, we prove that level-convergence (L-convergence) and variational convergence (Γ-convergence) of functions are equivalents when the limit function is levelcontinuous. More precisely, we prove the following results

Theorem 1. Let f : X → [0, ∞) be with sup_{x∈X} f(x) = M. If f is upper semicontinuous, then the following are equivalent:

(i) f is without proper local maximum points

(ii) \{f ≥ α\} = \overline{\{f > α\}}, ∀ α ∈ (0, M).

(iii) f is level-continuous.

Theorem 2. Let f_{n}, f ∈ F(X), f level-continuous. Then, the following conditions are equivalent:

(i) f_{n} →^{L} f

(ii) f_{n} →^{Γ} f.

Keywords. Regular topological spaces, Kuratowski limits, variational convergence.

References.

[1] E. De Giorgi, T. Franzoni, Su un tipo di convergenza variazionale, Atti Acc. Naz. Lincei Rend. Cl. Sc. Mat. Fis. Nat. (8) 58, 842-850 (1975).

1This work was partially supported by Fondecyt (Chile), through Project 1970535 and Diexa-UTA by Project 4732-97.

[2] H. Attouch,Variational Convergence for Function and Operators, Pitman, London (1984).

[3] G. Greco, M. Moschen, E. Quelho, On the variational convergence of fuzzy sets, to appear.

[4] M. Rojas-Medar, H. Román-Flores, On the equivalence of convergences of fuzzy sets, Fuzzy Sets and Systems (80), 217-224 (1996).

[5] H. Román-Flores, A.Flores, A. Pachá, L. Hernández, Proper local maximum points: on multivalued characterizations, Proc. 7^{o} Cong. Latino-Iberoamericano de Investigación Operativa (CLAIO’94), Santiago-Chile.

[6] H. Román-Flores, The compactness of E(X), Applied Mathematics Letters 11 (2), 13-17 (1998).

Bundle methods applied to solve large-scale power production problems

Claudia Sagastizábal

Depto. de Engenharia Eletrica, PUC-Rio R. Marques de Sao Vicente 225, Caixa Postal 38063 22452-970 Rio de Janeiro, Brazil

                          sagastiz@ele.puc-rio.br

Abstract. Lagrangian relaxation is nowadays the most widespread technique to optimize the schedule of a large-scale power-generation mix. A decomposition scheme arises naturally when dualizing the coupling constraints (demand and spinning reserve). This classical decomposition is not the only one. Actually, a “space-time” decomposition scheme is a convenient alternative: it can reduce the duality gap; it allows the inclusion of transmission and security constraints; and it has been assessed by recent numerical results. However, the (nonsmooth) resulting dual problem has about ten thousands variables.

To preserve efficiency, the dual algorithm can take advantage of the additive structure of the dual function. However, to avoid overload, such “disaggregation” into components requires a special implementation of the bundle method used to solve the dual.

We describe this algorithm and some variants using projection methods. We analyze pros and cons and report on the application of our algorithms to the French production mix (composed of 200 thermal plants and 20 hydro-valleys) both for the short term (horizon of 24h, deterministic data) as for the middle term (1 week horizon, stochastic data).

This work is partially done in collaboration with the French Electricity Board, EdF.

Nonconvex Duality and an Invex Continuous-Time Generalization of Gordan’s Theorem

Adilson J. V. Brandão^{a}, Marko A. Rojas-Medar^{a} and Geraldo N. Silva^{b}

a Departamento de Matemática Aplicada, IMECC-Unicamp C.P. 6065, 13081-970 Campinas-SP, Brazil

                           marko@ime.unicamp.br

b Universidade Estadual Paulista (Unesp) Caixa Postal 136, CEP 15054-000 S J Rio Preto - SP, Brazil

                     gsilva@nimitz.dcce.ibilce.unesp.br

Abstract. A theorem of alternatives asserts about the inconsistency of two alternative systems of inequalities and/or equalities, and can be stated as follows: either system (i) has a solution, or system (ii) has a solution, but never both.

Both necessary conditions and duality results can be obtained from theorems of alternatives (see, e.g. [2]). So, improving theorems of alternatives to incorporate general class of functions we can, in principle, enhance optimality conditions and duality results.

Among the most famous theorems of alternatives are Farkas’s lemma and Gordan’s theorem [6]. These classical results are for linear and/or convex alternative systems. More recently, with the advance of the nonsmooth analysis, many non-time dependent theorems of altenatives for generalized convex functions have been obtained (see, for instance [3,4,5,7].

In the continuous-time context, a convex Gordan theorem of alternatives has been derived in [8].

In this paper, we first look at nonsmooth continuous-time nonlinear programming problems. We show that, under Lipschitz invexity hypotheses, the saddlepoint inequalities are indeed equivalent to the Karush-Kuhn-Tucker KKT) optimality conditions. Then we formulate a new nonsmooth continuous-time Lagrangian dual problem and establish weak and strong duality theorems. Finally, we apply some of the prevously derived results to obtain a new invex continuous-time Gordan’s theorem of the alternatives. We close the work with a corollary which partialy generalizes a result in [1] from convex to invex functions.

References.

[1] H.F. Bohnenblust, S. Karlin and L.S. Sharpley, Solutions of Discrete, Two-person Games, in: Contributions to the Theory of Games, vol I, Annals of Mathematics Studies Number 24, Princeton, 1950, pp. 51-72.

[2] B.D. Craven, Mathematical Programming and Control Theory, Chapman and Hall, London, 1978.

[3] B.D. Craven and V. Jeyakumar, Alternative and Duality Theorems with Weakend Convexity, 31 (1987), 149-159.

[4] B.D. Craven and X.Q. Yang, A Nonsmooth Version of Alternative Theorem, Utilitas, 40 (1991), 117-128.

[5] M. Hayashi and H. Komiya, Perfect Duality and Convexlike Programs, J. Optim. Theory and Appl. 38 (1980), 179-189.

[6] O.L. Mangasarian, Nonlinear Programming, Classics in Applied Mathematics 10, SIAM, 1994.

[7] T. Weir and B. Mond, Pre-Invex Functions in Multiple Objective Optimization, J. Math. Anal. Appl. 136 (1988), 29-38.

[8] G.J. Zalmai, Continuous-time Generalization of Gordan’s transposition theorem, J. Math. Anal. Appl. 110 (1985), 130-140.

Truly globally convergent Newton-type methods for systems of monotone equations and complementarity

problems

M. V. Solodov and B. F. Svaiter

Instituto de Matematica Pura e Aplicada Rio de Janeiro, Brazil

                              solodov@impa.br

Abstract. We present a new globalization strategy for Newton methods for solving certain monotone problems. As in the classical damped Newton approach, the search direction is obtained by solving, possibly inexactly, the linearized model. However, to compute the appropriate stepsize, no merit function is used. Our linesearch procedure utilizes the monotonicity structure of the problem to construct a certain hyperplane which strictly separates the current iterate from the solution set. The next iterate is obtained by a (computaionally explicit) projection operation. The resulting algorithm is truly globally convergent in the sense that the whole sequence of iterates converges to a solution without any regularity or nondegeneracy assumptions. This is the key advantage over the standard damped Newton methods, which, for example, may get stuck in a stationary point of a merit function. Each iteration of the new method has the same order of computational cost as an iteration of the corresponding damped Newton method. Under standard assumptions, the local superlinear rate of convergence is also preserved.

Keywords. Newton methods, complementarity problems, proximal methods, projection methods, global convergence

Equilibrium Problem as a Convex Feasibility Problem

Wilfredo Sosa Sandoval

Instituto de Matemática Pura e Aplicada Estrada Dona Castorina 110, Jardim Botanico Rio de Janeiro - Brazil - CEP 22460-320 RJ

                               sosa@impa.br

Abstract. The main goal of this work is to show that some projective methods can be used to solve the equilibrium problem (EP) in the sense of Blum-Oettli [2]. We know that the EP contains special cases, for instance: optimization problems, complementarity problems, fixed point problems, variational inequality problems and problems of Nash equilibria. On the other hand, we also know that the projection methods are iterative algorithms for computing common points of convex sets. By the way, we proved under quite mild conditions (pseudomonotonicity in the sense of [1]) that the EP can be solved as a convex feasibility problem (infinite case) and so the projection methods in the sense of Butnario-Flam [4] and Burachik-Butnario-Iusem [3] can be used to solve this EP.

Keywords. equilibrium problem, convex feasibility problem, expected projection methods

References.

[1] Bianchi M., Hadjisavvas N. and Schaible S., Vector equilibrium problem with generalized monotone bifunctions. Journal of Optimization Theory and Applications, vol 92 pp 527-542, 1997.

[2] Blum E. and Oettli W., From optimization and variational inequalities to equilibrium problems, The Mathematics Student, vol 63 pp 123-145, 1994.

[3] Burachik S. R., Butnario D. and Iusem A.N., Iterative methods of solving stochastic convex feasibility problems and applications. To appear.

[4] Butnario D. and Flam S. D., Strong convergence of expected projection methods in Hilbert space, Numerical Functional Analysis and Optimization, vol 16 pp 601-636, 1995.

Enlargements of maximal monotone operators in Banach Spaces

Regina Sandra Burachik^{a} and Benar Fux Svaiter^{b}

aEngenharia de Sistemas de Computação, COPPE–UFRJ CP 68511, Rio de Janeiro–RJ, 21945–970 Brazil.

                             regi@cos.ufrj.br

bIMPA, Estrada Dona Castorina, 110. Rio de Janeiro, RJ, CEP 22460-320, Brazil.

                               benar@impa.br

Abstract. Given a maximal monotone operator T in a Banach space, we consider an enlargement T^{ε}, in which monotonicity is lost up to ε, in a very similar way to the εsubdifferential of a convex function. We establish in this general framework some theoretical properties of T^{ε}, like a transportation formula, local Lipschitz continuity, local boundedness, and a Brønsted & Rockafellar property.

AMS subject classification. Primary: 65K05; Secondary: 90C30, 52A41, 90C25.

Keywords. Banach spaces, maximal monotone operators, enlargement of an operator, Brønsted & Rockafellar property, transportation formula, Lipschitz continuity, local boundedness.

Proximal and Dynamical Approaches to Equilibrium Probl ems

A. Moudafi^{a} and Michel Théra^{b}

aUniversité des Antilles et de la Guyane, Département de Mathématiques -Informatique

97159 Pointe-à-Pitre, Guadeloupe, France

                            amoudafi@univ-ag.fr

bUniversité de Limoges, LACO 123, avenue Albert Thomas, 87060 Limoges Cedex, France

                           michel.thera@unilim.fr

Abstract. This lecture will be divided into two parts.

In the first part we propose an unified proximal approach for solving general equilibrium problems.

In the second part, by coupling the steepest descent method with general approximation methods, through a diagonal process, we will construct a general dynamical method which selects a particular solution of the considered problem.

On the Numerical Solution of Ill-Posed Control Problems via Proximal Regularization^{1}

Rainer Tichatschke

University Trier, Department of Mathematics D-54286-Trier, Germany

                            tichat@uni-trier.de

Abstract. A proximal point approach to ill-posed convex control problems governed by elliptic equations is studied. By means of multi-step proximal regularization (only w.r.t. the control functions) a stable penalty method is constructed. For distributed and boundary control problems with state constraints convergence of the approximately determined solutions of the regularized problems to an optimal process is proved. Some numerical results will be presented.

AMS subject classification. 49J20, 49M37, 65K10, 65M30

Keywords. Prox-regularization, ill-posed parabolic control problems, distributed control, penalty methods

1Supported by the German Research Foundation (DFG)

Optimal Control for Linear-Quadratic Problem with Boundary Conditions

Olga Vasilieva

Departamento de Matemáticas, Universidad del Valle AA 25360 Cali, Colombia

                     olgavas@pitagoras.univalle.edu.co

Abstract. This paper is concerned with the optimal design for linear-quadratic control problem of variable structure with boundary conditions. The faithful quadratic approximation formula for performance index response together with second-order necessary condition for optimality results in the simplified parameter-free succesive approximation algorithm appropriate for both non-singular and singular control design. The proposed quadratic approximation approach is applied to design a thermally insulated multiayer wall out of a specified set of matherials.

Key Words: performance index response, quadratic approximation, second-order criterion function, parameter-free algorithm, thermally insulated multilayer wall.

Estimating a Condition Measure for a Conic Linear Program

Jorge R. Vera

Universidad Católica de Chile, Dept. Ingeniería Industrial y Sistemas Campus San Joaquín, Vicuña Mackenna 4815, Santiago, Chile

                             jvera@ing.puc.cl

Abstract. In this talk we begin by reviwing some recent developments on the notion of illposedness and condition measures in conic linear optimization. Conic optimization includes many problems, in particular linear programming and semi-definite programming. Condition measures are defined in terms of distance to ill-posedness and they can be used to explain some estability properties of optimization problems as well as computational complexity of some algorithms. An important question is whether those measures can be actually computed. We show that they can be characterized as the optimal value of some convex optimization problems. Questions regarding complexity of estimating the condition measures are then addressed, based on the performance of two algorithms for convex optimization: an interior point algorithms based on a self-concordant barrier function, and the ellipsoidal algorithm.

AMS subject classification. 90C, 90C05, 90C60

Keywords. Conditioning, error analysis, convex optimization, complexity, interior point algorithms, ellipsoidal algorithm.

On the level sum of quasiconvex functions

Michel Volle

Université d’Avignon, Département de Mathématiques 33 rue L.Pasteur, 84000 Avignon, France

                        michel.volle@univ-avignon.fr

Abstract. We study a quasiconvex conjugation that transforms the level sum of functions into the pointwise sum of their conjugates and derive new duality results for the minimization of the max of two quasiconvex functions. We show that the level sum provides quasiconvex viscosity solutions for Hamilton-Jacobi equations in which the initial condition is a general continuous quasiconvex function which is not necessarily Lipschitz or bounded.

AMS subject classification. 90C26, 49L25

Keywords. nonconvex optimization, duality, viscosity solutions.