100 citations · 462 across the 26 of their papers we have counts for
21 papers · 1 filter
Progressive Bound Strengthening via Doubly Nonnegative Cutting Planes for Nonconvex Quadratic Programs
Zheng Qu, Defeng Sun, Jintao Xu
We introduce a cutting-plane framework for nonconvex quadratic programs (QPs) that progressively tightens convex relaxations. Our approach leverages the doubly nonnegative (DNN) re…
Globally Solving Concave Quadratic Programs via Doubly Nonnegative Relaxation
Zheng Qu, Tianyou Zeng, Yuchen Lou
We consider the problem of maximizing a convex quadratic function over a bounded polyhedral set. We design a new framework based on SDP relaxations and cutting plane methods for so…
A Correlatively Sparse Lagrange Multiplier Expression Relaxation for Polynomial Optimization
Zheng Qu, Xindong Tang
In this paper, we consider polynomial optimization with correlative sparsity. We construct correlatively sparse Lagrange multiplier expressions (CS-LMEs) and propose CS-LME reformu…
Exactness and Effective Degree Bound of Lasserre's Relaxation for Polynomial Optimization over Finite Variety
Zheng Hua, Zheng Qu
In this paper, we address the effective degree bound problem for Lasserre's hierarchy of moment-sum-of-squares (SOS) relaxations in polynomial optimization involving variables.…
Entropic Regularization of the Nested Distance
Zheng Qu, Benoît Tran
In 2012, Pflug and Pichler proved, under regularity assumptions, that the value function in Multistage Stochastic Programming (MSP) is Lipschitz continuous w.r.t. the Nested Distan…
Multiply Accelerated Value Iteration for Non-Symmetric Affine Fixed Point Problems and application to Markov Decision Processes
Marianne Akian, Stéphane Gaubert, Zheng Qu +1
We analyze a modified version of Nesterov accelerated gradient algorithm, which applies to affine fixed point problems with non self-adjoint matrices, such as the ones appearing in…
An adaptive proximal point algorithm framework and application to large-scale optimization
Meng Lu, Zheng Qu
We investigate the proximal point algorithm (PPA) and its inexact extensions under an error bound condition, which guarantees a global linear convergence if the proximal regulariza…
An inexact proximal augmented Lagrangian framework with arbitrary linearly convergent inner solver for composite convex optimization
Fei Li, Zheng Qu
We propose an inexact proximal augmented Lagrangian framework with explicit inner problem termination rule for composite convex optimization problems. We consider arbitrary linearl…
Solving Ergodic Markov Decision Processes and Perfect Information Zero-sum Stochastic Games by Variance Reduced Deflated Value Iteration
Marianne Akian, Stéphane Gaubert, Zheng Qu +1
Recently, Sidford, Wang, Wu and Ye (2018) developed an algorithm combining variance reduction techniques with value iteration to solve discounted Markov decision processes. This al…
L-SVRG and L-Katyusha with Arbitrary Sampling
Xun Qian, Zheng Qu, Peter Richtárik
We develop and analyze a new family of {\em nonaccelerated and accelerated loopless variance-reduced methods} for finite sum optimization problems. Our convergence analysis relies…
Restarting the accelerated coordinate descent method with a rough strong convexity estimate
Olivier Fercoq, Zheng Qu
We propose new restarting strategies for the accelerated coordinate descent method. Our main contribution is to show that for a well chosen sequence of restarting times, the restar…
Adaptive restart of accelerated gradient methods under local quadratic growth condition
Olivier Fercoq, Zheng Qu
By analyzing accelerated proximal gradient methods under a local quadratic growth condition, we show that restarting these algorithms at any frequency gives a globally linearly con…
Restarting accelerated gradient methods with a rough strong convexity estimate
Olivier Fercoq, Zheng Qu
We propose new restarting strategies for accelerated gradient and accelerated coordinate descent methods. Our main contribution is to show that the restarted method has a geometric…
Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
Zeyuan Allen-Zhu, Zheng Qu, Peter Richtárik +1
Accelerated coordinate descent is widely used in optimization due to its cheap per-iteration cost and scalability to large-scale problems. Up to a primal-dual transformation, it is…
Stochastic Dual Coordinate Ascent with Adaptive Probabilities
Dominik Csiba, Zheng Qu, Peter Richtárik
This paper introduces AdaSDCA: an adaptive variant of stochastic dual coordinate ascent (SDCA) for solving the regularized empirical risk minimization problems. Our modification co…
Coordinate Descent with Arbitrary Sampling II: Expected Separable Overapproximation
Zheng Qu, Peter Richtárik
The design and complexity analysis of randomized coordinate descent methods, and in particular of variants which update a random subset (sampling) of coordinates in each iteration,…
Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity
Zheng Qu, Peter Richtárik
We study the problem of minimizing the sum of a smooth convex function and a convex block-separable regularizer and propose a new randomized coordinate descent method, which we cal…
Randomized Dual Coordinate Ascent with Arbitrary Sampling
Zheng Qu, Peter Richtárik, Tong Zhang
We study the problem of minimizing the average of a large number of smooth convex functions penalized with a strongly convex regularizer. We propose and analyze a novel primal-dual…
Fast Distributed Coordinate Descent for Non-Strongly Convex Losses
Olivier Fercoq, Zheng Qu, Peter Richtárik +1
We propose an efficient distributed randomized coordinate descent method for minimizing regularized non-strongly convex loss functions. The method attains the optimal co…
Bundle-based pruning in the max-plus curse of dimensionality free method
Stephane Gaubert, Zheng Qu, Srinivas Sridharan
Recently a new class of techniques termed the max-plus curse of dimensionality-free methods have been developed to solve nonlinear optimal control problems. In these methods the di…
Curse of dimensionality reduction in max-plus based approximation methods: theoretical estimates and improved pruning algorithms
Stephane Gaubert, William McEneaney, Zheng Qu
Max-plus based methods have been recently developed to approximate the value function of possibly high dimensional optimal control problems. A critical step of these methods consis…