Two-Timescale Optimization Framework for Decentralized Linear-Quadratic Optimal Control

• URL: http://arxiv.org/abs/2406.11168v3
• Date: Thu, 22 Aug 2024 04:16:42 GMT
• Title: Two-Timescale Optimization Framework for Decentralized Linear-Quadratic Optimal Control
• Authors: Lechen Feng, Yuan-Hua Ni, Xuebo Zhang,
• Abstract summary: A $mathcal$-guaranteed linear decentralized-quadratic optimal control with convex parameterization convex-bounded uncertainty is studied.
• Score: 3.746304628644379
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A $\mathcal{H}_2$-guaranteed decentralized linear-quadratic optimal control with convex parameterization and convex-bounded uncertainty is studied in this paper, where several sparsity promoting functions are added, respectively, into the $\mathcal{H}_2$ cost to penalize the number of communication links among decentralized controllers. Then, the sparse feedback gain is investigated to minimize the modified $\mathcal{H}_2$ cost together with the stability guarantee, and the corresponding main results are of three parts. First, the weighted-$\ell_1$ sparsity promoting function is of concern, and a two-timescale algorithm is developed based on the BSUM (Block Successive Upper-bound Minimization) framework and a primal-dual splitting approach. Second, the optimization problem induced by piecewise quadratic sparsity penalty is investigated, which exhibits an accelerated convergence rate. Third, the nonconvex sparse optimization problem with $\ell_0$-penalty is studied, which can be approximated by successive coordinatewise convex optimization problems.

Related papers

• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  We propose two variance reduced ZO estimators for complex gradient problems. We improve the state-of-the-art function complexities from $mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$ to $tildecalOleft(fracdepsilon2right)$.
  arXiv  Detail & Related papers  (2024-10-03T15:04:01Z)
• Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
  We focus on the class of (strongly) convex $(L0)$-smooth functions and derive new convergence guarantees for several existing methods. In particular, we derive improved convergence rates for Gradient Descent with smoothnessed Gradient Clipping and for Gradient Descent with Polyak Stepsizes.
  arXiv  Detail & Related papers  (2024-09-23T13:11:37Z)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  We consider the problem of optimizing second-order smooth and strongly convex functions where the algorithm is only accessible to noisy evaluations of the objective function it queries. We provide the first tight characterization for the rate of the minimax simple regret by developing matching upper and lower bounds.
  arXiv  Detail & Related papers  (2024-06-28T02:56:22Z)
• Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient [40.22217106270146]
  Variance reduction techniques are designed to decrease the sampling variance, thereby accelerating convergence rates of first-order (FO) and zeroth-order (ZO) optimization methods. In composite optimization problems, ZO methods encounter an additional variance called the coordinate-wise variance, which stems from the random estimation. This paper proposes the Zeroth-order Proximal Double Variance Reduction (ZPDVR) method, which utilizes the averaging trick to reduce both sampling and coordinate-wise variances.
  arXiv  Detail & Related papers  (2024-05-28T02:27:53Z)
• Faster Convergence with Multiway Preferences [99.68922143784306]
  We consider the sign-function-based comparison feedback model and analyze the convergence rates with batched and multiway comparisons. Our work is the first to study the problem of convex optimization with multiway preferences and analyze the optimal convergence rates.
  arXiv  Detail & Related papers  (2023-12-19T01:52:13Z)
• ALEXR: An Optimal Single-Loop Algorithm for Convex Finite-Sum Coupled Compositional Stochastic Optimization [53.14532968909759]
  We introduce an efficient single-loop primal-dual block-coordinate algorithm, dubbed ALEXR. We establish the convergence rates of ALEXR in both convex and strongly convex cases under smoothness and non-smoothness conditions. We present lower complexity bounds to demonstrate that the convergence rates of ALEXR are optimal among first-order block-coordinate algorithms for the considered class of cFCCO problems.
  arXiv  Detail & Related papers  (2023-12-04T19:00:07Z)
• Non-Smooth Weakly-Convex Finite-sum Coupled Compositional Optimization [42.861002114813864]
  This paper investigates new families of compositional optimization problems, called $linebf n$on-underline underlinebf sakly underlinebf c$ompositional $underlineunderline.
  arXiv  Detail & Related papers  (2023-10-05T01:01:09Z)
• Oracle Complexity Reduction for Model-free LQR: A Stochastic Variance-Reduced Policy Gradient Approach [4.422315636150272]
  We investigate the problem of learning an $epsilon$-approximate solution for the discrete-time Linear Quadratic Regulator (LQR) problem. Our method combines both one-point and two-point estimations in a dual-loop variance-reduced algorithm.
  arXiv  Detail & Related papers  (2023-09-19T15:03:18Z)
• Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reduction [26.9632099249085]
  We propose two new variants of SPS and SLS, called AdaSPS and AdaSLS, which guarantee convergence in non-interpolation settings. We equip AdaSPS and AdaSLS with a novel variance reduction technique and obtain algorithms that require $smashwidetildemathcalO(n+1/epsilon)$ gradient evaluations.
  arXiv  Detail & Related papers  (2023-08-11T10:17:29Z)
• Stochastic Nested Compositional Bi-level Optimization for Robust Feature Learning [11.236838268731804]
  We develop and analyze algorithms for solving nested bi-level optimization problems. Our proposed algorithm does not rely on matrix complexity or mini-batches.
  arXiv  Detail & Related papers  (2023-07-11T15:52:04Z)
• Accelerated Optimization Landscape of Linear-Quadratic Regulator [0.0]
  A Nest-quadratic regulator (LQR) is a landmark problem in the field of optimal control. A Lipschiz Hessian property of LQR is presented. Euler scheme is utilized to discretize the hybrid dynamic system.
  arXiv  Detail & Related papers  (2023-07-07T13:34:27Z)
• Decentralized Weakly Convex Optimization Over the Stiefel Manifold [28.427697270742947]
  We focus on the Stiefel manifold in the decentralized setting, where a connected network of agents in $nMn log-1)$ are tested. We propose an method called the decentralized subgradient method (DRSM)$ for forcing a natural station below $nMn log-1)$.
  arXiv  Detail & Related papers  (2023-03-31T02:56:23Z)
• Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization [94.19177623349947]
  Non-smooth non optimization problems emerge in machine learning and business making. Two core challenges impede the development of efficient methods with finitetime convergence guarantee. Two-phase versions of GFM and SGFM are also proposed and proven to achieve improved large-deviation results.
  arXiv  Detail & Related papers  (2022-09-12T06:53:24Z)
• Distributed Sparse Regression via Penalization [5.990069843501885]
  We study linear regression over a network of agents, modeled as an undirected graph (with no centralized node) The estimation problem is formulated as the minimization of the sum of the local LASSO loss functions plus a quadratic penalty of the consensus constraint. We show that the proximal-gradient algorithm applied to the penalized problem converges linearly up to a tolerance of the order of the centralized statistical error.
  arXiv  Detail & Related papers  (2021-11-12T01:51:50Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  The problem of constrained decision process (CMDP) is investigated, where an agent aims to maximize the expected accumulated discounted reward subject to multiple constraints. A new utilities-dual convex approach is proposed with novel integration of three ingredients: regularized policy, dual regularizer, and Nesterov's gradient descent dual. This is the first demonstration that nonconcave CMDP problems can attain the lower bound of $mathcal O (1/epsilon)$ for all complexity optimization subject to convex constraints.
  arXiv  Detail & Related papers  (2021-10-20T02:57:21Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  We study optimization of areas under precision-recall curves (AUPRC), which is widely used for imbalanced tasks. We develop novel momentum methods with a better iteration of $O (1/epsilon4)$ for finding an $epsilon$stationary solution. We also design a novel family of adaptive methods with the same complexity of $O (1/epsilon4)$, which enjoy faster convergence in practice.
  arXiv  Detail & Related papers  (2021-07-02T16:21:52Z)
• Efficient Optimistic Exploration in Linear-Quadratic Regulators via Lagrangian Relaxation [107.06364966905821]
  We study the exploration-exploitation dilemma in the linear quadratic regulator (LQR) setting. Inspired by the extended value iteration algorithm used in optimistic algorithms for finite MDPs, we propose to relax the optimistic optimization of ofulq. We show that an $epsilon$-optimistic controller can be computed efficiently by solving at most $Obig(log (1/epsilon)big)$ Riccati equations.
  arXiv  Detail & Related papers  (2020-07-13T16:30:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.