This paper proposes a simple facet enumeration algorithm for convex polytopes. The complexity of the algorithm is analyzed. The algorithm is implemented in Matlab. Some polytopes with known H-representations and V-representations are used as test examples. The preliminary numerical test shows the effectiveness and efficiency of the proposed algorithm. Due to the duality between the … Read more
This paper introduces the class of weakly quasar-convex functions, a notion that simultaneously generalizes weak convexity (and hence convexity) and quasar-convexity. We establish the theoretical foundation for this new class by developing its basic calculus, deriving characterizations, and systematically investigating its closure and structural properties. Building on these tools, we analyze the proximal point algorithm … Read more
We present GPU-accelerated Bregman Douglas–Rachford splitting algorithm (BDRS) for discrete optimal transport problem in three input formats: an explicit cost matrix, a point cloud with a ground cost between them, and a separable cost on a regular grid. For each input format, we propose hardware-aware designs of mathematically equivalent representations for the BDRS iterations to … Read more
We study first-order optimality for constrained composite optimization problems whose objective is the sum of a locally Lipschitz function and a proper lower semicontinuous function. We focus on the case in which the limiting subdifferential of the latter function is empty at a point of interest, so that the usual KKT conditions are unavailable. We … Read more
Stochastic Gradient Descent (\(\textsf{SGD}\)) is one of the most classical optimization algorithms with favorable theoretical guarantees, yet its practical implementation differs subtly from its well-known form and is often referred to as Shuffling Stochastic Gradient Descent (\(\textsf{Shuffling SGD}\)). A particularly popular strategy in \(\textsf{Shuffling SGD}\) is Random Reshuffling (\(\textsf{RR}\)), which has achieved great empirical success. … Read more
We show that the Bregman Douglas–Rachford splitting method (BDRS) can fail for matrix scaling and unregularized optimal transport. For matrix scaling, we construct a strictly positive \(36\times6\) integer matrix, positive rational marginals of equal mass, and a positive auxiliary initialization for which the matrix iterates enter a nonconstant six-cycle after one iteration. The construction prescribes … Read more
This paper presents Peppy, an AI-assisted workflow for discovering tight, analytic convergence proofs for first-order optimization algorithms. Generic approaches to using LLMs to conduct mathematical research target an unspecified, broad spectrum of problems and sometimes use the Lean 4 proof assistant for formalization. On the other hand, Peppy leverages domain-specific knowledge more heavily and is … Read more
We study nonsmooth convex-concave saddle-point problems over compact convex sets, assuming access to stochastic subgradients of the payoff function. We develop single-loop projection-free algorithms that use linear minimization oracles over the primal and dual domains. Unlike prior projection-free approaches that rely on smoothing, our methods are purely subgradient-based and handle nonsmoothness directly. This design makes … Read more
We study gradient descent with predetermined nonnegative stepsizes on smooth strongly convex functions. Let \(p_{\mathrm{sil}}=\log_2(1+\sqrt2)\) and \(\kappa\) be the condition number. We prove the iteration lower bound \(\Omega\left(\kappa^{\frac{1}{p_{\mathrm{sil}}}-o(1)}\log\frac1\delta\right)\)for both relative squared distance and relative function error, uniformly over \(0<\delta<1\) and sufficiently large \(\kappa\). This matches the polynomial exponent of \(\kappa\) for the Silver stepsize schedule … Read more
Distributionally robust optimization (DRO) provides a principled framework for learning under distribution shift, but its practical use is hindered by the difficulty of evaluating worst-case risks for nonconvex loss functions. We study a penalized DRO formulation in which the adversary may choose any distribution but incurs a Wasserstein penalty for deviating from the empirical distribution. … Read more