Search

We consider a second order dynamical system for solving variational inequalities in Hilbert spaces. Under standard conditions, we prove the existence and uniqueness of strong global solution of the proposed dynamical system. The exponential convergence of trajectories is established under strong pseudo-monotonicity and Lipschitz continuity assumptions. A discrete version of the proposed dynamical system leads to a relaxed inertial projection algorithm whose linear convergence is proved under suitable conditions on parameters. We discuss the possibility of extension to general monotone inclusion problems. Finally some numerical experiments are reported demonstrating the theoretical results.

This paper studies the graph-theoretic conditions for stability of positive monotone systems. Using concepts from input-to-state stability and network small-gain theory, we first establish necessary and sufficient conditions for the stability of linear positive systems described by Metzler matrices. Specifically, we derive two sets of stability conditions based on two forms of input-to-state stability gains for Metzler systems, namely max-interconnection gains and sum-interconnection gains. Based on the max-interconnection gains, we show that the cyclic small-gain theorem becomes necessary and sufficient for the stability of Metzler systems; based on the sum-interconnection gains, we obtain novel graph-theoretic conditions for the stability of Metzler systems. All these conditions highlight the role of cycles in the interconnection graph and unveil how the structural properties of the graph affect stability. Finally, we extend our results to the nonlinear monotone system and obtain similar sufficient conditions for global asymptotic stability.

This paper addresses a control system governed by two ODEs with a hysteresis nonlinearity of generalized play type. The characteristic curves describing the hysteresis region are allowed to be unbounded and are not necessarily monotone. The existence of solutions and some of their properties are established for our control system.

We study a Dirichlet optimal control problem for a quasi-linear monotone elliptic equation, the so-called weighted p-Laplace problem. The coefficient of the p-Laplacian, the weight u, we take as a control in BV (Ω) ∩ L∞(Ω). In this article, we use box-type constraints for the control such that there is a strictly positive lower and some upper bound. In order to handle the inherent degeneracy of the p-Laplacian, we use a regularization, sometimes referred to as the ε-p-Laplacian. We derive existence and uniqueness of solutions to the underlying boundary value problem and the optimal control problem. In fact, we introduce a two-parameter model for the weighted ε-p- Laplacian, where we approximate the nonlinearity by a bounded monotone function, parametrized by k. Further, we discuss the asymptotic behavior of the solutions to the regularized problem on each (ε, k)-level as the parameters tend to zero and infinity, respectively. This author’s research was supported by the DFG-EC315 “Engineering of Advanced Materials” and by the Spanish Ministerio de Economía y Competitividad under projects MTM2011-22711 and MTM2014-57531-P.

We begin by considering second order dynamical systems of the from $\ddot x(t) + \gamma(t)\dot x(t) + \lambda(t)B(x(t))=0$, where $B: {\cal H}\rightarrow{\cal H}$ is a cocoercive operator defined on a real Hilbert space ${\cal H}$, $\lambda:[0,+\infty)\rightarrow [0,+\infty)$ is a relaxation function and $\gamma:[0,+\infty)\rightarrow [0,+\infty)$ a damping function, both depending on time. For the generated trajectories, we show existence and uniqueness of the generated trajectories as well as their weak asymptotic convergence to a zero of the operator $B$. The framework allows to address from similar perspectives second order dynamical systems associated with the problem of finding zeros of the sum of a maximally monotone operator and a cocoercive one. This captures as particular case the minimization of the sum of a nonsmooth convex function with a smooth convex one. Furthermore, we prove that when $B$ is the gradient of a smooth convex function the value of the latter converges along the ergodic trajectory to its minimal value with a rate of ${\cal O}(1/t)$.

A classical problem in ergodic control consists of studying the limit behavior of the optimal value $V_\lambda$ of a discounted cost functional with infinite horizon as the discount factor $\lambda$ tends to zero. In the literature, this problem has been addressed under various conditions ensuring that the rescaled value function $\lambda V_\lambda$ converges uniformly to a constant limit. The main goal of this paper is to study this problem without such conditions, so that the aforementioned limit need not be constant. So, under a nonexpansivity assumption, we derive Lipschitz bounds which yield compactness of $\{\lambda V_\lambda\}$ for both control systems and differential games. Then, we study the convergence of solutions to Hamilton--Jacobi equations under the hypothesis that the Hamiltonian is radially nondecreasing, hence allowing for the existence noncoercivity directions. Using PDE methods, we show that the convergence is monotone and we characterize the limit as the maximal subsolution of a cert...

$L^p$ optimal control with $p\in [0,1)$ is investigated. The difficulty of natural lack of convexity and thus of weak lower semicontinuity is addressed by introducing appropriately chosen regularization terms. Existence results and necessary optimality conditions are obtained, and convergence of a monotone scheme is proved. Special attention is given to the particular case of optimal control problems with quadratic tracking and regularized $L^0$ control costs are given. A maximum principle is derived and existence of controls, in some cases relaxed controls, is proved, and an estimate on the consequences of relaxation are estimated.

We restate observability in a set-valued setting which generalizes the standard output equation, then a close connection to viability kernels is established. Both global and local cases are studied by means of a set of single-valuedness results. Among these, we highlight the results which are derived by monotone set-valued mappings theory and the ones using contingent and paratingent derivatives. Moreover, this new setting gives rise to the notions of maximal observability domains and minimal unobservability domains, which we characterize in the framework of antitone mappings and their fixed points.

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^\infty(\Omega)$. 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.

We prove that the sequences generated by the Douglas-Rachford method converge weakly to zero of the sum of two maximal monotone operators using new tools introduced in recent works of Eckstein and the author. The assumption of maximal monotonicity of the sum is also removed, using a recent result of Bauschke.

We describe a general projective framework for finding a zero of the sum of $n$ maximal monotone operators over a real Hilbert space. Unlike prior methods for this problem, we neither assume $n=2$ nor first reduce the problem to the case $n=2$. Our analysis defines a closed convex extended solution set for which we can construct a separating hyperplane by individually evaluating the resolvent of each operator. At the cost of a single, computationally simple projection step, this framework gives rise to a family of splitting methods of unprecedented flexibility: numerous parameters, including the proximal stepsize, may vary by iteration and by operator. The order of operator evaluation may vary by iteration and may be either serial or parallel. The analysis essentially generalizes our prior results for the case $n=2$. We also include a relative error criterion for approximately evaluating resolvents, which was not present in our earlier work.

It is shown that stability of the celebrated MaxWeight or back pressure policies is a consequence of the following interpretation: either policy is myopic with respect to a surrogate value function of a very special form, in which the “marginal disutility” at a buffer vanishes for a vanishingly small buffer population. This observation motivates the $h$-MaxWeight policy, defined for a wide class of functions $h$. These policies share many of the attractive properties of the MaxWeight policy as follows: (i) Arrival rate data is not required in the policy. (ii) Under a variety of general conditions, the policy is stabilizing when $h$ is a perturbation of a monotone linear function, a monotone quadratic, or a monotone Lyapunov function for the fluid model. (iii) A perturbation of the relative value function for a workload relaxation gives rise to a myopic policy that is approximately average-cost optimal in heavy traffic, with logarithmic regret. The first results are obtained for a general Markovian network model. Asymptotic optimality is established for a general Markovian scheduling model with a single bottleneck, and with homogeneous servers.

We consider a class of Hamilton-Jacobi equations $H(x,Du(x))=0$ with no $u$-dependence and with continuity properties consistent with recent applications in queueing theory. Continuous viscosity solutions are considered in a compact polyhedral domain, with oblique derivative (Neumann-type) boundary conditions. Comparison and uniqueness results are presented, which use monotonicity of $H(x,p)$ in the $p$ variable for values of $p$ in the appropriate sub- and superdifferential sets of the solution $u(x)$. Several examples illustrate the results.

In this paper we study the convergence of an iterative algorithm for finding zeros with constraints for not necessarily monotone set-valued operators in a reflexive Banach space. This algorithm, which we call the proximal-projection method is, essentially, a fixed point procedure and our convergence results are based on new generalizations of Lemma Opial. We show how the proximal-projection method can be applied for solving ill-posed variational inequalities and convex optimization problems with data given or computable by approximations only. The convergence properties of the proximal-projection method we establish also allow us to prove that the proximal point method (with Bregman distances), whose convergence was known to happen for maximal monotone operators, still converges when the operator involved in it is monotone with sequentially weakly closed graph., 38 pages

This paper deals with an iterative method, in a real Hilbert space, for approximating a common element of the set of fixed points of a demicontractive operator (possibly quasi-nonexpansive or strictly pseudocontractive) and the set of solutions of a variational inequality problem for a monotone, Lipschitz continuous mapping. The considered algorithm can be regarded as a combination of a variation of the hybrid steepest descent method and the so-called extragradient method. Under classical conditions, we prove the strong convergence of the sequences of iterates given by the considered scheme.

A fundamental result due to Rockafellar states that every cyclically monotone operator $A$ admits an antiderivative $f$ in the sense that the graph of $A$ is contained in the graph of the subdifferential operator $\partial f$. Given a method $\mathfrak{m}$ that assigns every finite cyclically monotone operator $A$ some antiderivative $\mathfrak{m}_A$, we say that the method is primal-dual symmetric if $\mathfrak{m}$ applied to the inverse of $A$ produces the Fenchel conjugate of $\mathfrak{m}_A$. Rockafellar's antiderivatives do not possess this property. Utilizing Fitzpatrick functions and the proximal average, we present novel primal-dual symmetric intrinsic methods. The antiderivatives produced by these methods provide a solution to a problem posed by Rockafellar in 2005. The results leading to this solution are illustrated by various examples.

Well-posedness of abstract quantum mechanical systems is considered and the existence of optimal control of such systems is proved. First order optimality systems are derived. Convergence of the monotone scheme for the solution of the optimality system is proved.

We present a new approach to solve optimal control problems of the monotone follower type. The key feature of our approach is that it allows us to include an arbitrary dynamic fuel constraint. Instead of dynamic programming, we use the convexity of our cost functional to derive a first order characterization of optimal policies based on the Snell envelope of the objective functional's gradient at the optimum. The optimal control policy is constructed explicitly in terms of the solution to a representation theorem for stochastic processes obtained in Bank and El Karoui (2004), {Ann. Probab.}, 32, pp. 1030--1067. As an illustration, we show how our methodology allows us to extend the scope of the explicit solutions obtained for the classical monotone follower problem and for an irreversible investment problem arising in economics.

A broad class of optimization algorithms based on Bregman distances in Banach spaces is unified around the notion of Bregman monotonicity. A systematic investigation of this notion leads to a simplified analysis of numerous algorithms and to the development of a new class of parallel block-iterative surrogate Bregman projection schemes. Another key contribution is the introduction of a class of operators that is shown to be intrinsically tied to the notion of Bregman monotonicity and to include the operators commonly found in Bregman optimization methods. Special emphasis is placed on the viability of the algorithms and the importance of Legendre functions in this regard. Various applications are discussed.

A general approach to analyze convergence of the proximal-like methods for variational inequalities with set-valued maximal monotone operators is developed. It is oriented to methods coupling successive approximation of the variational inequality with the proximal point algorithm as well as to related methods using regularization on a subspace and weak regularization. This approach also covers so-called multistep regularization methods, in which the number of proximal iterations in the approximated problems is controlled by a criterion characterizing these iterations as to be effective. The conditions on convergence require control of the exactness of the approximation only in a certain region of the original space. Conditions ensuring linear convergence of the methods are established.

We consider the forward-backward splitting method for finding a zero of the sum of two maximal monotone mappings. This method is known to converge when the inverse of the forward mapping is strongly monotone. We propose a modification to this method, in the spirit of the extragradient method for monotone variational inequalities, under which the method converges assuming only the forward mapping is (Lipschitz) continuous on some closed convex subset of its domain. The modification entails an additional forward step and a projection step at each iteration. Applications of the modified method to decomposition in convex programming and monotone variational inequalities are discussed.

We study the convergence of a class of penalty and barrier methods for solving monotone variational inequalities with constraints. This class of methods is an extension of penalty and barrier methods for convex optimization to the setting of variational inequalities. Primal convergence is established under weaker conditions than usual: the solution set is supposed either to be a compact set or, for the case of interior barrier methods, the sum of a compact set and a linear space. Dual convergence is also analyzed. The analysis strongly exploits a new formula related to recession calculus.

The proximal point algorithm (PPA) is a method for solving inclusions of the form $0\in T(z)$, where T is a monotone operator on a Hilbert space. The algorithm is one of the most powerful and versatile solution techniques for solving variational inequalities, convex programs, and convex-concave mini-max problems. It possesses a robust convergence theory for very general problem classes and is the basis for a wide variety of decomposition methods called splitting methods. Yet the classical PPA typically exhibits slow convergence in many applications. For this reason, acceleration methods for the PPA algorithm are of great practical importance. In this paper we propose a variable metric implementation of the proximal point algorithm. In essence, the method is a Newton-like scheme applied to the Moreau--Yosida resolvent of the operator T. In this article, we establish the global and linear convergence of the proposed method. In addition, we characterize the superlinear convergence of the method. In a companion work, we establish the superlinear convergence of the method when implemented with Broyden updating (the nonsymmetric case) and BFGS updating (the symmetric case).

The present paper investigates the error committed by using an infinite time horizon Markov renewal program as an approximation of the (often more realistic) Markov renewal program with a finite time horizon t0. Under weak assumptions the error is shown to converge to zero exponentially fast when $t_0 \to \infty$. The convergence is based on explicit error bounds. Improved error bounds hold when the (transformed) transition law has a nontrivial stochastic lower bound. Some bounds use the discounted renewal function. For the latter, monotone upper and lower bounds are obtained by an iterative method combined with an extrapolation. Several examples demonstrate the applicability of the results.

We propose new methods for solving the variational inequality problem where the underlying function $F$ is monotone. These methods may be viewed as projection-type methods in which the projection direction is modified by a strongly monotone mapping of the form $I - \alpha F$ or, if $F$ is affine with underlying matrix $M$, of the form $I+ \alpha M^T$, with $\alpha \in (0,\infty)$. We show that these methods are globally convergent, and if in addition a certain error bound based on the natural residual holds locally, the convergence is linear. Computational experience with the new methods is also reported.

This paper investigates the boundedness and stability of solutions to the affine variational inequality problem. The concept of a solution ray to a variational inequality defined by an affine, mapping and on a closed convex set is introduced and characterized; the connection of such a ray with the boundedness of the solution set of the given problem is explained. In the case of the monotone affine variational inequality, a complete description of the solution set is obtained which leads to a simplified characterization of the boundedness of this set as well as to a new error bound result for approximate solutions to such a variational problem. The boundedness results are then combined with certain degree- theoretic arguments to establish the stability of the solution set of an affine variational inequality problem.

This paper proves an existence result for a complementarily problem (on a locally convex space) where the mapping is copositive, positive homogeneous, and of monotone type on a locally compact cone. A perturbation theorem is proved that extends a result of Mangasarian and Doverspike proved for $n \times n$ matrices on the nonnegative orthant.

In this paper feedback systems described by nonlinear (possibly multivalued) monotone operators are considered. We establish conditions for the existence and uniqueness of outputs corresponding to a given pair of inputs, conditions for causality, Lipschitz continuity and stability. Also, feedback systems over an extended Hilbert space are discussed. Finally, linear approximations to a nonlinear feedback system are studied.

We model a weapons development competition between two countries as a two person zero-sum stochastic game. Conditions are given which ensure that each player’s optimal strategy is monotone in the state, horizon length and discount factor. A non-zero-sum stochastic game model of a weapons development competition is also discussed.

The classical discrete minimax problem is considered. It is transformed into an equivalent problem by a monotone transformation of the initial functions. It was found that the classical Lagrangian ...

The structure of many sequential optimization problems over a finite or infinite horizon can be summarized in the mapping that defines the related dynamic programming algorithm. In this paper we take as a starting point this mapping and obtain results that are applicable to a broad class of problems. This approach has also been taken earlier by Denardo under contraction assumptions. The analysis here is carried out without contraction assumptions and thus the results obtained can be applied, for example, to the positive and negative dynamic programming models of Blackwell and Strauch. Most of the existing results for these models are generalized and several new results are obtained relating mostly to the convergence of the dynamic programming algorithm and the existence of optimal stationary policies.

The stochastic control problem of tracking a Brownian motion by a nondecreasing process (Monotone Follower) is related to a question of Optimal Stopping. Direct probabilistic arguments are employed to show that the two problems are equivalent, and that both admit optimal solutions.

In this paper the optimal replacement problem of a one-unit system under periodic inspection is analyzed utilizing Markov decision theory. The problem is formulated in a general setting and it is shown that an age replacement policy is in fact optimal if the component lifetime has monotone failure rate. A necessary and sufficient condition of optimality together with several characterizations of the optimal policy are presented.

The value function, V, of the optimal control problem in which the controls must be monotone nondecreasing is a $W^{1,\infty } $ generalized solution of the quasi-variational inequality (QVI) $\max \{ LV,V_y \} = 0$. Here $LV = V_t + f \cdot \nabla _x V + h$ and f, h the dynamics of the control problem. We extend the Crandall, Evans, Lions definition of viscosity solution for nonlinear first-order p.d.e.s. to systems like (QVI) and prove that V is the unique viscosity solution of (QVI). Further, V is the smallest function satisfying the inequalities $LV \leqq 0$, $V_y \leqq 0$.

Applied to strongly monotone variational inequalities, Newton’s algorithm achieves local quadratic convergence. In this paper it is shown how the basic Newton method can be modified to yield an algorithm whose global convergence can be guaranteed by monitoring the monotone decrease of the “gap function” associated with the variational inequality. Each iteration consists in the solution of a linear program in the space of primal-dual variables and of a linesearch. Convergence does not depend on strong monotonicity. However, under strong monotonicity and geometric stability assumptions, the set of active constraints at the solution is implicitly identified, and quadratic convergence is achieved.

We develop an abstract approximating process for control problems with convex cost governed by evolution equations involving monotone operators. Applications are given concerning necessary conditions of optimality for distributed control problems with hyperbolic, parabolic and delay differential state systems. These conditions are expressed by means of the Clarke [11] generalized gradient.

This paper is devoted to the study of convergence conditions for the monotone and autonomous iterative algorithm model. Two convergence conditions are presented, and it is shown that (i) they are not comparable and (ii) they contain the known convergence conditions for the model. The presentation of the results is facilitated by the introduction of the concept of extended characteristic set of an iterative procedure.

Noncooperative sequential games, including the noncooperative stochastic game of Rogers (1969) and Sobel (1971), are investigated in the monotone contraction operator framework of Denardo (1967). Sufficient conditions are determined for the existence of equilibrium points in this setting. Techniques for comparing and, approximating dynamic programs previously developed by the author are then applied to these sequential games, yielding conditions for the existence of $\varepsilon $-equilibrium points.

For the problem of minimizing a lower semicontinuous proper convex function f on a Hilbert space, the proximal point algorithm in exact form generates a sequence $\{ z^k \} $ by taking $z^{k + 1} $ to be the minimizes of $f(z) + ({1 / {2c_k }})\| {z - z^k } \|^2 $, where $c_k > 0$. This algorithm is of interest for several reasons, but especially because of its role in certain computational methods based on duality, such as the Hestenes-Powell method of multipliers in nonlinear programming. It is investigated here in a more general form where the requirement for exact minimization at each iteration is weakened, and the subdifferential $\partial f$ is replaced by an arbitrary maximal monotone operator T. Convergence is established under several criteria amenable to implementation. The rate of convergence is shown to be “typically” linear with an arbitrarily good modulus if $c_k $ stays large enough, in fact superlinear if $c_k \to \infty $. The case of $T = \partial f$ is treated in extra detail. Applicati...