An official website of the United States government
Abstract This article presents an extremum‐seeking control (ESC) algorithm for unmodeled nonlinear systems with known steady‐state gain and generally non‐convex cost functions with bounded curvature. The main contribution of this article is a novel gradient estimator, which uses a polyhedral set that characterizes all gradient estimates consistent with the collected data. The gradient estimator is posed as a quadratic program, which selects the gradient estimate that provides the best worst‐case convergence of the closed‐loop Lyapunov function. We show that the polyhedral‐based gradient estimator ensures the stability of the closed‐loop system formed by the plant and optimization algorithm. Furthermore, the estimated gradient provably produces the optimal robust convergence. We demonstrate our ESC controller through three benchmark examples and one practical example, which shows our ESC has fast and robust convergence to the optimal equilibrium.
more »
« less
Algorithm 1035: A Gradient-based Implementation of the Polyhedral Active Set Algorithm
The Polyhedral Active Set Algorithm (PASA) is designed to optimize a general nonlinear function over a polyhedron. Phase one of the algorithm is a nonmonotone gradient projection algorithm, while phase two is an active set algorithm that explores faces of the constraint polyhedron. A gradient-based implementation is presented, where a projected version of the conjugate gradient algorithm is employed in phase two. Asymptotically, only phase two is performed. Comparisons are given with IPOPT using polyhedral-constrained problems from CUTEst and the Maros/Meszaros quadratic programming test set.
more »
« less
- PAR ID:
- 10481498
- Publisher / Repository:
- Association for Computing Machinery
- Date Published:
- Journal Name:
- ACM Transactions on Mathematical Software
- Volume:
- 49
- Issue:
- 2
- ISSN:
- 0098-3500
- Page Range / eLocation ID:
- 1 to 13
- Subject(s) / Keyword(s):
- Nonlinear optimization polyhedral-constrained optimization active set method gradient projection method projection on polyhedron conjugate gradient method PASA PPROJ CG_DESCENT NAPHEAP
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Tuncer, N; Martcheva, M; Prosper, O; Childs, L (Ed.)In this chapter, we demonstrate how to use a nonlinear polyhedral con- strained optimization solver called the Polyhedral Active Set Algorithm (PASA) for solving a general singular control problem. We present a method for discretizing a general optimal control problem involving the use of the gradient of the Lagrangian for computing the gradient of the cost functional so that PASA can be applied. When a numerical solu- tion contains artifacts that resemble “chattering,” a phenomenon where the control oscillates wildly along the singular region, we recommend a method of regularizing the singular control problem by adding a term to the cost functional that measures a scalar multiple of the total variation of the control, where the scalar is viewed as a tuning parameter. We then demonstrate PASA’s performance on three singular control problems that give rise to different applications of mathematical biology. We also provide some exposition on the heuristics that we use in determining an appropriate size for the tuning parameter.more » « less
-
Holder-Brascamp-Lieb inequalities provide upper bounds for a class of multilinear expressions, in terms of L^p norms of the functions involved. They have been extensively studied for functions defined on Euclidean spaces. Bennett-Carbery-Christ-Tao have initiated the study of these inequalities for discrete Abelian groups and, in terms of suitable data, have characterized the set of all tuples of exponents for which such an inequality holds for specified data, as the convex polyhedron defined by a particular finite set of affine inequalities. In this paper we advance the theory of such inequalities for torsion-free discrete Abelian groups in three respects.The optimal constant in any such inequality is shown to equal 1 whenever it is finite.An algorithm that computes the admissible polyhedron of exponents is developed. It is shown that nonetheless, existence of an algorithm that computes the full list of inequalitiesin the Bennett-Carbery-Christ-Tao description of the admissible polyhedron for all data,is equivalent to an affirmative solution of Hilbert's Tenth Problem over the rationals.That problem remains open.more » « less
-
Abstract The manipulation of 3D objects is becoming crucial for many applications, such as health, industry, or entertainment, to mention some. However, these 3D objects require substantial energy and different types of resources. With the goal of obtaining a simplified representation of a 3D object that can be easily managed, for example, for transmission, in some recent works, the authors associate low-density point clouds with a 3D object that simplifies the original 3D object. More precisely, given a 3D object in a polyhedral format, some authors associate a chain code and then use grammar-free context to obtain key points that give rise to several point clouds with different densities. In this work, we complete the cycle by developing a polyhedral reconstruction from an associated low-density point cloud and the chain code. The polyhedral reconstruction is crucial for handling 3D objects because it allows us to visualize them after they are efficiently compressed and transmitted. We apply our algorithms to well-known 3D objects in the literature. We use the Hausdorff and Chamfer distances to compare our results with the state-of-the-art proposals. We show how our proposed polyhedral reconstruction based on a helical chain code reconstructs a medical image represented or transmitted by slices into a 3D object in a polyhedral format, helping thus to mitigate and alleviate the management of 3D medical objects. The polyhedron that we propose provides better compression when compared with the original set of slices of a 3D medical object.more » « less
-
Abstract We investigate a P 1 P_{1} finite element method for an elliptic distributed optimal control problem with pointwise state constraints and a state equation that includes advective/convective and reactive terms.The convergence of this method can be established for general polygonal/polyhedral domains that are not necessarily convex.The discrete problem is a strictly convex quadratic program with box constraints that can be solved efficiently by a primal-dual active set algorithm.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1145/3583559
