Narrow Results

In this paper, we propose a concept of a lattice pseudo-submodular (LPS) function and consider maximizing a monotone continuous real LPS function $\varphi (x)$ under a convex polytope constraint. The concept of LPS function was proposed to describe the properties of some discrete functions or nonconvex continuous functions. It is a generalization of the lattice submodular function. For the real LPS maximization problem, we design the monotone Pseudo Frank-Wolfe (PFW) algorithm by taking advantage of the second derivative bound. The PFW algorithm iterates by constantly optimize linear gradient function $v^T\nabla \varphi (x)$, and finally outputs the solution. We theoretically prove that PFK algorithm has an approximation ratio of $(1-e^{-{(\frac{\beta }{\beta +1})}^2})$ (where $\beta \in (0,1]$), and it needs at least $O(n\zeta )$ rounds (where $\zeta$ is a parameter given in advance). The PFW algorithm is also useful for multilinear extension of discrete lattice pseudo-submodular maximization problems.

A simple polyhedron is weakly-monotonic in direction provided that the intersection of the polyhedron and any plane with normal is simply-connected (i.e. empty, a point, a line-segment or a simple polygon). Furthermore, if the intersection is a convex set, then the polyhedron is said to be weakly-monotonic in the convex sense. Toussaint¹⁰ introduced these types of polyhedra as generalizations of the 2-dimensional notion of monotonicity. We study the following recognition problems:

Given a simple n-vertex polyhedron in 3-dimensions, we present an O(n log n) time algorithm to determine if there exists a direction such that when sweeping over the polyhedron with a plane in direction , the cross-section (or intersection) is a convex set. If we allow multiple convex polygons in the cross-section as opposed to a single convex polygon, then we provide a linear-time recognition algorithm. For simply-connected cross-sections (i.e. the cross-section is empty, a point, a line-segment or a simple polygon), we derive an O(n²) time recognition algorithm to determine if a direction exists.

We then study variations of monotonicity in 2-dimensions, i.e. for simple polygons. Given a simple n-vertex polygon P, we can determine whether or not a line ℓ can be swept over P in a continuous manner but with varying direction, such that any position of ℓ intersects P in at most two edges. We study two variants of the problem: one where the line is allowed to sweep over a portion of the polygon multiple times and one where it can sweep any portion of the polygon only once. Although the latter problem is slightly more complicated than the former since the line movements are restricted, our solutions to both problems run in O(n²) time.

In this paper, we characterize the monoid of endomorphisms of the semigroup of all monotone full transformations of a finite chain, as well as the monoids of endomorphisms of the semigroup of all monotone partial transformations and of the semigroup of all monotone partial permutations of a finite chain.

The authors study homogenization of some nonlinear partial differential equations of the form -div (a(hx, h²x, Du_h)) = f, where a is periodic in the first two arguments and monotone in the third. In particular the case where a satisfies degenerated structure conditions is studied. It is proved that u_h converges weakly in to the unique solution of a limit problem as h → ∞. Moreover, explicit expressions for the limit problem are obtained.

Let $h:A\to A$ and $𝜀$ be a partial order on $A$. We deal with properties of oriented graphs which correspond to the algebra $(A,h)$ in the case that $h$ is monotone with respect to $𝜀$. We derive that every mono-unary algebra except connected one with a cycle of odd length has the property that there exists a nontrivial partial order such that $(A,h)$ is monotone with respect to it. All mono-unary algebras such that there exists a linear order such that $h$ is monotone with respect to this order will be described; if the number of components of $(A,h)$ is infinite, then the number of such orders is equal to the cardinality of the power set of $A$.

The authors study homogenization of some nonlinear partial differential equations of the form -div (a (hx, h²x, Du_h))= f, where a is periodic in the first two arguments and monotone in the third. In particular the case where a satisfies degenerated structure conditions is studied. It is proved that u_h converges weakly in to the unique solution of a limit problem as h → ∞. Moreover, explicit expressions for the limit problem are obtained.

In the estimation of distributions with time-to-event data, it is often natural to impose shape and smoothness constraints on the hazard function. Systems that fail because of wearing out might be assumed to have monotone hazard, or perhaps monotone-convex. Organ transplant failures are often assumed to have convex or bathtub-shaped hazard function. In this paper we present estimates that maximize the likelihood over a set of shape-restricted regression splines. Right censoring is a simple extension. The methods are applied to real and simulated data sets to illustrate their properties and to compare with existing nonparametric estimators.