More Like this

1. A Single Recipe for Online Submodular Maximization with Adversarial or Stochastic Constraints

   Sadeghi, Omid; Raut, Prasanna; Fazel, Maryam (December 2020, Advances in neural information processing systems)

   null; null; null; null; null (Ed.)

   We consider an online optimization problem in which the reward functions are DR-submodular, and in addition to maximizing the total reward, the sequence of decisions must satisfy some convex constraints on average. Specifically, at each round t, upon committing to an action x_t, a DR-submodular utility function f_t and a convex constraint function g_t are revealed, and the goal is to maximize the overall utility while ensuring the average of the constraint functions is non-positive (so constraints are satisfied on average). Such cumulative constraints arise naturally in applications where the average resource consumption is required to remain below a specified threshold. We study this problem under an adversarial model and a stochastic model for the convex constraints, where the functions g_t can vary arbitrarily or according to an i.i.d. process over time. We propose a single algorithm which achieves sub-linear regret (with respect to the time horizon T) as well as sub-linear constraint violation bounds in both settings, without prior knowledge of the regime. Prior works have studied this problem in the special case of linear constraint functions. Our results not only improve upon the existing bounds under linear cumulative constraints, but also give the first sub-linear bounds for general convex long-term constraints. 

   more » « less
2. Minimum-Time Charging of Energy Storage in Microgrids via Approximate Conic Relaxation

   https://doi.org/10.23919/ECC51009.2020.9143992  

   Guthrie, James; Mallada, Enrique (May 2020, 2020 European Control Conference)

   null (Ed.)

   We study the problem of maximizing energy transfer to a load in a DC microgrid while respecting constraints on bus voltages and currents, and accounting for the impact of neighboring constant power loads. Both the objective and dynamics give rise to indefinite quadratic terms, resulting in a non-convex optimization problem. Through change of variables and relaxations we develop a closely related second-order cone program. The problem retains the same feasible set as the original problem but utilizes a linear approximation of the non-convex objective. We demonstrate how this can be used to design approximately optimal charging profiles for periodic pulsed loads in real time. 

   more » « less
3. Minimum-time charging of energy storage in microgrids via approximate conic relaxation

   Guthrie, James; Mallada, Enrirque (May 2020, European Control Conference)

   We study the problem of maximizing energy transfer to a load in a DC microgrid while respecting constraints on bus voltages and currents, and accounting for the impact of neighboring constant power loads. Both the objective and dynamics give rise to indefinite quadratic terms, resulting in a non-convex optimization problem. Through change of variables and relaxations we develop a closely related second-order cone program. The problem retains the same feasible set as the original problem but utilizes a linear approximation of the non-convex objective. We demonstrate how this can be used to design approximately optimal charging profiles for periodic pulsed loads in real time. 

   more » « less
4. A unifying framework of high-dimensional sparse estimation with dierence-of-convex (DC) regularization

   Cao, Shanshan; Huo, Xiaoming; Pang, Jong-Shi (August 2021, Statistical science)

   null (Ed.)

   Under the linear regression framework, we study the variable selection problem when the underlying model is assumed to have a small number of nonzero coefficients. Non-convex penalties in speci c forms are well-studied in the literature for sparse estimation. A recent work, Ahn, Pang, and Xin (2017), has pointed out that nearly all existing non-convex penalties can be represented as difference-of-convex (DC) functions, which are the difference of two convex functions, while itself may not be convex. There is a large existing literature on optimization problems when their objectives and/or constraints involve DC functions. Efficient numerical solutions have been proposed. Under the DC framework, directional-stationary (d-stationary) solutions are considered, and they are usually not unique. In this paper, we show that under some mild conditions, a certain subset of d-stationary solutions in an optimization problem (with a DC objective) has some ideal statistical properties: namely, asymptotic estimation consistency, asymptotic model selection consistency, asymptotic efficiency. Our assumptions are either weaker than or comparable with those conditions that have been adopted in other existing works. This work shows that DC is a nice framework to offer a uni ed approach to these existing works where non-convex penalties are involved. Our work bridges the communities of optimization and statistics. 

   more » « less
5. Block-Structured Optimization for Anomalous Pattern Detection in Interdependent Networks

   https://doi.org/10.1109/ICDM.2019.00137  

   Jie, Fei; Wang, Chunpai; Chen, Feng; Li, Lei; Wu, Xindong (November 2019, 2019 IEEE International Conference on Data Mining (ICDM))

   We propose a generalized optimization framework for detecting anomalous patterns (subgraphs that are interesting or unexpected) in interdependent networks, such as multi-layer networks, temporal networks, networks of networks, and many others. We frame the problem as a non-convex optimization that has a general nonlinear score function and a set of block-structured and non-convex constraints. We develop an effective, efficient, and parallelizable projection-based algorithm, namely Graph Block-structured Gradient Projection (GBGP), to solve the problem. It is proved that our algorithm 1) runs in nearly-linear time on the network size, and 2) enjoys a theoretical approximation guarantee. Moreover, we demonstrate how our framework can be applied to two very practical applications, and we conduct comprehensive experiments to show the effectiveness and efficiency of our proposed algorithm. 

   more » « less