Implicitly defined optimization problems

This paper considers the solution of the problem: inff[y, x(y)] s.t.y [y, x(y)] E ^k , wherex(y) solves: minF(x, y) s.t.x R(x, y) E ⁿ . In order to obtain local solutions, a first-order algorithm, which uses {dx(y)/dy} for solving a special case of the implicitly definedy-problem, is given. The derivative is obtained from {dx(y, r)/dy}, wherer is a penalty function parameter and {x(y, r)} are approximations to the solution of thex-problem given by a sequential minimization algorithm. Conditions are stated under whichx(y, r) and {dx(y, r)/dy} exist. The computation of {dx(y, r)/dy} requires the availability of _y F(x, y) and the partial derivatives of the other functions defining the setR(x, y) with respect to the parametersy.Research sponsored by National Science Foundation Grant ECS-8709795 and Office of Naval Research Contract N00014-89-J-1537. We thank the referees for constructive comments on an earlier version of this paper.     

Superstable implicit Runge-Kutta methods for second order initial value problems

Using the well known properties of thes-stage implicit Runge-Kutta methods for first order differential equations, single step methods of arbitrary order can be obtained for the direct integration of the general second order initial value problemsy=f(x, y, y),y(x _o)=y _o,y(x _o)=y _o. These methods when applied to the test equationy+2y+ ² y=0, ,0, +>0, are superstable with the exception of a finite number of isolated values ofh. These methods can be successfully used for solving singular perturbation problems for which f/y and/or f/y are negative and large. Numerical results demonstrate the efficiency of these methods.     

Die Entropie einer linear gebrochenen Funktion

Let the continuous broken linear transformationf of the unit interval into itself satisfyingf(0)=f(1)=0 be determined by the coordinates of its peak pointP (x, y). The topological entropyh off, as a function of (x, y), is zero outside the triangle max (x, 1–x)<y1. Inside it is shown to be nonzero, continuous, monotonically increasing both iny/x and iny/(1–x) and to assume its maximum log2 ony=1. The level curvec(h ₀) of constant corresponding entropyh ₀>0 is a continuous curve joining the two diagonalsy=x andy=1–x in whichh has discontinuities (jumping to zero). For 1/2log2<hlog 2 the curvesc(h) pass through (0,1) withy=1 as a tangent and fill up the area bounded below by the parabolay ²=1–x on whichh(x,y)=1/2 log 2. For 1/2 log 2 <h log 2 the curvec(h) is the image of the arc ofc(2h) between the hyperbolax ²–xy2x+1=0 and the diagonaly=1–x under the transformation .     

A new continuation method for complementarity problems with uniformP-functions

The complementarity problem with a nonlinear continuous mappingf from the nonnegative orthantR ₊ ⁿ ofR ⁿ intoR ⁿ can be written as the system of equationsF(x, y) = 0 and(x, y) R ₊ ²ⁿ , whereF denotes the mapping from the nonnegative orthantR ₊ ²ⁿ ofR ²ⁿ intoR ₊ ⁿ × Rⁿ defined byF(x, y) = (x ₁y₁,,x_ny_n, f₁(x) – y₁,, f_n(x) – y_n) for every(x, y) R ₊ ²ⁿ . Under the assumption thatf is a uniformP-function, this paper establishes that the mappingF is a homeomorphism ofR ₊ ²ⁿ ontoR ₊ ⁿ × Rⁿ. This result provides a theoretical basis for a new continuation method of tracing the solution curve of the one parameter family of systems of equationsF(x, y) = tF(x ⁰, y⁰) and(x, y) R ₊ ²ⁿ from an arbitrary initial point(x ⁰, y⁰) R ₊ ²ⁿ witht = 1 until the parametert attains 0. This approach is an extension of the one used in the polynomially bounded algorithm recently given by Kojima, Mizuno and Yoshise for solving linear complementarity problems with positive semi-definite matrices.     

A general minimax theorem

This paper is concerned with minimax theorems for two-person zero-sum games (X, Y, f) with payofff and as main result the minimax equality inf supf (x, y)=sup inff (x, y) is obtained under a new condition onf. This condition is based on the concept of averaging functions, i.e. real-valued functions defined on some subset of the plane with min {x, y}< (x, y)x, y} forx y and (x, x)=x. After establishing some simple facts on averaging functions, we prove a minimax theorem for payoffsf with the following property: Forf there exist averaging functions and such that for any x₁, x₂ X, > 0 there exists x₀ X withf (x₀, y) > f (x₁,y),f (x₂,y))– for ally Y, and for any y₁, y₂ Y, > 0 there exists y₀ Y withf (x, y₀) (f (x, y₁),f (x, y₂))+. This result contains as a special case the Fan-König result for concave-convex-like payoffs in a general version, when we take linear averaging with (x, y)=x+(1–)y, (x, y)=x+(1–)y, 0 <, < 1.Then a class of hide-and-seek games is introduced, and we derive conditions for applying the minimax result of this paper.

---

Zusammenfassung In dieser Arbeit werden Minimaxsätze für Zwei-Personen-Nullsummenspiele (X, Y,f) mit Auszahlungsfunktionf behandelt, und als Hauptresultat wird die Gültigkeit der Minimaxgleichung inf supf (x, y)=sup inff (x, y) unter einer neuen Bedingung an f nachgewiesen. Diese Bedingung basiert auf dem Konzept mittelnder Funktionen, d.h. reellwertiger Funktionen, welche auf einer Teilmenge der Ebene definiert sind und dort der Eigenschaft min {x, y} < < (x, y)x, y} fürx y, (x, x)=x, genügen. Nach der Herleitung einiger einfacher Aussagen über mittelnde Funktionen beweisen wir einen Minimaxsatz für Auszahlungsfunktionenf mit folgender Eigenschaft: Zuf existieren mittelnde Funktionen und, so daß zu beliebigen x₁, x₂ X, > 0 mindestens ein x₀ X existiert mitf (x₀,y) (f (x ₁,y),f (x₂,y)) – für alley Y und zu beliebigen y₁, y₂ Y, > 0 mindestens ein y₀ Y existiert mitf (x, y₀) (f (x, y₁),f (x, y ₂))+ für allex X. Dieses Resultat enthält als Spezialfall den Fan-König'schen Minimaxsatz für konkav-konvev-ähnliche Auszahlungsfunktionen in einer allgemeinen Version, wenn wir lineare Mittelung mit (x, y)=x+(1–)y, (x, y)= x+(1–)y, 0 <, < 1, betrachten.Es wird eine Klasse von Suchspielen eingeführt, welche mit dem vorstehenden Resultat behandelt werden können.

     

Approximate first-order and second-order directional derivatives of a marginal function in convex optimization

Given a convex functionf: ^p × ^q (–, +], the marginal function is defined on ^p by (x)=inf{f(x, y)|y ^q }. Our purpose in this paper is to express the approximate first-order and second-order directional derivatives of atx ₀ in terms of those off at (x ₀,y ₀), wherey ₀ is any element for which (x ₀)=f(x ₀,y ₀).The author is indebted to one referee for pointing out an inaccuracy in an earlier version of Theorem 4.1.     

Bilateral difference method for solving the boundary value problem for an ordinary differential equation

A method is proposed for calculating the bilateral approximations of the solution of the boundary value problem on [0, 1] for the equation y+p(x)y-q(x)y=f(x) and the derivative of the solution having the maximum deviation O(h² (h)+h³) on {kh} _k ^N =0, where(t) is the sum of the continuity moduli of the functions p, q,f, on the set of points {kh} _k ^N =0, h=1/N by means of O(N) operations. The data obtained for fairly smooth p, q,f allow interpolation to be used for calculating the bilateral approximations of the solution and its higher derivatives having the maximum deviation O(h³) on [0, 1].Translated from Matematicheskie Zametkii, Vol. 11, No. 4, pp. 421–430, April, 1972.     

A Note on a Boundary Value Problem

In this note, we prove that, for Robins boundary value problem, a unique solution exists if f_x(t, x, x), f_x(t, x, x), (t), and (t) are continuous, and f_x -(t), f_x -(t), 4(t) ² + ²(t) ++ 2(t), and 4(t) ² + ²(t) + 2(t).AMS Subject Classification (2000) 34B15     

Stochastically monotone Markov Chains

Summary A real-valued discrete time Markov Chain {X _n} is defined to be stochastically monotone when its one-step transition probability function pr {X _n+1y¦ X _n=x} is non-increasing in x for every fixed y. This class of Markov Chains arises in a natural way when it is sought to bound (stochastically speaking) the process {X _n} by means of a smaller or larger process with the same transition probabilities; the class includes many simple models of applied probability theory. Further, a given stochastically monotone Markov Chain can readily be bounded by another chain {Y _n}, with possibly different transition probabilities and not necessarily stochastically monotone, and this is of particular value when the latter process leads to simpler algebraic manipulations. A stationary stochastically monotone Markov Chain {X _n} has cov(f(X ₀), f(X _n)) cov(f(X ₀), f(X _n+1))0 (n =1, 2,...) for any monotonic function f(·). The paper also investigates the definition of stochastic monotonicity on a more general state space, and the properties of integer-valued stochastically monotone Markov Chains.     

On second order sublinear oscillation

The basic purpose of this paper is to present a new oscillation criterion for second order sublinear ordinary differential equations of the formx(t) +a(t)f[x(t)] = 0,t t ₀>0, wherea is a continuous function on [t ₀, ) without any restriction on its sign andf is a continuous function on the real line, which is continuously differentiable, except possibly at 0, and satisfiesyf(y)>0 andf(y)>0 fory 0, and . The results obtained include the average behavior of the integral of the coefficienta.     

Integral averages and oscillation of second order sublinear differential equations

New oscillation criteria are given for the second order sublinear differential equation

Multiscale convergence and reiterated homogenization of parabolic problems

Reiterated homogenization is studied for divergence structure parabolic problems of the form u /t–div (a(x,x/,x/²,t,t/ ^k)u )=f. It is shown that under standard assumptions on the function a(x, y ₁,y ₂,t,) the sequence {u } of solutions converges weakly in L ² (0,T; H ₀ ¹ ()) to the solution u of the homogenized problem u/t– div(b(x,t)u)=f.This revised version was published online in April 2005 with a corrected missing date string.     

Continuity properties of the normal cone to the level sets of a quasiconvex function

Two main properties of the subgradient mapping of convex functions are transposed for quasiconvex ones. The continuity of the functionxf(x)^–1f(x) on the domain where it is defined is deduced from some continuity properties of the normal coneN to the level sets of the quasiconvex functionf. We also prove that, under a pseudoconvexity-type condition, the normal coneN(x) to the set {x:f(x)f(x)} can be expressed as the convex hull of the limits of type {N(x _n)}, where {x _n} is a sequence converging tox and contained in a dense subsetD. In particular, whenf is pseudoconvex,D can be taken equal to the set of points wheref is differentiable.This research was completed while the second author was on a sabbatical leave at the University of Montreal and was supported by a NSERC grant. It has its origin in the doctoral thesis of the first author (Ref. 1), prepared under the direction of the second author.The authors are grateful to an anonymous referee and C. Zalinescu for their helpful remarks on a previous version of this paper.     

Approximation and regular perturbation of optimal control problems via Hamilton-Jacobi theory

We present two convergence theorems for Hamilton-Jacobi equations and we apply them to the convergence of approximations and perturbations of optimal control problems and of two-players zero-sum differential games. One of our results is, for instance, the following. LetT andT _h be the minimal time functions to reach the origin of two control systemsy = f(y, a) andy = f _h (y, a), both locally controllable in the origin, and letK be any compact set of points controllable to the origin. If f _h –f Ch, then |T(x) – T _h (x)| C _K h , for all x K, where is the exponent of Hölder continuity ofT(x).     

Large Deviations of Local Times of Lévy Processes

For X(t) a real-valued symmetric Lévy process, its characteristic function is E(e ^iX(t))=exp(–t()). Assume that is regularly varying at infinity with index 1<2. Let L ^x _t denote the local time of X(t) and L* _t =sup _xR L ^x _t . Estimates are obtained for P(L ⁰ _t y) and P(L* _t y) as y and t fixed.     

Some stochastic processes related to random density functions

If { _n } is an orthonormal system and {a _n} is a sequence of random variables such that _n (a _n )²=1 a.s. thenf(t)=| _n a _{n n} (t)|² produces a randomly selcted density function. We study the properties off under the assumptions that |a _n| is decreasing to zero at a geometric rate and { _n } is one of the following four function systems: trigonometric Jacobi, Hermite, or Laguerre. It is shown that, with probability one,f is an analytic function,f has at most a finite number of zeros in any finite interval, and the tail off goes to zero rapidly.     

Mappings that preserve cones in Lobachevskii space

Let ⁿ be n-dimensional Lobachevskii space, and {l_x:x ⁿ} be a family of lines, parallel to a linel ₀, 0ⁿ (in a given direction). Let {c_x:Xⁿ} be a family of circular cones in ⁿ of opening with axes l_X and vertex X. Then, iff:ⁿⁿ(n>2) is a bijective mapping andf(C_x)=C _f(x), it follows thatf is a motion in the space ⁿ.Translated from Matematicheskie Zametki, Vol. 13, No. 5, pp. 687–694, May, 1973.     

The interpolation ofℓ r sequences by hp functions

The sequence spaceH ^P (z)={{f (z_h)}:f H ^p} is defined for a fixed sequence Z={z_k} of different points of the open unit disk and the Hardy class HP of analytic functions in the disk. For an arbitrary p[1, ) is constructed a point sequence Z= {z_k} such that ¹h ^p(z), but ^r h^p (Z) for r > 1. It follows from a well-known result of L. Carleson that the inclusions ^r h (Z) for all r[1,] are equivalent.Translated from Matematicheskie Zametki, Vol. 21, No. 4, pp. 503–508, April, 1977.     

Quadratic spline interpolation on uniform meshes

The interpolation problem at uniform mesh points of a quadratic splines(x _i)=f _i,i=0, 1,...,N ands(x ₀)=f₀ is considered. It is known that s–f=O(h ³) and s–f=O(h ²), whereh is the step size, and that these orders cannot be improved. Contrary to recently published results we prove that superconvergence cannot occur for any particular point independent off other than mesh points wheres=f by assumption. Best error bounds for some compound formulae approximatingf _i andf _i ⁽³⁾ are also derived.     

Solvability of a problem on the plane motion of a viscous incompressible fluid with a free noncompact boundary

One considers the problem of the plane motion of a viscous incompressible fluid which fills partially a container V, bounded by the straight line ₁ = {x:x ₂ = 0} and the contour (V₁), consisting of two semilines ⁽¹⁾ = {x:x ₁<–1,x ₂ = h₀} ⁽²⁾ = {x:x ₁ = 0,x ₂h₀+1} joined by a smooth curvel ⁽³⁾. One assumes that the motion is due to a nonzero flow and by the motion of the lower wall ₁ with a constant velocity R0. The unique solvability of this problem is proved for small R and .Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 110, pp. 174–179, 1981.In conclusion, the author expresses his deep gratitude to V. A. Solonnikov for his guidance.