13 papers · 1 filter
A Logarithmic-dual-update Bregman ADMM for Optimal Transport
Di Hou, Kim-Chuan Toh
This paper studies an entropy Bregman alternating direction method of multipliers (BADMM) with logarithmic dual update for solving discrete optimal transport (OT) problems. The alg…
McADMM: A Multi-Clique Augmented Lagrangian-Based Algorithm for Large-Scale Sparse SDPs with Bound Constraints
Kristo Nugraha Lian, Nehal Ahmed Shaikh, Di Hou +2
sGS-PADMM [21, 14, 6] is a powerful and versatile class of convergent multi-block ADMM solvers for implementations on moderate-sized linear semidefinite programming (SDP) problems.…
Sparsity-Cone SDP Relaxations and Applications to Variable Fixing for Sparse Quadratic Programs
Di Hou, Thai P. D. Nguyen, Kim-Chuan Toh +1
Quadratic programs (QPs) with sparsity constraint are generally NP-hard, and their efficient global solution depends crucially on tractable tight convex relaxations. In this paper,…
A preconditioned augmented Lagrangian method for solving semidefinite programming problems
Tianyun Tang, Kim-Chuan Toh
In this work, we propose a preconditioned augmented Lagrangian method (ALM) for solving semidefinite programming (SDP) problems. The preconditioner is implemented via a weighted pe…
Gradient flow for finding E-optimal designs
Jieling Shi, Kim-Chuan Toh, Xin T. Tong +1
The -optimality criterion for a regression model maximizes the smallest eigenvalue of the information matrix and becomes non-differentiable when this eigenvalue has multiplicity…
Time-integrated Optimal Transport: A Robust Minimax Framework
Thai P. D. Nguyen, Hong T. M. Chu, Kim-Chuan Toh
Comparing time series in a principled manner requires capturing both temporal alignment and distributional similarity of features. Optimal transport (OT) has recently emerged as a…
A Low-rank Augmented Lagrangian Method for Polyhedral-SDP and Moment-SOS Relaxations of Polynomial Optimization
Di Hou, Tianyun Tang, Kim-Chuan Toh
Polynomial optimization problems (POPs) can be reformulated as geometric convex conic programs, as shown by Kim, Kojima, and Toh (SIOPT 30:1251-1273, 2020), though such formulation…
A Quadratically Convergent Alternating Projection Method for Nonconvex Sets
Nachuan Xiao, Shiwei Wang, Tianyun Tang +1
In this paper, we consider the feasibility problem, which aims to find a feasible point for the constraint set over a possibly non-regular subset…
An Exact Penalty Approach for Equality Constrained Optimization over a Convex Set
Nachuan Xiao, Tianyun Tang, Shiwei Wang +1
In this paper, we consider the nonlinear constrained optimization problem (NCP) with constraint set , where is a closed convex subset…
A low-rank augmented Lagrangian method for doubly nonnegative relaxations of mixed-binary quadratic programs
Di Hou, Tianyun Tang, Kim-Chuan Toh
Doubly nonnegative (DNN) programming problems are known to be challenging to solve because of their huge number of constraints and variables. In this work, we int…
A Bregman ADMM for Bethe variational problem
Yuehaw Khoo, Tianyun Tang, Kim-Chuan Toh
In this work, we propose a novel Bregman ADMM with nonlinear dual update to solve the Bethe variational problem (BVP), a key optimization formulation in graphical models and statis…
Optimization over convex polyhedra via Hadamard parametrizations
Tianyun Tang, Kim-Chuan Toh
In this paper, we study linearly constrained optimization problems (LCP). After applying Hadamard parametrization, the feasible set of the parametrized problem (LCPH) becomes an al…
Exploring chordal sparsity in semidefinite programming with sparse plus low-rank data matrices
Tianyun Tang, Kim-Chuan Toh
Semidefinite programming (SDP) problems are challenging to solve because of their high dimensionality. However, solving sparse SDP problems with small tree-width are known to be re…