Joint chance-constrained optimization problems under discrete distributions arise frequently in financial management and business operations. These problems can be reformulated as mixed-integer programs. The size of reformulated integer programs is usually very large even though the original problem is of medium size. This paper studies an augmented Lagrangian decomposition method for finding high-quality feasible solutions of complex optimization problems, including nonconvex chance-constrained problems. Different from the current augmented Lagrangian approaches, the proposed method allows randomness to appear in both the left-hand-side matrix and the right-hand-side vector of the chance constraint. In addition, the proposed method only requires solving a convex subproblem and a 0-1 knapsack subproblem at each iteration. Based on the special structure of the chance constraint, the 0-1 knapsack problem can be computed in quasi-linear time, which keeps the computation for discrete optimization subproblems at a relatively low level. The convergence of the method to a first-order stationary point is established under certain mild conditions. Numerical results are presented in comparison with a set of existing methods in the literature for various real-world models. It is observed that the proposed method compares favorably in terms of the quality of the best feasible solution obtained within a certain time for large-size problems, particularly when the objective function of the problem is nonconvex or the left-hand-side matrix of the constraints is random.

We study perspective reformulations (PRs) of semicontinuous quadratically constrained quadratic programs (SQCQPs) in this paper. Based on perspective functions, we first propose a class of PRs for SQCQPs and discuss how to find the best PR in this class via strong duality and lifting techniques. We then study the properties of the PR class and relate them to alternative formulations that are used to derive lower bounds for SQCQPs. Finally, we embed the PR bounds in branch-and-bound algorithms and conduct computational experiments to illustrate the effectiveness of the proposed approach.

We consider in this paper quadratic programming problems with cardinality and minimum threshold constraints that arise naturally in various real-world applications such as portfolio selection and subset selection in regression. This class of problems can be formulated as mixed-integer 0-1 quadratic programs. We propose a new semidefinite program (SDP) approach for computing the “best” diagonal decomposition that gives the tightest continuous relaxation of the perspective reformulation of the problem. We also give an alternative way of deriving the perspective reformulation by applying a special Lagrangian decomposition scheme to the diagonal decomposition of the problem. This derivation can be viewed as a “dual” method to the convexification method employing the perspective function on semicontinuous variables. Computational results show that the proposed SDP approach can be advantageous for improving the performance of mixed-integer quadratic programming solvers when applied to the perspective reformulations of the problem.