Nonlinear programming with cumulatively bounded variables

The problem [maximize f(x), subject to x₁ + … + x_j ? b_j for j = 1, …, N] is solved by a feasible direction method that takes advantage of its special structure. A direction vector that approximates the vector of Lagrange multipliers is used. In the one-dimensional subproblem the direction vector is bent every time a constraint becomes active. Convergence to a K-T point is proven. McCormick has used a similar method for the problem [maximize f(x), subject to x ? 0], with the gradient as direction vector. A computationally implementable algorithm is given, with a finite stepsize procedure and a finite stopping rule. Observations from numerous applications to a recurring banking problem are discussed. Related techniques might be useful in other situations.     

Enlargement procedure for resolution of singularities at simple singular solutions of nonlinear equations

Summary A solution of a nonlinear equation in Hilbert spaces is said to be a simple singular solution if the Fréchet derivative at the solution has one-dimensional kernel and cokernel. In this paper we present the enlargement procedure for resolution of singularities at simple singular solutions of nonlinear equations. Once singularities are resolved, we can compute accurately the singular solution by Newton's method. Conditions for which the procedure terminates in finite steps are given. In particular, if the equation defined in ⁿ is analytic and the simple singular solution is geometrically isolated, the procedure stops in finite steps, and we obtain the enlarged problem with an isolated solution. Numerical examples are given.This research is partially supported by Grant-in-Aid for Encouragment of Young Scientist No. 60740119, the Ministry of EducationDedicated to Professor Seiiti Huzino on his 60th birthday     

A reconstruction method for a two-dimensional inverse eigenvalue problem

In this paper we describe a method for constructing approximate solutions of a two-dimensional inverse eigenvalue problem. Here we consider the problem of recovering a functionq(x, y) from the eigenvalues of — +q(x, y) on a rectangle with Dirichlet boundary conditions. The potentialq(x, y) is assumed to be symmetric with respect to the midlines of the rectangle. Our method is a generalization of an algorithm Hald presented for the construction of symmetric potentials in the one-dimensional inverse Sturm-Liouville problem. Using a projection method, the inverse spectral problem is reduced to an inverse eigenvalue problem for a matrix. We show that if the given eigenvalues are small perturbations of simple eigenvalues ofq=0, then the matrix problem has a solution. This solution is used to construct a functionq which has the same lowest eigenvalues as the unknownq, and several numerical examples are given to illustrate the methods.     

On the numerical construction of an attractor for the Navier-Stokes system

In this paper the problem of the numerical approximation of the minimal global B-attractor for a semiflow generated by the Navier-Stokes equations in a two-dimensional bounded domain Ω is considered. The method suggested here is based on the formula , where G^N is a sequence of compact subsets of L₂(Ω), . The procedure of constructing G^N is finite and includes the numerical solution of the Navier-Stokes equations by means of the Galerkin method, together with an explicit finite-difference discretization in time. Bibliography: 5 titles. To dear teacher Olga A. Ladyzhenskaya on the occasion of the jubilee Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 200, 1992, pp. 91–97. Translated by V. I. Ochkur.     

Optimal cycles in doubly weighted graphs and approximation of bivariate functions by univariate ones

Summary The problem of finding optimal cycles in a doubly weighted directed graph (Problem A) is closely related to the problem of approximating bivariate functions by the sum of two univariate functions with respect to the supremum norm (Problem B). The close relationship between Problem A and Problem B is detected by the characterization (7.4) of the distance dist (f, t) of Problem B.In Part 1 we construct an algorithm for Problem A where the essential role is played by the minimal lengthsy _j(k) defined by (2.3). If weight functiont1 then the minimum of Problem A is computed by equality (2.4). Ift1 then the minimum is obtained by a binary search procedure, Algorithm 3.In Part 2 we construct our algorithms for solving Problem B by following exactly the ideas of Part 1. By Algorithm 4 we compute the minimal pseudolengthsh _k(y, M) defined by (7.5). If weight functiont1 then the infimum dist(f,t) of Problem B is obtained by equality (7.12) which is closely related to (2.4). Ift1 we compute the infimum dist(f,t) by the binary search procedure Algorithm 5.Additionally, Algorithm 4 leads to a constructive proof of the existence of continuous optimal solutions of Problem B (see Theorem 7.1e) which is already known in caset1 but unknown in caset1.Interesting applications to the steady-state behaviour of industrial processes with interference (Sect. 3) and the solution of integral equations (Problem C) are included.Supported by Deutsche Forschungsgemeinschaft Grant No. GO 270/3     

Steepest Descent Methods with Generalized Distances for Constrained Optimization

We consider the problem s.t. , where C is a closed and covex subset of with nonempty interior, and introduce a family of interior point methods for this problem, which can be seen as approximate versions of generalized proximal point methods. Each step consists of a one-dimensional search along either a curve or a segment in the interior of C. The information about the boundary of C is contained in a generalized distance which defines the segment of the curve, and whose gradient diverges at the boundary of C. The objective of the search is either f or f plus a regularizing term. When , the usual steepest descent method is a particular case of our general scheme, and we manage to extend known convergence results for the steepest descent method to our family: for nonregularized one-dimensional searches,under a level set boundedness assumption on f, the sequence is bounded, the difference between consecutive iterates converges to 0 and every cluster point of the sequence satisfies first-order optimality conditions for the problem, i.e. is a solution if f is convex. For the regularized search and convex f, no boundedness condition on f is needed and full and global convergence of the sequence to a solution of the problem is established.     

A model for real poker with an upper bound of assets

This paper considers a continuous model of two-person poker, where the maximal amount of betB is assumed and the player who acts first chooses the amount of bet in the game. We analyze a model, in which the range of the amount of bet is a finite interval [0,B], 0B<+, to obtain a saddle point of the payoff function as a pair of optimal strategies among mixed strategies. We compare our results with those of Karlin and Restrepo and those of Newman.The author wishes to thank Professors M. Sakaguchi and T. Kurisu of Osaka University for suggesting the problem as well as for guidance and encouragement.     

On the transport-diffusion algorithm and its applications to the Navier-Stokes equations

Summary This paper deals with an algorithm for the solution of diffusion and/or convection equations where we mixed the method of characteristics and the finite element method. Globally it looks like one does one step of transport plus one step of diffusion (or projection) but the mathematics show that it is also an implicit time discretization of thePDE in Lagrangian form. We give an error bound (h+t+h×h/t in the interesting case) that holds also for the Navier-Stokes equations even when the Reynolds number is infinite (Euler equation).     

An extension of the simplex algorithm for semi-infinite linear programming

We present a primal method for the solution of the semi-infinite linear programming problem with constraint index setS. We begin with a detailed treatment of the case whenS is a closed line interval in . A characterization of the extreme points of the feasible set is given, together with a purification algorithm which constructs an extreme point from any initial feasible solution. The set of points inS where the constraints are active is crucial to the development we give. In the non-degenerate case, the descent step for the new algorithm takes one of two forms: either an active point is dropped, or an active point is perturbed to the left or right. We also discuss the form of the algorithm when the extreme point solution is degenerate, and in the general case when the constraint index set lies in ^p . The method has associated with it some numerical difficulties which are at present unresolved. Hence it is primarily of interest in the theoretical context of infinite-dimensional extensions of the simplex algorithm.     

A finite element method for a singularly perturbed boundary value problem

Summary We examine the problem:u+a(x)u–b(x)u=f(x) for 0<x<1,a(x)>0,b(x)>, ² = 4>0,a, b andf inC ² [0, 1], in (0, 1],u(0) andu(1) given. Using finite elements and a discretized Green's function, we show that the El-Mistikawy and Werle difference scheme on an equidistant mesh of widthh is uniformly second order accurate for this problem (i.e., the nodal errors are bounded byCh ², whereC is independent ofh and ). With a natural choice of trial functions, uniform first order accuracy is obtained in theL (0, 1) norm. On choosing piecewise linear trial functions (hat functions), uniform first order accuracy is obtained in theL ¹ (0, 1) norm.     

Une méthode numérique pour le calcul des points de retournement. Application à un problème aux limites non-linéaire

Summary A finite element method (P₁) with numerical integration for approximating the boundary value problem –u=e ^u is considered. It is shown that the discrete problem has a solution branch (with turning point) which converges uniformely to a solution branch of the continuous problem. Error estimates are given; for example it is found that , >0, where ₀ and _h ⁰ are critical values of the parameter for continuous and discrete problems.

     

Asymptotic expansions andL ∞-error estimates for mixed finite element methods for second order elliptic problems

Summary Asymptotic expansions for mixed finite element approximations of the second order elliptic problem are derived and Richardson extrapolation can be applied to increase the accuracy of the approximations. A new procedure, which is called the error corrected method, is presented as a further application of the asymptotic error expansion for the first order BDM approximation of the scalar field. The key point in deriving the asymptotic expansions for the error is an establishment ofL ¹-error estimates for mixed finite element approximations for the regularized Green's functions. As another application of theL ¹-error estimates for the regularized Green's functions, we shall present maximum norm error estimates for mixed finite element methods for second order elliptic problems.     

Stability of collocation methods for the numerical solution ofy″=f (x,y)

The stability properties of the collocation methods using polynomials for the numerical solution ofy=f(x,y) are studied in this paper. A simple procedure which can be used to determine the stability region of any method is presented. It is shown that all methods using points symmetrically placed in each subinterval are always stable at least in a finite interval. Some methods which have an infinite interval of stability are derived and their practical value is discussed.     

Equivariant Surgery Theory: Deleting-Inserting Theorems of Fixed Point Manifolds on Spheres and Disks

The paper gives a tool to delete and insert fixed point manifolds for smooth actions of finite Oliver groups on spheres and disks. A similar result was already given in a joint article with E. Laitinen and K. Pawaowski for those of finite nonsolvable groups on spheres. It is useful in classifying smooth actions on spheres from the view point of fixed point data. The methods employed in the present paper are equivariant surgery and equivariant connected sum associated with elements in the Burnside ring. The idea of killing surgery obstructions is as follows: Let G be a finite group not of prime power order, C a contractible, finiteG CW complex, and an element in a K theoretic group arising as an obstruction class of geometric object f. It often holds that (1-[C])^m becomes trivial for large integers m where [C] is the element represented byC in the Burnside ring (G). One expects that the algebraic object (1 - [C])^m is realizable as the obstruction class of G connected sum of f's related to (1 - [C])^m. Since it is true for the case here, we can kill the obstruction by taking G connected sum off's     

Point systems with extremal properties and conformal mapping

Summary LetD be the unit disk. It is a well-known fact that by use of simply connected domain methods the general conformal mapping problem of doubly connected domains can be reduced to the special case of a regionD bounded by the unit circle and a Jordan curve inD, where . Here we treat this special case and assume to be piecewise analytic without cusps. Let be the conformal mapping of {<|w|<1} onto the doubly connected domainD with (1)=1. We approximate by interpolation with finite Laurent series using point systems with extremal properties. Numerical results for four examples are given.     

L ∞-Error estimate for an approximation of a parabolic variational inequality

Summary Almost optimalL -convergence of an approximation of a variational inequality of parabolic type is proved under regularity assumptions which are met by the solution of a one phase Stefan problem. The discretization employs piecewise linear finite elements in space and the backward Euler scheme in time. By means of a maximum principle the problem is reduced to an error estimate for an auxiliary parabolic equation. The latter bound is obtained by using the smoothing property of the Galerkin method.     

An interior point multiplicative method for optimization under positivity constraints

We analyze an algorithm for the problem minf(x) s.t.x 0 suggested, without convergence proof, by Eggermont. The iterative step is given by x _j ^k+1 =x _j ^k (1-_kf(x ^k)_j) with _k > 0 determined through a line search. This method can be seen as a natural extension of the steepest descent method for unconstrained optimization, and we establish convergence properties similar to those known for steepest descent, namely weak convergence to a KKT point for a generalf, weak convergence to a solution for convexf and full convergence to the solution for strictly convexf. Applying this method to a maximum likelihood estimation problem, we obtain an additively overrelaxed version of the EM Algorithm. We extend the full convergence results known for EM to this overrelaxed version by establishing local Fejér monotonicity to the solution set.Research for this paper was partially supported by CNPq grant No 301280/86.     

On the one-dimensional two-phase inverse Stefan problems

New formulations of the inverse nonstationary Stefan problems are considered: (a) forx [0,1] (the inverse problem IP₁; (b) forx [0, (t)] with a degenerate initial condition (the inverse problem IP). Necessary conditions for the existence and uniqueness of a solution to these problems are formulated. On the first phase {x [0, y(t)]{, the solution of the inverse problem is found in the form of a series; on the second phase {x [y(t), 1] orx [y(t), (t)]{, it is found as a sum of heat double-layer potentials. By representing the inverse problem in the form of two connected boundary-value problems for the heat conduction equation in the domains with moving boundaries, it can be reduced to the integral Volterra equations of the second kind. An exact solution of the problem IP is found for the self similar motion of the boundariesx=y(t) andx=(t).Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 45, No. 8, pp. 1058–1065, August, 1993.     

The maximum entropy method on the mean: Applications to linear programming and superresolution

A continuous deformation algorithm is proposed for solving a variational inequality problem on a polytopeK. The algorithm embeds the polytopeK intoK× [0, ) and starts by applying a variable dimension algorithm onK× {0} until an approximate solution is found onK× {0}. Then by tracing the path of solutions of a system of equations the algorithm virtually follows a path of approximate solution inK× [0, ). When the path inK× [0, ) returns to level 0, i.e.,K× {0}, the variable dimension algorithm is again used until a new approximate solution is found onK× {0}. The setK× [0, ) is triangulated so that the approximate solution on the path improves the accuracy as the level increases. A contrivance for a practical implementation of the algorithm is proposed and tested for some test problems.Corresponding author.     

Min-max game theory and algebraic Riccati equations for boundary control problems with continuous input-solution map. Part II: The general case

We consider the abstract dynamical framework of [LT3, class (H.2)] which models a variety of mixed partial differential equation (PDE) problems in a smooth bounded domain ⁿ , arbitraryn, with boundaryL ₂-control functions. We then set and solve a min-max game theory problem in terms of an algebraic Riccati operator, to express the optimal quantities in pointwise feedback form. The theory obtained is sharp. It requires the usual Finite Cost Condition and Detectability Condition, the first for existence of the Riccati operator, the second for its uniqueness and for exponential decay of the optimal trajectory. It produces an intrinsically defined sharp value of the parameter, here called _c (critical), _c0, such that a complete theory is available for > _c, while the maximization problem does not have a finite solution if 0 < < _c. Mixed PDE problems, all on arbitrary dimensions, except where noted, where all the assumptions are satisfied, and to which, therefore, the theory is automatically applicable include: second-order hyperbolic equations with Dirichlet control, as well as with Neumann control, the latter in the one-dimensional case; Euler-Bernoulli and Kirchhoff equations under a variety of boundary controls involving boundary operators of order zero, one, and two; Schroedinger equations with Dirichlet control; first-order hyperbolic systems, etc., all on explicitly defined (optimal) spaces [LT3, Section 7]. Solution of the min-max problem implies solution of theH -robust stabilization problem with partial observation.The research of C. McMillan was partially supported by an IBM Graduate Student Fellowship and that of R. Triggiani was partially supported by the National Science Foundation under Grant NSF-DMS-8902811-01 and by the Air Force Office of Scientific Research under Grant AFOSR-87-0321.