Studies On Algorithms For Nonconvex Optimization Problems With Discrete Structures

Nonconvex optimization problem with discrete constraint is an important class of optimization problem. It has many applications in real-word, such as financial optimization, network and transportation problem, signal processing and compressed sensing, and so on. Due to the combinational property of the problem, the feasible region of such problem is in general nonconvex, and thus the problem is NP-hard. Therefore, studying solutions methods for this kind of problems not only has important significance, but also has challenge extremely. Great developments have been obtained in the theory and algorithm of this kind of problem with the development of optimization techniques, but there also exist some drawbacks in these algorithms, such as larger computing cost and lower solving efficiency, and thus these methods are only suitable for small to medium size problems. Based on the exited theories and algorithms, we proposed some new effective methods for some special nonconvex optimization problems with discrete structures. The main contents of this thesis are as follows.In Chapter 1, we introduce briefly the research background of the nonconvex optimization problems with discrete structures, and give an introduction for the problems investigated in this thesis. The results and contributions of this thesis are also given in this Chapter. We give a review in detail for three classes of special nonconvex optimization problems with discrete structures in Chapter 2.In Chapter 3, we investigate the method for finding sparse solutions to gen-eral convex program. Finding sparse solutions of optimization problems are often encountered in real-world applications, especially when the number of nonzero entries in the decision variables has to be controlled. We present a successive con-vex approximation method for solving the regularization formulation of sparse convex programs. This method is based on D.C. approximation of the (?)0 function and generates a sequence of approximate solutions via solving convex subprob-lems successively. We prove the convergence of the method to a KKT point of the approximate regularization problem. A piece wise linear D.C. approximation to the  regularization term is also derived via an (?)1 exact penalty function of a mixed-integer program reformulation. We report computational results of the method using different D.C. approximations for test problems from limited diver-sified mean-variance portfolio selection. Our numerical results suggest that the proposed method is promising in finding sparse solutions of convex programs.In Chapter 4, we consider a probability-constrained optimization problem, where the random variables follow finite discrete distributions. The problem is in general nonconvex and can be reformulated as a mixed-integer program. By exploiting the special structure of the probabilistic constraint, we propose an alternating direction method for finding approximative optimal solutions of this problem. At each iteration, this method solves a convex quadratic program-ming subproblem and a 0-1 knapsack subproblem alternately. In the end, we establish the convergence of the method to a first-order stationary point under certain mild conditions, and preliminary computational results are reported for VaR-constrained portfolio selection problems and chance-constrained transporta-tion problems. Numerical results show that the proposed method is promising for finding solutions of good quality in reasonable time and compares favorably with CPLEX and other existing approximation methods, especially for large-size problems.In Chapter 5, we study the problem of asset allocation under the Basel Ac-cord risk measures. Financial institutions are currently required to meet more stringent capital requirements than they were before the recent financial crisis. The significant increase in capital requirements renders it necessary for banks to take into account the constraint of capital requirement when they make asset al-location decisions. In this Chapter, we propose a new asset allocation model that incorporates the regulatory capital requirements under both the Basel 2.5 Accord, which includes the combination of 120 VaRs, and the Basel III Accord, which in-cludes the combination of 60 CVaRs. We propose an unified algorithm based on the alternating direction augmented Lagrangian method to solve the model, we also establish the first-order optimality of the limit points of the sequence gener-ated by the algorithm under some mild conditions. Numerical experiments show that the algorithm compares favorably with other existed methods, especially in cases in which the model is non-convex.