Distributed Nonconvex Optimization: Gradient-free Iterations and $ε$-Globally Optimal Solution
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2020
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914783207358464 |
|---|---|
| author | He, Zhiyu He, Jianping Chen, Cailian Guan, Xinping |
| author_facet | He, Zhiyu He, Jianping Chen, Cailian Guan, Xinping |
| contents | Distributed optimization utilizes local computation and communication to realize a global aim of optimizing the sum of local objective functions. This article addresses a class of constrained distributed nonconvex optimization problems involving univariate objectives, aiming to achieve global optimization without requiring local evaluations of gradients at every iteration. We propose a novel algorithm named CPCA, exploiting the notion of combining Chebyshev polynomial approximation, average consensus, and polynomial optimization. The proposed algorithm is i) able to obtain $ε$-globally optimal solutions for any arbitrarily small given accuracy $ε$, ii) efficient in both zeroth-order queries (i.e., evaluations of function values) and inter-agent communication, and iii) distributed terminable when the specified precision requirement is met. The key insight is to use polynomial approximations to substitute for general local objectives, distribute these approximations via average consensus, and solve an easier approximate version of the original problem. Due to the nice analytic properties of polynomials, this approximation not only facilitates efficient global optimization, but also allows the design of gradient-free iterations to reduce cumulative costs of queries and achieve geometric convergence for solving nonconvex problems. We provide a comprehensive analysis of the accuracy and complexities of the proposed algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2008_00252 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Distributed Nonconvex Optimization: Gradient-free Iterations and $ε$-Globally Optimal Solution He, Zhiyu He, Jianping Chen, Cailian Guan, Xinping Optimization and Control Systems and Control Distributed optimization utilizes local computation and communication to realize a global aim of optimizing the sum of local objective functions. This article addresses a class of constrained distributed nonconvex optimization problems involving univariate objectives, aiming to achieve global optimization without requiring local evaluations of gradients at every iteration. We propose a novel algorithm named CPCA, exploiting the notion of combining Chebyshev polynomial approximation, average consensus, and polynomial optimization. The proposed algorithm is i) able to obtain $ε$-globally optimal solutions for any arbitrarily small given accuracy $ε$, ii) efficient in both zeroth-order queries (i.e., evaluations of function values) and inter-agent communication, and iii) distributed terminable when the specified precision requirement is met. The key insight is to use polynomial approximations to substitute for general local objectives, distribute these approximations via average consensus, and solve an easier approximate version of the original problem. Due to the nice analytic properties of polynomials, this approximation not only facilitates efficient global optimization, but also allows the design of gradient-free iterations to reduce cumulative costs of queries and achieve geometric convergence for solving nonconvex problems. We provide a comprehensive analysis of the accuracy and complexities of the proposed algorithm. |
| title | Distributed Nonconvex Optimization: Gradient-free Iterations and $ε$-Globally Optimal Solution |
| topic | Optimization and Control Systems and Control |
| url | https://arxiv.org/abs/2008.00252 |