Duan Li

Successive Convex Approximations to Cardinality-Constrained Quadratic Programs: A DC Approach

  • Duan Li
  • Jie Sun
  • Xiaoling Sun
  • Xiaojin Zheng
    • Categories Global Optimization, Integer Programming, Nonlinear Optimization

    In this paper we consider a cardinality-constrained quadratic program that minimizes a convex quadratic function subject to a cardinality constraint and linear constraints. This class of problems has found many applications, including portfolio selection, subset selection and compressed sensing. We propose a successive convex approximation method for this class of problems in which the cardinality … Read more

    Reweighted $\ell_1hBcMinimization for Sparse Solutions to Underdetermined Linear Systems

  • Duan Li
  • Yun-Bin Zhao
    • Categories Basic Sciences Applications, Linear Programming, Nonsmooth Optimization Tags , , , , ,

    Numerical experiments have indicated that the reweighted $\ell_1$-minimization performs exceptionally well in locating sparse solutions of underdetermined linear systems of equations. Thus it is important to carry out a further investigation of this class of methods. In this paper, we point out that reweighted $\ell_1$-methods are intrinsically associated with the minimization of the so-called merit … Read more

    Improving the Performance of MIQP Solvers for Quadratic Programs with Cardinality and Minimum Threshold Constraints: A Semidefinite Program Approach

  • Duan Li
  • Xiaoling Sun
  • Xiaojin Zheng
    • Categories (Mixed) Integer Nonlinear Programming, Second-Order Cone Programming, Semi-definite Programming

    We consider in this paper quadratic programming problems with cardinality and minimum threshold constraints which arise naturally in various real-world applications such as portfolio selection and subset selection in regression. We propose a new semidefinite program (SDP) approach for computing the “best” diagonal decomposition that gives the tightest continuous relaxation of the perspective reformulation. We … Read more

    A polynomial case of cardinality constrained quadratic optimization problem

  • Jianjun Gao
  • Duan Li
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Global Optimization Tags , , ,

    We investigate in this paper a fixed parameter polynomial algorithm for the cardinality constrained quadratic optimization problem, which is NP-hard in general. More specifically, we prove that, given a problem of size $n$, the number of decision variables, and $s$, the cardinality, if, for some $0

    On Duality Gap in Binary Quadratic Programming

  • Jianjun Gao
  • Duan Li
  • Chunli Liu
  • Xiaoling Sun
    • Categories 0-1 Programming, Quadratic Programming, Semi-definite Programming

    We present in this paper new results on the duality gap between the binary quadratic optimization problem and its Lagrangian dual or semidefinite programming relaxation. We first derive a necessary and sufficient condition for the zero duality gap and discuss its relationship with the polynomial solvability of the primal problem. We then characterize the zeroness … Read more

    Constructing Generalized Mean Functions Using Convex Functions with Regularity Conditions

  • S.C. Fang
  • Duan Li
  • Yun-Bin Zhao
    • Categories Convex Optimization, Generalized Convexity/Monoticity, Nonlinear Optimization Tags , , , ,

    The generalized mean function has been widely used in convex analysis and mathematical programming. This paper studies a further generalization of such a function. A necessary and sufficient condition is obtained for the convexity of a generalized function. Additional sufficient conditions that can be easily checked are derived for the purpose of identifying some classes … Read more