Search

We consider a stochastic variational inequality (SVI) problem with a continuous and monotone mapping over a closed and convex set. In strongly monotone regimes, we present a variable sample-size averaging scheme (VS-Ave) that achieves a linear rate with an optimal oracle complexity. In addition, the iteration complexity is shown to display a muted dependence on the condition number compared with standard variance-reduced projection schemes. To contend with merely monotone maps, we develop amongst the first proximal-point algorithms with variable sample-sizes (PPAWSS), where increasingly accurate solutions of strongly monotone SVIs are obtained via (VS-Ave) at every step. This allows for achieving a sublinear convergence rate that matches that obtained for deterministic monotone VIs. Preliminary numerical evidence suggests that the schemes compares well with competing schemes.

In this paper, distributed algorithms are proposed to find a Nash equilibrium for a generalized convex game with shared inequality and equality constraints and private inequality constraints that depend on the player itself. Both the objective functions and constraints could be nonsmooth and locally Lipschitz. Suppose that the players can communicate with their neighboring players and the communication graph can be represented by a connected undirected graph. By using the 1 penalty function, which is nondifferentiable, the constrained game is converted into an unconstrained game. The proposed differential inclusion exponentially converges to an Nash equilibrium of a strongly monotone game for centralized implementation, and exponentially converges to a η-neighborhood of an Nash equilibrium of a strongly monotone game for distributed implementation, with η being a positive constant that could be arbitrarily small. The distributed algorithm is based on a leader-following consensus scheme and the stability analysis of the algorithms uses nonsmooth analysis and singular perturbation for differential inclusion. A numerical example is given to show the effectiveness of the proposed algorithms.

In this paper, the distributed Nash equilibrium seeking problem for the games with convex compact set constraint is studied. A distributed estimator based on the leader-follower consensus law is presented to estimate the states of the players. Each player communicates its estimations to its neighbors. The projections of the estimations for the states of the players onto the constraint sets are used in the Nash equilibrium seeking strategy. By synthesizing the projection term of the player's state and the estimator-projection-based gradient play term, the Nash equilibrium seeking algorithm is proposed. The pseudo-gradient of the cost function is only assumed to be strongly monotone in the compact constraint region not required to be globally strongly monotone. Also, the proposed Nash equilibrium seeking algorithm for the constrained games is feasible under any initial states of the players if the given conditions are satisfied. The convergence of the seeking algorithm is proved. Numerical simulations are provided to validate the effectiveness of the proposed seeking algorithm.

In this paper, we propose distributed algorithms to seek generalized Nash equilibrium (GNE) of monotone games with affine coupling constraints. Each player can only utilize its local objective function, local feasible set and a local block of the coupling constraint, and can only communicate with its neighbours. The games are assumed to have monotone pseudo-subdifferential without Lipschitz continuity restrictions. Center-free distributed GNE seeking algorithms are proposed for equality and inequality coupling constraints, respectively. In both algorithms, the complicated GNE seeking task is decomposed into a sequential NE computation of regularized subgames and a distributed update of multipliers and auxiliary variables, based on local data and local communication. Our double-layer GNE seeking algorithms only require that the strongly monotone subgames are inexactly solved using any of the available distributed NE seeking algorithms. We relate both GNE seeking algorithms to preconditioned proximal algorithms (PPA) for finding zeros of monotone operators. Applications and numerical simulations are given for illustration.

Let (X, A) be a fixed measurable space and two monotone measures μ 1 and μ2 two monotone measures defined on A, we consider the pseudo-addition μ1 ⊕ μ2 of these two monotone measures. It is a new monotone measure λ. Such a monotone measure is absolutely continuous with respect to μ1 and μ2. Not only that, the new monotone measure preserves most of desirable structural characteristics of the monotone measures μ1 and μ2, such as subadditivity, null-additivity, etc. We shall present the generalized versions of convergence theorems for sequence of measurable functions, such as the Egoroff theorem and the Lusin theorem. These theorems are associated with two monotone measures on the measurable space. The previous results are covered by the results presented here. We shall show that each of usual nonlinear intrgrals, the Sugeno integral, the Choquet integral, and the Shilkret integral with respect to μ1 ⊕ μ2, is equal to the ⊕-sum of two same kinds of integrals with respect to μ1 and μ2, respectively.

Maximal monotone operators are set-valued mappings which extend (but are not limited to) the notion of subdifferential of a convex function. The proximal point algorithm is a method for finding a zero of a maximal monotone operator. The algorithm consists in fixed point iterations of a mapping called the resolvent which depends on the maximal monotone operator of interest. The paper investigates a stochastic version of the algorithm where the resolvent used at iteration k is associated to one realization of a random maximal monotone operator. We establish the almost sure ergodic convergence of the iterates to a zero of the expectation (in the Aumann sense) of the latter random operator. Application to constrained stochastic optimization is considered.

The pseudo-integral is based on a class of set functions which are a generalization of the classical measure. In this paper we have observed how to transform a pseudo-integral into another pseudo-integral that enables us to give the relationship between the pseudo-integral and other integrals based on monotone set functions such as the universal, Sugeno and Shilkret integrals. Also, using the transformed pseudo-integral we have obtained a monotone convergence theorem for the pseudo-integral. As a consequence of the monotone convergence theorem we get the Fatou's lemma for the pseudo-integral.

We give an example of a non-commutative monotone polynomial f which can be computed by a polynomial-size non-commutative formula, but every monotone non-commutative circuit computing f must have an exponential size. In the non-commutative setting this gives, a fortiori, an exponential separation between monotone and general formulas, monotone and general branching programs, and monotone and general circuits. This answers some questions raised by Nisan.

Traditionally, the field of deterministic optimization has been devoted to minimization of functions f(x; θ*) whose parameters, denoted by θ*, are known with certainty. Supervised learning theory on the other hand considers the question of employing training data to seek a function from a set of possible functions. Instances of learning algorithms include regression schemes and support vector machines, amongst others. We consider a hybrid problem of computation and learning that arises in online settings, where one may be interested in optimizing f(x; θ*) while learning θ* through a set of observations. More generally, we consider the solution of parameterized monotone variational inequality problems, which can capture a range of convex optimization problems and convex Nash games. The unknown parameter θ* is learned through the noisy observations of a linear function of θ*, denoted by l(x; θ*). This paper provides convergence statements for joint schemes when observations are corrupted by noise in regimes where the associated variational inequality problem may be either strongly monotone or merely monotone. The proposed schemes are shown to produce iterates that converge in mean to their true counterparts. Numerical results derived from the application of these techniques to convex optimization problems and nonlinear Nash-Cournot games is shown to be promising.

In the stability analysis of large-scale interconnected systems it is frequently desirable to be able to determine a decay point of the gain operator, i.e., a point whose image under the monotone operator is strictly smaller than the point itself. The set of such decay points plays a crucial role in checking, in a semi-global fashion, the local input-to-state stability of an interconnected system and in the numerical construction of a LISS Lyapunov function. We provide a homotopy algorithm that computes a decay point of a monotone op- erator. For this purpose we use a fixed point algorithm and provide a function whose fixed points correspond to decay points of the monotone operator. The advantage to an earlier algorithm is demonstrated. Furthermore an example is given which shows how to analyze a given perturbed interconnected system., 30 pages, 7 figures, 4 tables

In the face of increasing demand for wireless services, the design of spectrum assignment policies has gained enormous relevance. We consider one such instance in cognitive radio systems where recent efforts have focused on the application of game-theoretic approaches. Much of this work has been restricted to deterministic regimes and this paper considers a stochastic generalizations. The corresponding problems are seen to be stochastic Nash games over continuous strategy sets. Notably, the gradient map of player utilities is seen to be a monotone mapping over the cartesian product of strategy sets, leading to a monotone stochastic variational inequality. We consider the application of projection-based stochastic approximation schemes. However, such techniques are characterized by a key shortcoming in that the mappings were required to be be strongly monotone. Standard extensions of stochastic approximation schemes for merely monotone mappings rely on obtaining a sequence of increasingly exact solutions, a natively two-timescale scheme. However, obtaining solutions with increasing accuracy remains a challenging task in a simulation-based setting. Accordingly, we consider the development of single timescale techniques for computing equilibria when the associated gradient map does not admit strong monotonicity. We develop convergence theory for distributed single-timescale stochastic approximation schemes, namely stochastic iterative proximal point method which requires exactly one projection step at every step. Finally we apply this framework to the design of cognitive radio systems in uncertain regimes under temperature-interference constraints.

In this paper, we consider the distributed computation of equilibria arising in monotone stochastic Nash games over continuous strategy sets. Such games arise in settings when the gradient map of the player objectives is a monotone mapping over the cartesian product of strategy sets, leading to a monotone stochastic variational inequality. We consider the application of projection-based stochastic approximation (SA) schemes. However, such techniques are characterized by a key shortcoming: in their traditional form, they can only accommodate strongly monotone mappings. In fact, standard extensions of SA schemes for merely monotone mappings require the solution of a sequence of related strongly monotone problems, a natively two-timescale scheme. Accordingly, we consider the development of single timescale techniques for computing equilibria when the associated gradient map does not admit strong monotonicity. We first show that, under suitable assumptions, standard projection schemes can indeed be extended to allow for strict, rather than strong monotonicity. Furthermore, we introduce a class of regularized SA schemes, in which the regularization parameter is updated at every step, leading to a single timescale method. The scheme is a stochastic extension of an iterative Tikhonov regularization method and its global convergence is established. To aid in networked implementations, we consider an extension to this result where players are allowed to choose their steplengths independently and show the convergence of the scheme if the deviation across their choices is suitably constrained.

This paper discusses the nonlinear boundary value problem with a monotone potential operator.We obtain an existence and uniqueness theorem of weak solutions by using the monotone potential operator theories and Browder-Minty theorem.

The paper considers a class of delayed standard (S) cellular neural networks (CNNs) with non-negative interconnections between distinct neurons and a typical three-segment pwl neuron activation. It is also assumed that such cooperative SCNNs satisfy an irreducibility condition on the interconnection and delayed interconnection matrix. By means of a counterexample it is shown that the solution semiflow associated to such SCNNs in the general case does not satisfy the fundamental property of the omega-limit set dichotomy and is not eventually strongly monotone. The consequences of this result are discussed in the context of the existing methods for addressing convergence of monotone semiflows defined by delayed cooperative dynamical systems.

The abstract monotone iterative technique is well know and very important for applications to a variety of situations. With partial order defined in metric space, the purpose of this paper is to discuss the existence of coupled fixed point for mixed monotone mapping pairs. The results are quite different from the results in recent references. The paper also gives two examples to illustrate the theorems which indicate that the coupled fixed point may not be unique.

We first introduce an iterative algorithm for finding solutions of variational inequalities for Lipschitzian and monotone mappings in Hilbert spaces, and then prove a strong convergence theorem by using the modified algorithm. As its application, we deduce a strong convergence theorem for Lipschitzian and pseudo-contractions in Hilbert spaces. The results presented in this paper extend several known results.

In this paper, we establish a global absolute error bound for the generalized complementarity problem over a Polyhedral Cone (GCP) with the underlying mapping being r –strongly monotone and Holder-continuous, based on which the famous Levenberg-Marquardt (L-M) algorithm is employed for obtaining its solution, and we show that L-M algorithm is quadratically convergent without nondegenerate solution.

Nonexpansive mappings and inverse-strongly monotone mappings are two kinds of nonlinear operators, nonlinear functional analysis Operator theory is a very important theory, which has some valuable applications to operations research and economics. It has recently been applied to Engineering, particularly in the application of automatic control. In this paper, we introduce an iterative method for finding a common element of the set of fixed points of a nonexpansive mapping and the set of solutions of the variational inequality problem for an alpha inverse-strongly monotone mapping in Hilbert space. We obtain a strong convergence theorem for a sequence generated by this progress.

This paper proposes a new prediction-correction and relaxed hybrid steepest-descent method for a class of the variational inequality problem with a Lipschitzi and strongly monotone operator on a nonempty closed convex subset in real Hilbert space. In order to improve the computational efficiency, the proposed method integrates the Gauss-Seidel method into the prediction-correction method while taking advantage of some fundamental properties of the real Hilbert space. Finally, strong convergence of this method is proved under suitable assumptions.

We show that strongly monotone systems of ordinary differential equations which have a certain translation-invariance property are so that all solutions converge to a unique equilibrium. The result may be seen as a dual of a well-known theorem of Mierczynski for systems that satisfy a conservation law. An application to a reaction of interest in biochemistry is provided as an illustration.

We announce a new global small-gain theorem for feedback interconnections of monotone input-output systems with multi-valued input-state characteristics. This extends a small-gain theorem of Angeli and Sontag for monotone systems with singleton-valued characteristics. The proof of our theorem is based on Thieme’s convergence theory for asymptotically autonomous systems. We also provide an illustrative example.

Finding zero points for maximal monotone operator is a very active topic in different branches of mathematical and engineering sciences since many physically significant problems can be ultimately converted to it. Considerable research efforts have been devoted to the study of iterative algorithms of zero points for maximal monotone operators in recent years. By now, there already exist some algorithms, but they are not quite enough to deal with problems defined in a more general space. In this paper, a new hybrid approximate proximal-type algorithm is introduced which is proved to be strongly convergent to zero point of maximal monotone operator in Banach space by using some techniques of Lyapunov functional and generalized projection operator, etc. Moreover, the application of the new algorithm is demonstrated.

This paper extends to singular perturbations of strongly monotone systems a result of Hirsch's on generic convergence to equilibria.

Oscillators and switches are ubiquitous in gene regulatory networks. Understanding the dynamical properties of these systems is a necessity not only to reverse engineer their structure, but also to forward engineer novel structures in the context of the nascent field of "synthetic biology". In this work, we analyze two classes of cyclic gene networks. The first class corresponds to the "repressilator", which is to polemically equivalent to a class of negative gain networks. The second class corresponds to the "promotilator" which is topologically equivalent to a class of positive gain networks. We demonstrate that the repressilator can exhibit oscillatory behavior under conditions that we derive. We also demonstrate that the promotilator and its equivalent circuits belong to the class of strongly monotone systems, and as such, the behavior they can exhibit is convergence to stable equilibria.

A recent paper by Angeli and Sontag presented a stability criterium for feedback loops involving single input, single output models which admit a well-defined I/O characteristic and satisfy a monotonicity condition. This paper generalizes the argument to arbitrary strongly monotone systems. The main idea is to study the asymptotic behavior of a strongly monotone system by relating it to a graph on the plane which contains information about the equilibria of the system and their stability properties.

Exact and approximate versions of a nonlinear proximal point algorithm (NPA) are presented. Both are globally weakly convergent to a zero of T, a maximal monotone map on a real Hilbert space. Conditions implying sublinear, linear, superlinear, and finite convergence to the zero set of T are given. An implementation of the approximate version for T strongly monotone is stated. When applied to a convex (resp. saddle) function, the speed of approach to the minimum (resp. saddle) value is estimated.