No abstract uploaded!

This paper focuses on pricing and vertical cooperative advertising decisions in a two-tier supply chain. Using a Stackelberg game model where the manufacturer acts as the game leader and the retailer acts as the game follower, we obtain closed-form equilibrium solution and explicitly show how pricing and advertising decisions are made. When market demand decreases exponentially with respect to the retail price and increases with respect to national and local advertising expenditures in an additive way, the manufacturer benefits from providing percentage reimbursement for the retailer’s local advertising expenditure when demand price elasticity is large enough. Whether the manufacturer benefits from cooperative advertising is also closely related to supply chain member’s relative advertising efficiency. In the decision for adopting coop advertising strategy, it is critical for the manufacturer to identify how market demand depends on national and local advertisements. The findings from this research can enhance our understanding of cooperative advertising decisions in a two-tier supply chain with price-dependent demand.

Finding a fixed point to a nonexpansive operator, i.e., x = Tx, abstracts many problems in numerical linear algebra, optimization, and other areas of data sciences. To solve xed- point problems, we propose ARock, an algorithmic framework in which multiple agents (machines, processors, or cores) update x in an asynchronous parallel fashion. Asynchrony is crucial to parallel computing since it reduces synchronization wait, relaxes communication bottleneck, and thus speeds up computing significantly. At each step of ARock, an agent updates a randomly selected coordinate xi based on possibly out-of-date information on x. The agents share x through either global memory or communication. If writing xi is atomic, the agents can read and write x without memory locks. We prove that if the nonexpansive operator T has a fixed point, then with probability one, ARock generates a sequence that converges to a fixed point of T. Our conditions on T and step sizes are weaker than comparable work. Linear convergence is obtained under suitable assumptions. We propose special cases of ARock for linear systems, convex optimization, machine learning, as well as distributed and decentralized consensus problems. Numerical experiments of solving sparse logistic regression problems are presented.

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!

No abstract uploaded!

In this paper, we analyze the minimization of seminorms ∥L · ∥ on R^n under the constraint of a bounded I-divergence D(b,H·) for rather general linear operators H and L. The I-divergence is also known as Kullback–Leibler divergence and appears in many models in imaging science, in particular when dealing with Poisson data but also in the case of multiplicative Gamma noise. Often H represents, e.g., a linear blur operator and L is some discrete derivative or frame analysis operator. A central part of this paper consists in proving relations between the parameters of I-divergence constrained and penalized problems. To solve the I-divergence constrained problem, we consider various first-order primal–dual algorithms which reduce the problem to the solution of certain proximal minimization problems in each iteration step. One of these proximation problems is an I-divergence constrained least-squares problem which can be solved based on Morozov’s discrepancy principle by a Newton method. We prove that these algorithms produce not only a sequence of vectors which converges to a minimizer of the constrained problem but also a sequence of parameters which converges to a regularization parameter so that the corresponding penalized problem has the same solution. Furthermore, we derive a rule for automatically setting the constraint parameter for data corrupted by multiplicative Gamma noise. The performance of the various algorithms is finally demonstrated for different image restoration tasks both for images corrupted by Poisson noise and multiplicative Gamma noise.

No abstract uploaded!

No abstract uploaded!

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.

This paper studies the capacity allocation game between duopolistic airlines which could offer callable products. Previous literature has shown that callable products provide a riskless source of additional rev- enue for a monopolistic airline. We examine the impact of the introduction of callable products on the revenues and the booking limits of duopolistic airlines. The analytical results demonstrate that, when there is no spill of low-fare customers, offering callable products is a dominant strategy of both airlines and provides Pareto gains to both airlines. When customers of both fare classes spill, offering callable products is no longer a dominant strategy and may harm the revenues of the airlines. Numerical ex- amples demonstrate that whether the two airlines offer callable products and whether offering callable products is beneficial to the two airlines mainly depends on their loads and capacities. Specifically, when the difference between the loads of the airlines is large, the loads of the airlines play the most important role. When the difference between the loads of the airlines is small, the capacities of the airlines play the most important role. Moreover, numerical examples show that the booking limits of the two airlines in the case with callable products are always higher than those in the case without callable products.

We introduce a parallel machine scheduling problem in which the processing times of jobs are not given in advance but are determined by a system of linear constraints. The objective is to minimize the makespan, i.e., the maximum job completion time among all feasible choices. This novel problem is motivated by various real-world application scenarios. We discuss the computational complexity and algorithms for various settings of this problem. In particular, we show that if there is only one machine with an arbitrary number of linear constraints, or there is an arbitrary number of machines with no more than two linear constraints, or both the number of machines and the number of linear constraints are fixed constants, then the problem is polynomial-time solvable via solving a series of linear programming problems. If both the number of machines and the number of constraints are inputs of the problem instance, then the problem is NP-Hard. We further propose several approximation algorithms for the latter case.

We study the averaging of fronts moving with positive oscillatory normal velocity, which is periodic in space and stationary ergodic in time. The problem can be formulated as the homogenization of coercive level set Hamilton-Jacobi equations with spatio-temporal oscillations. To overcome the difficulties due to the oscillations in time and the linear growth of the Hamiltonian, we first study the long time averaged behavior of the associated reachable sets using geometric arguments. The results are new for higher than one dimensions even in the space-time periodic setting.

We adapt the Douglas–Rachford (DR) splitting method to solve nonconvex feasibility problems by studying this method for a class of nonconvex optimization problem. While the convergence properties of the method for convex problems have been well studied, far less is known in the nonconvex setting. In this paper, for the direct adaptation of the method to minimize the sum of a proper closed function g and a smooth function f with a Lipschitz continuous gradient, we show that if the step-size parameter is smaller than a computable threshold and the sequence generated has a cluster point, then it gives a stationary point of the optimization problem. Convergence of the whole sequence and a local convergence rate are also established under the additional assumption that f and g are semi-algebraic. We also give simple sufficient conditions guaranteeing the boundedness of the sequence generated. We then apply our nonconvex DR splitting method to finding a point in the intersection of a closed convex set C and a general closed set D by minimizing the squared distance to C subject to D. We show that if either set is bounded and the step-size parameter is smaller than a computable threshold, then the sequence generated from the DR splitting method is actually bounded. Consequently, the sequence generated will have cluster points that are stationary for an optimization problem, and the whole sequence is convergent under an additional assumption that C and D are semi-algebraic. We achieve these results based on a new merit function constructed particularly for the DR splitting method. Our numerical results indicate that our DR splitting method usually outperforms the usual DR splitting method and the alternating projection method in finding a sparse solution of a linear system, in terms of both the solution quality and the number of iterations taken.

This paper focuses on coordinate update methods, which are useful for solving problems involving large or high-dimensional datasets. They decompose a problem into simple subproblems, where each updates one, or a small block of, variables while fixing others. These methods can deal with linear and nonlinear mappings, smooth and nonsmooth functions, as well as convex and nonconvex problems. In addition, they are easy to parallelize. The great performance of coordinate update methods depends on solving simple sub-problems. To derive simple subproblems for several new classes of applications, this paper systematically studies coordinate-friendly operators that perform low-cost coordinate updates. Based on the discovered coordinate friendly operators, as well as operator splitting techniques, we obtain new coordinate update algorithms for a variety of problems in machine learning, image processing, as well as sub-areas of optimization. Several problems are treated with coordinate update for the first time in history. The obtained algorithms are scalable to large instances through parallel and even asynchronous computing. We present numerical examples to illustrate how effective these algorithms are.

We consider the problem of minimizing the sum of a smooth function h with a bounded Hessian and a nonsmooth function. We assume that the latter function is a composition of a proper closed function P and a surjective linear map M. This problem is nonconvex in general and encompasses many important applications in engineering and machine learning. In this paper, we examined two types of splitting methods for solving this nonconvex optimization problem: the alternating direction method of multipliers and the proximal gradient algorithm. For the direct adaptation of the alternating direction method of multipliers, we show that if the penalty parameter is chosen sufficiently large and the sequence generated has a cluster point, then it gives a stationary point of the nonconvex problem. We also establish convergence of the whole sequence under an additional assumption that the functions h and P are semialgebraic. Furthermore, we give simple sufficient conditions to guarantee boundedness of the sequence generated. These conditions can be satisfied for a wide range of applications including the least squares problem with the 1/2 regularization. Finally, when M is the identity so that the proximal gradient algorithm can be efficiently applied, we show that any cluster point is stationary under a slightly more flexible constant step-size rule than what is known in the literature for a nonconvex h. We illustrate our theoretical finding with a variety of applications such as signal denoising and sparse optimisation problems.

No abstract uploaded!

No abstract uploaded!

The total variation (TV) model is attractive in that it is able to preserve sharp attributes in images. However, the restored images from TV-based methods do not usually stay in a given dynamic range, and hence projection is required to bring them back into the dynamic range for visual presentation or for storage in digital media. This will affect the accuracy of the restoration as the projected image will no longer be the minimizer of the given TV model. In this paper, we show that one can get much more accurate solutions by imposing box constraints on the TV models and solving the resulting constrained models. Our numerical results show that for some images where there are many pixels with values lying on the boundary of the dynamic range, the gain can be as great as 10.28 decibel in the peak signal-to-noise ratio. One traditional hindrance using the constrained model is that it is difficult to solve. However, in this paper, we propose using the alternating direction method of multipliers (ADMM) to solve the constrained models. This leads to a fast and convergent algorithm that is applicable for both Gaussian and impulse noise. Numerical results show that our ADMM algorithm is better than some state-of-the-art algorithms for unconstrained models in terms of both accuracy and robustness with respect to the regularization parameter.

No abstract uploaded!

We propose a variational approach to obtain superresolution images from multiple low-resolution frames extracted from video clips. First the displacement between the lowresolution frames and the reference frame are computed by an optical flow algorithm. Then a low-rank model is used to construct the reference frame in high-resolution by incorporating the information of the low-resolution frames. The model has two terms: a 2-norm data fidelity term and a nuclear-norm regularization term. Alternating direction method of multipliers is used to solve the model. Comparison of our methods with other models on synthetic and real video clips show that our resulting images are more accurate with less artifacts. It also provides much finer and discernable details.

The Mumford–Shah model is one of the most important image segmentation models and has been studied extensively in the last twenty years. In this paper, we propose a two-stage segmentation method based on the Mumford–Shah model. The first stage of our method is to find a smooth solution g to a convex variant of the Mumford–Shah model. Once g is obtained, then in the second stage the segmentation is done by thresholding g into different phases. The thresholds can be given by the users or can be obtained automatically using any clustering methods. Because of the convexity of the model, g can be solved efficiently by techniques like the split-Bregman algorithm or the Chambolle–Pock method. We prove that our method is convergent and that the solution g is always unique. In our method, there is no need to specify the number of segments K (K ≥ 2) before finding g. We can obtain any K-phase segmentations by choosing (K − 1) thresholds after g is found in the first stage, and in the second stage there is no need to recompute g if the thresholds are changed to reveal different segmentation features in the image. Experimental results show that our two-stage method performs better than many standard two-phase or multiphase segmentation methods for very general images, including antimass, tubular, MRI, noisy, and blurry images.

Adult stem cells, which exist throughout the body, multiply by cell division to replenish dying cells or to promote regeneration to repair damaged tissues. To perform these functions during the lifetime of organs or tissues, stem cells need to maintain their populations in a faithful distribution of their epigenetic states, which are suscepti- ble to stochastic fluctuations during each cell division, unexpected injury, and potential genetic mutations that occur during many cell divisions. However, it remains unclear how the three processes of differentiation, proliferation, and apoptosis in regulating stem cells collectively manage these challenging tasks. Here, without consid- ering molecular details, we propose a genetic optimal control model for adult stem cell regeneration that includes the three fundamental processes, along with cell division and adaptation based on differ- ential fitnesses of phenotypes. In the model, stem cells with a distri- bution of epigenetic states are required to maximize expected performance after each cell division. We show that heteroge- neous proliferation that depends on the epigenetic states of stem cells can improve the maintenance of stem cell distributions to create balanced populations. A control strategy during each cell division leads to a feedback mechanism involving heterogeneous proliferation that can accelerate regeneration with less fluctuation in the stem cell population. When mutation is allowed, apoptosis evolves to maximize the performance during homeostasis after multiple cell divisions. The overall results highlight the importance of cross-talk between genetic and epigenetic regulation and the performance objectives during homeostasis in shaping a desirable heterogeneous distribution of stem cells in epigenetic states.

This paper studies the convergence of the adaptively iterative thresholding (AIT) algorithm for compressed sensing. We first introduce a generalized restricted isometry property (gRIP). Then, we prove that the AIT algorithm converges to the original sparse solution at a linear rate under a certain gRIP condition in the noise free case. While in the noisy case, its convergence rate is also linear until attaining a certain error bound. Moreover, as by-products, we also provide some sufficient conditions for the convergence of the AIT algorithm based on the two well-known properties, i.e., the coherence property and the restricted isometry property (RIP), respectively. It should be pointed out that such two properties are special cases of gRIP. The solid improvements on the theoretical results are demonstrated and compared with the known results. Finally, we provide a series of simulations to verify the correctness of the theoretical assertions as well as the effectiveness of the AIT algorithm.

No abstract uploaded!