Recent work has shown that stochastically perturbed gradient methods can efficiently escape strict saddle points of smooth functions. We extend this body of work to nonsmooth optimization, by analyzing an inexact analogue of a stochastically perturbed gradient method applied to the Moreau envelope. The main conclusion is that a variety of algorithms for nonsmooth optimization … Read more
We present and analyze a new generalized Frank-Wolfe method for the composite optimization problem (P): F*:= min_x f(Ax) + h(x), where f is a \theta-logarithmically-homogeneous self-concordant barrier and the function h has bounded domain but is possibly non-smooth. We show that our generalized Frank-Wolfe method requires O((Gap_0 + \theta + Var_h)\ln(\delta_0) + (\theta + Var_h)^2/\epsilon) … Read more
In this work, we extend the regularization framework from Kronqvist et al. (https://doi.org/10.1007/s10107-018-1356-3) by incorporating several new regularization functions and develop a regularized single-tree search method for solving convex mixed-integer nonlinear programming (MINLP) problems. We propose a set of regularization functions based on distance-metrics and Lagrangean approximations, used in the projection problem for finding new … Read more
In this work we investigate the min-max-min robust optimization problem applied to combinatorial problems with uncertain cost-vectors which are contained in a convex uncertainty set. The idea of the approach is to calculate a set of k feasible solutions which are worst-case optimal if in each possible scenario the best of the k solutions would … Read more
We present PDLP, a practical first-order method for linear programming (LP) that can solve to the high levels of accuracy that are expected in traditional LP applications. In addition, it can scale to very large problems because its core operation is matrix-vector multiplications. PDLP is derived by applying the primal-dual hybrid gradient (PDHG) method, popularized … Read more
In the application of data clustering to human-centric decision-making systems, such as loan applications and advertisement recommendations, the clustering outcome might discriminate against people across different demographic groups, leading to unfairness. A natural conflict occurs between the cost of clustering (in terms of distance to cluster centers) and the balance representation of all demographic groups … Read more
In this paper, we consider a class of nonsmooth problem that is the sum of a Lipschitz differentiable function and a nonsmooth and proper lower semicontinuous function. We discuss here the convergence rate of the function values for a nonmonotone accelerated proximal gradient method, which proposed in “Huan Li and Zhouchen Lin: Accelerated proximal gradient … Read more
Given a square matrix $A$ and a polynomial $p$, the Crouzeix ratio is the norm of the polynomial on the field of values of $A$ divided by the 2-norm of the matrix $p(A)$. Crouzeix’s conjecture states that the globally minimal value of the Crouzeix ratio is 0.5, regardless of the matrix order and polynomial degree, … Read more
The aim of this paper is two-fold: firstly, to present subspace embedding properties for s-hashing sketching matrices, with $s\geq 1$, that are optimal in the projection dimension $m$ of the sketch, namely, $m=O(d)$, where $d$ is the dimension of the subspace. A diverse set of results are presented that address the case when the input … Read more
MIMO radar plays a key role in autonomous driving, and the similarity waveform constraint is an important constraint for radar waveform design. However, the joint constant-modulus and similarity constraint is a difficult constraint. Only the special case with $\infty$-norm similarity and constant-modulus constraints is tackled by the semidefinite relaxation (SDR) and the successive quadratic refinement … Read more