On affine scaling algorithms for nonconvex quadratic programming

We investigate the use of interior algorithms, especially the affine-scaling algorithm, to solve nonconvex — indefinite or negative definite — quadratic programming (QP) problems. Although the nonconvex QP with a polytope constraint is a hard problem, we show that the problem with an ellipsoidal constraint is easy. When the hard QP is solved by successively solving the easy QP, the sequence of points monotonically converge to a feasible point satisfying both the first and the second order optimality conditions.Research supported in part by NSF Grant DDM-8922636 and the College Summer Grant, College of Business Administration, The University of Iowa.     

Partly convex programming and zermelo's navigation problems

Mathematical programs, that become convex programs after freezing some variables, are termed partly convex. For such programs we give saddle-point conditions that are both necessary and sufficient that a feasible point be globally optimal. The conditions require cooperation of the feasible point tested for optimality, an assumption implied by lower semicontinuity of the feasible set mapping. The characterizations are simplified if certain point-to-set mappings satisfy a sandwich condition.The tools of parametric optimization and basic point-to-set topology are used in formulating both optimality conditions and numerical methods. In particular, we solve a large class of Zermelo's navigation problems and establish global optimality of the numerical solutions.Research partly supported by NSERC of Canada.     

Finite-dimensional discrete linear stochastic accelerated-time systems and their application to quadratic stochastic dynamical systems

The limiting behavior of the trajectories {x ⁽ⁿ⁾ } of linear discrete stochastic systems of the form (K, P ^an+b ) _nN , whereK is the standard simplex in ^N ,P: ^{N N} is a linear operator,PK K,a ft,b ,a+b>0, is described. An application to a class of quadratic stochastic dynamical systems is considered.Translated fromMatematicheskie Zametki, Vol. 59, No. 5, pp. 709–718, May, 1996.     

Extended Rotation and Scaling Groups for Nonlinear Evolution Equations

A (1+1)-dimensional nonlinear evolution equation is invariant under the rotation group if it is invariant under the infinitesimal generator V=x _u –u _x . Then the solution satisfies the condition u _x=–x/u. For equations that do not admit the rotation group, we provide an extension of the rotation group. The corresponding exact solution can be constructed via the invariant set R ₀={u: u _x=xF(u)} of a contact first-order differential structure, where F is a smooth function to be determined. The time evolution on R ₀ is shown to be governed by a first-order dynamical system. We introduce an extension of the scaling groups characterized by an invariant set that depends on two constants and n1. When =0, it reduces to the invariant set S ₀ introduced by Galaktionov. We also introduce a generalization of both the scaling and rotation groups, which is described by an invariant set E ₀ with parameters a and b. When a=0 or b=0, it respectively reduces to R ₀ or S ₀. These approaches are used to obtain exact solutions and reductions of dynamical systems of nonlinear evolution equations.     

Distribution of the number of nonappearing lengths of cycles in a random mapping

One-to-one random mappings of the set 1, 2,..., n onto itself are considered. Limit theorems are proved for the quantities _i, 0in, max _i, min _i, where _i is the number of 0in components of the vector ( ₁, ₂,..., _n) which are equal to i, 0< i< n, and ar is the number of components of dimension r of the random mapping.Translated from Matematicheskle Zametki, Vol. 23, No. 6, pp. 895–898, June, 1978.The author is grateful to V. P. Chistyakov and V. E. Stepanov for many useful remarks.     

Weak and Strong Optimality Conditions for Constrained Control Problems with Discontinuous Control

In recent years, sufficient optimality criteria and solution stability in optimal control have been investigated widely and used in the analysis of discrete numerical methods. These results were concerned mainly with weak local optima, whereas strong optimality has been considered often as a purely theoretical aspect. In this paper, we show via an example problem how weak the weak local optimality can be and derive new strong optimality conditions. The criteria are suitable for practical verification and can be applied to the case of discontinuous controls with changes in the set of active constraints.     

Affine geometry over free unitary modules

In this paper we consider systems (P,L,,), where P is an arbitrary non-empty set, L a set of subsets of p and resp. a relation on PxP resp. LxL. In successive stages adding geometrical axioms, we characterize the class of those structures (P,L, ,), which coincides — up to isomorphisms — with the class of all Affine Barbilian-Spaces.     

Role of information in the stochastic zero-sum differential game

In this paper, a linear-quadratic Gaussian zero-sum differential game is studied. Maneuverability is defined to measure players' strength. It is shown that a more maneuverable player would prefer a more observable information system. An example is given to show that a more controllable player might not prefer more observable measurements in the stochastic environment.The research reported in this paper was made possible through support extended to the Division of Engineering and Applied Physics, Harvard University, by the US Office of Naval Research under the Joint Services Electronics Program by Contract No. N00014-75-c-0648 and by the National Science Foundation under Grant No. GK31511.     

A bound for the error in the numerical integration of a first order quasilinear equation

We obtain a bound for the error in the numerical integration of the quasilinear equation u_t+((u))_x=0 by a finite difference method in the case when (u)0.Translated from Matematicheskie Zametki, Vol. 12, No. 2, pp. 207–215, February, 1973.     

Geometric Convergence Rates for Time-Sampled Markov Chains

We consider time-sampled Markov chain kernels, of the form P = _n n P ⁿ . We prove bounds on the total variation distance to stationarity of such chains. We are motivated by the analysis of near-periodic MCMC algorithms.     

Parametric stochastic convexity and concavity of stochastic processes

A collection of random variables {X(), } is said to be parametrically stochastically increasing and convex (concave) in if X() is stochastically increasing in , and if for any increasing convex (concave) function , E(X()) is increasing and convex (concave) in whenever these expectations exist. In this paper a notion of directional convexity (concavity) is introduced and its stochastic analog is studied. Using the notion of stochastic directional convexity (concavity), a sufficient condition, on the transition matrix of a discrete time Markov process {X _n(), n=0,1,2,...}, which implies the stochastic monotonicity and convexity of {X _n(), }, for any n, is found. Through uniformization these kinds of results extend to the continuous time case. Some illustrative applications in queueing theory, reliability theory and branching processes are given.Supported by the Air Force Office of Scientific Research, U.S.A.F., under Grant AFOSR-84-0205. Reproduction in whole or in part is permitted for any purpose by the United States Government.     

On the consistency of conditional maximum likelihood estimators

Let {P _, : , H} be a family of probability measures admitting a sufficient statistic for the nuisance parameter . The paper presents conditions for consistency of (asymptotic) conditional maximum likelihood estimators for . An application to the Rasch-model (a stochastic model for psychological tests) yields a condition on the sequence of nuisance parameters which is sufficient for strong consistency of conditional maximum likelihood estimators, and necessary for the existence of any weakly consistent estimator-sequence.     

On Smoothness Properties and Approximability of Optimal Control Functions

The theory of discretization methods to control problems and their convergence under strong stable optimality conditions in recent years has been thoroughly investigated by several authors. A particularly interesting question is to ask for a natural smoothness category for the optimal controls as functions of time.In several papers, Hager and Dontchev considered Riemann integrable controls. This smoothness class is characterized by global, averaged criteria. In contrast, we consider strictly local properties of the solution function. As a first step, we introduce tools for the analysis of L elements at a point. Using afterwards Robinson's strong regularity theory, under appropriate first and second order optimality conditions we obtain structural as well as certain pseudo-Lipschitz properties with respect to the time variable for the control.Consequences for the behavior of discrete solution approximations are discussed in the concluding section with respect to L as well as L ₂ topologies.     

Constraint qualifications in quasidifferentiable optimization

The classical linearization procedure for differentiable nonlinear programming problems can be naturally generalized to the quasidifferentiable case. As in the classical case one has to impose so-called constraint qualifications on the constraint functions in order to ensure that optimality of a feasible point implies optimality of the nullvector for the corresponding quasilinearized problem. We present various constraint qualifications in a unified setting, propose a new one, and investigate the relations between these conditions.Supported by DFG Grant Pa 219/5-1.     

On a theorem of lovász on covers inr-partite hypergraphs

A theorem of Lovász asserts that (H)/*(H)r/2 for everyr-partite hypergraphH (where and * denote the covering number and fractional covering number respectively). Here it is shown that the same upper bound is valid for a more general class of hypergraphs: those which admit a partition (V ₁, ...,V _k ) of the vertex set and a partitionp ₁+...+p _k ofr such that |eV _i |p _i r/2 for every edgee and every 1ik. Moreover, strict inequality holds whenr>2, and in this form the bound is tight. The investigation of the ratio /* is extended to some other classes of hypergraphs, defined by conditions of similar flavour. Upper bounds on this ratio are obtained fork-colourable, stronglyk-colourable and (what we call)k-partitionable hypergraphs.Supported by grant HL28438 at MIPG, University of Pennsylvania, and by the fund for the promotion of research at the Technion.This author's research was supported by the fund for the promotion of research at the Technion.     

On basicity of exponentials inL P (dμ) and general prediction problems

Let be a nonnegative measure on the unit circle in the complex plane and 1<p<. It is of interest to find conditions on so that the set of exponentialse ⁱⁿ form a strongM-basis forL ^p (d). Some partial results are proved which can shed some light on this important open question. These results are of fundamental importance in the prediction theory of stochastic processes and other fields of applications. These results is then used to obtain a theorem which reduces some prediction problems to easier ones.To 80^th birthday of Paul ErdsThis research is supported by Office of Naval Research Grant No N00014-89-J-1824.     

On Infinite Systems of Linear Autonomous and Nonautonomous Stochastic Equations

The solvability of autonomous and nonautonomous stochastic linear differential equations in is studied. The existence of strong continuous (L^p-continuous) solutions of autonomous linear stochastic differential equations in with continuous (L^p-continuous) right-hand sides is proved. Uniqueness conditions are obtained. We give examples showing that both deterministic and stochastic linear nonautonomous differential equations with the same operator in may fail to have a solution. We also establish existence and uniqueness conditions for nonautonomous equations.     

Nondifferential optimization via adaptive smoothing

The problem of minimizing a nondifferential functionx f(x) (subject, possibly, to nondifferential constraints) is considered. Conventional algorithms are employed for minimizing a differential approximationf off (subject to differentiable approximations ofg). The parameter is adaptively reduced in such a way as to ensure convergence to points satisfying necessary conditions of optimality for the original problem.This research was supported by the UK Science and Engineering Research Council, the National Science Foundation under Grant No. ECS-8121149, and the Joint Services Electronics Program, Contract No. F49620-79-C-0178.     

On Dirichlet series satisfying Riemann's functional equation

Summary According to convention, Hamburger's theorem (1921) says-roughly-that Riemann's (s) is uniquely determined by its functional equation. In 1944 Hecke pointed out that there are two distinct versions of Hamburger's theorem. Hecke's remark has led me, in examining just how rough the convention is, to prove that, with a weakening of certain auxiliary conditions, there are infinitely many linearly independent solutions of Riemann's functional equation (Theorem 1). In Theorem 1, as in Hamburger's theorem, the weight parameter is 1/2. In Theorem 2 we obtain stronger results when this parameter is 2: a Mittag-Leffler theorem for Dirichlet series with functional equations.Oblatum 23-XII-1992 & 9-IX-1993Research supported in part by NSA/MSP Grant MDA 90-H-4025 To the memory of Martin Eichler