Coupled intervals in the discrete calculus of variations: necessity and sufficiency

In this work we study nonnegativity and positivity of a discrete quadratic functional with separately varying endpoints. We introduce a notion of an interval coupled with 0, and hence, extend the notion of conjugate interval to 0 from the case of fixed to variable endpoint(s). We show that the nonnegativity of the discrete quadratic functional is equivalent to each of the following conditions: The nonexistence of intervals coupled with 0, the existence of a solution to Riccati matrix equation and its boundary conditions. Natural strengthening of each of these conditions yields a characterization of the positivity of the discrete quadratic functional. Since the quadratic functional under consideration could be a second variation of a discrete calculus of variations problem with varying endpoints, we apply our results to obtain necessary and sufficient optimality conditions for such problems. This paper generalizes our recent work in [R. Hilscher, V. Zeidan, Comput. Math. Appl., to appear], where the right endpoint is fixed.     

Equivalent conditions to the nonnegativity of a quadratic functional in discrete optimal control

In this paper we provide a characterization of the nonnegativity of a discrete quadratic functional ? with fixed right endpoint in the optimal control setting. This characterization is closely related to the kernel condition earlier introduced by M. Bohner as a part of a focal points definition for conjoined bases of the associated linear Hamiltonian difference system. When this kernel condition is satisfied only up to a certain critical index m, the traditional conditions, which are the focal points, conjugate intervals, implicit Riccati equation, and partial quadratic functionals, must be replaced by a new condition. This new condition is determined to be the nonnegativity of a block tridiagonal matrix, representing the remainder of ? after the index m, on a suitable subspace. Applications of our result include the discrete Jacobi condition, a unification of the nonnegativity and positivity of ? into one statement, and an improved result for the special case of the discrete calculus of variations. Even when both endpoints of ? are fixed, this paper provides a new result. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Discrete Optimal Control: Second Order Optimality Conditions

In this paper, we present a survey and refinement of our recent results in the discrete optimal control theory. For a general nonlinear discrete optimal control problem (P) , second order necessary and sufficient optimality conditions are derived via the nonnegativity ( I S 0) and positivity ( I >0) of the discrete quadratic functional I corresponding to its second variation. Thus, we fill the gap in the discrete-time theory by connecting the discrete control problems with the theory of conjugate intervals, Hamiltonian systems, and Riccati equations. Necessary conditions for I S 0 are formulated in terms of the positivity of certain partial discrete quadratic functionals, the nonexistence of conjugate intervals, the existence of conjoined bases of the associated linear Hamiltonian system, and the existence of solutions to Riccati matrix equations. Natural strengthening of each of these conditions yields a characterization of the positivity of I and hence, sufficiency criteria for the original problem (P) . Finally, open problems and perspectives are also discussed.     

Nonnegativity and positivity of quadratic functionals in discrete calculus of variations: survey

In this paper we provide a survey of characterizations of the nonnegativity and positivity of discrete quadratic functionals which arise as the second variation for nonlinear discrete calculus of variations problems. These characterizations are in terms of (i) (strict) conjugate and (strict) coupled intervals, (ii) the conjoined bases of the associated Jacobi difference equation, and (iii) the solution of the corresponding Riccati difference equation. The results depend on the form of the boundary conditions of the quadratic functional and, basically, we distinguish three types: (a) separable endpoints with zero right endpoint (this of course includes the simplest case of both zero endpoints), (b) separable endpoints, and (c) jointly varying endpoints.     

Second Order Sufficiency Criteria for a Discrete Optimal Control Problem

In this work, we derive second order necessary and sufficient optimality conditions for a discrete optimal control problem with one variable endpoint and the other fixed, and with equality control constraints. In particular, the positivity of the second variation, which is a discrete quadratic functional with appropriate boundary conditions, is characterized in terms of the nonexistence of intervals conjugate to 0, the existence of a certain conjoined basis of the associated linear Hamiltonian difference system, or the existence of a symmetric solution to the implicit and explicit Riccati matrix equations. Some results require a certain minimal normality assumption, and are derived using the sensitivity analysis technique.     

Time scale symplectic systems without normality

We present a theory of the definiteness (nonnegativity and positivity) of a quadratic functional F over a bounded time scale. The results are given in terms of a time scale symplectic system (S), which is a time scale linear system that generalizes and unifies the linear Hamiltonian differential system and discrete symplectic system. The novelty of this paper resides in removing the assumption of normality in the characterization of the positivity of F, and in establishing equivalent conditions for the nonnegativity of F without any normality assumption. To reach this goal, a new notion of generalized focal points for conjoined bases (X,U) of (S) is introduced, results on the piecewise-constant kernel of X(t) are obtained, and various Picone-type identities are derived under the piecewise-constant kernel condition. The results of this paper generalize and unify recent ones in each of the discrete and continuous time setting, and constitute a keystone for further development in this theory.     

Riccati inequality and other results for discrete symplectic systems

In this paper we establish several new results regarding the positivity and nonnegativity of discrete quadratic functionals F associated with discrete symplectic systems. In particular, we derive (i) the Riccati inequality for the positivity of F with separated endpoints, (ii) a characterization of the nonnegativity of F for the case of general (jointly varying) endpoints, and (iii) several perturbation-type inequalities regarding the nonnegativity of F with zero endpoints. Some of these results are new even for the special case of discrete Hamiltonian systems.     

Jacobi's condition for singular extremals: An extended notion of conjugate points

For the simple fixed endpoint problem in the calculus of variations, Jacobi's condition (“there are no conjugate points in the interior of the underlying time interval”) is necessary for optimality if the trajectory under consideration is nonsingular. In this paper, we extend the notion of conjugate points so that the above condition (in terms of this new notion) is necessary also for singular extremals. This is achieved by showing that, without any additional assumption on the trajectory, the nonnegativity of the second variation on the space of admissible variations is equivalent to the nonexistence of these “extended conjugate points”.     

Reid Roundabout Theorem for Symplectic Dynamic Systems on Time Scales

The principal aim of this paper is to state and prove the so-called Reid roundabout theorem for the symplectic dynamic system (S) z ^Δ = \cal S _t z on an arbitrary time scale \Bbb T , so that the well known case of differential linear Hamiltonian systems ( \Bbb T = \Bbb R ) and the recently developed case of discrete symplectic systems ( \Bbb T = \Bbb Z ) are unified. We list conditions which are equivalent to the positivity of the quadratic functional associated with (S), e.g. disconjugacy (in terms of no focal points of a conjoined basis) of (S), no generalized zeros for vector solutions of (S), and the existence of a solution to the corresponding Riccati matrix equation. A certain normality assumption is employed. The result requires treatment of the quadratic functionals both with general and separated boundary conditions. Accepted 28 August 2000. Online publication 26 February 2001.     

Lyapunov sequences for exponential dichotomies

For a linear nonautonomous dynamics with discrete time, we study the relation between nonuniform exponential dichotomies and strict Lyapunov sequences. Given such a sequence, we obtain the stable and unstable subspaces from the intersection of the images and preimages of the cones defined by each element of the sequence. The main difficulty is to extract some information about the angles between the stable and unstable subspaces (or some appropriate notion in the case of Banach spaces) from the Lyapunov sequence. In particular, for a large class of nonuniform exponential dichotomies we give a complete characterization in terms of strict quadratic Lyapunov sequences, that is, strict Lyapunov sequences defined by quadratic forms. We also construct explicitly families of strict Lyapunov sequences for each nonuniform exponential dichotomy, in terms of Lyapunov norms.     

A notion of selective ultrafilter corresponding to topological Ramsey spaces

We introduce the relation of almost‐reduction in an arbitrary topological Ramsey space ? as a generalization of the relation of almost‐inclusion on ?^[∞]. This leads us to a type of ultrafilter ?? ? ? which corresponds to the well‐known notion of selective ultrafilter on ?. The relationship turns out to be rather exact in the sense that it permits us to lift several well‐known facts about selective ultrafilters on ? and the Ellentuck space ?^[∞] to the ultrafilter ?? and the Ramsey space ?. For example, we prove that the open coloring axiom holds on L (?)[??], extending therefore the result from [3] which gives the same conclusion for the Ramsey space ?^[∞]. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Applications of time scale symplectic systems without normality

Recently, the authors obtained new characterizations of the positivity and nonnegativity of a time scale quadratic functional F with separable endpoints related to a time scale symplectic system (S). In these results, the assumption of normality is absent. In this paper we present applications of such results. Namely, without assuming normality we derive Sturmian comparison theorems, results for general jointly varying endpoints, and characterizations of the positivity of F via the corresponding time scale Riccati equation, a certain perturbed quadratic functional, and a time scale Riccati inequality. These results generalize and unify many recent as well as classical ones.     

Random interval graphs

In this paper we introduce a notion ofrandom interval graphs: the intersection graphs of real, compact intervals whose end points are chosen at random. We establish results about the number of edges, degrees, Hamiltonicity, chromatic number and independence number of almost all interval graphs.     

Singular Sturmian separation theorems for nonoscillatory symplectic difference systems

ABSTRACT

In this paper, we derive new singular Sturmian separation theorems for nonoscillatory symplectic difference systems on unbounded intervals. The novelty of the presented theory resides in two aspects. We introduce the multiplicity of a focal point at infinity for conjoined bases, which we incorporate into our new singular Sturmian separation theorems. At the same time we do not impose any controllability assumption on the symplectic system. The presented results naturally extend and complete the known Sturmian separation theorems on bounded intervals by J. V. Elyseeva [Comparative index for solutions of symplectic difference systems, Differential Equations 45(3) (2009), pp. 445–459, translated from Differencial'nyje Uravnenija 45 (2009), no. 3, 431–444], as well as the singular Sturmian separation theorems for eventually controllable symplectic systems on unbounded intervals by O. Do?lý and J. Elyseeva [Singular comparison theorems for discrete symplectic systems, J. Difference Equ. Appl. 20(8) (2014), pp. 1268–1288]. Our approach is based on developing the theory of comparative index on unbounded intervals and on the recent theory of recessive and dominant solutions at infinity for possibly uncontrollable symplectic systems by the authors [P. ?epitka and R. ?imon Hilscher, Recessive solutions for nonoscillatory discrete symplectic systems, Linear Algebra Appl. 469 (2015), pp. 243–275; P. ?epitka and R. ?imon Hilscher, Dominant and recessive solutions at infinity and genera of conjoined bases for discrete symplectic systems, J. Difference Equ. Appl. 23(4) (2017), pp. 657–698]. Some of our results, including the notion of the multiplicity of a focal point at infinity, are new even for an eventually controllable symplectic difference system.     

Stability by the linear approximation for discrete equations

This paper is concerned with exponential stability of solutions of perturbed discrete equations. For a given m>1 we will provide necessary and sufficient conditions for exponential stability of all perturbed systems with perturbation of order m under the assumption that the unperturbed linear system is exponentially stable. Basing on this result we obtained necessary and sufficient conditions for exponential stability of the perturbed system for all perturbations of order m>1 for regular systems. Our results are expressed in terms of regular coefficients of the unperturbed system.     

Multiplicities of focal points for discrete symplectic systems: revisited

In this note, we define a notion of multiplicity of focal points for conjoined bases of discrete symplectic systems. We show that this definition is equivalent to the one given by Kratz in [Discrete oscillation, J. Difference Equ. Appl., 9(1), 135–147 (2003)] and, furthermore, it has a natural connection to the newly developed continuous time theory on linear Hamiltonian differential systems. Many results obtained recently by Bohner, Do?lý, and Kratz regarding the non-negativity of the corresponding discrete quadratic functionals, Sturmian separation and comparison theorems, and oscillation theorems relating the number of focal points of a certain special conjoined basis with the number of eigenvalues of the associated discrete symplectic eigenvalue problem, are now formulated in terms of this alternative definition of multiplicities.     

The maximum interval number of graphs with given genus

The interval number of a graph G, denoted i(G), is the least positive integer t such that G is the intersection graph of sets, each of which is the union of t compact real intervals. It is known that every planar graph has interval number at most 3 and that this result is best possible. We investigate the maximum value of the interval number for graphs with higher genus and show that the maximum value of the interval number of graphs with genus g is between ?√g? and 3 + ?√3g?. We also show that the maximum arboricity of graphs with genus g is either 1 + ?√3g? or 2 + ?√3g?.     

The time-varying discrete four block Nehari problem: A generalized Popov-Yakubovich type approach

The paper provides necessary and sufficient solvability conditions for the time-variant discrete four block Nehari problem in terms of the existence of the stabilizing solutions to two coupled Riccati equations. A parametrization of the class of all solutions is also given. The results are easily obtained from a signature condition — a generalized Popov Yakubovich type argument-imposed on an appropiate rational node. The present development may be seen as an alternative of the theory developed by Gohberg, Kaashoek and Woerdeman [15].     

Vanishing of the costate in pontryagin’s maximum principle and singular time optimal controls

We provide examples of time and norm optimal controls that satisfy Pontryagins maximum principle in an interval 0 t T but with a costate that vanishes in 0 t T - with < T. A refinement of this construction produces time optimal controls which do not satisfy the maximum principle, even in weak form. On the positive side, we show that when we drive to zero the costate is nonzero in the whole control interval.