Fast Moreau envelope computation I: numerical algorithms

The present article summarizes the state of the art algorithms to compute the discrete Moreau envelope, and presents a new linear-time algorithm, named NEP for NonExpansive Proximal mapping. Numerical comparisons between the NEP and two existing algorithms: The Linear-time Legendre Transform (LLT) and the Parabolic Envelope (PE) algorithms are performed. Worst-case time complexity, convergence results, and examples are included. The fast Moreau envelope algorithms first factor the Moreau envelope as several one-dimensional transforms and then reduce the brute force quadratic worst-case time complexity to linear time by using either the equivalence with Fast Legendre Transform algorithms, the computation of a lower envelope of parabolas, or, in the convex case, the non expansiveness of the proximal mapping.      

Moreau–Rockafellar Theorems for Nonconvex Set-Valued Maps

In this paper, we introduce the notion of (Benson) proper subgradient of a set-valued map and prove that, for some class of nonconvex set-valued maps, a proper subgradient of the sum of two set-valued maps can be expressed as the sum of two proper subgradients of these maps. This property is also established for weak subgradients. A result in Ref. [Lin, L.J.: J. Math. Anal. Appl. 186, 30–51 (1994)], obtained under some convexity assumption, is included as a special case of the corresponding result of this paper. The author thanks the anonymous referees for their valuable remarks.     

A generalization of Fenchel duality theory

This paper deals with an extention of Fenchel duality theory to fractional extremum problems, i.e., problems having a fractional objective function. The main result is obtained by regarding the classic Fenchel theorem as a decomposition property for the extremum of a sum of functions into a sum of extrema of functions, and then by extending it to the case where the addition is replaced by the quotient. This leads to a generalization of the classic concept of conjugate function. Several remarks are made about the conceivable further generalizations to other kinds of decomposition.     

Generalized Fenchel’s Conjugation Formulas and Duality for Abstract Convex Functions

In this paper, we present a generalization of Fenchel’s conjugation and derive infimal convolution formulas, duality and subdifferential (and ε-subdifferential) sum formulas for abstract convex functions. The class of abstract convex functions covers very broad classes of nonconvex functions. A nonaffine global support function technique and an extended sum-epiconjugate technique of convex functions play a crucial role in deriving the results for abstract convex functions. An additivity condition involving global support sets serves as a constraint qualification for the duality. Work of Z.Y. Wu was carried out while the author was at the Department of Applied Mathematics, University of New South Wales, Sydney, Australia.     

Towards an L^p Potential Theory for Sub-Markovian Semigroups： Kernels and Capacities

We study in fairly general measure spaces （X,μ） the （non-linear） potential theory of L^p sub-Markovian semigroups which are given by kernels having a density with respect to the underlying measure. In terms of mapping properties of the operators we provide sufficient conditions for the existence （and regularity） of such densities. We give various （dual） representations for several associated capacities and, in the corresponding abstract Bessel potential spaces, we study the role of the truncation property. Examples are discussed in the case of R^n where abstract Bessel potential spaces can be identified with concrete function spaces.     

The Passage Time Distribution for a Birth-and-Death Chain: Strong Stationary Duality Gives a First Stochastic Proof

A well-known theorem usually attributed to Keilson states that, for an irreducible continuous-time birth-and-death chain on the nonnegative integers and any d, the passage time from state 0 to state d is distributed as a sum of d independent exponential random variables. Until now, no probabilistic proof of the theorem has been known. In this paper we use the theory of strong stationary duality to give a stochastic proof of a similar result for discrete-time birth-and-death chains and geometric random variables, and the continuous-time result (which can also be given a direct stochastic proof) then follows immediately. In both cases we link the parameters of the distributions to eigenvalue information about the chain. We also discuss how the continuous-time result leads to a proof of the Ray–Knight theorem. Intimately related to the passage-time theorem is a theorem of Fill that any fastest strong stationary time T for an ergodic birth-and-death chain on {0,…,d} in continuous time with generator G, started in state 0, is distributed as a sum of d independent exponential random variables whose rate parameters are the nonzero eigenvalues of −G. Our approach yields the first (sample-path) construction of such a T for which individual such exponentials summing to T can be explicitly identified. Research of J.A. Fill was supported by NSF grant DMS–0406104 and by The Johns Hopkins University’s Acheson J. Duncan Fund for the Advancement of Research in Statistics.     

An Answer to S. Simons’ Question on the Maximal Monotonicity of the Sum of a Maximal Monotone Linear Operator and a Normal Cone Operator

The question whether or not the sum of two maximal monotone operators is maximal monotone under Rockafellar’s constraint qualification—that is, whether or not “the sum theorem” is true—is the most famous open problem in Monotone Operator Theory. In his 2008 monograph “From Hahn-Banach to Monotonicity”, Stephen Simons asked whether or not the sum theorem holds for the special case of a maximal monotone linear operator and a normal cone operator of a closed convex set provided that the interior of the set makes a nonempty intersection with the domain of the linear operator. In this note, we provide an affirmative answer to Simons’ question. In fact, we show that the sum theorem is true for a maximal monotone linear relation and a normal cone operator. The proof relies on Rockafellar’s formula for the Fenchel conjugate of the sum as well as some results featuring the Fitzpatrick function.