Search

The paper considers the problem of absolute stability of systems with time-periodic nonlinear blocks. The approach presented in this paper is based on the so-called quadratic criterion and relies on integral-quadratic inequalities (constraints), which also involve time delays. The results are given in the frequency domain. The paper also includes geometric interpretation and numerical treatment of the new stability criteria. [ABSTRACT FROM AUTHOR]

The paper studies the convergence properties of (continuous-time) best-response dynamics from game theory. Despite their fundamental role in game theory, best-response dynamics are poorly understood in many games of interest due to the discontinuous, set-valued nature of the best-response map. The paper focuses on elucidating several important properties of best-response dynamics in the class of multiagent games known as potential games--a class of games with fundamental importance in multiagent systems and distributed control. It is shown that in almost every potential game and for almost every initial condition, the best-response dynamics (i) have a unique solution, (ii) converge to pure-strategy Nash equilibria, and (iii) converge at an exponential rate. [ABSTRACT FROM AUTHOR]

In this paper we investigate a passivity approach to collective coordination and synchronization problems in the presence of quantized measurements and show that coordination tasks can be achieved in a practical sense for a large class of passive systems. [ABSTRACT FROM AUTHOR]

This paper considers stability and harmonic analysis of a general class of pulse-modulated systems. The systems are modeled using the dynamic phasor model, which explores the cyclic nature of the modulation functions by representing the system state as a Fourier series expansion defined over a moving time window. The contribution of the paper is to show that a special type of periodic Lyapunov function can be used to analyze the system and that the analysis conditions become tractable for computation after truncation. The approach provides a trade-off between complexity and accuracy that includes standard state space averaged models as a special case. The paper also shows how the dynamic phasor model can be used to derive a frequency domain input-to-state map which is analogous to the harmonic transfer function. [ABSTRACT FROM AUTHOR]

In the first part of the paper, we reexamine the all-pairs shortest path (APSP) problem and present a new algorithm with running time O(n³ log³ log n/ log² n), which improves all known algorithms for general real-weighted dense graphs. In the second part of the paper, we use fast matrix multiplication to obtain truly subcubic APSP algorithms for a large class of "geometrically weighted" graphs, where the weight of an edge is a function of the coordinates of its vertices. For example, for graphs embedded in Euclidean space of a constant dimension d, we obtain a time bound near O(n3-(3-ω)/(2d+4)), where logω < 2.376; in two dimensions, this is O(n2.922). Our framework greatly extends the previously considered case of small-integer-weighted graphs, and incidentally also yields the first truly subcubic result (near O(n3-(3-logω)/4) = O(n2.844) time) for APSP in real- vertex-weighted graphs, as well as an improved result (near O(n(3+logω)/2) = O(n2.688) time) for the all-pairs lightest shortest path problem for small-integer-weighted graphs. [ABSTRACT FROM AUTHOR]

Dissipative systems have played an important role in the analysis and synthesis of dynamical systems. The commonly used definition of dissipativity often requires an assumption on the controllability of the system. In this paper we use a definition of dissipativity that is slightly different (and less often used in the literature) to study a linear, time-invariant, possibly uncontrollable dynamical system. We provide a necessary and sufficient condition for an uncontrollable system to be strictly dissipative with respect to a supply rate under the assumption that the uncontrollable poles are not "mixed"; i.e., no pair of uncontrollable poles is symmetric about the imaginary axis. This condition is known to be related to the solvability of a Lyapunov equation; we link Lyapunov functions for autonomous systems to storage functions of an uncontrollable system. The set of storage functions for a controllable system has been shown to be a convex bounded polytope in the literature. We show that for an uncontrollable system the set of storage functions is unbounded, and that the unboundedness arises precisely due to the set of Lyapunov functions for an autonomous linear system being unbounded. Further, we show that stabilizability of a system results in this unbounded set becoming bounded from below. Positivity of storage functions is known to be very important for stability considerations because the maximum stored energy that can be drawn out is bounded when the storage function is positive. In this paper we establish the link between stabilizability of an uncontrollable system and existence of positive definite storage functions. In most of the results in this paper, we assume that no pair of the uncontrollable poles of the system is symmetric about the imaginary axis; we explore the extent of necessity of this assumption and also prove some results for the case of single output systems regarding this necessity. [ABSTRACT FROM AUTHOR]

This paper considers an extension of the Merton optimal investment problem to the case where the risky asset is subject to transaction costs and capital gains taxes. We derive the dynamic programming equation in the sense of constrained viscosity solutions. We next introduce a family of functions (Vϵ)ϵ>0, which converges to our value function uniformly on compact subsets, and which is characterized as the unique constrained viscosity solution of an approximation of our dynamic programming equation. In particular, this result justifies the numerical results reported in the accompanying paper [I. Ben Tahar, H. M. Soner, and N. Touzi (2005), Modeling Continuous-Time Financial Markets with Capital Gains Taxes, preprint, http://www.cmap.polytechnique.fr/~touzi/bst06.pdf]. [ABSTRACT FROM AUTHOR]

In this paper we discuss stability and stabilization of continuous and discrete multidimensional input/output (IO) behaviors (of dimension r) which are described by linear systems of complex partial differential (resp., difference) equations with constant coefficients, where the signals are taken from various function spaces, in particular from those of polynomial-exponential functions. Stability is defined with respect to a disjoint decomposition of the r-dimensional complex space into a stable and an unstable region, with the standard stable region in the one-dimensional continuous case being the set of complex numbers with negative real part. A rational function is called stable if it has no poles in the unstable region. An IO behavior is called stable if the characteristic variety of its autonomous part has no points in the unstable region. This is equivalent to the stability of its transfer matrix and an additional condition. The system is called stabilizable if there is a compensator IO system such that the output feedback system is well-posed and stable. We characterize stability and stabilizability and construct all stabilizing compensators of a stabilizable IO system (parametrization). The theorems and proofs are new but essentially inspired and influenced by and related to the stabilization theorems concerning multidimensional IO maps as developed, for instance, by Bose, Guiver, Shankar, Sule, Xu, Lin, Ying, Zerz, and Quadrat and, of course, the seminal papers of Vidyasagar, Youla, and others in the one-dimensional case. In contrast to the existing literature, the theorems and proofs of this paper do not need or employ the so-called fractional representation approach, i.e., various matrix fraction descriptions of the transfer matrix, thus avoiding the often lengthy matrix computations and seeming to be of interest even for one-dimensional systems (at least to the author). An important mathematical tool, new in systems theory, is Gabriel's localization theory which, only in the case of ideal-convex (Shankar, Sule) unstable regions, coincides with the usual one. Algorithmic tests for stability, stabilizability, and ideal-convexity, and the algorithmic construction of stabilizing compensators, are addressed but still encounter many difficulties; see in particular the open problems listed by Xu et al. [ABSTRACT FROM AUTHOR]

The ultimate objective of this paper is to develop new techniques that can be used for the analysis of performance degradation due to statistical uncertainty for a wide class of linear stochastic systems. For this we need new technical tools similar to those used in [L. Gerencsér, Statist. Plann. Inference, 41 (1994), pp. 303–325]. The immediate technical objective is to extend the previous technical results to the Djereveckii-Fradkov-Ljung scheme with enforced boundedness. Our starting point is a standard approximation of the estimation error used in the asymptotic theory of recursive estimation. Tight control of the difference between the estimation error and its standard approximation, referred to as residuals, is a crucial point in our applications. The main technical advance of the present paper is a set of strong approximation theorems for three closely related recursive estimation algorithms in which, for any q ≥ 1, the Lq-norms of the residual terms are shown to tend to zero with rate N-1/2-ϵ with some ϵ > 0. This is a significant extension of previous results for the recursive prediction error or RPE estimator of ARMA processes given in [L. Gerencsér, Systems Control Lett., 21 (1993), pp. 347–351]. Two useful corollaries will be derived. In the first a standard transform of the estimation-error process for the basic recursive estimation method, Algorithm CR, will be shown to be L-mixing, while in the second the asymptotic covariance matrix of the estimator for the same method will be given. Applications to multivariable adaptive prediction and the minimum-variance self-tuning regulator for ARMAX systems will be described. [ABSTRACT FROM AUTHOR]

The paper describes the set of solutions of the discrete-time algebraic Riccati equation. It is shown that each solution is a combination of a pair of opposite unmixed solutions. There is a one-to-one correspondence between solutions and invariant subspaces of the closed loop matrix of an unmixed solution. The results of the paper provide an extended counterpart of the parametrization theory of continuous-time algebraic Riccati equations by Willems, Coppel, and Shayman. [ABSTRACT FROM AUTHOR]

Various sufficient conditions for approximate controllability of linear evolution systems in abstract spaces have been obtained, but approximate controllability of semilinear control systems usually requires some complicated and limited assumptions. In this paper, we show the approximate controllability of the abstract semilinear deterministic and stochastic control systems under the natural assumption that the associated linear control system is approximately control-lable. The results are obtained using new properties of symmetric operators (which are proved in this paper), compact semigroups, the Schauder fixed point theorem, and/or the contraction mapping principle. [ABSTRACT FROM AUTHOR]

This paper studies the impulse control of a general Markov process under the average (or ergodic) cost when the impulse instants are restricted to be the arrival times of an exogenous process, and this restriction is referred to as a constraint. A detailed setting is described, a characterization of the optimal cost is obtained as a solution of an HJB equation, and an optimal impulse control is identified. [ABSTRACT FROM AUTHOR]

Markov chain Monte Carlo (MCMC) has been widely used to approximate the expectation of the statistic of a given probability measure π on a finite set, and the asymptotic variance is a typical approach to evaluating the performance of MCMC methods. In this paper, we provide a lower bound of the worst-case analysis of the asymptotic variance over general Markov chains with invariant probability π, reversible as well as nonreversible ones, and construct an optimal transition matrix that achieves this lower bound. In fact, for any statistic f to be evaluated, an MCMC with the constructed optimal transition matrix produces a smaller asymptotic variance than independent sampling. [ABSTRACT FROM AUTHOR]

In this paper we treat null-controllability properties for the linear Kuramoto- Sivashinsky equation on a network with two types of boundary conditions. More precisely, the equation is considered on a star-shaped tree with Dirichlet and Neumann boundary conditions. By using the moment theory we can derive null-controllability properties with boundary controls acting on the external vertices of the tree. In particular, the controllability holds if the anti-diffusion parameter of the equation does not belong to a critical countable set of real numbers. We point out that the critical set for which the null-controllability fails differs from the first model to the second one. [ABSTRACT FROM AUTHOR]

This paper deals with shape optimization for elastic materials under stochastic loads. It transfers the paradigm of stochastic dominance, which allows for flexible risk aversion via comparison with benchmark random variables, from finite-dimensional stochastic programming to shape optimization. Rather than handling risk aversion in the objective, this enables risk aversion by including dominance constraints that single out subsets of nonanticipative shapes which compare favorably to a chosen stochastic benchmark. This new class of stochastic shape optimization problems arises by optimizing over such feasible sets. The analytical description is built on risk-averse cost measures. The actual optimized cost functional measures the volume and perimeter of the structure. In the implementation, shapes are represented by a phase field which permits an easy estimate of a regularized perimeter. The analytical description and the numerical implementation of dominance constraints are built on risk-averse measures for the cost functional. A suitable numerical discretization is obtained using finite elements both for the displacement and the phase field function. Different numerical experiments demonstrate the potential of the proposed stochastic shape optimization model and in particular the impact of high variability of forces or probabilities in the different realizations. [ABSTRACT FROM AUTHOR]

This paper discusses asymptotic analysis and adaptive design of convex estimators over the Hölder class under the sup-norm risk and the pointwise risk using constrained optimization and asymptotic statistical techniques. Specifically, convex B-spline estimators are proposed to achieve uniform optimal convergence rates and adaptive procedures. The presence of the convex shape constraint complicates asymptotic performance analysis, particularly uniform convergence analysis. This in turn requires deep understanding of a family of size varying constrained optimization problems on spline coeficients. To address these issues, we establish the uniform Lipschitz property of optimal spline coeficients in the l∞-norm by exploiting the structure of underlying constrained optimization 8 problems. By using this property, polyhedral theory, and statistical techniques, we show that the convex B-spline estimator attains uniform consistency and optimal rates of convergence on the entire interval of interest over the Hölder class under the sup-norm risk and the pointwise risk. In addition, adaptive estimates are constructed under both risks when the Hölder exponent is between one and two. These estimates achieve a maximal risk within a constant factor of the minimax risk over the Hölder class. [ABSTRACT FROM AUTHOR]

This paper deals with input adaptation in dynamic processes in order to guarantee feasible and optimal operation despite the presence of uncertainty. For those optimal control problems having terminal and mixed control-state path constraints, two orthogonal sets of adaptation directions can be distinguished in the input space: the sensitivity-seeking directions, along which a small variation from an optimal nominal solution will not affect the respective active constraints, and the complementary constraint-seeking directions, along which a variation will affect the respective constraints. It follows that selective input adaptation strategies can be defined, namely, adaptation in the sensitivity- and constraint-seeking directions. This paper proves the important result that, for small parametric perturbations, the cost variation resulting from adaptation in the sensitivity-seeking directions (over no input adaptation) is typically smaller than the cost variation due to adaptation in the constraint-seeking directions. It is also established that no selective input adaptation along a sensitivity-seeking direction can reduce the dominant, first-order term in the optimality gap; adaptation along a constraint-seeking direction is necessary to cancel it out. These results are illustrated with two numerical case studies. [ABSTRACT FROM AUTHOR]

This paper presents a time optimal control problem with control constraints of the rectangular type for internally controlled heat equations. An existence result of time optimal controls for such a problem is established. The rectangular type of control constraints originates from the study of time optinial control problems for ordinary differential equations. In the finite dimensional case, there is no difference between such problems with control constraints of the rectangular type and those of the ball type, from the perspective of the study on the existence of optimal controls. Interestingly, in the infinite dimensional case, the problem with control constraints of the rectangular type differs essentially from that with control constraints of the ball type. For infinite dimensional systems, the existence for time optimal controls with constraints of the ball type has already been discussed in the literature, while the study of the rectangular type has not been touched upon as far as we know. [ABSTRACT FROM AUTHOR]

The article presents a research paper on the use of averaging method to study singularly perturbed differential inclusions in evolution triple. The estimation of the upper and lower limits of the slow solution set are provided when the small parameter tends to zero and the upper or the lower limit averaged system exists. It also includes an illustrative example. It also discusses sufficient conditions of the existence of the limit of the solution set.

The object of this paper is to revisit the results of Bernhard [J. Optim. Theory Appl., 27 (1979), pp. 51-69] on two-person zero-sum linear quadratic differential games and generalize them to utility functions without positivity assumptions on the matrices acting on the state variable and to linear dynamics with bounded measurable data matrices. Our paper specializes to state feedback via Lebesgue measurable affine closed loop strategies with possible non-L2-integrable singularities. After sharpening the recent results of Delfour [SIAM J. Control Optim., 46 (2007), pp. 750-774] on the characterization of the open loop lower and upper values of the game, it first deals with L2-integrable closed loop strategies and then with the larger family of strategies that may have non-L2-integrable singularities. A new conceptually meaningful and mathematically precise definition of a closed loop saddle point is introduced to simultaneously handle state feedbacks of the L2 type and smooth locally bounded ones, except at most in the neighborhood of finitely many instants of time. A necessary and sufficient condition is that the free end problem be normalizable almost everywhere. This relaxation of the classical notion allows singularities in the feedback law at an infinite number of instants, including accumulation points that are not isolated. A complete classification of closed loop saddle points is given in terms of the convexity/concavity properties of the utility function, and connections are given with the open loop lower value, upper value, and value of the game. [ABSTRACT FROM AUTHOR]

This paper analyzes a class of singular control problems for which value functions are not necessarily smooth. Necessary and sufficient conditions for the well-known smooth fit principle, along with the regularity of the value functions, are given. Explicit solutions for the optimal policy and for the value functions are provided. In particular, when payoff functions satisfy the usual Inada conditions, the boundaries between action and continuation regions are smooth and strictly monotonic, as postulated and exploited in the existing literature (see [A. K. Dixit and R. S. Pindyck, Investment under Uncertainty, Princeton University Press, Princeton, NJ, 1994]; [M. H. A. Davis et al., Adv. in Appl. Probab., 19 (1987), pp. 156-176]; [T. Ø. Kobila, Stochastics Stochastics Rep., 43 (1993), pp. 29-63]; [A. B. Abel and J. C. Eberly, J. Econom. Dynam. Control, 21 (1997), pp. 831-852]; [A. Øksendal, Finance Stoch., 4 (2000), pp. 223-250]; [J. A. Scheinkman and T. Zariphopoulou, J. Econom. Theory, 96 (2001), pp. 180-207]; [A. Merhi and M. Zervos, SIAM J. Control Optim., 46 (2007), pp. 839-876]; and [L. H. Alvarez, A General Theory of Optimal Capacity Accumulation under Price Uncertainty and Costly Reversibility, Working Paper, Helsinki Center of Economic Research, Helsinski, Finland, 2006]). Illustrative examples for both smooth and nonsmooth cases are discussed to emphasize the pitfall of solving singular control problems with a priori smoothness assumptions. [ABSTRACT FROM AUTHOR]

This paper shows that the treatment of play or backlash as an input-output operator in mechanical networks leads to solutions which are unsatisfactory from a physical point of view. This contrasts with a simple behavioral definition of ideal play. With this definition, play cannot be treated in isolation as an input-output relation. As a result, methods of nonlinear feedback systems are not readily applicable to establish well-posedness of solutions of mechanical networks incorporating this play element. By means of simple network examples, this paper explores the issues involved in establishing well-posedness of mechanical networks incorporating springs, dampers, masses, and inerters together with the behavioral model of ideal play. Connections with the approach of Nordin, Galic, and Gutman are analyzed and a model implementation given. [ABSTRACT FROM AUTHOR]

In this paper we consider the convergence of the infinite dimensional version of the Kleinman–Newton algorithm for solving the algebraic Riccati operator equation associated with the linear quadratic regulator problem in a Hilbert space. We establish mesh independence for this algorithm and apply the result to systems governed by delay equations. Numerical examples are presented to illustrate the results. [ABSTRACT FROM AUTHOR]

In this paper, we study one kind of stochastic recursive optimal control problem with the obstacle constraint for the cost functional described by the solution of a reflected backward stochastic differential equation. We give the dynamic programming principle for this kind of optimal control problem and show that the value function is the unique viscosity solution of the obstacle problem for the corresponding Hamilton–Jacobi–Bellman equation. [ABSTRACT FROM AUTHOR]

This paper presents new graph-theoretic results appropriate for the analysis of a variety of consensus problems cast in dynamically changing environments. The concepts of rooted, strongly rooted, and neighbor-shared are defined, and conditions are derived for compositions of sequences of directed graphs to be of these types. The graph of a stochastic matrix is defined, and it is shown that under certain conditions the graph of a Sarymsakov matrix and a rooted graph are one and the same. As an illustration of the use of the concepts developed in this paper, graphtheoretic conditions are obtained which address the convergence question for the leaderless version of the widely studied Vicsek consensus problem. [ABSTRACT FROM AUTHOR]

This paper addresses the asymptotic stability of switched time delay systems with heterogeneous time invariant time delays. Piecewise Lyapunov—Razumikhin functions are introduced for the switching candidate systems to investigate the stability in the presence of an infinite number of switchings. We provide sufficient conditions in terms of the minimum dwell time to guarantee asymptotic stability under the assumptions that each switching candidate is delay-independently or delay-dependently stable. Conservatism analysis is also provided by comparing with the dwell time conditions for switched delay-free systems. Finally, a numerical example is given to validate the results. [ABSTRACT FROM AUTHOR]

In this paper the authors study a model for the optimal operation of a bank or insurance company which was recently introduced by Peura and Keppo. The model generalizes a previous one of Milne and Robertson by allowing the bank to raise capital as well as to pay out dividends. Optimal operation of the bank is determined by solving an optimal control problem. In this paper it is shown that the solution of the optimal control problem proposed by Peura and Keppo exists for all values of the parameters and is unique. [ABSTRACT FROM AUTHOR]

Relaxed controls have proved to be very useful in studying the existence of optimal controls in optimal control theory. Many positive results have been obtained in the literature. However, negative results have also made their rare appearances. The optimal control problem considered in this paper looks quite simple. Yet, by treating such a problem, we can get interesting results, substantiating our idea as to whether an optimal control exists or not. In our opinion, the method used in the paper can be applied to more generalized cases. [ABSTRACT FROM AUTHOR]

This papers analyzes a class of nonlinear additive-increase multiplicative-decrease (AIMD) protocols that are widely deployed in communication networks. It is demonstrated that the use of these protocols guarantees that the system has a unique stable outcome to which it converges geometrically under all starting points. The development is based on a contraction argument and the derivation of explicit bounds on the contraction coefficient of corresponding operators in terms of the network parameters. In particular, bounds on the corresponding rate of convergence are obtained, improving upon known bounds for standard (linear) AIMD networks. [ABSTRACT FROM AUTHOR]

In this paper, we study some optimal control problems governed by certain semilinear parabolic equations with K-approximate periodic solutions. We first prove the existence and uniqueness theorems for K-approximate periodic solutions of the equations. We then use these results to establish the qualified Pontryagin maximum principle. The existence for such optimal controls is also investigated in the paper. [ABSTRACT FROM AUTHOR]

This paper deals with optimal feedback control of measure-valued solutions of nonlinear diffusion governed by McKean-Vlasov equations. Questions of existence, uniqueness, and regularity properties of measure-valued solutions are addressed. A class of feedback controls furnished with a weak topology is introduced, and some important topological properties of the attainable set corresponding to these controls are presented. We consider several typical control problems with objective functionals which are functions of measures and prove the existence of optimal controls. [ABSTRACT FROM AUTHOR]

The paper presents a scheme to calculate approximations of reach sets and tubes for linear control systems with time-varying coefficients, bounds on the controls, and constraints on the state. The scheme provides tight external approximations by ellipsoid-valued tubes. The tubes touch the reach tubes from the outside at each point of their boundary so that the surface of the reach tube is totally covered by curves that belong to the approximating tubes. The result is an exact parametric representation of reach tubes through families of external ellipsoidal tubes. The parameters that characterize the approximating ellipsoids are solutions of ordinary differential equations with coefficients given partly in explicit analytical form and partly through the solution of a recursive optimization problem. The scheme combines the calculation of external approximations of infinite sums and intersections of ellipsoids, and suggests an approach to calculate reach sets of hybrid systems. [ABSTRACT FROM AUTHOR]

In this paper we study a discrete version of the classical team decision problem. It has been shown previously that the general discrete team decision problem is NP-hard. Here we present an efficient approximation algorithm for this problem. For the maximization version of this problem with nonnegative rewards, this algorithm computes decision rules which are guaranteed to be within a fixed bound of optimal. [ABSTRACT FROM AUTHOR]

This paper has been conceived as an overview on the controllability properties of some relevant (linear and nonlinear) parabolic systems. Specifically, we deal with the null controllability and the exact controllability to the trajectories. We try to explain the role played by the observability inequalities in this context and the need of global Carleman estimates. We also recall the main ideas used to overcome the difficulties motivated by nonlinearities. First, we considered the classical heat equation with Dirichlet conditions and distributed controls. Then we analyze recent extensions to other linear and semilinear parabolic systems and/or boundary controls. Finally, we review the controllability properties for the Stokes and Navier—Stokes equations that are known to date. In this context, we have paid special attention to obtaining the necessary Carleman estimates. Some open questions are mentioned throughout the paper. We hope that this unified presentation will be useful for those researchers interested in the field. [ABSTRACT FROM AUTHOR]

In this paper, we study an optimal singular stochastic control problem. By using a time transformation, this problem is shown to be equivalent to an auxiliary control problem defined as a combination of an optimal stopping problem and a classical control problem. For this auxiliary control problem, the controller must choose a stopping time (optimal stopping), and the new control variables belong to a compact set. This equivalence is obtained by showing that the (discontinuous) state process governed by a singular control is given by a time transformation of an auxiliary state process governed by a classical bounded control. it is proved that the value functions for these two problems are equal. For a general form of the cost, the existence of an optimal singular control is established under certain technical hypotheses. Moreover, the problem of approximating singular optimal control by absolutely continuous controls is discussed in the same class of admissible controls. [ABSTRACT FROM AUTHOR]

We study second order sufficient optimality conditions (SSC) for optimal control problems with control appearing linearly. Specifically, time-optimal bang-bang controls will be investigated. In [N. P. Osmolovskii, Sov. Phys. Dokl., 33 (1988), pp. 883-885; Theory of HigherOrder Conditions in Optimal Control, Doctor of Sci. thesis, Moscow, 1988 (in Russian); Russian J. Math. Phys., 2 (1995), pp. 487-516; Russian J. Math. Phys., 5 (1997), pp. 373-388; Proceedings of the Conference "Calculus of Variations and Optimal Control," Chapman & Hall/CRC, Boca Raton, FL, 2000, pp. 198-216; A. A. Milyutin and N. P. Osmolovskii, Calculus of Variations and Optimal Control, Transl. Math. Monogr. 180, AMS, Providence, RI, 1998], SSC have been developed in terms of the positive definiteness of a quadratic form on a critical cone or subspace. No systematical numerical methods for verifying SSC are to be found in these papers. In the present paper, we study explicit representations of the critical subspace. This leads to an easily implementable test for SSC in the case of a bang-bang control with one or two switching points. In general, we show that the quadratic form can be simplified by a transformation that uses a solution to a linear matrix differential equation. Particular conditions even allow us to convert the quadratic form to perfect squares. Three numerical examples demonstrate the numerical viability of the proposed tests for SSC. [ABSTRACT FROM AUTHOR]

This paper studies first order conditions (Karush-Kuhn-Tucker conditions) for discretized optimal control problems with non smooth constraints. We present a simple condition which can be used to verify that a local optimal point satisfies the first order conditions and that a point satisfying the first order conditions is a global or local optimal solution of the optimal control problem. [ABSTRACT FROM AUTHOR]

This paper presents the mathematical conditions and the associated design methodology of an active fault diagnosis technique for continuous-time linear systems. Given a set of faults known a priori, the system is modeled by a finite family of linear time-invariant systems, accounting for one healthy and several faulty configurations. By assuming bounded disturbances and using a residual generator, an invariant set and its projection in the residual space (i.e., its limit set) are computed for each system configuration. Each limit set, related to a single system configuration, is parameterized with respect to the system input. Thanks to this design, active fault isolation can be guaranteed by the computation of a test input, either constant or periodic, such that the limit sets associated with different system configurations are separated, and the residual converges toward one limit set only. In order to alleviate the complexity of the explicit computation of the limit set, an implicit dual representation is adopted, leading to efficient procedures, based on quadratic programming, for computing the test input. The developed methodology offers a competent continuous-time solution to the optimization-based computation of the test input via Hahn-Banach duality. Simulation examples illustrate the application of the proposed active fault diagnosis methods and its efficiency in providing a solution, even in relatively large state-dimensional problems. [ABSTRACT FROM AUTHOR]

This paper investigates the asymptotic behavior of some common opinion dynamic models in a continuum of agents. We show that as long as the interactions among the agents are symmetric, the distribution of the agents' opinions converges. We also investigate whether convergence occurs in a stronger sense than merely in distribution, namely, whether the opinion of almost every agent converges. We show that while this is not the case in general, it becomes true under plausible assumptions on interagent interactions, namely that agents with similar opinions exert a nonnegligible pull on each other, or that the interactions are entirely determined by their opinions via a smooth function. [ABSTRACT FROM AUTHOR]

In this paper, the robust controllability for linear systems with constrained controls x = Ax+Bu, u ∊ Ω is studied under the assumption that Ω is an arbitrary subset satisfying the only condition 0 ∊ clcoΩ and the system matrices are subjected to structured perturbations. The notion of the structured local and global controllability radii are defined. Based on properties of convex processes, some general formulas for the complex and the real controllability radii, for both local and global controllability concepts, are established with respect to structured affine perturbations and multiperturbations of matrices A,B. As particular cases, the general results are applied to linear systems with bounded controls and single-input linear systems, yielding some explicit and computable formulas of controllability radii. Examples are given to illustrate the obtained results. [ABSTRACT FROM AUTHOR]

A common theme in mathematics is to define generalized solutions to deal with problems that potentially do not have solutions. A classical example is the introduction of least squares solutions via the normal equations associated with a possibly infeasible system of linear equations. In this paper, we introduce a "normal problem" associated with finding a zero of the sum of two maximally monotone operators. If the original problem admits solutions, then the normal problem returns this same set of solutions. The normal problem may yield solutions when the original problem does not admit any; furthermore, it has attractive variational and duality properties. Several examples illustrate our theory. [ABSTRACT FROM AUTHOR]

This paper deals with first- and second-order necessary optimality conditions for a class of optimal control problems governed by semilinear elliptic partial differential equations with mixed pointwise state-control constraints. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to examine whether the presence of singular configurations poses an obstruction to the small-time local controllability (STLC) and stabilizability of the attitude dynamics of a spacecraft actuated by single-gimbal control moment gyroscopes (CMGs). We identify a class of singular CMG configurations called critically singular configurations, at which the linearized dynamics fail to be controllable. Linear controllability, and hence STLC and stabilizability, hold at equilibria in which the CMG array is in a nonsingular or singular, but not critically singular, configuration. We give sufficient conditions and necessary conditions on critically singular configurations for STLC to hold. In particular, we show that STLC and stabilizability fail to hold at an equilibrium if the magnitude of the total spin angular momentum of the CMG array has a local maximum at the equilibrium. [ABSTRACT FROM AUTHOR]

In this paper, we extend the notion of person-by-person (pbp) optimization to binary decision spaces. The novelty of our approach is the adaptation to a dynamic team context of notions borrowed from the pseudo-boolean optimization field as completely local-global or unimodal functions and submodularity. We also generalize the concept of pbp optimization to the case where groups of m decisions makers make joint decisions sequentially, which we refer to as mbm optimization. The main contribution is a description of sufficient conditions, verifiable in polynomial time, under which a pbp or an mbm optimization algorithm converges to the team-optimum. As a second contribution, we present a local and greedy algorithm characterized by approximate decision strategies (i.e., strategies based on a local state vector) that return the same decisions as in the complete information framework (where strategies are based on full state vector). As a last contribution, we also show that there exists a subclass of submodular team problems, recognizable in polynomial time, for which the pbp optimization converges for at least an opportune initialization of the algorithm. [ABSTRACT FROM AUTHOR]

In this paper we study a Dirichlet optimal control problem for a nonlinear monotone equation with degenerate weight function and with the coefficients which we adopt as controls in L∞(Ω). Since these types of equations can exhibit the Lavrentieff phenomenon, we consider the optimal control problem in coefficients in the so-called class of H-admissible solutions. Using the direct method of calculus of variations we discuss the solvability of the above optimal control problem, and prove the attainability of H-optimal pairs via optimal solutions of some nondegenerate perturbed optimal control problems. We also introduce the concept of the Mosco-stability for the above optimal control problem and study the variational properties of Mosco-stable problems with respect to the special type of domain perturbations. [ABSTRACT FROM AUTHOR]

For Boolean functions that are ϵ-far from the set of linear functions, we study the lower bound on the rejection probability (denoted by rej(ϵ)) of the linearity test suggested by Blum, Luby, and Rubinfeld [J. Comput. System Sci., 47 (1993), pp. 549-595]. This problem is arguably the most fundamental and extensively studied problem in property testing of Boolean functions. The previously best bounds for rej(ϵ) were obtained by Bellare et al. [IEEE Trans. Inform. Theory, 42 (1996), pp. 1781-1795]. They used Fourier analysis to show that rej(ϵ) ≤ ϵ for every 0 ≤ ϵ ≤1/2. They also conjectured that this bound might not be tight for ϵ's which are close to 1/2. In this paper we show that this indeed is the case. Specifically, we improve the lower bound of rej(ϵ) ≤ ϵ by an additive constant that depends only on ϵ: rej(ϵ) ≤ +min{1376ϵ³(1-2ϵ)12, ¼ϵ(1-2ϵ)4}, for every 0 ≤ ϵ ≤ 1/2. Our analysis is based on a relationship between rej(ϵ) and the weight distribution of a coset code of the Hadamard code. We use both Fourier analysis and coding theory tools to estimate this weight distribution. [ABSTRACT FROM AUTHOR]

For Boolean functions that are ϵ-far from the set of linear functions, we study the lower bound on the rejection probability (denoted by rej(ϵ)) of the linearity test suggested by Blum, Luby, and Rubinfeld [J. Comput. System Sci., 47 (1993), pp. 549-595]. This problem is arguably the most fundamental and extensively studied problem in property testing of Boolean functions. The previously best bounds for rej(ϵ) were obtained by Bellare et al. [IEEE Trans. Inform. Theory, 42 (1996), pp. 1781-1795]. They used Fourier analysis to show that rej(ϵ) ⩾ ϵ for every 0 ⩽ ϵ ⩽ 1/2. They also conjectured that this bound might not be tight for ϵ's which are close to 1/2. In this paper we show that this indeed is the case. Specifically, we improve the lower bound of rej(ϵ) ⩾ ϵ by an additive constant that depends only on ϵ: rej(ϵ) ⩾ ϵ+min{1376ϵ3(1-2ϵ)12, ¼ϵ(1-2ϵ)4}, for every 0 ⩽ ϵ ⩽ 1/2. Our analysis is based on a relationship between rej(ϵ) and the weight distribution of a coset code of the Hadamard code. We use both Fourier analysis and coding theory tools to estimate this weight distribution. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of testing whether a Boolean-valued function f is a halfspace, i.e., a function of the form f(x) = sgn(w · x - θ?). We consider halfspaces over the continuous domain Rn (endowed with the standard multivariate Gaussian distribution) as well as halfspaces over the Boolean cube {-1, 1}n (endowed with the uniform distribution). In both cases we give an algorithm that distinguishes halfspaces from functions that are ϵ-far from any halfspace using only poly( 1/ϵ ) queries, independent of the dimension n. Two simple structural results about halfspaces are at the heart of our approach for the Gaussian distribution: The first gives an exact relationship between the expected value of a halfspace f and the sum of the squares of f's degree- 1 Hermite coefficients, and the second shows that any function that approximately satisfies this relationship is close to a halfspace. We prove analogous results for the Boolean cube {-1, 1}n (with Fourier coefficients in place of Hermite coefficients) for balanced halfspaces in which all degree- 1 Fourier coefficients are small. Dealing with general halfspaces over {-1, 1}n poses significant additional complications and requires other ingredients. These include "cross-consistency" versions of the results mentioned above for pairs of halfspaces with the same weights but different thresholds; new structural results relating the largest degree-1 Fourier coefficient and the largest weight in unbalanced halfspaces; and algorithmic techniques from recent work on testing juntas [E. Fischer, G. Kindler, D. Ron, S. Safra, and A. Samorodnitsky, Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science, 2002, pp. 103-112]. [ABSTRACT FROM AUTHOR]

We show that Edge Dominating Set, Hamiltonian Cycle, and Graph Coloring are W[1]-hard parameterized by clique-width. It was an open problem, explicitly mentioned in several papers, whether any of these problems is fixed parameter tractable when parameterized by the clique-width, that is, solvable in time g(k) · nO(1) on η-vertex graphs of clique-width k, where g is some function of k only. Our results imply that the running time O(nf(k)) of many clique-widthbased algorithms is essentially the best we can hope for (up to a widely believed assumption from parameterized complexity, namely FPT ≠ W[1]). [ABSTRACT FROM AUTHOR]

This paper shows how to compute O(√log n)-approximations to the Sparsest Cut and Balanced Separator problems in Õ(n²) time, thus improving upon the recent algorithm of Arora, Rao, and Vazirani [Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004, pp. 222-231]. Their algorithm uses semidefinite programming and requires Õ (n9.5) time. Our algorithm relies on efficiently finding expander flows in the graph and does not solve semidefinite programs. The existence of expander flows was also established by Arora, Rao, and Vazirani. [ABSTRACT FROM AUTHOR]