Shuzhong Zhang

Geometric Rounding: A Dependent Rounding Scheme for Allocation Problems

  • Dongdong Ge
  • Yinyu Ye
  • Shuzhong Zhang
  • Simai He
  • Zizhuo Wang
    • Categories Applications - OR and Management Sciences, Approximation Algorithms

    This paper presents a general technique to develop approximation algorithms for allocation problems with integral assignment constraints. The core of the method is a randomized dependent rounding scheme, called geometric rounding, which yields termwise rounding ratios (in expectation), while emphasizing the strong correlation between events. We further explore the intrinsic geometric structure and general theoretical … Read more

    Approximation Algorithms for Indefinite Complex Quadratic Maximization Problems

  • Yongwei Huang
  • Shuzhong Zhang
    • Categories Approximation Algorithms, Semi-definite Programming Tags , , ,

    In this paper we consider the following two types of complex quadratic maximization problems: (i) maximize $z^{\HH} Q z$, subject to $z_k^m=1$, $k=1,…,n$, where $Q$ is a Hermitian matrix with $\tr Q=0$ and $z\in \C^n$ is the decision vector; (ii) maximize $\re y^{\HH}Az$, subject to $y_k^m=1$, $k=1,…,p$, and $z_l^m=1$, $l=1,…,q$, where $A\in \C^{p\times q}$ and … Read more

    Complex Matrix Decomposition and Quadratic Programming

  • Yongwei Huang
  • Shuzhong Zhang
    • Categories Semi-definite Programming Tags , , ,

    This paper studies the possibilities of the Linear Matrix Inequality (LMI) characterization of the matrix cones formed by nonnegative complex Hermitian quadratic functions over specific domains in the complex space. In its real case analog, such studies were conducted in Sturm and Zhang in 2003. In this paper it is shown that stronger results can … Read more

    Complex Quadratic Optimization and Semidefinite Programming

  • Yongwei Huang
  • Shuzhong Zhang
    • Categories Approximation Algorithms, Semi-definite Programming Tags , , ,

    In this paper we study the approximation algorithms for a class of discrete quadratic optimization problems in the Hermitian complex form. A special case of the problem that we study corresponds to the max-3-cut model used in a recent paper of Goemans and Williamson. We first develop a closed-form formula to compute the probability of … Read more

    An (\sqrt{n}\log \frac{(x^0)^Ts^0}{\epsilon})$ iteration primal-dual path-following method, based on wide neighborhoods and large updates, for monotone linear complementarity problems

  • Wenbao Ai
  • Shuzhong Zhang
    • Categories Linear, Cone and Semidefinite Programming Tags , ,

    In this paper we propose a new class of primal-dual path-following interior point algorithms for solving monotone linear complementarity problems. At each iteration, the method would select a target on the central path with a large update from the current iterate, and then the Newton method is used to get the search directions, followed by … Read more

    On Conically Ordered Convex Programs

  • Shuzhong Zhang
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    In this paper we study a special class of convex optimization problems called {\em conically ordered convex programs}\/ (COCP), where the feasible region is given as the level set of a vector-valued nonlinear mapping, expressed as a nonnegative combination of convex functions. The nonnegativity of the vectors is defined using a pre-described conic ordering. The … Read more

    Approximation Bounds for Quadratic Maximization with Semidefinite Programming Relaxation

  • Dachuan Xu
  • Shuzhong Zhang
    • Categories Approximation Algorithms Tags , , ,

    In this paper, we consider a class of quadratic maximization problems. One important instance in that class is the famous quadratic maximization formulation of the max-cut problem studied by Goemans and Williamson. Since the problem is NP-hard in general, following Goemans and Williamson, we apply the approximation method based on the semidefinite programming (SDP) relaxation. … Read more

    Multivariate Nonnegative Quadratic Mappings

  • Zhi-Quan Luo
  • Jos F. Sturm
  • Shuzhong Zhang
    • Categories Linear, Cone and Semidefinite Programming Tags , ,

    In this paper we study several issues related to the characterization of specific classes of multivariate quadratic mappings that are nonnegative over a given domain, with nonnegativity defined by a pre-specified conic order. In particular, we consider the set (cone) of nonnegative quadratic mappings defined with respect to the positive semidefinite matrix cone, and study … Read more

    Recursive Approximation of the High Dimensional Max Function

  • Ş. İlker Birbil
  • S.C. Fang
  • Shuzhong Zhang
  • Hans Frenk
    • Categories Convex and Nonsmooth Optimization Tags , ,

    An alternative smoothing method for the high dimensional $\max $ function has been studied. The proposed method is a recursive extension of the two dimensional smoothing functions. In order to analyze the proposed method, a theoretical framework related to smoothing methods has been discussed. Moreover, we support our discussion by considering some application areas. This … Read more

    A D-Induced Duality and Its Applications

  • Jan Brinkhuis
  • Shuzhong Zhang
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    This paper attempts to extend the notion of duality for convex cones, by basing it on a pre-described conic ordering and a fixed bilinear mapping. This is an extension of the standard definition of dual cones, in the sense that the {\em nonnegativity}\/ of the inner-product is replaced by a pre-specified conic ordering, defined by … Read more