nonconvex

Floorplanning with I/O assignment via feasibility-seeking and superiorization methods

  • ShanYu
  • Yair Censor
  • Guojie Luo
    • Categories Applications - Science and Engineering, Constrained Nonlinear Optimization, VLSI layout Tags , , , , , ,

    The feasibility-seeking approach offers a systematic framework for managing and resolving intricate constraints in continuous problems, making it a promising avenue to explore in the context of floorplanning problems with increasingly heterogeneous constraints. The classic legality constraints can be expressed as the union of convex sets. However, conventional projection-based algorithms for feasibility-seeking do not guarantee … Read more

    The cost of nonconvexity in deterministic nonsmooth optimization

  • Adrian Lewis
    • Categories Nonsmooth Optimization Tags , , , ,

    \(\) We study the impact of nonconvexity on the complexity of nonsmooth optimization, emphasizing objectives such as piecewise linear functions, which may not be weakly convex. We focus on a dimension-independent analysis, slightly modifying a black-box algorithm of Zhang et al. that approximates an $\epsilon$-stationary point of any directionally differentiable Lipschitz objective using $O(\epsilon^{-4})$ calls … Read more

    A Nonmonontone Accelerated Proximal Gradient Method with Variable Stepsize Strategy for Nonsmooth and Nonconvex Minimization Problems

  • Hongwei Liu
  • Wang Ting
    • Categories Nonsmooth Optimization Tags , , , , ,

    We propose a new nonmonontone accelerated proximal gradient method with variable stepsize strategy for minimizing the sum of a nonsmooth function with a smooth one in the nonconvex setting. In this algorithm, the objective function value be allowed to increase discontinuously, but is decreasing from the overall point of view. The variable stepsize strategy don’t … Read more

    The Landscape of the Proximal Point Method for Nonconvex-Nonconcave Minimax Optimization

  • Benjamin Grimmer
  • Haihao Lu
  • Vahab S. Mirrokni
  • Pratik Worah
    • Categories Robust Optimization, Unconstrained Optimization Tags , , , , , ,

    Minimax optimization has become a central tool for modern machine learning with applications in generative adversarial networks, robust optimization, reinforcement learning, etc. These applications are often nonconvex-nonconcave, but the existing theory is unable to identify and deal with the fundamental difficulties posed by nonconvex-nonconcave structures. In this paper, we study the classic proximal point method … Read more

    Adversarial Classification via Distributional Robustness with Wasserstein Ambiguity

  • Nam Ho-Nguyen
  • Stephen Wright
    • Categories Nonlinear Optimization, Robust Optimization Tags , , , ,

    We study a model for adversarial classification based on distributionally robust chance constraints. We show that under Wasserstein ambiguity, the model aims to minimize the conditional value-at-risk of the distance to misclassification, and we explore links to adversarial classification models proposed earlier and to maximum-margin classifiers. We also provide a reformulation of the distributionally robust … Read more

    On Generalized Surrogate Duality in Mixed-Integer Nonlinear Programming

  • Maxime Gasse
  • Ambros Gleixner
  • Andrea Lodi
  • Felipe Serrano
  • Benjamin Müller
  • Gonzalo Muñoz
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Nonlinear Optimization Tags ,

    The most important ingredient for solving mixed-integer nonlinear programs (MINLPs) to global epsilon-optimality with spatial branch and bound is a tight, computationally tractable relaxation. Due to both theoretical and practical considerations, relaxations of MINLPs are usually required to be convex. Nonetheless, current optimization solver can often successfully handle a moderate presence of nonconvexities, which opens … Read more

    Inexact proximal stochastic second-order methods for nonconvex composite optimization

  • Xiao Wang
  • Hongchao Zhang
    • Categories Nonlinear Optimization Tags , , , , , ,

    In this paper, we propose a framework of Inexact Proximal Stochastic Second-order (IPSS) methods for solving nonconvex optimization problems, whose objective function consists of an average of finitely many, possibly weakly, smooth functions and a convex but possibly nons- mooth function. At each iteration, IPSS inexactly solves a proximal subproblem constructed by using some positive … Read more

    Finding Second-Order Stationary Points in Constrained Minimization: A Feasible Direction Approach

  • Nadav Hallak
  • Marc Teboulle
    • Categories Constrained Nonlinear Optimization Tags , ,

    This paper introduces a method for computing points satisfying the second-order necessary optimality conditions in constrained nonconvex minimization. The method comprises two independent steps corresponding to the first and second order conditions. The first-order step is a generic closed map algorithm which can be chosen from a variety of first-order algorithms, making it The second-order … Read more

    On the Convergence to Stationary Points of Deterministic and Randomized Feasible Descent Directions Methods

  • Amir Beck
  • Nadav Hallak
    • Categories Constrained Nonlinear Optimization Tags , ,

    This paper studies the class of nonsmooth nonconvex problems in which the difference between a continuously differentiable function and a convex nonsmooth function is minimized over linear constraints. Our goal is to attain a point satisfying the stationarity necessary optimality condition, defined as the lack of feasible descent directions. Although elementary in smooth optimization, this … Read more

    A simple Newton method for local nonsmooth optimization

  • Adrian Lewis
  • Calvin Wylie
    • Categories Nonsmooth Optimization Tags , , , ,

    Superlinear convergence has been an elusive goal for black-box nonsmooth optimization. Even in the convex case, the subgradient method is very slow, and while some cutting plane algorithms, including traditional bundle methods, are popular in practice, local convergence is still sluggish. Faster variants depend either on problem structure or on analyses that elide sequences of … Read more