This paper considers regularized block multiconvex optimization, where the feasible set and objective function are generally nonconvex but convex in each block of variables. It also accepts nonconvex blocks and requires these blocks to be updated by proximal minimization. We review some interesting applications and propose a generalized block coordinate descent method. Under certain conditions, we show that any limit point satisfies the Nash equilibrium conditions. Furthermore, we establish global convergence and estimate the asymptotic convergence rate of the method by assuming a property based on the Kurdyka-Lojasiewicz inequality. The proposed algorithms are tested on nonnegative matrix and tensor factorization, as well as matrix and tensor recovery from incomplete observations. The tests include synthetic data and hyperspectral data, as well as image sets from the CBCL and ORL databases. Compared to the existing state-of-the-art algorithms, the proposed algorithms demonstrate superior performance in both speed and solution quality. The MATLAB code of nonnegative matrix/tensor decomposition and completion, along with a few demos, are accessible from the authors' homepages.

This paper studies the inventory management problem of dual channels operated by one vendor. Demands of dual channels are inventory-level-dependent.We propose a multi-period stochastic dynamic programming model which shows that under mild conditions, the myopic inventory policy is optimal for the infinite horizon problem. To investigate the importance of capturing demand dependency on inventory levels, we consider a heuristic where the vendor ignores demand dependency on inventory levels, and compare the optimal inventory levels with those recommended by the heuristic. Through numerical examples, we show that the vendor may order less for dual channels than those recommended by the heuristic, and the difference between the inventory levels in the two cases can be so large that the demand dependency on inventory levels cannot be neglected. In the end, we numerically examine the impact of different ways to treat unmet demand and obtain some managerial insights.

It is well known that the nonlinear filter has important applications in military, engineering and commercial industries. In this paper, we propose efficient and accurate numerical algorithms for the realization of the Yau-Yau method for solving nonlinear filtering problems by using finite difference schemes. The Yau-Yau method reduces the nonlinear filtering problem to the initial-value problem of Kolmogorov equations. We first solve this problem by the implicit Euler method, which is stable in most cases, but costly. Then, we propose a quasi-implicit Euler method which is feasible for acceleration by fast Fourier transformations. Furthermore, we propose a superposition technique which enables us to deal with the nonlinear filtering problem in an off-time process and thus, save a large amount of computational cost. Next, we prove that the numerical solutions of Kolmogorov equations by our schemes are always nonnegative in each iteration. Consequently, our iterative process preserves the probability density functions. In addition, we prove convergence of our schemes under some mild conditions. Numerical results show that the proposed algorithms are efficient and promising.

This paper is concerned with a mean-reversion trading rule. In contrast to most market models treated in the literature, the underlying market is solely determined by a two-state Markov chain. The major advantage of such Markov chain model is its striking simplicity and yet its capability of capturing various market movements. The purpose of this paper is to study an optimal trading rule under such a model. The objective of the problem under consideration is to nd a sequence stopping (buying and selling) times so as to maximize an expected return. Under some suitable conditions, explicit solutions to the associated HJ equations (variational inequalities) are obtained. The optimal stopping times are given in terms of a set of threshold levels. A verication theorem is provided to justify their optimality. Finally, a numerical example is provided to illustrate the results.

No abstract uploaded!

No abstract uploaded!

No abstract uploaded!

This paper studies the eect of risk-aversion in the competitive newsvendor game. Multiple newsvendors with risk-averse preferences face a random demand and the demand is allocated proportionally to their inventory levels. Each newsvendor aims to maximize his expected utility instead of his expected prot. Assuming a general form of risk-averse utility function, we prove that there exists a pure Nash equilibrium in this game, and it is also unique under certain conditions. We nd that the order quantity of each newsvendor is decreasing in the degree of risk-aversion and increasing in the initial wealth. Newsvendors with moderate preferences of risk-aversion make more prots compared with the risk-neutral situation. We also discuss the joint eect of risk-aversion and competition. If the eect of risk-aversion is strong enough to dominate the eect of competition, the total inventory level under competition will be lower than that under centralized decision-making.

Nonconvex optimization arises in many areas of computational science and engineering. However, most nonconvex optimization algorithms are only known to have local convergence or subsequence convergence properties. In this paper, we propose an algorithm for nonconvex optimization and establish its global convergence (of the whole sequence) to a critical point. In addition, we give its asymptotic convergence rate and numerically demonstrate its efficiency. In our algorithm, the variables of the underlying problem are either treated as one block or multiple disjoint blocks. It is assumed that each non-differentiable component of the objective function, or each constraint, applies only to one block of variables. The differentiable components of the objective function, however, can involve multiple blocks of variables together. Our algorithm updates one block of variables at a time by minimizing a certain prox-linear surrogate, along with an extrapolation to accelerate its convergence. The order of update can be either deterministically cyclic or randomly shuffled for each cycle. In fact, our convergence analysis only needs that each block be updated at least once in every fixed number of iterations. We show its global convergence (of the whole sequence) to a critical point under fairly loose conditions including, in particular, the Kurdyka–Łojasiewicz condition, which is satisfied by a broad class of nonconvex/nonsmooth applications. These results, of course, remain valid when the underlying problem is convex.We apply our convergence results to the coordinate descent iteration for non-convex regularized linear regression, as well as amodified rank-one residue iteration for nonnegative matrix factorization. We show that both applications have global convergence. Numerically,we tested our algorithm on nonnegative matrix and tensor factorization problems, where random shuffling clearly improves the chance to avoid low-quality local solutions.

In this paper, a brief introduction of the nonlinear filtering problems and a review of the quasi-implicit Euler method are presented. The major contribution of this paper is that we propose a nonnegativity-preserving algorithm of Yau-Yau method for solving high-dimensional nonlinear filtering problems by applying quasi-implicit Euler method with discrete sine transform. Furthermore, our algorithms are directly applicable on the compact difference schemes, so that the number of spatial points can be substantially reduced and retain the same accuracy. Numerical results indicate that the proposed algorithm is capable of solving up to six-dimensional nonlinear filtering problems efficiently and accurately.

In this paper, we study the Kurdyka–Łojasiewicz (KL) exponent, an important quantity for analyzing the convergence rate of first-order methods. Specifically, we develop various calculus rules to deduce the KL exponent of new (possibly nonconvex and nonsmooth) functions formed from functions with known KL exponents. In addition, we show that the well-studied Luo–Tseng error bound together with a mild assumption on the separation of stationary values implies that the KL exponent is 1/2 . The Luo–Tseng error bound is known to hold for a large class of concrete structured optimization problems, and thus we deduce the KL exponent of a large class of functions whose exponents were previously unknown. Building upon this and the calculus rules, we are then able to show that for many convex or nonconvex optimization models for applications such as sparse recovery, their objective function’s KL exponent is 1/2 . This includes the least squares problem with smoothly clipped absolute deviation regularization or minimax concave penalty regularization and the logistic regression problem with l_1 regularization. Since many existing local convergence rate analysis for first-order methods in the nonconvex scenario relies on the KL exponent,our results enable us to obtain explicit convergence rate for various first-order methods when they are applied to a large variety of practical optimization models. Finally, we further illustrate how our results can be applied to establishing local linear convergence of the proximal gradient algorithm and the inertial proximal algorithm with constant step sizes for some specific models that arise in sparse recovery.

It has been an open question whether the family of merit functions $\psi _p\(p> 1) $, the generalized Fischer-Burmeister (FB) merit function, associated to the second-order cone is smooth or not. In this paper we answer it partly, and show that \psi _p is smooth for \psi _p , and we provide the condition for its coerciveness. Numerical results are reported to illustrate the influence of \psi _p on the performance of the merit function method based on \psi _p .

In this paper, we establish sublinear and linear convergence of fixed point iterations generated by averaged operators in a Hilbert space. Our results are achieved under a bounded Holder regularity assumption which generalizes the well-known notion of bounded linear regularity. As an application of our results, we provide a convergence rate analysis for many important iterative methods in solving broad mathematical problems such as convex feasibility problems and variational inequality problems. These include Krasnoselskii–Mann iterations, the cyclic projection algorithm, forward-backward splitting and the Douglas–Rachford feasibility algorithm along with some variants. In the important case in which the underlying sets are convex sets described by convex polynomials in a finite dimensional space, we show that the Holder regularity properties are automatically satisfied, from which sublinear convergence follows.

No abstract uploaded!

This paper is concerned with an optimal strategy for simultaneously trading of a pair of stocks. The idea of pairs trading is to monitor their price movements and compare their relative strength over time. A pairs trade is triggered by their prices divergence and consists of a pair of positions to short the strong stock and to long the weak one. Such a strategy bets on the reversal of their price strengths. From the viewpoint of technical tractability, typical pairs-trading models usually assume a difference of the stock prices satisfies a mean-reversion equation. In this paper, we consider the optimal pairs-trading problem by allowing the stock prices to follow general geometric Brownian motions. The objective is to trade the pairs over time to maximize an overall return with a fixed commission cost for each transaction. The optimal policy is characterized by threshold curves obtained by solving the associated HJB equations. Numerical examples are included to demonstrate the dependence of our trading rules on various parameters and to illustrate how to implement the results in practice.

No abstract uploaded!

In this paper, we analyze the convergence of the alternating direction method of multipliers (ADMM) for minimizing a nonconvex and possibly nonsmooth objective function, φ(x0, . . . , x p, y), subject to coupled linear equality constraints. Our ADMM updates each of the primal variables x0, . . . , x p, y, followed by updating the dual variable.We separate the variable y from xi ’s as it has a special role in our analysis. The developed convergence guarantee covers a variety of nonconvex functions such as piecewise linear functions, lq quasi-norm, Schatten-q quasi-norm (0 < q < 1), minimax concave penalty (MCP), and smoothly clipped absolute deviation penalty. It also allows nonconvex constraints such as compact manifolds (e.g., spherical, Stiefel, and Grassman manifolds) and linear complementarity constraints. Also, the x0-block can be almost any lower semi-continuous function. By applying our analysis, we show, for the first time, that several ADMM algorithms applied to solve nonconvex models in statistical learning, optimization on manifold, and matrix decomposition are guaranteed to converge. Our results provide sufficient conditions for ADMM to converge on (convex or nonconvex) monotropic programs with three or more blocks, as they are special cases of our model. ADMM has been regarded as a variant to the augmented Lagrangian method (ALM). We present a simple example to illustrate how ADMM converges but ALM diverges with bounded penalty parameter β. Indicated by this example and other analysis in this paper, ADMM might be a better choice than ALM for some nonconvex nonsmooth problems, because ADMM is not only easier to implement, it is also more likely to converge for the concerned scenarios.

Motivated by big data applications, first-order methods have been extremely popular in recent years. However, naive gradient methods generally converge slowly. Hence, much efforts have been made to accelerate various first-order methods. This paper proposes two accelerated methods towards solving structured linearly constrained convex programming, for which we assume composite convex objective that is the sum of a differentiable function and a possibly nondifferentiable one. The first method is the accelerated linearized augmented Lagrangian method (LALM). At each update to the primal variable, it allows linearization to the differentiable function and also the augmented term, and thus it enables easy subproblems. Assuming merely convexity, we show that LALM owns O(1/t) convergence if parameters are kept fixed during all the iterations and can be accelerated to O(1/t^2) if the parameters are adapted, where t is the number of total iterations. The second method is the accelerated linearized alternating direction method of multipliers (LADMM). In addition to the composite convexity, it further assumes two-block structure on the objective. Different from classic ADMM, our method allows linearization to the objective and also augmented term to make the update simple. Assuming strong convexity on one block variable, we show that LADMM also enjoys O(1=t2) convergence with adaptive parameters. This result is a significant improvement over that in [Goldstein et. al, SIIMS'14], which requires strong convexity on both block variables and no linearization to the objective or augmented term. Numerical experiments are performed on quadratic programming, image denoising, and support vector machine. The proposed accelerated methods are compared to nonaccelerated ones and also existing accelerated methods. The results demonstrate the validness of acceleration and superior performance of the proposed methods over existing ones.

Kurdyka–Łojasiewicz (KL) exponent plays an important role in estimating the convergence rate of many contemporary first-order methods. In particular, a KL exponent of 1/2 for a suitable potential function is related to local linear convergence. Nevertheless, KL exponent is in general extremely hard to estimate. In this paper, we show under mild assumptions that KL exponent is preserved via inf-projection. Inf-projection is a fundamental operation that is ubiquitous when reformulating optimization problems via the lift-and-project approach. By studying its operation on KL exponent, we show that the KL exponent is 1/2 for several important convex optimization models, including some semidefinite-programming-representable functions and some functions that involve C2-cone reducible structures, under conditions such as strict complementarity. Our results are applicable to concrete optimization models such as group-fused Lasso and overlapping group Lasso. In addition, for nonconvex models, we show that the KL exponent of many difference-of-convex functions can be derived from that of their natural majorant functions, and the KL exponent of the Bregman envelope of a function is the same as that of the function itself. Finally, we estimate the KL exponent of the sum of the least squares function and the indicator function of the set of matrices of rank at most k.

We consider image deblurring problem in the presence of impulsive noise. It is known that \emph{total variation} (TV) regularization with L1-norm penalized data fitting (TVL1 for short) works reasonably well only when the level of impulsive noise is relatively low. For high level impulsive noise, TVL1 works poorly. The reason is that all data, both corrupted and noise free, are equally penalized in data fitting, leading to insurmountable difficulty in balancing regularization and data fitting. In this paper, we propose to combine TV regularization with nonconvex \emph{smoothly clipped absolute deviation} (SCAD) penalty for data fitting (TVSCAD for short). Our motivation is simply that data fitting should be enforced only when an observed data is not severely corrupted, while for those data more likely to be severely corrupted, less or even null penalization should be enforced. A \emph{difference of convex functions} algorithm is adopted to solve the nonconvex TVSCAD model, resulting in solving a sequence of TVL1-equivalent problems, each of which can then be solved efficiently by the alternating direction method of multipliers. Theoretically, we establish global convergence to a critical point of the nonconvex objective function. The R-linear and at-least-sublinear convergence rate results are derived for the cases of anisotropic and isotropic TV, respectively. Numerically, experimental results are given to show that the TVSCAD approach improves those of the TVL1 significantly, especially for cases with high level impulsive noise, and is comparable with the recently proposed iteratively corrected TVL1 method [\textit{Inverse Problems}, 32 (2016), pp.~085004].

Finding the maximum eigenvalue of a symmetric tensor is an important topic in tensor computation and numerical multilinear algebra. In this paper, we introduce a new class of structured tensors called W-tensors, which not only extends thewell-studied nonnegative tensors by allowing negative entries but also covers several important tensors arising naturally from spectral hypergraph theory.We then show that finding the maximum H-eigenvalue of an even-order symmetric W-tensor is equivalent to solving a structured semidefinite program and hence can be validated in polynomial time. This yields a highly efficient semidefinite program algorithm for computing themaximumH-eigenvalue of W-tensors and is based on a new structured sums-of-squares decomposition result for a nonnegative polynomial induced by W-tensors. Numerical experiments illustrate that the proposed algorithm can successfully find the maximum H-eigenvalue of W-tensors with dimension up to 10,000, subject to machine precision. As applications, we provide a polynomial time algorithm for computing the maximum H-eigenvalues of large-size Laplacian tensors of hyperstars and hypertrees, where the algorithm can be up to 13 times faster than the state-of-the-art numerical method introduced by Ng, Qi, and Zhou in 2009. Finally, we also show that the proposed algorithm can be used to test the copositivity of a multivariate form associated with symmetric extended Z-tensors,whose order may be even or odd.

No abstract uploaded!

No abstract uploaded!

The alternating direction method of multipliers (ADMM) is a popular and efficient first-order method that has recently found numerous applications, and the proximal ADMM is an important variant of it. The main contributions of this paper are the proposition and the analysis of a class of inertial proximal ADMMs, which unify the basic ideas of the inertial proximal point method and the proximal ADMM, for linearly constrained separable convex optimization. This class of methods are of inertial nature because at each iteration the proximal ADMM is applied to a point extrapolated at the current iterate in the direction of last movement. The recently proposed inertial primal-dual algorithm [A. Chambolle and T. Pock, On the ergodic convergence rates of a first-order primaldual algorithm, preprint, 2014, Algorithm 3] and the inertial linearized ADMM [C. Chen, S. Ma, and J. Yang, arXiv:1407.8238, eq. (3.23)] are covered as special cases. The proposed algorithmic framework is very general in the sense that the weighting matrices in the proximal terms are allowed to be only positive semidefinite, but not necessarily positive definite as required by existing methods of the same kind. By setting the two proximal terms to zero, we obtain an inertial variant of the classical ADMM, which is to the best of our knowledge new. We carry out a unified analysis for the entire class of methods under very mild assumptions. In particular, convergence, as well as asymptotic $o(1/\sqrt{k})$ and nonasymptotic $O(1/\sqrt{k})$ rates of convergence, are established for the best primal function value and feasibility residues, where k denotes the iteration counter. The global iterate convergence of the generated sequence is established under an additional assumption. We also present extensive experimental results on total variation–based image reconstruction problems to illustrate the profits gained by introducing the inertial extrapolation steps.

Frequentists' inference often delivers point estimators associated with condence intervals or sets for parameters of interest. Constructing the condence intervals or sets requires understanding the sampling distributions of the point estimators, which, in many but not all cases, are related to asymptotic Normal distributions ensured by central limit theorems. Although previous literature has established various forms of central limit theorems for statistical inference in super population models, we still need general and convenient forms of central limit theorems for some randomization-based causal analysis of experimental data, where the parameters of interests are functions of a nite population and randomness comes solely from the treatment assignment. We use central limit theorems for sample surveys and rank statistics to establish general forms of the nite population central limit theorems that are particularly useful for proving asymptotic distributions of randomization tests under the sharp null hypothesis of zero individual causal eects, and for obtaining the asymptotic repeated sampling distributions of the causal eect estimators. The new central limit theorems hold for general experimental designs with multiple treatment levels, multiple treatment factors and vector outcomes, and are immediately applicable for studying the asymptotic properties of many methods in causal inference, including instrumental variable, regression adjustment, rerandomization, clustered randomized experiments, and so on. Previously, the asymptotic properties of these problems are often based on heuristic arguments, which in fact rely on general forms of nite population central limit theorems that have not been established before. Our new theorems ll in this gap by providing more solid theoretical foundation for asymptotic randomization-based causal inference.