Ting Kei Pong

A Newton-CG based augmented Lagrangian method for finding a second-order stationary point of nonconvex equality constrained optimization with complexity guarantees

  • Chuan He
  • Zhaosong Lu
  • Ting Kei Pong
    • Categories Constrained Nonlinear Optimization Tags , , , , ,

    In this paper we consider finding a second-order stationary point (SOSP) of nonconvex equality constrained optimization when a nearly feasible point is known. In particular, we first propose a new Newton-CG method for finding an approximate SOSP of unconstrained optimization and show that it enjoys a substantially better complexity than the Newton-CG method [56]. We … Read more

    Optimal error bounds in the absence of constraint qualifications with applications to the p-cones and beyond

  • Scott B. Lindstrom
  • Bruno F. Lourenço
  • Ting Kei Pong
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    We prove tight Hölderian error bounds for all p-cones. Surprisingly, the exponents differ in several ways from those that have been previously conjectured; moreover, they illuminate p-cones as a curious example of a class of objects that possess properties in 3 dimensions that they do not in 4 or more. Using our error bounds, we … Read more

    Error bounds, facial residual functions and applications to the exponential cone

  • Scott B. Lindstrom
  • Bruno F. Lourenço
  • Ting Kei Pong
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We construct a general framework for deriving error bounds for conic feasibility problems. In particular, our approach allows one to work with cones that fail to be amenable or even to have computable projections, two previously challenging barriers. For the purpose, we first show how error bounds may be constructed using objects called one-step facial … Read more

    A Strictly Contractive Peaceman-Rachford Splitting Method for the Doubly Nonnegative Relaxation of the Minimum Cut Problem

  • Xinxin Li
  • Ting Kei Pong
  • Hao Sun
  • Henry Wolkowicz
    • Categories (Mixed) Integer Nonlinear Programming, Linear, Cone and Semidefinite Programming, Optimization Software Benchmark Tags , , , , , ,

    The minimum cut problem, MC, and the special case of the vertex separator problem, consists in partitioning the set of nodes of a graph G into k subsets of given sizes in order to minimize the number of edges cut after removing the k-th set. Previous work on this topic uses eigenvalue, semidefinite programming, SDP, … Read more

    Douglas-Rachford splitting for nonconvex feasibility problems

  • Guoyin Li
  • Ting Kei Pong
    • Categories Nonsmooth Optimization

    We adapt the Douglas-Rachford (DR) splitting method to solve nonconvex feasibility problems by studying this method for a class of nonconvex optimization problem. While the convergence properties of the method for convex problems have been well studied, far less is known in the nonconvex setting. In this paper, for the direct adaptation of the method … Read more

    Global convergence of splitting methods for nonconvex composite optimization

  • Guoyin Li
  • Ting Kei Pong
    • Categories Nonsmooth Optimization

    We consider the problem of minimizing the sum of a smooth function $h$ with a bounded Hessian, and a nonsmooth function. We assume that the latter function is a composition of a proper closed function $P$ and a surjective linear map $\M$, with the proximal mappings of $\tau P$, $\tau > 0$, simple to compute. … Read more

    Eigenvalue, Quadratic Programming, and Semidefinite Programming Relaxations for a Cut Minimization Problem

  • Ting Kei Pong
  • Henry Wolkowicz
  • Hao Sun
  • Ningchuan Wang
    • Categories Combinatorial Optimization, Graphs and Matroids, Semi-definite Programming Tags , , , ,

    We consider the problem of partitioning the node set of a graph into $k$ sets of given sizes in order to \emph{minimize the cut} obtained using (removing) the $k$-th set. If the resulting cut has value $0$, then we have obtained a vertex separator. This problem is closely related to the graph partitioning problem. In … Read more

    Gauge optimization, duality, and applications

  • Michael P. Friedlander
  • Ives Macêdo
  • Ting Kei Pong
    • Categories Convex Optimization Tags , , ,

    Gauge functions significantly generalize the notion of a norm, and gauge optimization, as defined by Freund (1987), seeks the element of a convex set that is minimal with respect to a gauge function. This conceptually simple problem can be used to model a remarkable array of useful problems, including a special case of conic optimization, … Read more

    Convex relaxation for finding planted influential nodes in a social network

  • Lisa Elkin
  • Ting Kei Pong
  • Stephen A. Vavasis
    • Categories Convex Optimization, Data-Mining Tags , ,

    We consider the problem of maximizing influence in a social network. We focus on the case that the social network is a directed bipartite graph whose arcs join senders to receivers. We consider both the case of deterministic networks and probabilistic graphical models, that is, the so-called “cascade” model. The problem is to find the … Read more

    The proximal-proximal gradient algorithm

  • Ting Kei Pong
    • Categories Applications - Science and Engineering, Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

    We consider the problem of minimizing a convex objective which is the sum of a smooth part, with Lipschitz continuous gradient, and a nonsmooth part. Inspired by various applications, we focus on the case when the nonsmooth part is a composition of a proper closed convex function P and a nonzero affine map, with the … Read more