Jingye Xu

Probabilistic analysis of dual decomposition on two-stage stochastic integer programs

  • Jingye Xu
    • Categories Integer Programming, Stochastic Programming Tags ,

    Two-stage stochastic integer programs provide a powerful framework for modeling decision-making under uncertainty, but they are notoriously difficult to solve at scale due to their high dimensionality and intrinsic nonconvexity. Decomposition-based algorithms such as Benders methods and Branch-and-Price (related dual decomposition methods) have become standard computational approaches for such problems and demonstrate excellent empirical performance … Read more

    Asymptotically tight Lagrangian dual of smooth nonconvex problems via improved error bound of Shapley-Folkman Lemma

  • Jingye Xu
    • Categories Convex Optimization, Nonlinear Optimization Tags , ,

    In convex geometry, the Shapley–Folkman Lemma asserts that the nonconvexity of a Minkowski sum of $n$-dimensional bounded nonconvex sets does not accumulate once the number of summands exceeds the dimension $n$, and thus the sum becomes approximately convex. Originally published by Starr in the context of quasi-equilibrium in nonconvex market models in economics, the lemma … Read more

    Computational complexity of decomposing a symmetric matrix as a sum of positive semidefinite and diagonal matrices

  • Levent Tunçel
  • Stephen A. Vavasis
  • Jingye Xu
    • Categories Finance and Economics, Statistics Tags

    We study several variants of decomposing a symmetric matrix into a sum of a low-rank positive semidefinite matrix and a diagonal matrix. Such decompositions have applications in factor analysis and they have been studied for many decades. On the one hand, we prove that when the rank of the positive semidefinite matrix in the decomposition … Read more