Nonlinear Optimization

Order-2 Tightness of Block-Sparse SOS Relaxations for One-Layer ReLU Network Verification with a Matching Input-Sharing Graph

Categories Data Science Theory, Quadratic Programming, Semi-definite Programming Tags , , , ,

Azuma, Kim, and Yamashita formulated the verification problem for one-layer ReLU networks as a quadratically constrained quadratic program and established tight semidefinite relaxations for the edgeless case and for one-unit settings. In this work, we represent the sharing pattern of undecided ReLUs over a box input set through an input-sharing graph and focus on the … Read more

Convexlikeness and Supportedness in Quadratic Multiobjective Optimization

Categories Multi-Criteria Optimization, Quadratic Programming Tags , , , , , , ,

This paper studies geometric and structural properties of quadratic multiobjective optimization problems. Thereby, a multiobjective optimization problem is called convexlike if the upper image, i.e., the image set plus the nonnegative orthant, is a convex set. Moreover, we say that a feasible point is supported in case it is a minimal solution of a weighted … Read more

Robust Chance-Constrained Optimization using a Continuous Parameter Space Wasserstein-2 Ambiguity Set of Gaussian Mixtures

Categories Nonlinear Optimization, Robust Optimization, Stochastic Programming Tags , , , ,

We study distributionally robust linear chance-constrained problems in which uncertainty is modeled by a Gaussian mixture model (GMM). Finite-support distributionally robust (FDR) formulations, widely used in data-driven robust optimization, robustify over empirical mixture support points and therefore primarily stress-test the fitted nominal mixture. This can be insufficient when service reliability depends on structural misspecification of … Read more

Tight Conic Relaxations for Rank-one Doubly Nonnegative Matrix Completion

Categories Cone Programming, Global Optimization Applications, Quadratic Programming Tags , , , ,

We study tight conic relaxations for a quadratically constrained quadratic programming (QCQP) formulation of rank-one doubly nonnegative (DNN) matrix completion. Motivated by sparse QCQPs whose lifted matrix variables include elements not directly specified by the objective or constraints, we interpret tightness as a rank-one completion property for the unspecified elements. For sparsity patterns whose blocks … Read more

Exploring polynomial models in the Search Step of Direct Multisearch

Categories Multi-Criteria Optimization, Nonlinear Optimization Tags , , , ,

Direct Multisearch (DMS) is a class of direct-search algorithms designed for multiobjective derivative-free optimization. Its framework consists of an optional search step and a poll step, the latter ensuring the corresponding theoretical convergence properties. Recently, a search strategy based on the minimization of quadratic polynomial models, constructed from previously evaluated points, was proposed to improve … Read more

Adaptive Scenario Partitioning for Stochastic Bilevel Linear Programs

Categories Bilevel Optimization, Constrained Nonlinear Optimization, Stochastic Programming Tags , , , ,

This paper develops an adaptive scenario partitioning approach for stochastic bilevel linear programs. The method extends the Adaptive Partitioning Method, originally designed for two-stage stochastic programs, to settings in which a leader makes a first-stage decision while anticipating scenario dependent optimal responses from a follower. The proposed approach solves a sequence of aggregated master problems … Read more

Parallel versions of the mesh adaptive direct search algorithm

Categories Nonlinear Optimization, Optimization Software and Modeling Systems, Parallel Algorithms Tags , , ,

This work surveys the different parallel variants of the mesh adaptive direct search (MADS) algorithm for constrained blackbox optimization. These problems can inherently imply high computational costs due to the possible large number of variables and multi-modality of the search space. In addition, the potential time-intensive nature and time heterogeneity of the blackboxes defining the … Read more

A Direction Adaptation Evaluation Strategy for Noisy Derivative-Free Optimization

Categories Global Optimization, Nonlinear Optimization Tags , , , , ,

In this paper, we develop a direction adaptation evolution strategy (DAES)—a new MAES-type method—for noisy derivative-free optimization, designed to reconcile the population-based search mechanisms of evolution strategies with rigorous complexity analysis. Unlike standard MAES schemes, DAES fixes the adaptation matrix to the identity and replaces matrix adaptation with a structured direction-generation mechanism based on symmetric … Read more

bAdag: an adaptive block coordinate gradient method for smooth nonconvex functions

Categories Data Science Algorithms, Unconstrained Optimization Tags , , ,

A new Block Coordinate Gradient (BCG) method, dubbed bAdag, for smooth, nonconvex minimization problem is proposed; it falls in the class of Objective Function Free Optimization (OFFO) methods, and it is based on the AdaGrad algorithm. At each iteration, our method computes an adaptive step size based on the cumulative sum of block gradients, instead … Read more

GPU-accelerated superiorization on constrained physical problems with SupPy

Categories Applications - OR and Management Sciences, Biomedical Applications, Constrained Nonlinear Optimization Tags , , , , ,

The superiorization method (SM) is situated between feasibility-seeking and constrained optimization. Instead of aiming at the minimum of a given objective function over a constraint set, it seeks a feasible point at which the objective function value is reduced — though not necessarily minimal — compared to that reached by the feasibility-seeking algorithm alone. This … Read more