Month: April 2022

Automatic Reformulations for Convex Mixed-Integer Nonlinear Optimization: Perspective and Separability

  • Meenarli Sharma
  • Ashutosh Mahajan
    • Categories (Mixed) Integer Nonlinear Programming, Optimization Software and Modeling Systems Tags , , , ,

    Tight reformulations of combinatorial optimization problems like Convex Mixed-Integer Nonlinear Programs (MINLPs) enable one to solve these problems faster by obtaining tight bounds on the optimal value. We consider two techniques for reformulation: perspective reformulation and separability detection. We develop routines for the automatic detection of problem structures suitable for these reformulations and implement new … Read more

    Distributed Projections onto a Simplex

  • Yongzheng Dai
  • Chen Chen
    • Categories Linear, Cone and Semidefinite Programming, Parallel Algorithms Tags , , ,

    Projecting a vector onto a simplex is a well-studied problem that arises in a wide range of optimization problems. Numerous algorithms have been proposed for determining the projection; however, all but one of these algorithms are serial. We address this gap by developing a method that preprocesses the input vector by decomposing and distributing it … Read more

    Worst-Case Complexity of TRACE with Inexact Subproblem Solutions for Nonconvex Smooth Optimization

  • Frank E. Curtis
  • Qi Wang
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , , ,

    An algorithm for solving nonconvex smooth optimization problems is proposed, analyzed, and tested. The algorithm is an extension of the Trust Region Algorithm with Contractions and Expansions (TRACE) [Math. Prog. 162(1):132, 2017]. In particular, the extension allows the algorithm to use inexact solutions of the arising subproblems, which is an important feature for solving large-scale … Read more

    Improved RIP-Based Bounds for Guaranteed Performance of Two Compressed Sensing Algorithms

  • Yun-Bin Zhao
  • Zhi-Quan Luo
    • Categories Constrained Nonlinear Optimization, Global Optimization Applications, Nonsmooth Optimization Tags , , , ,

    Iterative hard thresholding (IHT) and compressive sampling matching pursuit (CoSaMP) are two mainstream compressed sensing algorithms using the hard thresholding operator. The guaranteed performance of the two algorithms for signal recovery was mainly analyzed in terms of the restricted isometry property (RIP) of sensing matrices. At present, the best known bound using RIP of order … Read more

    A Generalized Formulation for Group Selection via ADMM

  • Chengyu Ke
  • Sunyoung Shin
  • Yifei Lou
  • Miju Ahn
    • Categories Nonlinear Optimization Tags , , ,

    This paper studies a statistical learning model where the model coefficients have a pre-determined non-overlapping group sparsity structure. We consider a combination of a loss function and a regularizer to recover the desired group sparsity patterns, which can embrace many existing works. We analyze the stationary solution of the proposed formulation, obtaining a sufficient condition … Read more

    A generalized block-iterative projection method for the common fixed point problem induced by cutters

  • Yair Censor
  • Daniel Reem
  • Maroun Zaknoon
    • Categories Convex Optimization, Nonlinear Optimization Tags , , , ,

    The block-iterative projections (BIP) method of Aharoni and Censor [Block-iterative projection methods for parallel computation of solutions to convex feasibility problems, Linear Algebra and its Applications 120, (1989), 165-175] is an iterative process for finding asymptotically a point in the nonempty intersection of a family of closed convex subsets. It employs orthogonal projections onto the … Read more

    Convexity and continuity of specific set-valued maps and their extremal value functions

  • Gabriele Eichfelder
  • Tobias Gerlach
  • Stefan Rocktäschel
    • Categories Convex Optimization, Generalized Convexity/Monoticity, Nonlinear Optimization Tags , , ,

    In this paper, we study several classes of set-valued maps, which can be used in set-valued optimization and its applications, and their respective maximum and minimum value functions. The definitions of these maps are based on scalar-valued, vector-valued, and cone-valued maps. Moreover, we consider those extremal value functions which are obtained when optimizing linear functionals … Read more

    Models for two- and three-stage two-dimensional cutting stock problems with a limited number of open stacks

  • Mateus Martin
  • Horacio Hideki Yanasse
  • Maristela O. Santos
  • Reinaldo Morabito
    • Categories Production and Logistics Tags , , ,

    We address three variants of the two-dimensional cutting stock problem in which the guillotine cutting of large objects produces a set of demanded items. The characteristics of the variants are: the rectangular shape of the objects and items; the number of two or three orthogonal guillotine stages; and, a sequencing constraint that limits the number … Read more

    A Route-Based Algorithm for the Electric Vehicle Routing Problem with Multiple Technologies

  • Dario Bezzi
  • Alberto Ceselli
  • Giovanni Righini
    • Categories Applications - OR and Management Sciences Tags , , ,

    We consider a variant of the electric vehicle routing problem: a fleet of identical vehicles of limited capacity needs to visit a set of customers with given demands. An upper limit is imposed on the duration of the routes. Vehicles have limited autonomy: they may need to stop en-route at recharge stations. Recharges can be … Read more

    A practical second-order optimality condition for cardinality-constrained problems with application to an augmented Lagrangian method

  • Jean C. A. Medeiros
  • Ademir A. Ribeiro
  • Mael Sachine
  • Leonardo D. Secchin
    • Categories Nonlinear Optimization Tags , ,

    This paper addresses the mathematical programs with cardinality constraints (MPCaC). We first define two new tailored (strong and weak) second-order necessary conditions, MPCaC-SSONC and MPCaC-WSONC. We then propose a constraint qualification (CQ), namely, MPCaC-relaxed constant rank constraint qualification (MPCaC-RCRCQ), and establish the validity of MPCaC-SSONC at minimizers under this new CQ. All the concepts proposed … Read more