39 research outputs found
Entropy-based framework for combinatorial optimization problems and enabling the grid of the future
No full textThis thesis is divided into two parts. In the first part, I describe efficient meta-heuristic algorithms for a series of combinatorially complex optimization problems, while the second part is concerned with robust and scalable control architecture for a network of paralleled converter/inverter systems (DC/AC microgrids).
Combinatorial optimization problems arise in many applications in various forms in seemingly unrelated areas such as data compression, pattern recognition, image segmentation, resource allocation, routing, and scheduling, graph aggregation, and graph partition problems. These optimization problems are characterized by a combinatorial number of configurations, where a cost value can be assigned to each configuration, and the goal is to find the configuration that minimizes the cost. Moreover, these optimization problems are largely non-convex, computationally complex and suffer from multiple local minima that riddle the cost surface. Most heuristics to these optimization problems are very sensitive to initial guess solutions, and efforts to make them robust to initializations typically come at significant computational costs such that the algorithms lose practicality in many applications. In our work, we are motivated by solutions that are employed by nature to similar combinatorial optimization problems; well described in terms of laws such as maximum entropy principle (MEP) in statistical physics literature. We propose to use MEP in solving a variety of combinatorial optimization problems.
Our main current contributions are threefold - (i) First we provide a clustering or resource allocation viewpoint to several combinatorial optimization problems: (a) data clustering, (b) graph partitioning (such as clustering of power networks), (c) traveling salesman problem (TSP) and its variants, and (d) hard problems on graphs, such as multiway -cut. This viewpoint enables a unified approach to handle a broad class of problems, and therefore efficient MEP based heuristics can be leveraged to obtain high-quality solutions. (ii) Second, we explore MEP based ideas to clustering problems specified by pairwise distances. Many problems in graph theory are indeed specified in terms of the corresponding edge-weight matrices (and not in terms of the nodal locational coordinates). (iii) Finally, our framework allows for inclusion of several constraints in the clustering/resource allocation problems. These constraints may correspond to capacity constraints in case of resource allocations where capacity of each resource is limited, or minimum-tour length constraints in case of traveling salesman problems (TSPs) and its variants.
In the second part of this thesis, we describe a novel distributed, robust and optimal control architecture for both DC as well as AC microgrids. Microgrids are grid systems that allow integration of local power sources, such as photovoltaics (PVs), wind, battery and other distributed energy resources (DERs) with local loads connected at the DC-link or the point of common coupling (PCC). Microgrids are hypothesized as viable alternatives to the traditional electric grid. In a microgrid, the main goals of the control design are to regulate voltage and frequency at the PCC and ensuring a prescribed sharing of power among different sources; for instance, economic considerations can dictate that power provided by the sources should be in a certain proportion or according to a prescribed priority. The main challenges arise from the uncertainties in the size and the schedules of loads, the complexity of a coupled multi-converter network, the uncertainties in the model parameters at each converter, and the adverse effects of interfacing DC power sources with AC loads, such as the Hz ripple that must be provided by the DC sources. A systematic control design that addresses all the challenges and objectives for the multi-converter/inverter control is still lacking in the existing literature. The main contribution of the control architecture proposed by us is its capability to addresses all the primary objectives - a) voltage and frequency regulation at the PCC with guaranteed robustness margins, b) prescribed time-varying power sharing in a network of parallel converters, c) controlling the tradeoff between 120Hz ripple on the total current provided by the power sources and the ripple on the DC-link voltage. An important contribution of our work is that our control architecture allows for closed-loop analysis and robust control synthesis for the entire grid network. We introduce a structure in the control architecture, whereby, we show that analysis of the entire multi-component microgrid can be simplified to that of an equivalent {\em single-component} system. Besides analysis, this simplification facilitates using robust and optimal control tools for achieving multiple objectives simultaneously; in contrast in existing architectures, closed-loop analysis for entire networks is typically difficult, and posing optimal control and robustness objectives for the entire network practically untenable.Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2018-09-27 without embargo termsThe student, Mayank Baranwal, accepted the attached license on 2018-06-12 at 14:47.The student, Mayank Baranwal, submitted this Dissertation for approval on 2018-06-12 at 15:02.This Dissertation was approved for publication on 2018-06-14 at 11:09.DSpace SAF Submission Ingestion Package generated from Vireo submission #12625 on 2018-09-27 at 10:44:46Made available in DSpace on 2018-09-27T16:17:25Z (GMT). No. of bitstreams: 2
BARANWAL-DISSERTATION-2018.pdf: 9153294 bytes, checksum: c75788709974a4e9333d5c0826bea4dd (MD5)
LICENSE.txt: 4212 bytes, checksum: ca75c4cd4a96259eb5b8cb6c66eaee32 (MD5)
Previous issue date: 2018-06-1
Application of field programmable analog arrays (FPAAs) to fast scanning probe microscopy
No full textFor a long time, signal processing used to be accomplished by microprocessors and DSPs (Digital Signal Processors). The advent of reconfigurable computing devices, such as Complex Programmable Logic Devices (CPLDs) and Field Programmable Gate Arrays (FPGAs) has given a new dimension to signal processing applications by not only allowing users to customize the hardware to suit the specific requirements but also making high speed applications a possibility, too. More recently, Field Programmable Analog Arrays (FPAAs) have emerged as interesting alternatives to most signal processing based applications. Even though the use of FPAA devices is still limited due to small number of suppliers, a growing interest in using FPAAs for various engineering applications is expected. In this thesis, we exploit the FPAAs to demonstrate their usefulness and ease of implementation in developing fast and robust controllers for an Atomic Force Microscope (AFM) unit.
Atomic Force Microscopes (AFMs) are getting faster. However, video-rate imaging still remains a big challenge to the AFM community. Therefore AFMs are required to have very fast nanopositioning systems. However, high-bandwidth requirement on the positioning system poses fundamental limitations on the image resolution. The resolution of an image depends on the controller’s capabilities to attenuate the measurement noises. Tools from robust control theory are employed to not only quantify the measurement noises and parametric uncertainties, but also synthesize the controllers in an optimal setting.
However, implementation of such controllers require electronics that can support high-bandwidth operations. Field Programmable Analog Arrays (FPAAs), which have bandwidth up to 400 kHz, have been employed to demonstrate not only the direct implementation of these controllers in terms of transfer functions, but also high-bandwidth tracking performance, too, when compared to most other commercially available Digital Signal Processors (DSPs). A significant improvement in the closed-loop bandwidth (∼ 500Hz) has been demonstrated. A part of the work is dedicated to the Q-control of microcantilevers. Since, cantilevers are second-order flexible structures with high resonant frequencies (∼ 50kHz) , Q-control of cantilevers requires estimating velocity at resonant frequencies. High-bandwidth advantage of FPAAs can be exploited to achieve the desired Q-control.Item withdrawn by Laura Spradlin ([email protected]) on 2014-07-23T19:53:05Z
Item was in collections:
University of Illinois Theses & Dissertations (ID: 1)
No. of bitstreams: 1
Baranwal_Mayank.pdf: 3951829 bytes, checksum: 32947bb8dad204546cbb45d02618a4f2 (MD5)Made available in DSpace on 2014-09-16T17:24:58Z (GMT). No. of bitstreams: 2
Mayank_Baranwal.pdf: 3952435 bytes, checksum: 77957071add0f48500346e5832e0df15 (MD5)
license.txt: 4065 bytes, checksum: e284bc54d5d468503a634d777fc6a26a (MD5
Accelerating Distributed Optimization via Fixed-time Convergent Flows: Extensions to Non-convex Functions and Consistent Discretization
No full textDistributed optimization has gained significant attention in recent years,
primarily fueled by the availability of a large amount of data and
privacy-preserving requirements. This paper presents a fixed-time convergent
optimization algorithm for solving a potentially non-convex optimization
problem using a first-order multi-agent system. Each agent in the network can
access only its private objective function, while local information exchange is
permitted between the neighbors. The proposed optimization algorithm combines a
fixed-time convergent distributed parameter estimation scheme with a fixed-time
distributed consensus scheme as its solution methodology. The results are
presented under the assumption that the team objective function is strongly
convex, as opposed to the common assumptions in the literature requiring each
of the local objective functions to be strongly convex. The results extend to
the class of possibly non-convex team objective functions satisfying only the
Polyak-\L ojasiewicz (PL) inequality. It is also shown that the proposed
continuous-time scheme, when discretized using Euler's method, leads to
consistent discretization, i.e., the fixed-time convergence behavior is
preserved under discretization. Numerical examples comprising large-scale
distributed linear regression and training of neural networks corroborate our
theoretical analysis.Comment: Under review. 10 pages, 1 figur
A Methodology Establishing Linear Convergence of Adaptive Gradient Methods under PL Inequality
No full textAdaptive gradient-descent optimizers are the standard choice for training neural network models. Despite their faster convergence than gradient-descent and remarkable performance in practice, the adaptive optimizers are not as well understood as vanilla gradient-descent. A reason is that the dynamic update of the learning rate that helps in faster convergence of these methods also makes their analysis intricate. Particularly, the simple gradient-descent method converges at a linear rate for a class of optimization problems, whereas the practically faster adaptive gradient methods lack such a theoretical guarantee. The Polyak-Łojasiewicz (PL) inequality is the weakest known class, for which linear convergence of gradient-descent and its momentum variants has been proved. Therefore, in this paper, we prove that AdaGrad and Adam, two well-known adaptive gradient methods, converge linearly when the cost function is smooth and satisfies the PL inequality. Our theoretical framework follows a simple and unified approach, applicable to both batch and stochastic gradients, which can potentially be utilized in analyzing linear convergence of other variants of Adam.Accepted for publication at the main track of 27th European Conference on Artificial Intelligence (ECAI-2024
Weighted kernel deterministic annealing: A maximum-entropy principle approach for shape clustering
No full text
On the Persistence of Clustering Solutions and True Number of Clusters in a Dataset
No full textTypically clustering algorithms provide clustering solutions with prespecified number of clusters. The lack of a priori knowledge on the true number of underlying clusters in the dataset makes it important to have a metric to compare the clustering solutions with different number of clusters. This article quantifies a notion of persistence of clustering solutions that enables comparing solutions with different number of clusters. The persistence relates to the range of dataresolution scales over which a clustering solution persists; it is quantified in terms of the maximum over two-norms of all the associated cluster-covariance matrices. Thus we associate a persistence value for each element in a set of clustering solutions with different number of clusters. We show that the datasets where natural clusters are a priori known, the clustering solutions that identify the natural clusters are most persistent - in this way, this notion can be used to identify solutions with true number of clusters. Detailed experiments on a variety of standard and synthetic datasets demonstrate that the proposed persistence-based indicator outperforms the existing approaches, such as, gap-statistic method, X-means, Gmeans, PG-means, dip-means algorithms and informationtheoretic method, in accurately identifying the clustering solutions with true number of clusters. Interestingly, our method can be explained in terms of the phase-transition phenomenon in the deterministic annealing algorithm, where the number of distinct cluster centers changes (bifurcates) with respect to an annealing parameter
PowRL: A Reinforcement Learning Framework for Robust Management of Power Networks
No full textPower grids, across the world, play an important societal and economical role by providing uninterrupted, reliable and transient-free power to several industries, businesses and household consumers. With the advent of renewable power resources and EVs resulting into uncertain generation and highly dynamic load demands, it has become ever so important to ensure robust operation of power networks through suitable management of transient stability issues and localize the events of blackouts. In the light of ever increasing stress on the modern grid infrastructure and the grid operators, this paper presents a reinforcement learning (RL) framework, PowRL, to mitigate the effects of unexpected network events, as well as reliably maintain electricity everywhere on the network at all times. The PowRL leverages a novel heuristic for overload management, along with the RL-guided decision making on optimal topology selection to ensure that the grid is operated safely and reliably (with no overloads). PowRL is benchmarked on a variety of competition datasets hosted by the L2RPN (Learning to Run a Power Network). Even with its reduced action space, PowRL tops the leaderboard in the L2RPN NeurIPS 2020 challenge (Robustness track) at an aggregate level, while also being the top performing agent in the L2RPN WCCI 2020 challenge. Moreover, detailed analysis depicts state-of-the-art performances by the PowRL agent in some of the test scenarios
