Constrained Nonlinear Optimization

Constrained stochastic blackbox optimization using a progressive barrier and probabilistic estimates

  • Kwassi Joseph Dzahini
  • Michael Kokkolaras
  • Sébastien Le Digabel
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Stochastic Approaches Tags , , ,

    This work introduces the StoMADS-PB algorithm for constrained stochastic blackbox optimization, which is an extension of the mesh adaptive direct-search (MADS) method originally developed for deterministic blackbox optimization under general constraints. The values of the objective and constraint functions are provided by a noisy blackbox, i.e., they can only be computed with random noise whose … Read more

    Exterior-point Optimization for Nonconvex Learning

  • Shuvomoy Das Gupta
  • Bartolomeo Stellato
  • Bart Paul Gerard Van Parys
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization, Statistics Tags , , ,

    In this paper we present the nonconvex exterior-point optimization solver (NExOS)—a novel first-order algorithm tailored to constrained nonconvex learning problems. We consider the problem of minimizing a convex function over nonconvex constraints, where the projection onto the constraint set is single-valued around local minima. A wide range of nonconvex learning problems have this structure including … Read more

    A Reformulation-Linearization Technique for Optimization over Simplices

  • Aras Selvi
  • Dick den Hertog
  • Wolfram Wiesemann
    • Categories Constrained Nonlinear Optimization, Global Optimization, Global Optimization Theory Tags , ,

    We study non-convex optimization problems over simplices. We show that for a large class of objective functions, the convex approximation obtained from the Reformulation-Linearization Technique (RLT) admits optimal solutions that exhibit a sparsity pattern. This characteristic of the optimal solutions allows us to conclude that (i) a linear matrix inequality constraint, which is often added … Read more

    An Inertial Block Majorization Minimization Framework for Nonsmooth Nonconvex Optimization

  • Nicolas Gillis
  • Le Thi Khanh Hien
  • Duy Nhat Phan
    • Categories Constrained Nonlinear Optimization Tags , , , , ,

    In this paper, we introduce TITAN, a novel inerTial block majorIzation minimization framework for non-smooth non-convex opTimizAtioN problems. TITAN is a block coordinate method (BCM) that embeds inertial force to each majorization-minimization step of the block updates. The inertial force is obtained via an extrapolation operator that subsumes heavy-ball and Nesterov-type accelerations for block proximal … Read more

    Tight bounds on the maximal perimeter and the maximal width of convex small polygons

  • Christian Bingane
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Quadratic Programming Tags , , , , ,

    A small polygon is a polygon of unit diameter. The maximal perimeter and the maximal width of a convex small polygon with $n=2^s$ vertices are not known when $s \ge 4$. In this paper, we construct a family of convex small $n$-gons, $n=2^s$ and $s\ge 3$, and show that the perimeters and the widths obtained … Read more

    Optimizing hypergraph-based polynomials modeling job-occupancy in queueing with redundancy scheduling

  • Daniel Brosch
  • Monique Laurent
  • Andries Steenkamp
    • Categories Constrained Nonlinear Optimization Tags , , ,

    We investigate two classes of multivariate polynomials with variables indexed by the edges of a uniform hypergraph and coefficients depending on certain patterns of union of edges. These polynomials arise naturally to model job-occupancy in some queuing problems with redundancy scheduling policy. The question, posed by Cardinaels, Borstand van Leeuwaarden (arXiv:2005.14566, 2020), is to decide … Read more

    Global optimality in minimum compliance topology optimization of frames and shells by moment-sum-of-squares hierarchy

  • Didier Henrion
  • Martin Kružík
  • Marek Tyburec
  • Jan Zeman
    • Categories Civil and Environmental Engineering, Constrained Nonlinear Optimization, Semi-definite Programming Tags , , , , ,

    The design of minimum-compliance bending-resistant structures with continuous cross-section parameters is a challenging task because of its inherent non-convexity. Our contribution develops a strategy that facilitates computing all guaranteed globally optimal solutions for frame and shell structures under multiple load cases and self-weight. To this purpose, we exploit the fact that the stiffness matrix is … Read more

    Regret Minimization in Stochastic Non-Convex Learning via a Proximal-Gradient Approach

  • Volkan Cevher
  • Nadav Hallak
  • Panayotis Mertikopoulos
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization

    Motivated by applications in machine learning and operations research, we study regret minimization with stochastic first-order oracle feedback in online constrained, and possibly non-smooth, non-convex problems. In this setting, the minimization of external regret is beyond reach, so we focus on a local regret measures defined via a proximal-gradient residual mapping. To achieve no (local) … Read more

    Inexact Variable Metric Method for Convex-Constrained Optimization Problems

  • Douglas S. Gonçalves
  • Max L. N. Gonçalves
  • Tiago Menezes
    • Categories Constrained Nonlinear Optimization

    This paper is concerned with the inexact variable metric method for solving convex-constrained optimization problems. At each iteration of this method, the search direction is obtained by inexactly minimizing a strictly convex quadratic function over the closed convex feasible set. Here, we propose a new inexactness criterion for the search direction subproblems. Under mild assumptions, … Read more

    Largest small polygons: A sequential convex optimization approach

  • Christian Bingane
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Quadratic Programming Tags , , , , ,

    A small polygon is a polygon of unit diameter. The maximal area of a small polygon with $n=2m$ vertices is not known when $m\ge 7$. Finding the largest small $n$-gon for a given number $n\ge 3$ can be formulated as a nonconvex quadratically constrained quadratic optimization problem. We propose to solve this problem with a … Read more