Nonlinear Optimization

Superiorization and Perturbation Resilience of Algorithms: A Continuously Updated Bibliography

  • Yair Censor
    • Categories Applications - Science and Engineering, Constrained Nonlinear Optimization Tags , , ,

    This document presents a (mostly) chronologically-ordered bibliography of scientific publications on the superiorization methodology and perturbation resilience of algorithms which is compiled and continuously updated by us at: http://math.haifa.ac.il/yair/bib-superiorization-censor.html. Since the beginnings of this topic we try to trace the work that has been published about it since its inception. To the best of our … Read more

    A characterization of positive spanning sets with ties to strongly edge-connected digraphs

  • Denis Cornaz
  • Sébastien Kerleau
  • Clément W. Royer
    • Categories Graphs and Matroids, Nonlinear Optimization, Unconstrained Optimization

    Positive spanning sets (PSSs) are families of vectors that span a given linear space through non-negative linear combinations. Despite certain classes of PSSs being well understood, a complete characterization of PSSs remains elusive. In this paper, we explore a relatively understudied relationship between positive spanning sets and strongly edge-connected digraphs, in that the former can … Read more

    Tight Semidefinite Relaxations for Verifying Robustness of Neural Networks

  • Godai Azuma
  • Sunyoung Kim
  • Makoto Yamashita
    • Categories Optimization in Data Science, Quadratic Programming, Semi-definite Programming Tags , , , ,

    For verifying the safety of neural networks (NNs), Fazlyab et al. (2019) introduced a semidefinite programming (SDP) approach called DeepSDP. This formulation can be viewed as the dual of the SDP relaxation for a problem formulated as a quadratically constrained quadratic program (QCQP). While SDP relaxations of QCQPs generally provide approximate solutions with some gaps, … Read more

    A relaxed version of Ryu’s three-operator splitting method for structured nonconvex optimization

  • Felipe Atenas
  • Jan Harold Alcantara
    • Categories Nonlinear Optimization, Nonsmooth Optimization

    In this work, we propose a modification of Ryu’s splitting algorithm for minimizing the sum of three functions, where two of them are convex with Lipschitz continuous gradients, and the third is an arbitrary proper closed function that is not necessarily convex. The modification is essential to facilitate the convergence analysis, particularly in establishing a … Read more

    An iterative process for the feasibility-seeking problem with sets that are unions of convex sets

  • Yair Censor
  • Alexander J. Zaslavski
    • Categories Constrained Nonlinear Optimization, Convex Optimization Tags , , , ,

    In this paper we deal with the feasibility-seeking problem for unions of convex sets (UCS) sets and propose an iterative process for its solution. Renewed interest in this problem stems from the fact that it was recently discovered to serve as a modeling approach in fields of applications and from the ongoing recent research efforts … Read more

    Direct-search methods for decentralized blackbox optimization

  • Elhoucine Bergou
  • Youssef Diouane
  • Vyacheslav Kungurtsev
  • Clément W. Royer
    • Categories Network Optimization, Nonlinear Optimization, Unconstrained Optimization

    Derivative-free optimization algorithms are particularly useful for tackling blackbox optimization problems where the objective function arises from complex and expensive procedures that preclude the use of classical gradient-based methods. In contemporary decentralized environments, such functions are defined locally on different computational nodes due to technical or privacy constraints, introducing additional challenges within the optimization process. … Read more

    On the Semidefinite Representability of Continuous Quadratic Submodular Minimization With Applications to Moment Problems

  • Samuel Burer
  • Karthik Natarajan
    • Categories Quadratic Programming, Robust Optimization, Semi-definite Programming Tags , ,

    We show that continuous quadratic submodular minimization with bounds is solvable in polynomial time using semidefinite programming, and we apply this result to two moment problems arising in distributionally robust optimization and the computation of covariance bounds. Accordingly, this research advances the ongoing study of continuous submodular minimization and opens new application areas therein. ArticleDownload … Read more

    On regularized structure exploiting Quasi-Newton methods for inverse problems

  • Raphael Kuess
  • Andrea Walther
    • Categories Infinite Dimensional Optimization, Nonlinear Systems and Least-Squares Tags , , , ,

    This paper introduces a regularized, structure-exploiting Powell-Symmetric-Broyden (RSE-PSB) method under modified secant conditions for solving ill-posed inverse problems in both infinite dimensional and finite dimensional settings. The approximation of the symmetric, yet potentially indefinite, second-order term, which is neglected by standard Levenberg-Marquardt (LM) approaches, integrates regularization and structure exploitation directly within the Quasi-Newton (QN) framework, … Read more

    Efficient search strategies for constrained multiobjective blackbox optimization

  • Sébastien Le Digabel
  • Antoine Lesage-Landry
  • Ludovic Salomon
  • Christophe Tribes
    • Categories Multi-Criteria Optimization, Nonlinear Optimization Tags ,

    Multiobjective blackbox optimization deals with problems where the objective and constraint functions are the outputs of a numerical simulation. In this context, no derivatives are available, nor can they be approximated by finite differences, which precludes the use of classical gradient-based techniques. The DMulti-MADS algorithm implements a state-of-the-art direct search procedure for multiobjective blackbox optimization … Read more

    New Algorithms for maximizing the difference of convex functions

  • Aharon Ben-Tal
  • Luba Tetruashvili
    • Categories Global Optimization, Global Optimization Applications, Nonlinear Optimization

    Maximizing the difference of 2 convex functions over a convex feasible set (the so called DCA problem) is a hard problem. There is a large number of publications addressing this problem. Many of them are variations of widely used DCA algorithm [20]. The success of this algorithm to reach a good approximation of a global … Read more