Search

We consider a two-stage submodular maximization problem subject to a cardinality constraint andkmatroid constraints, where the objective function is the expected difference of a nonnegative monotone submodular function and a nonnegative monotone modular function. We give two bi-factor approximation algorithms for this problem. The first is a deterministic$\left( {{1 \over {k + 1}}\left( {1 - {1 \over {{e^{k + 1}}}}} \right),1} \right)$-approximation algorithm, and the second is a randomized$\left( {{1 \over {k + 1}}\left( {1 - {1 \over {{e^{k + 1}}}}} \right) - \varepsilon ,1} \right)$-approximation algorithm with improved time efficiency.

In this paper we give a description of the structure of compact global attractor (Levinson center) for monotone Bohr/Levitan almost periodic dynamical system $x'=f(t,x)$ (*) with the strictly monotone first integral. It is shown that Levinson center of equation (*) consists of the Bohr/Levitan almost periodic (respectively, almost automorphic, recurrent or Poisson stable) solutions. We establish the main results in the framework of general non-autonomous (cocycle) dynamical systems. We also give some applications of theses results to different classes of differential/difference equations.

In this paper, we investigate the monotone variational inequality in Hilbert spaces. Based on Censor’s subgradient extragradient method, we propose two modified subgradient extragradient algorithms with self-adaptive and inertial techniques for finding the solution of the monotone variational inequality in real Hilbert spaces. Strong convergence analysis of the proposed algorithms have been obtained under some mild conditions.

Team formation plays an essential role in the labor market. In this paper, we propose two bicriteria algorithms to construct a balance between gain and cost in a team formation problem under the streaming model, subject to a cardinality constraint. We formulate the problem as maximizing the difference of a non-negative normalized monotone submodular function and a non-negative linear function. As an extension, we also consider the case where the first function is $$\gamma $$ -weakly submodular. Combining the greedy technique with the threshold method, we present bicriteria streaming algorithms and give detailed analysis for both of these models. Our analysis is competitive with that in Ene’s work.

In this work, we study the generalized Nash equilibrium (GNE, see Definition 1 ) seeking problem for monotone generalized noncooperative games with set constraints and shared affine inequality constraints. A novel projected gradient-based regularized penalized dynamical system is proposed to solve this issue. The idea is to use a differentiable penalty function with a time-varying penalty parameter to deal with the inequality constraints. A time-varying regularization term is used to deal with the ill-poseness caused by the monotonicity assumption and the time-varying penalty term. The proposed dynamical system extends the regularized dynamical system in the literature to the projected gradient-based regularized penalized dynamical system, which can be used to solve generalized noncooperative games with set constraints and coupled constraints. Furthermore, we propose a distributed algorithm by using leader-following consensus, where the players have access to neighboring information only. For both cases, the asymptotic convergence to the least-norm variational equilibrium of the game is proven. Numerical examples show the effectiveness and efficiency of the proposed algorithms.

This paper is contributed to the structural stability of multi-wave configurations to Cauchy problem for the compressible non-isentropic Euler system with adiabatic exponent γ ∈ (1, 3]. Given some small BV perturbations of the initial state, the author employs a modified wave front tracking method, constructs a new Glimm functional, and proves its monotone decreasing based on the possible local wave interaction estimates, then establishes the global stability of the multi-wave configurations, consisting of a strong 1-shock wave, a strong 2-contact discontinuity, and a strong 3-shock wave, without restrictions on their strengths.

We consider the stochastic generalized Nash equilibrium problem (SGNEP) with expected-value cost functions. Inspired by Yi and Pavel (2019), we propose a distributed generalized Nash equilibrium seeking algorithm based on the preconditioned forward-backward operator splitting for SGNEPs, where, at each iteration, the expected value of the pseudogradient is approximated via a number of random samples. Our main contribution is to show almost sure convergence of the proposed algorithm if the pseudogradient mapping is restricted (monotone and) cocoercive.

In this paper, we generalize the concept of a monotone convergence space (also called a d-space) to the setting of a Q -cotopological space, where Q is a commutative and integral quantale. We establish a D-completion for every stratified Q -cotopological space, which is a category reflection of the category S Q -CTop of stratified Q -cotopological spaces onto the full subcategory S Q -DCTop of monotone convergence Q -cotopological spaces. By introducing the notion of a tapered set, a direct characterization of the completion is obtained: the D-completion of each stratified Q -cotopological space X consists exactly of those tapered closed sets in X. We show that the D-completion can be applied to obtain a universal fuzzy directed completion of a Q -ordered set by endowing it with the Scott cotopology, taking the D-completion, and then passing to the specialization Q -order. Consequently, the category Q -DOrd of fuzzy directed complete Q -ordered sets and Scott continuous functions is reflective in the category Q -Ordσ of Q -ordered sets and Scott continuous functions.

In this paper, we introduce a new type of a generalized split monotone variational inclusion (GSMVI) problem in the framework of real Hilbert spaces. By incorporating an inertial extrapolation method and an Halpern iterative technique, we establish a strong convergence result for approximating a solution of GSMVI and fixed point problems of certain nonlinear mappings in the framework of real Hilbert spaces. Many existing results are derived as corollaries to our main result. Furthermore, we present a numerical example to support our main result and propose an open problem for interested researchers in this area. The result obtained in this paper improves and generalizes many existing results in the literature.

In this paper, we introduce a new iterative forward-backward splitting method with an error for solving the variational inclusion problem of the sum of two monotone operators in real Hilbert spaces. We suggest and analyze this method under some mild appropriate conditions imposed on the parameters such that another strong convergence theorem for these problem is obtained. We also apply our main result to improve the fast iterative shrinkage thresholding algorithm (IFISTA) with an error for solving the image deblurring problem. Finally, we provide numerical experiments to illustrate the convergence behavior and show the effectiveness of the sequence constructed by the inertial technique to the fast processing with high performance and the fast convergence with good performance of IFISTA.

This study considers a mechanism design problem in which service slots are allocated over time to buyers arriving at different periods. Some buyers can accept delayed service, whereas others cannot. Buyers have a multidimensional type representing their valuation and patience level. The seller fully commits to a mechanism with or without complete contingent contracts. We show that a deterministic mechanism is periodic ex-post incentive compatible if and only if the allocation rule is monotone in valuation and the "price equivalence" holds. In cases both with and without contingent contracts, the dynamic pivot mechanism with a reserve price maximizes the seller's expected revenue under a regularity condition, which is characterized by the linearity of the virtual valuation function. When the regularity holds, the fully optimal mechanism with contingent contracts is multi-contracting-proof, whereas the constrained optimal mechanism without contingent contracts is not.

We study distributed algorithms for seeking a Nash equilibrium in a class of convex networked Nash games with strongly monotone mappings. Each player has access to her own smooth local cost function and can communicate to her neighbors in some undirected graph. To deal with fast distributed learning of Nash equilibria under such settings, we introduce a so called augmented game mapping and provide conditions under which this mapping is strongly monotone. We consider a distributed gradient play algorithm for determining a Nash equilibrium (GRANE). The algorithm involves every player performing a gradient step to minimize her own cost function while sharing and retrieving information locally among her neighbors in the network. Using the reformulation of the Nash equilibrium problem based on the strong monotone augmented game mapping, we prove the convergence of this algorithm to a Nash equilibrium with a geometric rate. Furthermore, we introduce the Nesterov type acceleration for the gradient play algorithm. We demonstrate that, similarly to the accelerated algorithms in centralized optimization and variational inequality problems, our accelerated algorithm outperforms GRANE in the convergence rate. Moreover, to relax assumptions required to guarantee the strongly monotone augmented mapping, we analyze the restricted strongly monotone property of this mapping and prove geometric convergence of the distributed gradient play under milder assumptions.

We investigate the problem of the successive refinement for Wyner-Ziv coding with degraded side information and obtain a complete characterization of the rate region for the quadratic vector Gaussian case. The achievability part is based on the evaluation of the Tian-Diggavi inner bound that involves Gaussian auxiliary random vectors. For the converse part, a matching outer bound is obtained with the aid of a new extremal inequality. Herein, the proof of this extremal inequality depends on the integration of the monotone path argument and the doubling trick as well as information-estimation relations., 19 pages, 1 figure

In this paper, we study the problem of maximizing a monotone non-decreasing submodular function $$f :2^\Omega \rightarrow {\mathbb {R}}_{+}$$ subject to a cardinality constraint, i.e., $$\max \{ f(A) : |A| \le k, A \subseteq \Omega \} $$ . We propose a deterministic algorithm based on a new greedy strategy for solving this problem. We prove that when the objective function f satisfies certain assumptions, the algorithm we propose can return a $$1 - \kappa _f (1 - \frac{1}{k})^k$$ approximate solution with O(kn) value oracle queries, where $$\kappa _f$$ is the curvature of the monotone submodular function f. We also show that our algorithm outperforms the traditional greedy algorithm in some cases. Furthermore, we demonstrate how to implement our algorithm in practice.

In this paper we introduce the notions of continuity, meet continuity and quasicontinuity of Δ-spaces, where a Δ-space is a monotone determined, weak monotone convergence space. We prove that: a Δ-space $(X, \mathcal {O}(X))$ is continuous iff the topology lattice $\mathcal {O}(X)$ is completely distributive; a Δ-space $(X, \mathcal {O}(X))$ is meet continuous iff $\mathcal {O}(X)$ is a complete Heyting algebra; a Δ-space $(X, \mathcal {O}(X))$ is continuous iff it is both meet continuous and quasicontinuous. The concepts of continuity, s2-continuity, 𝜃-continuity, strong continuity of posets are shown to be special cases of the continuity of Δ-spaces. We also introduce a type of directed completion of Δ-spaces, called Scott completion. For each Δ-space $(X, \mathcal {O}(X))$ , the topology lattice $\mathcal {O}(X)$ is isomorphic to the topology lattice of its Scott completion. The D-completion, D𝜃-completion and $D_{s_{2}}$ -completion of posets are included in the Scott completion.

An inertial shadow Douglas-Rachford splitting algorithm for finding zeros of the sum of monotone operators is proposed in Hilbert spaces. Moreover, a three-operator splitting algorithm for solving ...

This paper investigates dynamically consistent updates of weighted unanimity rules given by variational Bewley preferences (VBP), a class of incomplete preferences characterized by pairs of utility index over consequences and ambiguity index over priors. We show that these dynamically consistent updates are also VBP that preserves the same ranking over consequences and feature conditional ambiguity index obtained through the full Bayesian update of the unconditional one. Moreover, we study conditional forced-choice relations, which capture choices that a decision-maker must take after learning some event. Formally, they are monotone continuous weak orders. We show that any conditional forced-choice relation that preserves the ambiguity attitude of a given unconditional VBP has a variational representation with the same affine utility function over consequences and the ambiguity index of its corresponding dynamically consistent update. Thus, our result provides a novel foundation for full Bayesian updating of variational preferences.

We continue our study of a new boundedness condition for affine permutations, motivated by the fruitful concept of periodic boundary conditions in statistical physics. We focus on bounded affine permutations of size $N$ that avoid the monotone decreasing pattern of fixed size $m$. We prove that the number of such permutations is asymptotically equal to $(m-1)^{2N} N^{(m-2)/2}$ times an explicit constant as $N\to\infty$. For instance, the number of bounded affine permutations of size $N$ that avoid $321$ is asymptotically equal to $4^N (N/4\pi)^{1/2}$. We also prove a permuton-like result for the scaling limit of random permutations from this class, showing that the plot of a typical bounded affine permutation avoiding $m\cdots1$ looks like $m-1$ random lines of slope $1$ whose $y$ intercepts sum to $0$.

In this paper we study the principal spectral theory and asynchronous exponential growth for age-structured models with nonlocal diffusion of Neumann type. First, we provide two general sufficient conditions to guarantee existence of the principal eigenvalue of the age-structured operator with nonlocal diffusion. Then we show that such conditions are also enough to ensure that the semigroup generated by solutions of the age-structured model with nonlocal diffusion exhibits asynchronous exponential growth. Compared with previous studies, we prove that the semigroup is essentially compact instead of eventually compact, where the latter is usually obtained by showing the compactness of solution trajectories. Next, following the technique developed in Vo (Principal spectral theory of time-periodic nonlocal dispersal operators of Neumann type. arXiv:1911.06119 , 2019), we overcome the difficulty that the principal eigenvalue of a nonlocal Neumann operator is not monotone with respect to the domain and obtain some limit properties of the principal eigenvalue with respect to the diffusion rate and diffusion range. Finally, we establish the strong maximum principle for the age-structured operator with nonlocal diffusion.

Anomaly detection is essential to guarantee the correctness of sensory data collected from Internet of Things. The latest detection approaches only operate under one of the two general forms of short-term or long-term anomaly. In this article, we propose monotone split and conquer (MSC) scheme to tackle both anomaly forms. The proposed scheme exploits the spatial–temporal correlation between neighboring sensors to detect abnormal sensory data. MSC splits the collected data into monotonic subtrends in the training phase to establish the trend-based normal profiles for the online detection phase. To eradicate the overfitting phenomenon, we further develop a general formulation to estimate the square prediction error (SPE) control limit. Both monotone split and general formulation contribute to the advancement of MSC in terms of accuracy (ACC) and false positive rate (FPR) in the online detection phase. To evaluate the performance of MSC, we design a general anomaly model to generate artificial short-term and long-term anomalies. Numerical experiments with the Intel Berkeley Research Lab (IBRL) data set demonstrate that MSC obtains about 8% higher ACC and 5% lower FPR on average when compared to existing schemes. Remarkably, MSC requires only a few observations for anomaly detection as it is applicable to real-time systems.

The paper concerns with a new iterative method for solving a monotone variational inclusion problem in a Hilbert space. The method is of the proximal contraction type incorporated with the regularization technique. Under the prediction stepsize conditions, we establish the strong convergence of the iterative sequences generated by the method to a particular solution of the problem satisfying a variational inequality problem. Finally, we give some numerical examples to illustrate the behavior of the new method in comparison with existing ones.

We develop two-scale methods for computing the convex envelope of a continuous function over a convex domain in any dimension.This hinges on a fully nonlinear obstacle formulation [A. M. Oberman, "The convex envelope is the solution of a nonlinear obstacle problem", Proc. Amer. Math. Soc. 135(6):1689--1694, 2007]. We prove convergence and error estimates in the max norm. The proof utilizes a discrete comparison principle, a discrete barrier argument to deal with Dirichlet boundary values, and the property of flatness in one direction within the non-contact set. Our error analysis extends to a modified version of the finite difference wide stencil method of [A. M. Oberman, "Computing the convex envelope using a nonlinear partial differential equation", Math. Models Meth. Appl. Sci, 18(05):759--780, 2008].

We construct a continuous nowhere monotone and nondifferentiable function depending on a single parameter q0 ϵ (0; 1). For functions from this continual class, we describe their structural, variational, fractal, and integrodifferential properties.

We study the split monotone variational inclusion problem in two real Hilbert spaces. Combining the inertial and relaxation techniques with the proximal contraction algorithm, we propose two new me...

It is the purpose of this paper to introduce an iterative process which converges strongly to a common point of the set of solutions of a finite family of generalized equilibrium problems, the set of fixed points of a finite family of continuous asymptotically quasi- $$\phi$$ -nonexpansive mappings in the intermediate sense, and the set of zeros of a finite family of $$\gamma$$ -inverse strongly monotone mappings in uniformly convex and uniformly smooth real Banach space. Our results improve and unify most of the results that have been proved for this important class of nonlinear mappings.

We consider knowledge-oriented models, problems, and algorithms for routing traveling salesmen in complex networks. The formalization leads to models of pseudo-Boolean discrete optimization with constraints that take into account the specifics of the multiple traveling salesmen problem. We consider a class of problems that can be represented in the form of pseudo-Boolean optimization models with separable objective functions (monotone, linear) and constraints in the form of disjunctive normal forms (DNFs). We demonstrate the possibility of an approximate synthesis of DNF constraints based on precedent information. The methodology, theoretical principles, and algorithms for solving problems of this class are presented. It is shown that the solution of routing problems can be based on the application of a multiagent approach in combination with clustering of the original problem, pseudo-Boolean optimization algorithms with disjunctive constraints, and metaheuristics.

Monotone Boolean circuits are circuits where each gate is either an AND gate or an OR gate. In other words, negation gates are not allowed on monotone circuits. This class of circuits has sparked the attention of researchers working in several subfields of combinatorics and complexity theory. In this work, we consider the notion of certification-width of a monotone Boolean circuit, a complexity measure that intuitively quantifies the minimum number of edges that need to be traversed by a minimal set of positive weight inputs in order to certify that a given circuit is satisfied. We call the problem of computing this invariant as Succinct Monotone Circuit Certification (SMCC) . We prove that SMCC is NP-complete even when the input monotone circuit is planar. Subsequently, we show that k -SMCC , the problem parameterized by the size of the solution, is W[1]-hard, but still in W[P]. In contrast, we show that k -SMCC is fixed-parameter tractable when restricted to monotone circuits of bounded genus.

Decentralized dual methods play significant roles in large-scale optimization, which effectively resolve many constrained optimization problems in machine learning and power systems. In this article, we focus on studying a class of totally non-smooth constrained composite optimization problems over multi-agent systems, where the mutual goal of agents in the system is to optimize a sum of two separable non-smooth functions consisting of a strongly-convex function and another convex (not necessarily strongly-convex) function. Agents in the system conduct parallel local computation and communication in the overall process without leaking their private information. In order to resolve the totally non-smooth constrained composite optimization problem in a fully decentralized manner, we devise a synchronous decentralized dual proximal (SynDe-DuPro) gradient algorithm and its asynchronous version (AsynDe-DuPro) based on the randomized block-coordinate method. Both SynDe-DuPro and AsynDe-DuPro algorithms are theoretically proved to achieve the globally optimal solution to the totally non-smooth constrained composite optimization problem relied on the quasi-Fejer monotone theorem. As a main result, AsynDe-DuPro algorithm attains the globally optimal solution without requiring all agents to be activated at each iteration and thus is more robust than most existing synchronous algorithms. The practicability of the proposed algorithms and correctness of the theoretical findings are demonstrated by the experiments on a constrained Decentralized Sparse Logistic Regression (DSLR) problem in machine learning and a Decentralized Energy Resources Coordination (DERC) problem in power systems.

This paper clarifies the relationship between dynamic fairness, inequality, and mobility. Suppose agents assess the degree of fairness in a society based on the distribution of expected future income, conditional on current income. Within Markovian environments characterised by stochastically monotone transition rules, in which a globally stable steady-state income distribution exists, we show that the degree of dynamic fairness is jointly determined by inequality and mobility. When mobility is held constant, inequality harms fairness; on the contrary, when inequality is held constant, mobility enhances fairness. Moreover, any particular degree of fairness can be obtained by one of many combinations of inequality and mobility, and trade-offs always exists between any two such pairs. Our results hold true with both the standard Lorenz curve and the generalised Lorenz curve and extend to multi-period settings.

In this paper, we study the generalized submodular maximization problem with a non-negative monotone submodular set function as the objective function and subject to a matroid constraint. The problem is generalized through the curvature parameter α ∈ [ 0 , 1 ] which measures how far a set function deviates from linearity to submodularity. We propose a deterministic approximation algorithm which uses the approximation algorithm proposed by Buchbinder et al. [2] as a building block and inherits the approximation guarantee for α = 1 . For general value of the curvature parameter α ∈ [ 0 , 1 ] , we present an approximation algorithm with a factor of 1 + h α ( y ) + Δ ⋅ [ 3 + α − ( 2 + α ) y − ( 1 + α ) h α ( y ) ] 2 + α + ( 1 + α ) ( 1 − y ) , where y ∈ [ 0 , 1 ] is a predefined parameter for tuning the ratio. In particular, when α = 1 we obtain a ratio 0.5008 when setting y = 0.9 , coinciding with the renowned state-of-art approximate ratio; when α = 0 that the object is a linear function, the approximation factor equals one and our algorithm is indeed an exact algorithm that always produces optimum solutions.

In this letter, we present a fast method for autonomously planing manipulation tasks for mobile manipulators. The planner defines an optimal order to perform pick-and-place operations for taking objects from a cluttered scene to specific deposit areas considering both, manipulator and mobile base motion. Our method first examines the grasping feasibility of the objects with an inverse reachability map. Then, it defines all the placing locations for the objects and analyses the corresponding preconditions to reach them. Finally, it defines a sequence for rearranging the objects that minimize the execution time. We take advantage of the environment's underlying combinatorial structure to define the shortest path. In this work, we consider both the monotone case, where each object may be moved at most once, and the non-monotone cases. An experimental evaluation on the Human Support Robot (HSR) shows the effectiveness of our solutions and the scalability of our method as the number of objects increases for both cases. Tests on monotone problem instances with 20 objects show the proposed method can save up to 17% base traveling time when comparing to baseline methods at the cost of less than 9 seconds planning time. In a test on a simple non-monotone instance, the proposed method further reduces the total execution time by 25% by minimizing the total number of actions in a few seconds of planning time. The characteristic speed in re-planning makes our method suitable for online usage.

The storage and distribution of medical supplies are important parts of epidemic prevention and control. This paper first proposes a new nonsmooth two-stage stochastic equilibrium model of medical supplies in epidemic management. The first stage addresses the storage in the pre-disaster phase, and the second stage focuses on the dynamic distribution by enrolling competitions among multiple hospitals over a period of time in the post-disaster phase. The uncertainties are the numbers of infected people treated in multiple hospitals during the period of time, which are time-varying around a nominal distribution predicted by historical experience. The two-stage stochastic equilibrium model is further approximated and transformed to a monotone two-stage stochastic variational inequality (SVI) model that is computationally tractable, with the aid of a smooth approximation technique. We employ the progressive hedging method (PHM) to solve a case study in the city of Wuhan in China suffered from the COVID-19 pandemic. Numerical results are presented to demonstrate the effectiveness of the proposed model in planning the storage and dynamic distribution of medical supplies in epidemic management.

In this paper we investigate the Sturmian theory for general (possibly uncontrollable) linear Hamiltonian systems by means of the Lidskii angles, which are associated with a symplectic fundamental matrix of the system. In particular, under the Legendre condition we derive formulas for the multiplicities of the left and right proper focal points of a conjoined basis of the system, as well as the Sturmian separation theorems for two conjoined bases of the system, in terms of the Lidskii angles. The results are new even in the completely controllable case. As the main tool we use the limit theorem for monotone matrix-valued functions by Kratz (1993). The methods allow to present a new proof of the known monotonicity property of the Lidskii angles. The results and methods can also be potentially applied in the singular Sturmian theory on unbounded intervals, in the oscillation theory of linear Hamiltonian systems without the Legendre condition, in the comparative index theory, or in linear algebra in the theory of matrices.

This paper considers the Lurye system of a discrete-time, linear time-invariant plant in negative feedback with a nonlinearity. Both monotone and slope-restricted nonlinearities are considered. The main result is a procedure to construct destabilizing nonlinearities for the Lurye system. If the plant satisfies a certain phase condition then a monotone nonlinearity can be constructed so that the Lurye system has a non-trivial periodic cycle. Several examples are provided to demonstrate the construction. This represents a contribution for absolute stability analysis since the constructed nonlinearity provides a less conservative upper bound than existing bounds in the literature., 6 pages, 8 figures, submitted to IEEE CSL

In this paper, we propose a numerical approach for solving composite primal-dual monotone inclusions with a priori information. The underlying a priori information set is represented by the intersection of fixed point sets of a finite number of operators, and we propose and algorithm that activates the corresponding set by following a finite-valued random variable at each iteration. Our formulation is flexible and includes, for instance, deterministic and Bernoulli activations over cyclic schemes, and Kaczmarz-type random activations. The almost sure convergence of the algorithm is obtained by means of properties of stochastic Quasi-Fej\'er sequences. We also recover several primal-dual algorithms for monotone inclusions in the context without a priori information and classical algorithms for solving convex feasibility problems and linear systems. In the context of convex optimization with inequality constraints, any selection of the constraints defines the a priori information set, in which case the operators involved are simply projections onto half spaces. By incorporating random projections onto a selection of the constraints to classical primal-dual schemes, we obtain faster algorithms as we illustrate by means of a numerical application to a stochastic arc capacity expansion problem in a transport network., Comment: 23 Pages, 4 figures, 4 Tables

In this paper, we introduce a new inertial self-adaptive parallel subgradient extragradient method for finding common solution of variational inequality problems with monotone and Lipschitz continu...

We are interested in the optimal control problem associated with certain quadratic cost functionals depending on the solution $X=X^\alpha$ of the stochastic mean-field type evolution equation in $\mathbb R^d$ $dX_t=b(t,X_t,\mathcal L(X_t),\alpha_t)dt+\sigma(t,X_t,\mathcal L(X_t),\alpha_t)dW_t,$ $X_0\sim \mu$ given, under assumptions that enclose a sytem of FitzHugh-Nagumo neuron networks, and where for practical purposes the control $\alpha_t$ is deterministic. To do so, we assume that we are given a drift coefficient that satisfies a one-sided Lipshitz condition, and that the dynamics is subject to a (convex) level set constraint of the form $\pi(X_t)\leq0$. The mathematical treatment we propose follows the lines of the recent monograph of Carmona and Delarue for similar control problems with Lipshitz coefficients. After addressing the existence of minimizers via a martingale approach, we show a maximum principle and then numerically investigate a gradient algorithm for the approximation of the optimal control., Comment: 32 pages; 11 figures

Personalized medicine allows individuals to choose the best fit of their treatments based on their characteristics through an individualized treatment regime. In this paper, we develop a pool adjacent violators algorithm-assisted learning method to find the optimal individualized treatment regime under the monotone single-index outcome gain model. The proposed estimator is more efficient than peers, and it is robust to the misspecification of the propensity score model or the baseline regression model. The optimal treatment regime is also robust to the misspecification of the functional form of the expected outcome gain model. Simulation studies verified our theoretical results. We also provide an estimate of the expected outcome gain model. Plotting the expected outcome gain versus an individual's characteristics index can visualize how significant the treatment effect is over the control. We apply the proposed method to an AIDS study.

In this paper we propose a new concept of quasi-uniform monotonicity weaker than the uniform monotonicity which has been developed in the study of nonlinear operator equation Au = b. We prove that if A is a quasi-uniformly monotone and hemi-continuous operator, then A−1 is strictly monotone, bounded and continuous, and thus the Galerkin approximations converge. Also we show an application of a quasi-uniformly monotone and hemi-continuous operator to the proof of the well-posedness and convergence of Galerkin approximations to the solution of steady-state electromagnetic p-curl systems.

The aim of this paper is to propose two modified forward-backward splitting algorithms for zeros of the sum of a maximal monotone operator and a Bregman inverse strongly monotone operator in reflexive Banach spaces. We prove weak and strong convergence theorems of the generated sequences by the proposed methods under some suitable conditions. We apply our results to study the variational inequality problem and the equilibrium problem. Finally, a numerical example is given to illustrate the proposed methods. The results presented in this paper improve and generalize many known results in recent literature.

An edge-ordered graph is a graph with a total ordering of its edges. A path $$P=v_1v_2\ldots v_k$$ in an edge-ordered graph is called increasing if $$(v_iv_{i+1}) < (v_{i+1}v_{i+2})$$ for all $$i = 1,\ldots,k-2$$ ; and it is called decreasing if $$(v_iv_{i+1}) > (v_{i+1}v_{i+2})$$ for all $$i = 1,\ldots,k-2$$ . We say that P is monotone if it is increasing or decreasing. A rooted tree T in an edge-ordered graph is called monotone if either every path from the root to a leaf is increasing or every path from the root to a leaf is decreasing. Let G be a graph. In a straight-line drawing D of G, its vertices are drawn as different points in the plane and its edges are straight line segments. Let $$\overline{\alpha}(G)$$ be the largest integer such that every edge-ordered straight-line drawing of G contains a monotone non-crossing path of length $$\overline{\alpha}(G)$$ . Let $$\overline{\tau}(G)$$ be the largest integer such that every edge-ordered straight-line drawing of G contains a monotone non-crossing complete binary tree of $$\overline{\tau}(G)$$ edges. In this paper we show that $$\overline \alpha(K_n) = \Omega(\log\log n)$$ , $$\overline \alpha(K_n) = O(\log n), \overline \tau(K_n) = \Omega(\log\log \log n)$$ and $$\overline \tau(K_n) = O(\sqrt{n \log n})$$ .

In this paper we provide a specific construction method of ordered directionally monotone functions. We show that the functions obtained with this construction method can be used to build edge detectors for grayscale images. We compare the results of these detectors to those obtained with some other ones that are widely used in the literature. Finally, we show how a consensus edge detector can be built improving the results obtained both by our proposal and by those in the literature when applied individually. This work was supported by the Slovak Research and Development Agency through grant APVV-18-0052 and the Grant Agency of the Czech Republic, through grant GACR 1806915S, and by the Spanish Government through project PID2019-108392GB-I00 (AEI/FEDER, UE) .

In this paper, a new modified Perry-type derivative-free projection method for solving large-scale nonlinear monotone equations is presented. The method is developed by combining a modified Perry’s conjugate gradient method with the hyperplane projection technique. Global convergence and numerical results of the proposed method are established. Preliminary numerical results show that the proposed method is promising and efficient compared to some existing methods in the literature.

It is well known that stochastic dominance is equivalent to a unanimity property for monotone expected utilities. For lotteries over a finite set of prizes, we establish an analogous relationship between likelihood ratio dominance and monotone betweenness preferences, which are an important generalization of expected utility. (JEL D11, D44)

In recent years there is a vast application of conjugate gradient methods to restore the disturbed signals in compressive sensing. This research aims at developing a scheme, which is more effective for restoring disturbed signals than the popular PCG method (Liu & Li, 2015). To realize the desired goal, a new conjugate gradient approach combined with the projection scheme of Solodov and Svaiter [Kluwer Academic Publishers, pp. 355-369(1998)] for solving monotone nonlinear equations with convex constraints is presented. The main idea employed in this algorithm is to approximate the Jacobian matrix via acceleration parameter in order to propose an effective conjugate gradient parameter. In addition, the step length is calculated using inexact line search technique. The proposed approach is proved to converge globally under some mild conditions . The numerical experiment, depicts the efficacy our method. Apart from generating search directions that are vital for global convergence, a significant contribution of the new method lies in its applications to solve the l 1 -norm regularization problem in signal recovery. Experiments with the scheme and the effective PCG solver, existing in the previous literature, shows that the new method provides much better results.

In this paper, we propose an accelerated variant of the proximal point algorithm for computing a zero of an arbitrary maximally monotone operator A. The method incorporates an inertial term (based upon the acceleration techniques introduced by Nesterov), relaxation factors and a correction term. In a general Hilbert space setting, we obtain the weak convergence of the iterates $$(x_n)$$ to equilibria, with the fast rate $$\Vert x_{n+1}-x_{n}\Vert =o(n^{-1})$$ (for the discrete velocity). In particular, when using constant proximal indexes, we establish the accuracy of $$(x_n)$$ to a zero of A with the worst-case rate $$\Vert A_{\lambda }(x_n)\Vert =o(n^{-1})$$ ( $$A_{\lambda }$$ being the Yosida regularization of A with some index $$\lambda $$ ). Furthermore, given any positive integer p and using an appropriate adjustment of increasing proximal indexes, we obtain the worst-case convergence rate $$\Vert A_{\lambda }(x_n)\Vert =o(n^{-(p+1)})$$ . This acceleration process can be applied to various proximal-type algorithms such as the augmented Lagrangian method, the alternating direction method of multipliers, operator splitting methods and so on. Our methodology relies on a Lyapunov analysis combined with a suitable reformulation of the considered algorithm. Numerical experiments are also performed.

The problem of computing the meet over all paths (MOP) solution in a monotone data flow framework over an infinite meet semilattice is generally undecidable [1] . Hence, the maximum fixed point (MFP) solution, which is polynomial time computable on semi-lattices of finite height, is generally used in practice for program analysis questions in monotone data flow frameworks. However, we show that if the semi-lattice is finite, computing MOP solution is NL -complete with respect to log space reductions, which implies parallelizability and polynomial time computability. It is also shown that the problem of computing the maximum fixed point (MFP) solution is P -complete with respect to log space reductions, and hence not efficiently parallelizable, even when the flow graph is directed acyclic and the semilattice has just four elements. These results appear in contrast with the fact that when the semilattice is not finite, solving the MOP problem is significantly harder than MFP.

In this note, we show a generalized version of convergence in measure theorem of Sugeno integrals in the framework concerning ordered pair of monotone measures. The condition of a kind of absolute continuity we employed is not only sufficient, but also necessary for the generalized version. The previous two versions (standard-form and pseudo-form) of the convergence in measure theorem are recovered by this generalized version. Thus, the convergence in measure theorems of Sugeno integrals are unified in general framework. In the same way the convergence in measure theorem and strict convergence in measure theorem of seminnormed fuzzy integrals are generalized, respectively. The relations between the convergence in measure and the convergence pseudo-in measure of measurable functions sequence are described in the context relating to a pair of monotone measures.

In this paper, optimal bounds for the sine and hyperbolic tangent means by arithmetic and centroidal means in exponential type are established using the monotone form of L'Hospital's rule and the criterion for the monotonicity of the quotient of power series.

We consider a birth–death process with killing where transitions from state i may go to either state $i-1$ or state $i+1$ or an absorbing state (killing). Stochastic ordering results on the killing time are derived. In particular, if the killing rate in state i is monotone in i, then the distribution of the killing time with initial state i is stochastically monotone in i. This result is a consequence of the following one for a non-negative tri-diagonal matrix M: if the row sums of M are monotone, so are the row sums of $M^n$ for all $n\ge 2$ .