Walaa M. Moursi

Exact Solutions for the NP-hard Wasserstein Barycenter Problem using a Doubly Nonnegative Relaxation and a Splitting Method

  • Woosuk L. Jung
  • Walaa M. Moursi
  • Henry Wolkowicz
    • Categories Combinatorial Optimization, Meta Heuristics, Semi-definite Programming

    \(\) The simplified Wasserstein barycenter problem consists in selecting one point from \(k\) given sets, each set consisting of \(n\) points, with the aim of minimizing the sum of distances to the barycenter of the \(k\) points chosen. This problem is known to be NP-hard. We compute the Wasserstein barycenter by exploiting the Euclidean distance … Read more

    Range of the displacement operator of PDHG with applications to quadratic and conic programming

  • Tao Jiang
  • Walaa M. Moursi
  • Stephen A. Vavasis
    • Categories Generalized Convexity/Monoticity, Quadratic Programming, Second-Order Cone Programming Tags , , , , ,

    Primal-dual hybrid gradient (PDHG) is a first-order method for saddle-point problems and convex programming introduced by Chambolle and Pock. Recently, Applegate et al. analyzed the behavior of PDHG when applied to an infeasible or unbounded instance of linear programming, and in particular, showed that PDHG is able to diagnose these conditions. Their analysis hinges on … Read more

    Regularized Nonsmooth Newton Algorithms for Best Approximation

  • Yair Censor
  • Walaa M. Moursi
  • Tyler Weames
  • Henry Wolkowicz
    • Categories Convex Optimization, Linear Programming, Nonsmooth Optimization Tags , , , , ,

    We consider the problem of finding the best approximation point from a polyhedral set, and its applications, in particular to solving large-scale linear programs. The classical projection problem has many various and many applications. We study a regularized nonsmooth Newton type solution method where the Jacobian is singular; and we compare the computational performance to … Read more