Algorithms for a class of nondifferentiable problems

A nonlinear programming problem with nondifferentiabilities is considered. The nondifferentiabilities are due to terms of the form min(f ₁(x),...,f _n(x)), which may enter nonlinearly in the cost and the constraints. Necessary and sufficient conditions are developed. Two algorithms for solving this problem are described, and their convergence is studied. A duality framework for interpretation of the algorithms is also developed.This work was supported in part by the National Science Foundation under Grant No. ENG-74-19332 and Grant No. ECS-79-19396, in part by the U.S. Air Force under Grant AFOSR-78-3633, and in part by the Joint Services Electronics Program (U.S. Army, U.S. Navy, and U.S. Air Force) under Contract N00014-79-C-0424.     

A splitting type algorithm for multi-valued complementarity problems

We consider a generalized complementarity problem whose cost mapping is multi-valued and is the sum of upper Z and antitone mappings. We suggest a simple splitting type algorithm which utilizes an extended Jacobi iteration. Its convergence is proved under mild assumptions. Preliminary results of numerical experiments confirm efficiency of the algorithm presented. This work was supported by RFBR–NNSF Grant No. 07-01-92101.     

Sufficient conditions for Stackelberg and Nash strategies with memory

Sufficiency conditions for Stackelberg strategies for a class of deterministic differential games are derived when the players have recall of the previous trajectory. Sufficient conditions for Nash strategies when the players have recall of the trajectory are also derived. The state equation is linear, and the cost functional is quadratic. The admissible strategies are restricted to be affine in the information available.This work was supported in part by the Joint Services Electronics Program under Contract No. N00014-79-C-0424, in part by the National Science Foundation under Grant No. ECS-79-19396, and in part by Department of Energy under Contract No. EX-76-C-01-2088.     

Geometric singular perturbation analysis of oxidation heat pulses for two-phase flow in porous media

When air or oxygen is injected into a petroleum reservoir, and oxidation or combustion is induced, a combustion front forms if heat loss to the surrounding rock formation is negligible. Here, we employ a simple model for combustion, which takes into account oil viscosity reduction, but neglects gas density dependence on temperature and uses a simplified oxidation reaction. We show that for small heat loss, this combustion front is actually the lead part of a pulse, while the trailing part of the pulse is a slow cooling process. If the heat loss is too large, we show that such a pulse does not exist. The proofs use geometric singular perturbation theory and center manifold reduction.Dedicated to Constantine Dafermos on his 60^th birthdayThis work was supported in part by: CNPq under Grant 300204/83-3; CNPq/NSF under Grant 91.0011/99-0; MCT under Grant PCI 650009/97-5; FINEP under Grant 77.97.0315.00; FAPERJ under Grants E-26/150.936/99 and E-26/151.893/2000; NSF under Grant DMS-9973105.     

Controlled Markov processes on the infinite planning horizon: Weighted and overtaking cost criteria

Stochastic control problems for controlled Markov processes models with an infinite planning horizon are considered, under some non-standard cost criteria. The classical discounted and average cost criteria can be viewed as complementary, in the sense that the former captures the short-time and the latter the long-time performance of the system. Thus, we study a cost criterion obtained as weighted combinations of these criteria, extending to a general state and control space framework several recent results by Feinberg and Shwartz, and by Krass et al. In addition, a functional characterization is given for overtaking optimal policies, for problems with countable state spaces and compact control spaces; our approach is based on qualitative properties of the optimality equation for problems with an average cost criterion.Research partially supported by the Engineering Foundation under grant RI-A-93-10, in part by the National Science Foundation under grant NSF-INT 9201430, and in part by a grant from the AT&T Foundation.Research partially supported by the Air Force Office of Scientific Research under Grant F49620-92-J-0045, and in part by the National Science Foundation under Grant CDR-8803012.     

Approximation procedures based on the method of multipliers

In this paper, we consider a method for solving certain optimization problems with constraints, nondifferentiabilities, and other ill-conditioning terms in the cost functional by approximating them by well-behaved optimization problems. The approach is based on methods of multipliers. The convergence properties of the methods proposed can be inferred from corresponding properties of multiplier methods with partial elimination of constraints. A related analysis is provided in this paper.This work was supported in part by the Joint Services Electronics Program (US Army, US Navy, and US Air Force) under Contract No. DAAB-07-72-C-0259, and by the National Science Foundation under Grant No. ENG-74-19332.     

An efficient cost scaling algorithm for the assignment problem

The cost scaling push-relabel method has been shown to be efficient for solving minimum-cost flow problems. In this paper we apply the method to the assignment problem and investigate implementations of the method that take advantage of assignment's special structure. The results show that the method is very promising for practical use.This author's research was supported in part by ONR Young Investigator Award N00014-91-J-1855, NSF Presidential Young Investigator Grant CCR-8858097 with matching funds from AT&T, DEC and 3M, and a grant from the Powell Foundation.This author's research was supported by the above-mentioned ONR and NSF grants.     

A convergence theorem of Rosen’s gradient projection method

Since Rosen’s gradient projection method was published in 1960, a rigorous convergence proof of his method has remained an open question. A convergence theorem is given in this paper. Part of this author’s work was done while he studied at the Department of Mathematics, University of California at Santa Barbara, and was supported by the National Science Foundation under Grant No. MCS83-14977. Part of this author’s work was done while he visited the Computer Science Department, University of Minnesota, Minneapolis, and was supported by the National Science Foundation under Grant No. MCS81-01214.     

Sensitivity of Pareto Solutions in Multiobjective Optimization

The paper presents a sensitivity analysis of Pareto solutions on the basis of the Karush-Kuhn-Tucker (KKT) necessary conditions applied to nonlinear multiobjective programs (MOP) continuously depending on a parameter. Since the KKT conditions are of the first order, the sensitivity properties are considered in the first approximation. An analogue of the shadow prices, well known for scalar linear programs, is obtained for nonlinear MOPs. Two types of sensitivity are investigated: sensitivity in the state space (on the Pareto set) and sensitivity in the cost function space (on the balance set) for a vector cost function. The results obtained can be used in applications for sensitivity computation under small variations of parameters. Illustrative examples are presented.Research of this author was partially supported by Grant BEC2003-09067-C04-03.Research of this author was partially supported by NSERC Grant RGPIN-3492-00.Research of this author was partially supported by Grant BEC2003-09067-C04-02.     

Modifications and implementation of the ellipsoid algorithm for linear programming

We give some modifications of the ellipsoid algorithm for linear programming and describe a numerically stable implementation. We are concerned with practical problems where user-supplied bounds can usually be provided. Our implementation allows constraint dropping and updates bounds on the optimal value, and should be able to terminate with an indication of infeasibility or with a provably good feasible solution in a moderate number of iterations.The work of this author was supported in part by the U.S. Army Research Office under Grant DAAG29-77-G-0114 and the National Science Foundation under Grant MCS-8006065.The work of this author was supported in part by the National Science Foundation under Grant ECS-7921279.     

The topological degree theory for a class of noncompact multimaps

In questo lavoro viene definito il grado topologico per mappe multivoche di Vietoris fondamentalmente restrittibili. Tale grado è ad un sol valore, contrariamente a costruzioni precedenti. Le tecniche sono sostanzialmente di tipo analitico ed evitano le complicazioni tecniche della topologia algebrica. Entrata in Redazione il 30 Novembre 1998. The work of G. Conti and P. Zecca is partially supported by a National Grant 40% MURST. The work of V. Obukhovski is partially supported by the Russian Foundation for Basic Research Grant 96-01-00360. The work of the second author was carried out during his tenure at the University of Florence under a fellowship from the Italian Ministery of Forign Affairs through Landau Network-Centro Volta and the Italian CNR.     

On semilinear differential inclusions with lower semicontinuous nonlinearities

In questo lavoro si dà un teorema di esistenza di soluzioni per un inclusione differenziale semilineare in uno spazio di Banach. Le ipotesi sono deboli in quanto si suppone che l'operatore lineare A sia il generatore di un semigruppo fortemente continuo, senza ipotesi di compattezza, e la non linerità multivoca sia semicontinua inferiormente, non necessariamente a valori convessi. The work of the first two authors is partially supported by the Russian Foundation for basic Research Grant 99-01-00333. The work of the second author was carried out during his tenure at the University of Florence under a Fellowship from the Italian Ministry of Foreign Affairs through Landau Network—Centro Volta. The work of P. Zecca is supported by a National Grant 40% of MURST.     

A least-squares-based method for a class of nonsmooth minimization problems with applications in plasticity

This paper introduces a globally convergent algorithm for solving a class of nonsmooth optimization problems, involving square roots of quadratic forms. The class includes in particular limit analysis problems in plasticity. The algorithm combines smoothing with successive approximation. The main computational effort in each iteration is solving a linear weighted least-squares problem. The convergence of the algorithm is proved and ana priori error estimate is obtained. Numerical results are presented for two limit analysis problems.The work of the first author was partially supported by NSF Grant DDM-89-96112. Parts of the work was done during his stay at the University of Bayreuth as a guest of the DFG. The work of the second author was supported in part by the Air Force Office of Scientific Research under contract AFOSR-88-0218 and by a National Science Foundation Grant ECS-8802239 at the University of Maryland, Baltimore County Campus.     

The augmented lagrangian method for equality and inequality constraints in hilbert spaces

In this paper we consider an augmented Lagrangian method for the minimization of a nonlinear functional in the presence of an equality constraint whose image space is in a Hilbert space, an inequality constraint whose image space is finite dimensional, and an affine inequality constraint whose image space is in an infinite dimensional Hilbert space. We obtain local convergence of this method without imposing strict complementarity conditions when the equality, as well as the inequality constraint with finite dimensional image space are augmented. To the author's knowledge this result even generalizes the convergence results which are known when all spaces are finite dimensional.This research was supported by the Air Force Office of Scientific Research under Grant AFOSR-84-0398 and AFOSR-85-0303, by the National Aeronautics and Space Administration under Grant NAG-1-517, and by NSF under Grant UINT-8521208.This research was supported in part by the Fonds zur Förderung der wissenschaftichen Forschung under S3206 and P6005 and by AFOSR-84-0398. Part of this work was performed while the author was visiting the Division of Applied Mathematics, Brown University, Providence, RI, USA.     

Symbolic dynamics and nonlinear semiflows

Summary For a transverse homoclinic orbit of a mapping (not necessarily invertible) on a Banach space, it is shown that the mapping restricted to orbits near is equivalent to the shift automorphism on doubly infinite sequences on finitely many symbols. Implications of this result for the Poincaré map of semiflows are given.This work was supported by the Air Force Office of Scientific Research under Grant #81-0198, by the National Science Foundation under Grant #MCS-8205355 and by the Army Research Office under Grant ù DAAG-29-83-K-0029.     

The translation representation theorem

Short of a new theorem on semigroups of operators, a new proof of an old theorem on this subject is a suitable offering to Einar Hille on his 85th birthday.The work of both authors was supported in part by the National Science Foundation, the first author under Grant No. MCS-76-07039 and the second author under Grant No. MCS-77-04908 A 01.     

Dines—Fourier—Motzkin quantifier elimination and an application of corresponding transfer principles over ordered fields

A constructive procedure using Dines—Fourier—Motzkin elimination is given for eliminating quantifiers in a linear first order formula over ordered fields. An ensuing transfer principle is illustrated by showing that a locally one-to-one affine map is globally one-to-one and onto all over ordered fields.This research is based on work supported in part by the National Science Foundation under Grant DMS-86-03232, by the Department of Energy grant DE-FG03-87ER25028 and by the United States-Israel Binational Science Foundation Grant 85-00295.     

Pricing problems with a continuum of customers as stochastic Stackelberg games

The pricing problem where a company sells a certain kind of product to a continuum of customers is considered. It is formulated as a stochastic Stackelberg game with nonnested information structure. The inducible region concept, recently developed for deterministic Stackelberg games, is extended to treat the stochastic pricing problem. Necessary and sufficient conditions for a pricing scheme to be optimal are derived, and the pricing problem is solved by first delineating its inducible region, and then solving a constrained optimal control problem.The research work reported here as supported in part by the National Science Foundation under Grant ECS-81-05984, Grant ECS-82-10673, and by the Air Force Office of Scientific Research under AFOSR Grant 80-0098.