On conforming finite element methods for the inhomogeneous stationary Navier-Stokes equations

Summary We consider the stationary Navier-Stokes equations, written in terms of the primitive variables, in the case where both the partial differential equations and boundary conditions are inhomogeneous. Under certain conditions on the data, the existence and uniqueness of the solution of a weak formulation of the equations can be guaranteed. A conforming finite element method is presented and optimal estimates for the error of the approximate solution are proved. In addition, the convergence properties of iterative methods for the solution of the discrete nonlinear algebraic systems resulting from the finite element algorithm are given. Numerical examples, using an efficient choice of finite element spaces, are also provided.Supported, in part, by the U.S. Air Force Office of Scientific Research under Grant No. AF-AFOSR-80-0083Supported, in part, by the same agency under Grant No. AF-AFOSR-80-0176-A. Both authors were also partially supported by NASA Contract No. NAS1-15810 while they were in residence at the Institute for Computer Applications in Science and Engineering, NASA Langley Research Center, Hampton, VA 23665, USA     

Additional aspects of the Stackelberg strategy in nonzero-sum games

The Stackelberg strategy in nonzero-sum games is a reasonable solution concept for games where, either due to lack of information on the part of one player about the performance function of the other, or due to different speeds in computing the strategies, or due to differences in size or strength, one player dominates the entire game by imposing a solution which is favorable to himself. This paper discusses some properties of this solution concept when the players use controls that are functions of the state variables of the game in addition to time. The difficulties in determining such controls are also pointed out. A simple two-stage finite state discrete game is used to illustrate these properties.This work was supported in part by the U.S. Air Force under Grant No. AFOSR-68-1579D, in part by NSF under Grant No. GK-36276, and in part by the Joint Services Electronics Program under Contract No. DAAB-07-72-C-0259 with the Coordinated Science Laboratory, University of Illinois, Urbana, Illinois.     

Countably additive gambling with a general expected reward

Summary Optimal strategies and the optimal return function are characterized for a Borel gambling problem in which the utility of a strategy is the expectation under the strategy of a general, measurable function g defined on the space of all infinite histories. These results are based on a previous paper with Lester Dubins where g was assumed to be shift-invariant.Research supported by National Science Foundation Grant MCS77-28424     

Further properties of nonzero-sum differential games

The general nonzero-sum differential game hasN players, each controlling a different set of inputs to a single nonlinear dynamic system and each trying to minimize a different performance criterion. These general games have several interesting features which are absent in the two bestknown special cases (the optimal control problem and the two-person, zero-sum differential game). This paper considers some of the difficulties which arise in attempting to generalize ideas which are well known in optimal control theory, such as theprinciple of optimality and the relation betweenopen-loop andclosed-loop controls. Two types of solutions are discussed: theNash equilibrium and thenoninferior set. Some simple multistage discrete games are used to illustrate phenomena which also arise in the continuous formulation.This research was supported by Joint Services Electronics Contracts Nos. N00014-67-A-0298-0006, 0005, 0008 and by NASA Grant No. NGR 22-007-068.     

Optimal impulsive control of compartment models,II: Algorithm

The optimal impulsive control of systems arising from linear compartment models for drug distribution in the human body is considered. A system of linear, time-invariant, homogeneous differential equations is given along with a set of continuous constraints on state and control. The object is to develop a constructive algorithm for the computation of the optimal control relative to a convex cost functional. Under suitable hypotheses, satisfying the continuous constraints is equivalent to satisfying the constraints at a finite set of abstractly definedcritical points. Once these critical points have been determined, the solution of the optimal control problem is found as the solution of an ordinary finite-dimensional convex programming problem. An iterative algorithm is given for the situation in which the critical points cannot all be determineda priori.This work was supported in part by the National Science Foundation under Grant No. MPS-74-13332.     

Camera placement in integer lattices

The camera placement problem concerns the placement of a fixed number of point-cameras on thed-dimensional integer lattice in order to maximize their visibility. We reduce the problem to a finite discrete optimization problem and give a characterization of optimal configurations of size at most 3 ^d . A preliminary version of this work appears in [8]. The research of E. Kranakis was supported by NSERC Grant No. 907002.     

Global dynamics of approximate solutions to an age-structured epidemic model with diffusion

We consider an age-dependent s-i-s epidemic model with diffusion whose mortality is unbounded. We approximate the solution using Galerkin methods in the space variable combined with backward Euler along the characteristic direction in the age and time variables. It is proven that the scheme is stable and convergent in optimal rate in l ^∞,2 (L ²) norm. To investigate the global behavior of the discrete solution resulting from the algorithm, we reformulate the resulting system into a monotone form. Positivity of the nonlocal birth process is proved using the positivity of the first eigenvalue of the resulting matrix system and using the fact that the positivity is preserved along the characteristics. The difference equation of the steady state coupled with nonlocal birth process is solved by developing monotone iterative schemes. The stability of the discrete solution of the steady state is then analyzed by constructing suitable positive subsolutions. Mathematics subject classifications (2000) 65M12, 65M25, 65M60, 92D25 M.-Y. Kim: This work was supported by Korea Research Foundation Grant (KRF-2001-041-D00037).     

Turnpike properties for a class of piecewise deterministic systems arising in manufacturing flow control

This paper deals with a general class of piecewise deterministic control systems that encompasses FMS flow control models. One uses the Markov renewal decision process formalism to characterize optimal policies via a discrete event dynamic programming approach. A family of control problems with a random stopping time is associated with these optimality conditions. These problems can be reformulated as infinite horizon deterministic control problems. It is then shown how the so-calledturnpike property should hold for these deterministic control problems under classical convexity assumptions. These turnpikes have the same generic properties as the attractors obtained via a problem specific approach in FMS flow control models and production planning and are calledhedging points in this literature.This research has been supported by NSERC-Canada, Grants No. A4952 by FCAR-Québec, Grant No. 88EQ3528, Actions Structurantes, MESS-Québec, Grant No. 6.1/7.4(28), and FNRS-Switzerland.     

Projection and restriction methods in geometric programming and related problems

Mathematical programming problems with unattained infima or unbounded optimal solution sets are dual to problems which lackinterior points, e.g., problems for which the Slater condition fails to hold or for which the hypothesis of Fenchel's theorem fails to hold. In such cases, it is possible to project the unbounded problem onto a subspace and to restrict the dual problem to an affine set so that the infima are not altered. After a finite sequence of such projections and restrictions, dual problems are obtained which have bounded optimal solution sets andinterior points. Although results of this kind have occasionally been used in other contexts, it is in geometric programming (both in the original psynomial form and the generalized form) where such methods appear most useful. In this paper, we present a treatment of dual projection and restriction methods developed in terms of dual generalized geometric programming problems. Analogous results are given for Fenchel and ordinary dual problems.This research was supported in part by Grant No. AFOSR-73-2516 from the Air Force Office of Scientific Research and by Grant No. NSF-ENG-76-10260 from the National Science Foundation.The authors wish to express their appreciation to the referees for several helpful comments.     

Capacitated,balanced, sequential location-allocation problems on chains and trees

This paper considers finite horizon, multiperiod, sequential, minisum location-allocation problems on chain graphs and tree networks. The demand has both deterministic and probabilistic components, and increases dynamically from period to period. The problem is to locate one additionalcapacitated facility in each of thep specified periods, and to determine the service allocations of the facilities, in order to optimally satisfy the demand on the network. In this context, two types of objective criteria or location strategies are addressed. The first is a myopic strategy in which the present period cost is minimized sequentially for each period, and the second is a discounted present worth strategy. For the chain graph, we analyze ap-facility problem under both these criteria, while for the tree graph, we analyze a 3-facility myopic problem, and a 2-facility discounted present worth problem. All these problems are nonconvex, and we specify a finite set of candidate solutions which may be compared in order to determine a global optimal solution.     

Superconvergence of tricubic block finite elements

In this paper, we first introduce interpolation operator of projection type in three dimen- sions, from which we derive weak estimates for tricubic block finite elements. Then using the estimate for the W 2, 1-seminorm of the discrete derivative Green’s function and the weak estimates, we show that the tricubic block finite element solution uh and the tricubic interpolant of projection type Πh3u have superclose gradient in the pointwise sense of the L∞-norm. Finally, this supercloseness is applied to superc...     

Numerical solution of the zero-head seepage problem by discretization of the variational inequality

The problem of zero-head seepage through a cutoff is reduced to solving a variational inequality which is discretized by the finite element method. The discrete variational inequality is solved by a two-layer iterative process. A rate of convergence bound is obtained for the approximate solution and the optimal parameters of the two-layer iterative process are determined. A numerical experiment supports the theoretical results.Translated from Vychislitel'naya i Prikladnaya Matematika, No. 58, pp. 45–56, 1986.     

Inventory control as a discrete system control for the fixed-order quantity system

This paper shows how to model a problem to find optimal number of replenishments in the fixed-order quantity system as a basic problem of optimal control of the discrete system. The decision environment is deterministic and the time horizon is finite. A discrete system consists of the law of dynamics, control domain and performance criterion. It is primarily a simulation model of the inventory dynamics, but the performance criterion enables various order strategies to be compared. The dynamics of state variables depends on the inflow and outflow rates. This paper explicitly defines flow regulators for the four patterns of the inventory: discrete inflow – continuous/discrete outflow and continuous inflow – continuous/discrete outflow. It has been discussed how to use suggested model for variants of the fixed-order quantity system as the scenarios of the model. To find the optimal process, the simulation-based optimization is used.     

A Branch and Bound algorithm for the minimax regret spanning arborescence

The paper considers the problem of finding a spanning arborescence on a directed network whose arc costs are partially known. It is assumed that each arc cost can take on values from a known interval defining a possible economic scenario. In this context, the problem of finding the spanning arborescence which better approaches to that of minimum overall cost under each possible scenario is studied. The minimax regret criterion is proposed in order to obtain such a robust solution of the problem. As it is shown, the bounds on the optimal value of the minimax regret optimization problem obtained in a previous paper, can be used here in a Branch and Bound algorithm in order to give an optimal solution. The computational behavior of the algorithm is tested through numerical experiments. This research has been supported by the Spanish Ministry of Education and Science and FEDER Grant No. MTM2006-04393 and by the European Alfa Project, “Engineering System for Preparing and Making Decisions Under Multiple Criteria”, II-0321-FA.     

A Class of Inverse Dominant Problems under Weighted l ∞ Norm and an Improved Complexity Bound for Radzik’s Algorithm

In this paper, we first discuss a class of inverse dominant problems under weighted l_∞ norm, which is how to change the original weights of elements with bounds in a finite ground set so that a given set becomes a weakly dominant set with respect to a given collection of subsets under the new weights and the largest change of the weights is minimum. This model includes a large class of improvement problems in combinatorial optimization. We propose a Newton-type algorithm for the model. This algorithm can solve the model in strongly polynomial time if the subproblem involved is solvable in strongly polynomial time. In the second part of the paper, we improve the complexity bound for Radzik’s Newton-type method which is designed to solve linear fractional combinatorial optimization problems. As Radzik’s method is closely related to our algorithm, this bound also estimates the complexity of our algorithm. Supported by the Hong Kong Universities Grant Council (CERG CITYU 9040883 and 9041091). Xiaoguang Yang - The author is also grateful for the support by the National Key Research and Development Program of China (Grant No. 2002CB312004) and the National Natural Science Foundation of China (Grant No. 70425004).     

Optimal impulsive control of compartment models,I: Qualitative aspects

Optimal impulsive control of systems arising from linear compartment models for drug distribution in the human body is considered. A system of linear, time-invariant, homogeneous differential equations is given along with a set of continuous constraints on state and control. The object is to develop a constructive algorithm for the computation of the optimal control relative to a convex cost functional. It is first shown that under suitable hypotheses, satisfying the continuous constraints is equivalent to satisfying the constraints at a finite set of abstractly definedcritical points. Once these critical points have been determined, the solution of the optimal control problem is found as the solution of a finite-dimensional convex programming problem. The set of critical points can often be determineda priori solely from the qualitative behavior of the solutions of the system. A class of such problems, generalizing the so-calledplateau effect, is considered in detail. It is shown that the solution achieving the plateau effect is indeed optimal in certain cases. In a subsequent paper, an iterative algorithm will be given for the solution of these problems when the critical points cannot all be determineda priori.This work was supported in part by the National Science Foundation under Grant No. GP-20130.     

Nonobtuse Tetrahedral Partitions that Refine Locally Towards Fichera-Like Corners

Linear tetrahedral finite elements whose dihedral angles are all nonobtuse guarantee the validity of the discrete maximum principle for a wide class of second order elliptic and parabolic problems. In this paper we present an algorithm which generates nonobtuse face-to-face tetrahedral partitions that refine locally towards a given Fichera-like corner of a particular polyhedral domain. The first author was supported by the Swedish Foundation for Strategic Research, the second author was supported by Grant No. 49051 of the Academy of Finland, the third author was supported by Grant No. A 1019201 of the Academy of Sciences of the Czech Republic and by Institutional Research Plan AV0Z 10190503.     

Adaptive control of constrained Markov chains: Criteria and policies

We consider the constrained optimization of a finite-state, finite action Markov chain. In the adaptive problem, the transition probabilities are assumed to be unknown, and no prior distribution on their values is given. We consider constrained optimization problems in terms of several cost criteria which are asymptotic in nature. For these criteria we show that it is possible to achieve the same optimal cost as in the non-adaptive case.We first formulate a constrained optimization problem under each of the cost criteria and establish the existence of optimal stationary policies.Since the adaptive problem is inherently non-stationary, we suggest a class ofAsymptotically Stationary (AS) policies, and show that, under each of the cost criteria, the costs of an AS policy depend only on its limiting behavior. This property implies that there exist optimal AS policies. A method for generating adaptive policies is then suggested, which leads to strongly consistent estimators for the unknown transition probabilities. A way to guarantee that these policies are also optimal is to couple them with the adaptive algorithm of [3]. This leads to optimal policies for each of the adaptive constrained optimization problems under discussion.This work was supported in part through United States-Israel Binational Science Foundation Grant BSF 85-00306.