More Like this

1. Comparing solution paths of sparse quadratic minimization with a Stieltjes matrix

   https://doi.org/10.1007/s10107-023-01966-0  

   He, Ziyu ; Han, Shaoning ; Gómez, Andrés ; Cui, Ying ; Pang, Jong-Shi ( May 2023 , Mathematical Programming)

   This paper studies several solution paths of sparse quadratic minimization problems as a function of the weighing parameter of the bi-objective of estimation loss versus solution sparsity. Three such paths are considered: the “$$\ell _0$$${\ell }_0$-path” where the discontinuous$$\ell _0$$${\ell }_0$-function provides the exact sparsity count; the “$$\ell _1$$${\ell }_1$-path” where the$$\ell _1$$${\ell }_1$-function provides a convex surrogate of sparsity count; and the “capped$$\ell _1$$${\ell }_1$-path” where the nonconvex nondifferentiable capped$$\ell _1$$${\ell }_1$-function aims to enhance the$$\ell _1$$${\ell }_1$-approximation. Serving different purposes, each of these three formulations is different from each other, both analytically and computationally. Our results deepen the understanding of (old and new) properties of the associated paths, highlight the pros, cons, and tradeoffs of these sparse optimization models, and provide numerical evidence to support the practical superiority of the capped$$\ell _1$$${\ell }_1$-path. Our study of the capped$$\ell _1$$${\ell }_1$-path is interesting in its own right as the path pertains to computable directionally stationary (= strongly locally minimizing in this context, as opposed to globally optimal) solutions of a parametric nonconvex nondifferentiable optimization problem. Motivated by classical parametric quadratic programming theory and reinforced by modern statistical learning studies, both casting an exponential perspective in fully describing such solution paths, we also aim to address the question of whether some of them can be fully traced in strongly polynomial time in the problem dimensions. A major conclusion of this paper is that a path of directional stationary solutions of the capped$$\ell _1$$${\ell }_1$-regularized problem offers interesting theoretical properties and practical compromise between the$$\ell _0$$${\ell }_0$-path and the$$\ell _1$$${\ell }_1$-path. Indeed, while the$$\ell _0$$${\ell }_0$-path is computationally prohibitive and greatly handicapped by the repeated solution of mixed-integer nonlinear programs, the quality of$$\ell _1$$${\ell }_1$-path, in terms of the two criteria—loss and sparsity—in the estimation objective, is inferior to the capped$$\ell _1$$${\ell }_1$-path; the latter can be obtained efficiently by a combination of a parametric pivoting-like scheme supplemented by an algorithm that takes advantage of the Z-matrix structure of the loss function.

    

   more » « less
2. Control of a consumer‐resource agent‐based model using partial differential equation approximation

   https://doi.org/10.1002/oca.2778  

   Fitzpatrick, Ben G. ; Federico, Paula ; Kanarek, Andrew ; Lenhart, Suzanne ( August 2021 , Optimal Control Applications and Methods)

   Agent‐based models (ABMs) are increasing in popularity as tools to simulate and explore many biological systems. Successes in simulation lead to deeper investigations, from designing systems to optimizing performance. The typically stochastic, rule‐based structure of ABMs, however, does not lend itself to analytic and numerical techniques of optimization the way traditional dynamical systems models do. The goal of this work is to illustrate a technique for approximating ABMs with a partial differential equation (PDE) system to design some management strategies on the ABM. We propose a surrogate modeling approach, using differential equations that admit direct means of determining optimal controls, with a particular focus on environmental heterogeneity in the ABM. We implement this program with both PDE and ordinary differential equation (ODE) approximations on the well‐known rabbits and grass ABM, in which a pest population consumes a resource. The control problem addressed is the reduction of this pest population through an optimal control formulation. After fitting the ODE and PDE models to ABM simulation data in the absence of control, we compute optimal controls using the ODE and PDE models, which we them apply to the ABM. The results show promise for approximating ABMs with differential equations in this context.

    

   more » « less
3. Learning sparse nonparametric DAGs

   Zheng, Xun ; Dan, Chen ; Aragam, Bryon ; Ravikumar, Pradeep ; Xing, Eric ( July 2020 , International Conference on Artificial Intelligence and Statistics)

   null (Ed.)

   We develop a framework for learning sparse nonparametric directed acyclic graphs (DAGs) from data. Our approach is based on a recent algebraic characterization of DAGs that led to a fully continuous program for score-based learning of DAG models parametrized by a linear structural equation model (SEM). We extend this algebraic characterization to nonparametric SEM by leveraging nonparametric sparsity based on partial derivatives, resulting in a continuous optimization problem that can be applied to a variety of nonparametric and semiparametric models including GLMs, additive noise models, and index models as special cases. Unlike existing approaches that require specific modeling choices, loss functions, or algorithms, we present a completely general framework that can be applied to general nonlinear models (e.g. without additive noise), general differentiable loss functions, and generic black-box optimization routines. 

   more » « less
4. Learning Sparse Nonparametric DAGs

   Zheng, X. ; Dan, C. ; Aragam, B. ; Ravikumar, P. ; Xing, E. ( April 2020 , Proceedings of Machine Learning Research)

   We develop a framework for learning sparse nonparametric directed acyclic graphs (DAGs) from data. Our approach is based on a recent algebraic characterization of DAGs that led to a fully continuous program for scorebased learning of DAG models parametrized by a linear structural equation model (SEM). We extend this algebraic characterization to nonparametric SEM by leveraging nonparametric sparsity based on partial derivatives, resulting in a continuous optimization problem that can be applied to a variety of nonparametric and semiparametric models including GLMs, additive noise models, and index models as special cases. Unlike existing approaches that require specific modeling choices, loss functions, or algorithms, we present a completely general framework that can be applied to general nonlinear models (e.g. without additive noise), general differentiable loss functions, and generic black-box optimization routines. 

   more » « less
5. Global optimization of stiff dynamical systems

   https://doi.org/10.1002/aic.16836  

   Wilhelm, Matthew E. ; Le, Anne V. ; Stuber, Matthew D. ( November 2019 , AIChE Journal)

   We present a deterministic global optimization method for nonlinear programming formulations constrained by stiff systems of ordinary differential equation (ODE) initial value problems (IVPs). The examples arise from dynamic optimization problems exhibiting both fast and slow transient phenomena commonly encountered in model‐based systems engineering applications. The proposed approach utilizes unconditionally stable implicit integration methods to reformulate the ODE‐constrained problem into a nonconvex nonlinear program (NLP) with implicit functions embedded. This problem is then solved to global optimality in finite time using a spatial branch‐and‐bound framework utilizing convex/concave relaxations of implicit functions constructed by a method which fully exploits problem sparsity. The algorithms were implemented in the Julia programming language within the EAGO.jl package and demonstrated on five illustrative examples with varying complexity relevant in process systems engineering. The developed methods enable the guaranteed global solution of dynamic optimization problems with stiff ODE–IVPs embedded.

    

   more » « less