Optimization and Control (math.OC)

Abstract: We consider a class of stochastic smooth convex optimization problems under rather general assumptions on the noise in the stochastic gradient observation. As opposed to the classical problem setting in which the variance of noise is assumed to be uniformly bounded, herein we assume that the variance of stochastic gradients is related to the "sub-optimality" of the approximate solutions delivered by the algorithm. Such problems naturally arise in a variety of applications, in particular, in the well-known generalized linear regression problem in statistics. However, to the best of our knowledge, none of the existing stochastic approximation algorithms for solving this class of problems attain optimality in terms of the dependence on accuracy, problem parameters, and mini-batch size. We discuss two non-Euclidean accelerated stochastic approximation routines--stochastic accelerated gradient descent (SAGD) and stochastic gradient extrapolation (SGE)--which carry a particular duality relationship. We show that both SAGD and SGE, under appropriate conditions, achieve the optimal convergence rate, attaining the optimal iteration and sample complexities simultaneously. However, corresponding assumptions for the SGE algorithm are more general; they allow, for instance, for efficient application of the SGE to statistical estimation problems under heavy tail noises and discontinuous score functions. We also discuss the application of the SGE to problems satisfying quadratic growth conditions, and show how it can be used to recover sparse solutions. Finally, we report on some simulation experiments to illustrate numerical performance of our proposed algorithms in high-dimensional settings.

Abstract: This paper addresses the analysis of a boundary feedback system involving a non-homogeneous Euler-Bernoulli beam governed by the equation $m(x)u_{tt}+\mu(x)u_{t}$$+\left(r(x)u_{xx}\right)_{xx}=0$, subject to the initial $u(x,0)=u_0(x)$, $u_t(x,0)=v_0(x)$ and boundary conditions $u(0,t)=0$, $\left (-r(x)u_{xx}(x,t)\right )_{x=0}=-k^{-}_r u_{x}(0,t)-k^{-}_a u_{xt}(0,t)$, $u(\ell,t)=0$, $\left (-r(x)u_{xx}(x,t)\right )_{x=\ell}=-k^{+}_r u_{x}(\ell,t)-k^{+}_a u_{xt}(\ell,t)$, with boundary control at both ends resulting from the rotation and angular velocity. The approach proposed in this study relies on the utilization of regular weak solutions, energy identity, and a physically motivated Lyapunov function. By imposing natural assumptions concerning physical parameters and other inputs, which ensure the existence of a regular weak solution, we successfully derive a uniform exponential decay estimate for the system's energy. The decay rate constant featured in this estimate is solely dependent on the physical and geometric properties of the beam. These properties encompass crucial parameters such as the viscous external damping coefficient $\mu(x)$, as well as the boundary springs $k^{-}_r,k^+_r $ and dampers $k^{-}_a,k^+_a$. To illustrate the practical effectiveness of our theoretical findings, numerical examples are provided. These examples serve to demonstrate the applicability and relevance of our derived results in real-world scenarios.

Abstract: Let $E\subset \mathbb R^n$, $n\ge 2$, be a set of finite perimeter with $|E|=|B|$, where $B$ denotes the unit ball. When $n=2$, since convexification decreases perimeter (in the class of open connected sets), it is easy to prove the existence of a convex set $F$, with $|E|=|F|$, such that $$ P(E) - P(F) \ge c\,|E\Delta F|, \qquad c>0. $$ Here we prove that, when $n\ge 3$, there exists a convex set $F$, with $|E|=|F|$, such that $$ P(E) - P(F) \ge c(n) \,f\big(|E\Delta F|\big), \qquad c(n)>0,\qquad f(t)=\frac{t}{|\log t|} \text{ for }t \ll 1. $$ Moreover, one can choose $F$ to be a small $C^2$-deformation of the unit ball. Furthermore, this estimate is essentially sharp as we can show that the inequality above fails for $f(t)=t.$ Interestingly, the proof of our result relies on a new stability estimate for Alexandrov's Theorem on constant mean curvature sets.

Abstract: The decentralized optimization paradigm assumes that each term of a finite-sum objective is privately stored by the corresponding agent. Agents are only allowed to communicate with their neighbors in the communication graph. We consider the case when the agents additionally have local affine constraints and the communication graph can change over time. We provide the first linearly convergent decentralized algorithm for time-varying networks by generalizing the optimal decentralized algorithm ADOM to the case of affine constraints. We show that its rate of convergence is optimal for first-order methods by providing the lower bounds for the number of communications and oracle calls.

Abstract: We investigate the notion of Wasserstein median as an alternative to the Wasserstein barycenter, which has become popular but may be sensitive to outliers. In terms of robustness to corrupted data, we indeed show that Wasserstein medians have a breakdown point of approximately $\frac{1}{2}$. We give explicit constructions of Wasserstein medians in dimension one which enable us to obtain $L^p$ estimates (which do not hold in higher dimensions). We also address dual and multimarginal reformulations. In convex subsets of $\mathbb{R}^d$, we connect Wasserstein medians to a minimal (multi) flow problem \`a la Beckmann and a system of PDEs of Monge-Kantorovich-type, for which we propose a $p$-Laplacian approximation. Our analysis eventually leads to a new numerical method to compute Wasserstein medians, which is based on a Douglas-Rachford scheme applied to the minimal flow formulation of the problem.

Abstract: AC optimal power flow (AC OPF) is a fundamental problem in power system operation and control. Accurately modeling the network physics via the AC power flow equations makes AC OPF a challenging nonconvex problem that results in significant computational challenges. To search for global optima, recent research has developed a variety of convex relaxations to bound the optimal objective values of AC OPF problems. However, the quality of these bounds varies for different test cases, suggesting that OPF problems exhibit a range of difficulties. Understanding this range of difficulty is helpful for improving relaxation algorithms. Power grids are naturally represented as graphs, with buses as nodes and power lines as edges. Graph theory offers various methods to measure power grid graphs, enabling researchers to characterize system structure and optimize algorithms. Leveraging graph theory-based algorithms, this paper presents an empirical study aiming to find correlations between optimality gaps and local structures in the underlying test case's graph. Network graphlets, which are induced subgraphs of a network, are used to investigate the correlation between power system topology and OPF relaxation tightness. Specifically, this paper examines how the existence of particular graphlets that are either too frequent or infrequent in the power system graph affects the tightness of the OPF convex relaxation. Numerous test cases are analyzed from a local structural perspective to establish a correlation between their topology and their OPF convex relaxation tightness.

Abstract: Power systems often include a specific set of lines that are crucial for the regular operations of the grid. Identifying the reasons behind the criticality of these lines is an important challenge in power system studies. When a line fails, the line outage distribution factor (LODF) quantifies the changes in power flow on the remaining lines. This paper proposes a network analysis from a local structural perspective to investigate the impact of local structural patterns in the underlying graph of power systems on the LODF of individual lines. In particular, we focus on graphlet analysis to determine the local structural properties of each line. This research analyzes potential connections between specific graphlets and the most critical lines based on their LODF. In this regard, we investigate N-1 and N-2 contingency analysis for various test cases and identifies the lines that have the greatest impact on the LODFs of other lines. We then determine which subgraphs contain the most significant lines. Our findings reveal that the most critical lines often belong to subgraphs with a less meshed but more radial structure. These findings are further validated through various test cases. Particularly, it is observed that networks with a higher percentage of ring or meshed subgraphs on their most important line (based on LODF) experience a lower LODF when that critical line is subject to an outage. Additionally, we investigate how the LODF of the most critical line varies among different test cases and examine the subgraph characteristics of those critical lines.