Nonsmooth Optimization

Subgradient Convergence Implies Subdifferential Convergence on Weakly Convex Functions: With Uniform Rates Guarantees

Categories Nonsmooth Optimization, Stochastic Programming

In nonsmooth, nonconvex stochastic optimization, understanding the uniform convergence of subdifferential mappings is crucial for analyzing stationary points of sample average approximations of risk as they approach the population risk. Yet, characterizing this convergence remains a fundamental challenge. This work introduces a novel perspective by connecting the uniform convergence of subdifferential mappings to that of subgradient … Read more

Approaches to iterative algorithms for solving nonlinear equations with an application in tomographic absorption spectroscopy

Categories Biomedical Applications, Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , , , ,

In this paper we propose an approach for solving systems of nonlinear equations without computing function derivatives. Motivated by the application area of tomographic absorption spectroscopy, which is a highly-nonlinear problem with variables coupling, we consider a situation where straightforward translation to a fixed point problem is not possible because the operators that represent the … Read more

Understanding the Douglas-Rachford splitting method through the lenses of Moreau-type envelopes

Categories Convex and Nonsmooth Optimization, Generalized Convexity/Monoticity, Nonsmooth Optimization Tags , , , ,

We analyze the Douglas-Rachford splitting method for weakly convex optimization problems, by the token of the Douglas-Rachford envelope, a merit function akin to the Moreau envelope. First, we use epi-convergence techniques to show that this artifact approximates the original objective function via epigraphs. Secondly, we present how global convergence and local linear convergence rates for … Read more

Second-Order Strong Optimality and Second-Order Duality for Nonsmooth Constrained Multiobjective Fractional Programming Problems

Categories Multi-Criteria Optimization, Nonsmooth Optimization Tags , , , ,

This paper investigates constrained nonsmooth multiobjective fractional programming problem (NMFP) in real Banach spaces. It derives a quotient calculus rule for computing the first- and second-order Clarke derivatives of fractional functions involving locally Lipschitz functions. A novel second-order Abadie-type regularity condition is presented, defined with the help of the Clarke directional derivative and the P´ales-Zeidan … Read more

Fast convergence of the primal-dual dynamical system and algorithms for a nonsmooth bilinearly coupled saddle point problem

Categories Game Theory, Nonsmooth Optimization Tags , , , ,

This paper is devoted to study the convergence rates of a second-order dynamical system and its corresponding discretizations associated with a nonsmooth bilinearly coupled convex-concave saddle point problem. We derive the convergence rate of the primal-dual gap for the second-order dynamical system with asymptotically vanishing damping term. Based on the implicit discretization, we propose a … Read more

Scalable Projection-Free Optimization Methods via MultiRadial Duality Theory

Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , ,

Recent works have developed new projection-free first-order methods based on utilizing linesearches and normal vector computations to maintain feasibility. These oracles can be cheaper than orthogonal projection or linear optimization subroutines but have the drawback of requiring a known strictly feasible point to do these linesearches with respect to. In this work, we develop new … Read more

Some Primal-Dual Theory for Subgradient Methods for Strongly Convex Optimization

Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , , , ,

We consider (stochastic) subgradient methods for strongly convex but potentially nonsmooth non-Lipschitz optimization. We provide new equivalent dual descriptions (in the style of dual averaging) for the classic subgradient method, the proximal subgradient method, and the switching subgradient method. These equivalences enable $O(1/T)$ convergence guarantees in terms of both their classic primal gap and a … Read more

Splitting Methods for Nonconvex Optimisation: Convergence and Saddle Point Avoidance Through Shadow Sequences

Categories Generalized Convexity/Monoticity, Nonsmooth Optimization Tags , , , , , ,

In nonconvex optimisation, commonly used methods are usually shown to converge to stationary points, while guarantees of convergence to local minimisers have comparatively received less attention. To close this gap, we analyse the convergence behaviour of the Davis–Yin three-operator splitting method. More precisely, for structured weakly convex semialgebraic optimisation problems, we establish convergence to local … Read more

Weak convexity and approximate subdifferentials

Categories Complementarity and Variational Inequalities, Generalized Convexity/Monoticity, Nonsmooth Optimization

We explore and construct an enlarged subdifferential for weakly convex functions. The resulting object turns out to be continuous with respect to both the function argument and the enlargement parameter. We carefully analyze connections with other constructs in the literature and particularize to the weakly convex setting well-known variational principles. By resorting to the new … Read more

An Inexact Restoration Direct Multisearch Filter Approach to Multiobjective Constrained Derivative-free Optimization

Categories Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , , , ,

Direct Multisearch (DMS) is a well-established class of methods for multiobjective derivative-free optimization, where constraints are addressed by an extreme barrier approach, only evaluating feasible points. In this work, we propose a filter approach, combined with an inexact feasibility restoration step, to address constraints in the DMS framework. The filter approach treats feasibility as an … Read more