Structure Algorithms for Partially Ordered Isotonic Regression

Abstract

An algorithm for isotonic regression is called a structure algorithm if it searches for a “solution partition”—that is, a class of sets on each of which the isotonic regression is a constant. We discuss structure algorithms for partially ordered isotonic regression. In this article we provide a new class of structure algorithms called the isotonic block class (IBC) type algorithms. One of these is called the isotonic block class with recursion method (IBCR) algorithm, which works for partially ordered isotonic regression. It is a generalization of the pooled adjacent violators algorithm and is simpler than the min-max algorithm. We also give a polynomial time algorithm—the isotonic block class with stratification (IBCS) algorithm for matrix-ordered isotonic regression. We demonstrate the efficiency of our IBCR algorithm by using simulation to estimate the relative frequencies of the numbers of level sets of isotonic regressions on certain two-dimensional grids with the matrix order.     

Lipschitz continuous dynamic programming with discount II

We construct an alternative theoretical framework for stochastic dynamic programming which allows us to replace concavity assumptions with more flexible Lipschitz continuous assumptions. This framework allows us to prove that the value function of stochastic dynamic programming problems with discount is Lipschitz continuous in the presence of nonconcavities in the data of the problem. Our method allows us to treat problems with noninterior optimal paths. We also describe a discretization algorithm for the numerical computation of the value function, and we obtain the rate of convergence of this algorithm.     

SINGLE PROJECTION ALGORITHM FOR VARIATIONAL INEQUALITIES IN BANACH SPACES WITH APPLICATION TO CONTACT PROBLEM

We study the single projection algorithm of Tseng for solving a variational inequality problem in a 2-uniformly convex Banach space. The underline cost function of the variational inequality is assumed to be monotone and Lipschitz continuous. A weak convergence result is obtained under reasonable assumptions on the variable step-sizes. We also give the strong convergence result for when the underline cost function is strongly monotone and Lipchitz continuous. For this strong convergence case, the proposed method does not require prior knowledge of the modulus of strong monotonicity and the Lipschitz constant of the cost function as input parameters, rather, the variable step-sizes are diminishing and non-summable. The asymptotic estimate of the convergence rate for the strong convergence case is also given. For completeness, we give another strong convergence result using the idea of Halpern's iteration when the cost function is monotone and Lipschitz continuous and the variable step-sizes are bounded by the inverse of the Lipschitz constant of the cost function.Finally, we give an example of a contact problem where our proposed method can be applied.     

Incrementally Updated Gradient Methods for Constrained and Regularized Optimization

We consider incrementally updated gradient methods for minimizing the sum of smooth functions and a convex function. This method can use a (sufficiently small) constant stepsize or, more practically, an adaptive stepsize that is decreased whenever sufficient progress is not made. We show that if the gradients of the smooth functions are Lipschitz continuous on the space of n-dimensional real column vectors or the gradients of the smooth functions are bounded and Lipschitz continuous over a certain level set and the convex function is Lipschitz continuous on its domain, then every cluster point of the iterates generated by the method is a stationary point. If in addition a local Lipschitz error bound assumption holds, then the method is linearly convergent.     

Lipschitz stability estimate in the inverse Robin problem for the Stokes system

We are interested in the inverse problem of recovering a Robin coefficient defined on some non-accessible part of the boundary from available data on another part of the boundary in the non-stationary Stokes system. We prove a Lipschitz stability estimate under the a priori assumption that the Robin coefficient lives in some compact and convex subset of a finite dimensional vectorial subspace of the set of continuous functions. To do so, we use a theorem proved by L. Bourgeois and which establishes Lipschitz stability estimates for a class of inverse problems in an abstract framework.     

An inertial subgradient-type method for solving single-valued variational inequalities and fixed point problems

In this paper, we introduce an inertial subgradient-type algorithm to find the common element of fixed point set of a family of nonexpansive mappings and the solution set of the single-valued variational inequality problem. Under the assumption that the mapping is monotone and Lipschitz continuous, we show that the sequence generated by our algorithm converges strongly to some common element of the fixed set and the solution set. Moreover, preliminary numerical experiments are also reported.     

On the strong convergence of a projection-based algorithm in Hilbert spaces

In this paper, we introduce a new projection-based algorithm for solving variational inequality problems with a Lipschitz continuous pseudo-monotone mapping in Hilbert spaces. We prove a strong convergence of the generated sequences. The numerical behaviors of the proposed algorithm on test problems are illustrated and compared with previously known algorithms.     

Continuous functions with impermeable graphs

We construct a Hölder continuous function on the unit interval which coincides in uncountably (in fact continuum) many points with every function of total variation smaller than 1 passing through the origin. We conclude that this function has impermeable graph—one of the key concepts introduced in this paper—and we present further examples of functions both with permeable and impermeable graphs. Moreover, we show that typical (in the sense of Baire category) continuous functions have permeable graphs. The first example function is subsequently used to construct an example of a continuous function on the plane which is intrinsically Lipschitz continuous on the complement of the graph of a Hölder continuous function with impermeable graph, but which is not Lipschitz continuous on the plane. As another main result, we construct a continuous function on the unit interval which coincides in a set of Hausdorff dimension 1 with every function of total variation smaller than 1 which passes through the origin.     

强奇异积分算子的多线性交换子的Sharp极大函数估计和连续性

本文对由强奇异积分算子和加权Lipschitz函数生成的多线性交换子证明了其sharp极大函数估计,作为应用,得到了该多线性交换子的连续性.     

A differential operator and weak topology for Lipschitz maps

We show that the Scott topology induces a topology for real-valued Lipschitz maps on Banach spaces which we call the L-topology. It is the weakest topology with respect to which the L-derivative operator, as a second order functional which maps the space of Lipschitz functions into the function space of non-empty weak^∗ compact and convex valued maps equipped with the Scott topology, is continuous. For finite dimensional Euclidean spaces, where the L-derivative and the Clarke gradient coincide, we provide a simple characterization of the basic open subsets of the L-topology. We use this to verify that the L-topology is strictly coarser than the well-known Lipschitz norm topology. A complete metric on Lipschitz maps is constructed that is induced by the Hausdorff distance, providing a topology that is strictly finer than the L-topology but strictly coarser than the Lipschitz norm topology. We then develop a fundamental theorem of calculus of second order in finite dimensions showing that the continuous integral operator from the continuous Scott domain of non-empty convex and compact valued functions to the continuous Scott domain of ties is inverse to the continuous operator induced by the L-derivative. We finally show that in dimension one the L-derivative operator is a computable functional.     

A characterization of the blow-up time for the solution of a conservation law in several space variable

We derive a necessary and sufficient condition on the L^∞ Cauchy data for a conservation law in several space variables under which the solution will be locally Lipschitz continuous up to time T . The largesf such T is therefore the “blow-up” time. Roughly, our condition is that the data can be approximated by smoother functions satisfying uniformly a certain estimate. We present an example which shows that the existence of the approximations is crucial: it is not sufficient that the data itself satisfy this estimate.     

Optimal subgradient algorithms for large-scale convex optimization in simple domains

This paper describes two optimal subgradient algorithms for solving structured large-scale convex constrained optimization. More specifically, the first algorithm is optimal for smooth problems with Lipschitz continuous gradients and for Lipschitz continuous nonsmooth problems, and the second algorithm is optimal for Lipschitz continuous nonsmooth problems. In addition, we consider two classes of problems: (i) a convex objective with a simple closed convex domain, where the orthogonal projection onto this feasible domain is efficiently available; and (ii) a convex objective with a simple convex functional constraint. If we equip our algorithms with an appropriate prox-function, then the associated subproblem can be solved either in a closed form or by a simple iterative scheme, which is especially important for large-scale problems. We report numerical results for some applications to show the efficiency of the proposed schemes.     

最小化三个凸函数之和的一个简单原始-对偶算法

提出一个简单的原始-对偶算法求解三个凸函数之和的最小化问题, 其中目标函数包含有梯度李普希兹连续的光滑函数, 非光滑函数和含有复合算子的非光滑函数. 在新方法中, 对偶变量迭代使用预估-矫正的方案. 分析了算法的收敛性和收敛速率. 最后, 数值实验说明了算法的有效性.     

奇异积分交换子在加权Herz型Hardy空间上的有界性质

T_b表示由加权Lipschitz函数b与Calderon-Zygmund奇异积分算子T生成的交换子.研究了T_b在加权Herz型Hardy空间上的有界性质,并在端点处证明了交换子是从加权Herz型Hardy空间到加权弱Herz空间的有界算子.     

Endpoint estimates for Marcinkiewicz integrals on weighted weak hardy spaces

In this paper, we obtain the(W H1ω, W L1ω) type estimate for the Marcinkiewicz integral and the(W H1 b,ω, W L1ω) type estimate for the commutator generated by a BMO function and the Marcinkiewicz integral, where the kernel satisfies a certain logarithmic type Lipschitz condition.     

Quasi‐Lipschitz condition in potential theory

The velocity of an incompressible flow in a bounded three‐dimensional domain is represented by its vorticity with the help of an apparently new representation formula. Using this formula we prove a quasi‐Lipschitz estimate for in dependence of the supremum norm of . Our quasi‐Lipschitz bound extends to the case where is represented by any continuous ≠ rot     

A MODIFIED LEVENBERG-MARQUARDT ALGORITHM FOR SINGULAR SYSTEM OF NONLINEAR EQUATIONS

Based on the work of paper,we propose a modified Levenberg-Marquardt algoithm for solving singular system of nonlinear equations F(x)=0,where F(x):R^n→R^n is continuously differentiable and F‘(x)is Lipschitz continuous.The algorithm is equivalent to a trust region algorithm in some sense,and the global convergence result is given.The sequence generated by the algorithm converges to the solution quadratically,if ||F(x)||2 provides a local error bound for the system of nonlinear equations.Numerical results show that the algorithm performs well.     

Approximation by <Emphasis Type="Italic">q</Emphasis> Baskakov Beta operators

In the present paper we introduce the q analogue of the Baskakov Beta operators.We establish some direct results in the polynomial weighted space of continuous functions defined on the interval [0,∞) .Then we obtain point-wise estimate,using the Lipschitz type maximal function.     

Peaceman–Rachford splitting for a class of nonconvex optimization problems

We study the applicability of the Peaceman–Rachford (PR) splitting method for solving nonconvex optimization problems. When applied to minimizing the sum of a strongly convex Lipschitz differentiable function and a proper closed function, we show that if the strongly convex function has a large enough strong convexity modulus and the step-size parameter is chosen below a threshold that is computable, then any cluster point of the sequence generated, if exists, will give a stationary point of the optimization problem. We also give sufficient conditions guaranteeing boundedness of the sequence generated. We then discuss one way to split the objective so that the proposed method can be suitably applied to solving optimization problems with a coercive objective that is the sum of a (not necessarily strongly) convex Lipschitz differentiable function and a proper closed function; this setting covers a large class of nonconvex feasibility problems and constrained least squares problems. Finally, we illustrate the proposed algorithm numerically.     

Analysis of direct searches for discontinuous functions

It is known that the Clarke generalized directional derivative is nonnegative along the limit directions generated by directional direct-search methods at a limit point of certain subsequences of unsuccessful iterates, if the function being minimized is Lipschitz continuous near the limit point. In this paper we generalize this result for discontinuous functions using Rockafellar generalized directional derivatives (upper subderivatives). We show that Rockafellar derivatives are also nonnegative along the limit directions of those subsequences of unsuccessful iterates when the function values converge to the function value at the limit point. This result is obtained assuming that the function is directionally Lipschitz with respect to the limit direction. It is also possible under appropriate conditions to establish more insightful results by showing that the sequence of points generated by these methods eventually approaches the limit point along the locally best branch or step function (when the number of steps is equal to two). The results of this paper are presented for constrained optimization and illustrated numerically.