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
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
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
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
We study oracle-complexity lower bounds for first-order methods applied to smooth equality-constrained nonconvex optimization, separating two components of approximate KKT accuracy: feasibility and stationarity. Under iteration-wise Jacobian regularity, we prove a lower bound of order \(\Omega(\frac{L_c\Delta_c}{\sigma^2}+\log\log(\frac{\sigma^2}{L_c\epsilon}))\) to achieve \(\epsilon\)-feasibility. For stationarity, we construct a nonlinear equality-constrained hard instance whose multiplier-minimized stationarity residual reduces exactly to … Read more
In this paper, we study nonconvex equality-constrained optimization problems in which only stochastic first-order approximations of the objective and constraint functions are available. Owing to the stochasticity in both objective and constraints, most existing stochastic first-order methods incur relatively high oracle complexity, particularly in terms of stochastic constraint function evaluations. To address this issue, we … Read more
Variable projection is a classical technique for separable nonlinear least-squares problems, in which variables that enter linearly are eliminated exactly, yielding a reduced nonlinear problem. By expressing this framework as a particular instance of a broader class of bilevel optimization problems, we develop a constrained variable-projection framework for data-science models, where the remaining variables are … Read more
We study exact semidefinite programming (SDP) relaxation for a given sparse quadratically constrained quadratic program (QCQP). The SDP relaxation is exact if, whenever it has an optimal solution, it admits a rank-at-most-one optimal solution that corresponds to an optimal solution of the QCQP. Using the maximal cliques of a chordal extension of the aggregate sparsity … Read more
We present the Quadratic-Quasi-Newton (QQN) algorithm, a novel optimization method that combines gradient descent and quasi-Newton directions through quadratic interpolation. QQN constructs a parametric path d(t) = t(1 − t)(−∇f) + t 2 d L-BFGS and performs univariate optimization along this path, creating an adaptive interpolation that requires no additional hyperparameters beyond those of its … Read more
Modern experimentation in business and public policy often studies targeted interventions whose effects depend on the heterogeneous attributes of individuals. We examine heterogeneous treatment effects through the lens of optimal design of experiments, which allocates treatment decisions to maximize the precision of estimated treatment-covariate interactions. We introduce the D-optimal partitioning problem for balancing the information … Read more