Foliations invariant under Lie group transverse actions

In this paper we study (smooth and holomorphic) foliations which are invariant under transverse actions of Lie groups. Authors’ address: Alexandre Behague and Bruno Scárdua, Instituto de Matemática, Universidade Federal do Rio de Janeiro, Caixa Postal 68530, 21945-970 Rio de Janeiro, RJ, Brazil     

Conical projection algorithms for linear programming

The Linear Programming Problem is manipulated to be stated as a Non-Linear Programming Problem in which Karmarkar's logarithmic potential function is minimized in the positive cone generated by the original feasible set. The resulting problem is then solved by a master algorithm that iteratively rescales the problem and calls an internal unconstrained non-linear programming algorithm. Several different procedures for the internal algorithm are proposed, giving priority either to the reduction of the potential function or of the actual cost. We show that Karmarkar's algorithm is equivalent to this method in the special case in which the internal algorithm is reduced to a single steepest descent iteration. All variants of the new algorithm have the same complexity as Karmarkar's method, but the amount of computation is reduced by the fact that only one projection matrix must be calculated for each call of the internal algorithm.Research partly sponsored by CNPq-Brazilian National Council for Scientific and Technological Development, by National Science Foundation grant ECS-857362, Office of Naval Research contract N00014-86-K-0295, and AFOSR grant 86-0116.On leave from COPPE-Federal University of Rio de Janeiro, Cx. Postal 68511, 21941 Rio de Janeiro, RJ, Brasil.     

Load balancing and capacity constraints in a hierarchical location model

Recent work on the location of perinatal facilities in the municipality of Rio de Janeiro resulted in the development of an uncapacitated, three-level hierarchical model. An important issue that arose during the course of the research was the need to include some form of capacity constraints into the model, especially in the higher, resource intensive level of the hierarchy. This need was felt from technical discussions related to the research work and from contacts with municipality health officials.A capacitated model is presented and solved using a Lagrangean heuristic. For smaller problems optimal solutions are found using CPLEX; it is found that the heuristic usually gives high quality solutions. Next a bi-criterion model is formulated in which the additional objective measure is the imbalance in facility loading. This is solved exactly for a small problem and approximately for the 152-vertex Rio de Janeiro data.     

On the convergence properties of Hildreth's quadratic programming algorithm

We prove the linear convergence rate of Hildreth's method for quadratic programming, in both its sequential and simulateneous versions. We give bounds on the asymptotic error constant and compare these bounds to those given by Mandel for the cyclic relaxation method for solving linear inequalities.Research of this author was partially supported by CNPq grant No. 301280/86.On leave from the Universidade Federal do Rio de Janeiro, Instituto de Matemática, Rio de Janeiro, R.J. 21.910, Brazil. Research of this author was partially supported by NIH grant HL28438.     

A hierarchical model for the location of perinatal facilities in the municipality of Rio de Janeiro

We present a 3-level hierarchical model for the location of maternal and perinatal health care facilities in Rio de Janeiro. Relaxations and heuristics are developed for this model and computational results are given for problems available in the literature, for networks ranging from 10 to 400 vertices. The quality of the solutions produced by the procedures we developed do not differ significantly among themselves. The model is also applied to a case study corresponding to real 1995 data of the municipality of Rio de Janeiro.     

Exact penalty function algorithm with simple updating of the penalty parameter

A new globally convergent algorithm for minimizing an objective function subject to equality and inequality constraints is presented. The algorithm determines a search direction by solving a quadratic programming subproblem, which always has an optimal solution, and uses an exact penalty function to compute the steplength along this direction through an Armijo-type scheme. The special structure of the quadratic subproblem is exploited to construct a new and simple method for updating the penalty parameter. This method may increase or reduce the value of the penalty parameter depending on some easily performed tests. A new method for updating the Hessian of the Lagrangian is presented, and a Q-superlinear rate of convergence is established.This work was supported in part by the British Council and the Conselho Nacional de Desenvolvimento Cientifico & Tecnologico/CNPq, Rio de Janeiro, Brazil.The authors are very grateful to Mr. Lam Yeung for his invaluable assistance in computing the results and to a reviewer for constructive advice.     

Hyperbolic 0–1 programming and query optimization in information retrieval

Unconstrained hyperbolic 0–1 programming can be solved in linear time when the numerator and the denominator are linear and the latter is always positive. It is NP-hard, and finding an approximate solution with a value equal to a positive multiple of the optimal one is also NP-hard, if this last hypothesis does not hold. Determining the optimal logical form of a query in information retrieval, given the attributes to be used, can be expressed as a parametric hyperbolic 0–1 program and solved in O(n logn) time, wheren is the number of elementary logical conjunctions of the attributes. This allows to characterize the optimal queries for the Van Rijsbergen synthetic criterion.This research was done in part during a visit of the first author to the Pontifical Catholic University of Rio de Janeiro in July and August 1987, sponsored by CNPq. It was also supported in part by grants 0271 and 0066 of the AFOSR to Rutgers University. The second author was with Centro de Análise de Sistemas Navais, Rio de Janeiro.     

Integrating Geographical Information Systems and Multi-Criteria Methods: A Case Study

This paper presents an application of the integration between Geographical Information Systems (GIS) and Multi-Criteria Decision Analysis (MCDA) to aid spatial decisions. We present a hypothetical case study to illustrate the GIS–MCDA integration: the selection of the best municipal district of Rio de Janeiro State, Brazil, in relation to the quality of urban life. The best municipal district is the one that presents the closest characteristics to those considered ideal by the decision-maker. The approach adopted is the Multi-Objective Linear Programming (MOLP) and the chosen method is the Pareto Race.     

Auxiliary problem principle extended to variational inequalities

The auxiliary problem principle has been proposed by the author as a framework to describe and analyze iterative optimization algorithms such as gradient or subgradient as well as decomposition/coordination algorithms (Refs. 1–3). In this paper, we extend this approach to the computation of solutions to variational inequalities. In the case of single-valued operators, this may as well be considered as an extension of ideas already found in the literature (Ref. 4) to the case of nonlinear (but still strongly monotone) operators. The case of multivalued operators is also investigated.This research has been supported by the Centre National de la Recherche Scientifique (ATP Complex Technological Systems) and by the Centre National d'Études des Télécommunications (Contract No. 83.5B.034.PAA). It has been conducted partly while the author was visiting the Department of Electrical Engineering of the Pontificia Catholic University of Rio de Janeiro in July–August 1984 under the CAPES/COFECUB scientific exchange program.     

An index theory for paths that are solutions of a class of strongly indefinite variational problems

We generalize the Morse index theorem of [12,15] and we apply the new result to obtain lower estimates on the number of geodesics joining two fixed non conjugate points in certain classes of semi-Riemannian manifolds. More specifically, we consider semi-Riemannian manifolds admitting a smooth distribution spanned by commuting Killing vector fields and containing a maximal negative distribution for . In particular we obtain Morse relations for stationary semi-Riemannian manifolds (see [7]) and for the G?del-type manifolds (see [3]). Received: 4 April 2001 / Accepted: 27 September 2001 / Published online: 23 May 2002 The authors are partially sponsored by CNPq (Brazil) Proc. N. 301410/95 and N. 300254/01-6. Parts of this work were done during the visit of the two authors to the IMPA, Instituto de Matemática Pura e Aplicada, Rio de Janeiro, Brazil, in January and February 2001. The authors wish to express their gratitude to all Faculty and Staff of the IMPA for their kind hospitality.     

An algorithm to locate perinatal facilities in the municipality of Rio de Janeiro

In order to reduce infant mortality in the municipality of Rio de Janeiro it is desired to encourage all mothers-to-be to attend the appropriate health care facilities. A 3-level hierarchical prenatal–neonatal health care system is described together with a basic model for optimising accessibility to facilities. A genetic algorithm to solve the basic model is developed and some numerical experience reported. Extensions to the basic model and planned future research are briefly indicated.     

Algorithms for generalized fractional programming

A generalized fractional programming problem is specified as a nonlinear program where a nonlinear function defined as the maximum over several ratios of functions is to be minimized on a feasible domain of ⁿ . The purpose of this paper is to outline basic approaches and basic types of algorithms available to deal with this problem and to review their convergence analysis. The conclusion includes results and comments on the numerical efficiency of these algorithms.This research was supported by NSERC (grant A8312) and Cooperation franco-québécoise (projet 20-02-13). Paper presented at Workshop on Mathematical Programming Catholic University of Rio de Janeiro, Brazil, October 10–14, 1988.     

On unconditional bases in spaces of holomorphic functions in infinite dimensions

This paper was written during the first author's stay at the Department of Mathematics of the Universidade Federal do Rio de Janeiro. He wants to thank the Department for the kind invitation and the CAPES/DAAD for its financial support.     

Lyapunov coupled equations for continuous-time infinite Markov jump linear systems

This paper deals with Lyapunov equations for continuous-time Markov jump linear systems (MJLS). Out of the bent which wends most of the literature on MJLS, we focus here on the case in which the Markov chain has a countably infinite state space. It is shown that the infinite MJLS is stochastically stabilizable (SS) if and only if the associated countably infinite coupled Lyapunov equations have a unique norm bounded strictly positive solution. It is worth mentioning here that this result do not hold for mean square stabilizability (MSS), since SS and MSS are no longer equivalent in our set up (see, e.g., [J. Baczynski, Optimal control for continuous time LQ-problems with infinite Markov jump parameters, Ph.D. Thesis, Federal University of Rio de Janeiro, UFRJ/COPPE, 2000]). To some extent, a decomplexification technique and tools from operator theory in Banach space and, in particular, from semigroup theory are the very technical underpinning of the paper.     

An acceleration scheme for cyclic subgradient projections method

An algorithm for solving convex feasibility problem for a finite family of convex sets is considered. The acceleration scheme of De Pierro (em Methodos de projeção para a resolução de sistemas gerais de equações algébricas lineares. Thesis (tese de Doutoramento), Instituto de Matemática da UFRJ, Cidade Universitária, Rio de Janeiro, Brasil, 1981), which is designed for simultaneous algorithms, is used in the algorithm to speed up the fully sequential cyclic subgradient projections method. A convergence proof is presented. The advantage of using this strategy is demonstrated with some examples.     

Building the Additive Utility Functions for CAD-UFRJ Evaluation Staff Criteria

This paper presents an application of the UTA method for building utility functions for the evaluation criteria defined by the Staff Evaluation Commission (CAD) of the Rio de Janeiro Federal University (UFRJ). Every year, the CAD-UFRJ gives the staff evaluation results for each Postgraduate Engineering Programme. However, the method used to generate the staff evaluation is assumed unknown. Trying to find the CAD-UFRJ preference structure, the evaluation results supplied by CAD-UFRJ are used to apply the UTA method. Some additional information obtained from the CAD-UFRJ data is incorporated in the optimal solutions analysis.     

On Topological Derivatives for Elastic Solids with Uncertain Input Data

In this paper, a new approach to the derivation of the worst scenario and the maximum range scenario methods is proposed. The derivation is based on the topological derivative concept for the boundary-value problems of elasticity in two and three spatial dimensions. It is shown that the topological derivatives can be applied to the shape and topology optimization problems within a certain range of input data including the Lamé coefficients and the boundary tractions. In other words, the topological derivatives are stable functions and the concept of topological sensitivity is robust with respect to the imperfections caused by uncertain data. Two classes of integral shape functionals are considered, the first for the displacement field and the second for the stresses. For such classes, the form of the topological derivatives is given and, for the second class, some restrictions on the shape functionals are introduced in order to assure the existence of topological derivatives. The results on topological derivatives are used for the mathematical analysis of the worst scenario and the maximum range scenario methods. The presented results can be extended to more realistic methods for some uncertain material parameters and with the optimality criteria including the shape and topological derivatives for a broad class of shape functionals. This research is partially supported by the Brazilian Agency CNPq under Grant 472182/2007-2, FAPERJ under Grant E-26/171.099/2006 (Rio de Janeiro) and Brazilian-French Research Program CAPES/COFECUB under Grant 604/08 between LNCC in Petrópolis and IECN in Nancy, and by the Research Grant CNRS-CSAV between Institut Elie Cartan in Nancy and the Institut of Mathematics in Prague. The support is gratefully acknowledged.     

Solution of polyhedra

The paper is an exposition of the authors talk on the Seminar on Differential Geometry in IMPA in Rio de Janeiro. It presents a short survey of some recent results in the metric theory of polyhedra in 3-space. Namely we emphasize on some applicatons of the theorem which is a vast generalization of the Herons formule for the area of a triangle to volumes of polyhedra.*The author is partially supported by grants of RFBR No. 02-01-00101 and Russian Ministry of Education E02-1.0-43.     

Multi-phase dynamic constraint aggregation for set partitioning type problems

Dynamic constraint aggregation is an iterative method that was recently introduced to speed up the linear relaxation solution process of set partitioning type problems. This speed up is mostly due to the use, at each iteration, of an aggregated problem defined by aggregating disjoint subsets of constraints from the set partitioning model. This aggregation is updated when needed to ensure the exactness of the overall approach. In this paper, we propose a new version of this method, called the multi-phase dynamic constraint aggregation method, which essentially adds to the original method a partial pricing strategy that involves multiple phases. This strategy helps keeping the size of the aggregated problem as small as possible, yielding a faster average computation time per iteration and fewer iterations. We also establish theoretical results that provide some insights explaining the success of the proposed method. Tests on the linear relaxation of simultaneous bus and driver scheduling problems involving up to 2,000 set partitioning constraints show that the partial pricing strategy speeds up the original method by an average factor of 4.5.