Stochastic optimization has established itself as a major method to handle uncertainty in various optimization problems by modeling the uncertainty by a probability distribution over possible realizations. Traditionally, the main focus in stochastic optimization has been various stochastic mathematical programming (such as linear programming, convex programming). In recent years, there has been a surge of interest in stochastic combinatorial optimization problems from the theoretical computer science community. In this article, we survey some of the recent results on various stochastic versions of classical combinatorial optimization problems. Since most problems in this domain are NP-hard (or #P-hard, or even PSPACE-hard), we focus on the results which provide polynomial time approximation algorithms with provable approximation guarantees. Our discussions are centered around a few representative problems, such as stochastic knapsack, stochastic matching, multi-armed bandit etc. We use these examples to introduce several popular stochastic models, such as the fixed-set model, 2-stage stochastic optimization model, stochastic adaptive probing model etc, as well as some useful techniques for designing approximation algorithms for stochastic combinatorial optimization problems, including the linear programming relaxation approach, boosted sampling, content resolution schemes, Poisson approximation etc.We also provide some open research questions along the way. Our purpose is to provide readers a quick glimpse to the models, problems, and techniques in this area, and hopefully inspire new contributions .
We consider the online scheduling problem on two parallel machines with the Grade of Service (GoS) eligibility constraints. The jobs arrive over time, and the objective is to minimize the makespan. We develop a (1 + α)-competitive optimal algorithm, where α ≈ 0.555 is a solution of α3 − 2α2 − α + 1 = 0.
In this paper, we present a new adaptive trust-region method for solving nonlinear unconstrained optimization problems. More precisely, a trust-region radius based on a nonmonotone technique uses an approximation of Hessian which is adaptively chosen. We produce a suitable trust-region radius; preserve the global convergence under classical assumptions to the first-order critical points; improve the practical performance of the new algorithm compared to other exiting variants.Moreover, the quadratic convergence rate is established under suitable conditions. Computational results on the CUTEst test collection of unconstrained problems are presented to show the effectiveness of the proposed algorithm compared with some exiting methods.
We propose a two-phase-SQP (Sequential Quadratic Programming) algorithm for equality-constrained optimization problem. In this paper, an iteration process is developed, and at each iteration, two quadratic sub-problems are solved. It is proved that, under some suitable assumptions and without computing further higher-order derivatives, this iteration process achieves higher-order local convergence property in comparison to Newton-SQP scheme. Theoretical advantage and a note on l1 merit function associated to the method are provided.
In this paper, we propose a modified proximal gradient method for solving a class of nonsmooth convex optimization problems, which arise in many contemporarystatistical and signal processing applications. The proposed method adopts a new scheme to construct the descent direction based on the proximal gradient method. It is proven that the modified proximal gradient method is Q-linearly convergent without the assumption of the strong convexity of the objective function. Some numerical experiments have been conducted to evaluate the proposed method eventually.
We study the computational complexities of three problems on multi-agent scheduling on a single machine. Among the three problems, the computational complexities of the first two problems were still open and the last problem was shown to be unary NP-hard in the literature. We show in this paper that the first two problems are unary NP-hard. We also show that the unary NP-hardness proof for the last problem in the literature is invalid, and so, the exact complexity of the problem is still open.
Linear programming is the core problem of various operational research problems. The dominant approaches for linear programming are simplex and interior point methods. In this paper, we showthat the alternating direction method of multipliers (ADMM), which was proposed long time ago while recently found more and more applications in a broad spectrum of areas, can also be easily used to solve the canonical linear programming model. The resulting per-iteration complexity is O(mn) where m is the constraint number and n the variable dimension. At each iteration, there are m subproblems that are eligible for parallel computation; each requiring only O(n) flops. There is no inner iteration as well.We thus introduce the newADMMapproach to linear programming, which may inspire deeper research for more complicated scenarios with more sophisticated results.
In this paper, we consider a block-structured convex optimization model, where in the objective the block variables are nonseparable and they are further linearly coupled in the constraint. For the 2-block case, we propose a number of first-order algorithms to solve this model. First, the alternating direction method of multipliers (ADMM) is extended, assuming that it is easy to optimize the augmented Lagrangian function with one block of variables at each time while fixing the other block. We prove that O(1/t) iteration complexity bound holds under suitable conditions, where t is the number of iterations. If the subroutines of the ADMM cannot be implemented, then we propose new alternative algorithms to be called alternating proximal gradient method of multipliers, alternating gradient projection method of multipliers, and the hybrids thereof. Under suitable conditions, the O(1/t) iteration complexity bound is shown to hold for all the newly proposed algorithms. Finally, we extend the analysis for the ADMM to the general multi-block case.
The logarithmic quadratic proximal (LQP) regularization is a popular and powerful proximal regularization technique for solving monotone variational inequalities with nonnegative constraints. In this paper,we propose an implementable two-step method for solving structured variational inequality problems by combining LQP regularization and projection method. The proposed algorithm consists of two parts.The first step generates a pair of predictors via inexactly solving a system of nonlinear equations. Then, the second step updates the iterate via a simple correction step. We establish the global convergence of the new method under mild assumptions. To improve the numerical performance of our new method, we further present a self-adaptive version and implement it to solve a traffic equilibrium problem. The numerical results further demonstrate the efficiency of the proposed method.
Over past decades, deceptive counterfeits which cannot be recognized by ordinary consumers when purchasing, such as counterfeit cosmetics, have posed serious threats on consumers’ health and safety, and resulted in huge economic loss and inestimable brand damages to the genuine goods at the same time. Thus, how to effectively control and eliminate deceptive counterfeits in the market has become a critical problem to the local government. One of the principal challenges in combating the cheating action for the government is how to enhance the enforcement of relative quality inspection agencies like industrial administration office (IAO). In this paper,we formulate a two-stage counterfeit product model with a fixed checking rate from IAO and a penalty for holding counterfeits. Tominimize the total expected cost over two stages,the retailer adopts optimal ordering policies which are correlated with the checking rate and penalty. Under certain circumstances, we find that the optimal expected cost function for the retailer is first-order continuous and convex. The optimal ordering policy in stage two depends closely on the inventory level after the first sales period. When the checking rate in stage one falls into a certain range, the optimal ordering policy for the retailer at each stage is to order both kinds of products. Knowing the retailer’s optimal ordering policy at each stage, IAO can modify the checking rate accordingly to keep the ratio of deceptive counterfeits on the market under a certain level.
Using Cholesky factorization, the dual face algorithm was described for solving standard Linear programming (LP) problems, as it would not be very suitable for sparse computations. To dodge this drawback, this paper presents a variant using Gauss-Jordan elimination for solving bounded-variable LP problems.
Bond portfolio immunization is a classical issue in finance. Since Macaulay gave the concept of duration in 1938, many scholars proposed different kinds of duration immunization models. In the literature of bond portfolio immunization using multifactor model, to the best of our knowledge, researchers only use the first-order immunization, which is usually called as duration immunization, and no one has considered second-order effects in immunization, which is well known as “convexity” in the case of single-factor model. In this paper, we introduce the second-order information associated with multifactor model into bond portfolio immunization and reformulate the corresponding problems as tractable semidefinite programs. Both simulation analysis and empirical study show that the second-order immunization strategies exhibit more accurate approximation to the value change of bonds and thus result in better immunization performance.
Based on the idea of maximum determinant positive definite matrix completion, Yamashita (Math Prog 115(1):1–30, 2008) proposed a new sparse quasi-Newton update, called MCQN, for unconstrained optimization problems with sparse Hessian structures. In exchange of the relaxation of the secant equation, the MCQN update avoids solving difficult subproblems and overcomes the ill-conditioning of approximate Hessian matrices. However, local and superlinear convergence results were only established for the MCQN update with the DFP method. In this paper, we extend the convergence result to the MCQN update with the whole Broyden’s convex family. Numerical results are also reported, which suggest some efficient ways of choosing the parameter in the MCQN update the Broyden’s family.
Joint probability function refers to the probability function that requires multiple conditions to satisfy simultaneously. It appears naturally in chanceconstrained programs. In this paper, we derive closed-form expressions of the gradient and Hessian of joint probability functions and develop Monte Carlo estimators of them. We then design a Monte Carlo algorithm, based on these estimators, to solve chance-constrained programs. Our numerical study shows that the algorithm works well, especially only with the gradient estimators.
