Study On Algorithms And Applications For Several Conic Programming Problems

Second-order cone programming, copositive cone programming and doubly nonneg-ative cone programming are three important classes of optimization problems, among which second-order cone programming belongs to symmetric conic programming, eopos-itive cone programming and doubly nonnegative cone programming are both asymmetric conic programming. Since the special characteristics of these conic programming, they have widely applications in the real world. For example, artificial intelligence, inter-net of things, data mining, portfolio selection, dynamical systems and control, and so on. Moreover, copositive cone programming includes many important and challenging NP-hard problems in the areas of combinatorial optimization, such as stability number of a graph, quadratic-assignment, maximum clique, etc. Therefore, the studies on al-gorithms and practical applications for these three kinds of special conic programming have important theoretical significance and practical value.Based on the comprehensive understanding of the research progress for second-order cone programming and copositive cone programming as well as doubly nonnegative cone programming, this thesis aims to investigate the algorithms and applications for these three types of conic programming. The main contributions of the thesis are as follows:◣In Chapter2, we study a class of nonconvex quadratic programming problems with second-order cone constraint. First, according to the characteristics of the second-order cone constraint, the original problem is equivalently reformulated as a quadratically constrained quadratic programming problem. By using the lifting technique and the linear conic duality theory, the latter problem is converted into an equivalent linear conic programming problem, where the constraint cone can be inner approximated by a summation of positive seniideh’nite cone and the cone of special one. Then, a suf-ficient global optimization condition is developed for the original problem in terms of the relationship between the optima] solution of linear conic programming problem and the KKT solution of quadratically constrained quadratic; programming problem. Based on this condition, an algorithm for solving the original problem is presented. Theo-retically, the proposed algorithm which provides either a global optimal solution or a lower bound for the original problem. Finally, we test some elementary examples. The numerical results show that the proposed algorithm can effectively obtain the global optimal solutions or the tighter bounds for the test examples.? Chapter3is devoted to studying a type of copositive cone programming prob-lems. Based on the definition of copositive matrices, another equivalent expression for copositive matrices is presented. Using this new expression for copositive matrices, the original problem is equivalently transformed into a semi-infinite programming problem. Employing the idea of discretization method for solving semi-infinite programming, a new discretization algorithm for solving the latter semi-infinite programming problem is proposed. Moreover, under some mild assumptions, this new algorithm posses the finite-step convergence.? In Chapter4, we discuss a kind of multiple objective quadratic programming prob-lems with linear and nonnegative constraints, which does not have a single solution that simultaneously minimizes each objective function in general. So seeking Pareto efficient solutions is the key to solve the original problem. Exploiting the technique of the linear weighted sum method, the original multiple objective quadratic programming problem is transformed into a single objective one. Such a problem is nonconvex and NP-hard in general. By using the techniques of lifting and doubly nonnegative cone relaxation, respectively, this single objective quadratic programming problem is relaxed to a com-putable convex doubly nonnegative cone programming problem. The optimal solutions of this computable convex problem are Pareto (weekly) efficient solutions for the origi-nal problem under some mild conditions. Moreover, the proposed method is tested with some random examples and practical portfolio selection example. The numerical results show that the proposed method is effective and promising.? Chapter5focuses on the relationship between the semidifinite cone relaxation and the doubly nonnegative cone relaxation for binary quadratic programming problem. Under some suitable assumptions, we prove that the doubly nonnegative relaxation for the original problem is equivalent to a new semidifinite cone relaxation with tighter bound. If the original problem reduces to the Max-Cut problem, the doubly nonnegative cone relaxation for it is equivalent to the standard semidifinite cone relaxation. If the original problem reduces to the Densest k-Subgraph problem, the doubly nonnegative cone relaxation is equivalent to a tighter semidifinite cone relaxation. Furthermore, some comparative numerical results are reported to show the efficiency of these relaxation problems, respectively.