Publications
71 results found
Campos JS, Misener R, Parpas P, 2022, Partial lasserre relaxation for sparse max-cut, Optimization and Engineering, ISSN: 1389-4420
A common approach to solve or find bounds of polynomial optimization problems like Max-Cut is to use the first level of the Lasserre hierarchy. Higher levels of the Lasserre hierarchy provide tighter bounds, but solving these relaxations is usually computationally intractable. We propose to strengthen the first level relaxation for sparse Max-Cut problems using constraints from the second order Lasserre hierarchy. We explore a variety of approaches for adding a subset of the positive semidefinite constraints of the second order sparse relaxation obtained by using the maximum cliques of the graph’s chordal extension. We apply this idea to sparse graphs of different sizes and densities, and provide evidence of its strengths and limitations when compared to the state-of-the-art Max-Cut solver BiqCrunch and the alternative sparse relaxation CS-TSSOS.
Ho CP, Kocvara M, Parpas P, 2022, Newton-type multilevel optimization method, Optimization Methods and Software, Vol: 37, Pages: 45-78, ISSN: 1029-4937
Inspired by multigrid methods for linear systems of equations, multilevel optimization methods have been proposed to solve structured optimization problems. Multilevel methods make more assumptions regarding the structure of the optimization model, and as a result, they outperform single-level methods, especially for large-scale models. The impressive performance of multilevel optimization methods is an empirical observation, and no theoretical explanation has so far been proposed. In order to address this issue, we study the convergence properties of a multilevel method that is motivated by second-order methods. We take the first step toward establishing how the structure of an optimization problem is related to the convergence rate of multilevel algorithms.
Borovykh A, Kantas N, Parpas P, et al., 2021, On stochastic mirror descent with interacting particles: Convergence properties and variance reduction, Physica D: Nonlinear Phenomena, Vol: 418, Pages: 1-21, ISSN: 0167-2789
An open problem in optimization with noisy information is the computation of an exact minimizer that is independent of the amount of noise. A standard practice in stochastic approximation algorithms is to use a decreasing step-size. This however leads to a slower convergence. A second alternative is to use a fixed step-size and run independent replicas of the algorithm and average these. A third option is to run replicas of the algorithm and allow them to interact. It is unclear which of these options works best. To address this question, we reduce the problem of the computation of an exact minimizer with noisy gradient information to the study of stochastic mirror descent with interacting particles. We study the convergence of stochastic mirror descent and make explicit the tradeoffs between communication and variance reduction. We provide theoretical and numerical evidence to suggest that interaction helps to improve convergence and reduce the variance of the estimate.
Pecci F, Parpas P, Stoianov I, 2020, Sequential convex optimization for detecting and locating blockages in water distribution networks, Journal of Water Resources Planning and Management, Vol: 146, ISSN: 0733-9496
Unreported partially/fully closed valves or other type of pipe blockages in water distribution networks result in unexpected energy losses within the systems, which we also refer to as faults. We investigate the problem of detection and localization of such faults. We propose a novel optimization-based method, which relies on the solution of a non-linear inverse problem with l1 regularization. We develop a sequential convex optimization algorithm to solve the resulting non-smooth non-convex optimization problem. The proposed algorithm enables the use of non-smooth terms within the problem formulation, and exploits the sparse structure inherent in water network models. The performance of the developed method is numerically evaluated to detect and localize blockages in a large water distribution network using both simulated and experimental data. In all experiments, the sequential convex optimization algorithm converged in less than three seconds, suggesting that the proposed fault detection and localization method is suitable for near real-time implementation. Furthermore, we experimentally validate the developed method for near real-time fault diagnosis in a large operational water network from the UK. The method is shown to successfully detect and localize blockages, with real system modelling uncertainties.
Campos JS, Misener R, Parpas P, 2019, A multilevel analysis of the Lasserre hierarchy, European Journal of Operational Research, Vol: 277, Pages: 32-41, ISSN: 0377-2217
This paper analyzes the relation between different orders of the Lasserre hierarchy for polynomial optimization (POP). Although for some cases solving the semidefinite programming relaxation corresponding to the first order of the hierarchy is enough to solve the underlying POP, other problems require sequentially solving the second or higher orders until a solution is found. For these cases, and assuming that the lower order semidefinite programming relaxation has been solved, we develop prolongation operators that exploit the solutions already calculated to find initial approximations for the solution of the higher order relaxation. We can prove feasibility in the higher order of the hierarchy of the points obtained using the operators, as well as convergence to the optimal as the relaxation order increases. Furthermore, the operators are simple and inexpensive for problems where the projection over the feasible set is “easy” to calculate (for example integer {0, 1} and {−1,1} POPs). Our numerical experiments show that it is possible to extract useful information for real applications using the prolongation operators. In particular, we illustrate how the operators can be used to increase the efficiency of an infeasible interior point method by using them as an initial point. We use this technique to solve quadratic integer {0, 1} problems, as well as MAX-CUT and integer partition problems.
Ho CP, Parpas P, 2019, Empirical risk minimization: probabilistic complexity and stepsize strategy, Computational Optimization and Applications, Vol: 73, Pages: 387-410, ISSN: 0926-6003
Empirical risk minimization is recognized as a special form in standard convex optimization. When using a first order method, the Lipschitz constant of the empirical risk plays a crucial role in the convergence analysis and stepsize strategies for these problems. We derive the probabilistic bounds for such Lipschitz constants using random matrix theory. We show that, on average, the Lipschitz constant is bounded by the ratio of the dimension of the problem to the amount of training data. We use our results to develop a new stepsize strategy for first order methods. The proposed algorithm, Probabilistic Upper-bound Guided stepsize strategy, outperforms the regular stepsize strategies with strong theoretical guarantee on its performance.
Hovhannisyan V, Panagakis I, Parpas P, et al., 2019, Fast multilevel algorithms for compressive principal component pursuit, SIAM Journal on Imaging Sciences, Vol: 12, Pages: 624-649, ISSN: 1936-4954
Recovering a low-rank matrix from highly corrupted measurements arises in compressed sensing of structured high-dimensional signals (e.g., videos and hyperspectral images among others). Robust principal component analysis (RPCA), solved via principal component pursuit (PCP), recovers a low-rank matrix from sparse corruptions that are of unknown value and support by decomposing the observation matrix into two terms: a low-rank matrix and a sparse one, accounting for sparse noise and outliers. In the more general setting, where only a fraction of the data matrix has been observed, low-rank matrix recovery is achieved by solving the compressive principal component pursuit (CPCP). Both PCP and CPCP are well-studied convex programs, and numerousiterative algorithms have been proposed for their optimisation. Nevertheless, these algorithms involve singular value decomposition (SVD) at each iteration, which renders their applicability challenging in the case of massive data. In this paper, we propose a multilevel approach for the solution of PCP and CPCP problems. The core principle behind our algorithm is to apply SVD in models of lower-dimensionality than the original one and then lift its solution to the original problem dimension. Hence, our methods rely on the assumption that the low rank component can be represented in a lower dimensional space. We show that the proposed algorithms are easy to implement, converge at the same rate but with much lower iteration cost. Numerical experiments on numerous synthetic and real problems indicate that the proposed multilevel algorithms are several times faster than their original counterparts, namely PCP and CPCP.
Haughton TW, Angeloudis P, Parpas P, et al., 2018, Optimal Component Modularisation of Process Plants for Modular Construction, EURO 2018
Hovhannisyan V, Panagakis Y, Zafeiriou S, et al., 2018, Multilevel approximate robust principal component analysis, 16th IEEE International Conference on Computer Vision (ICCV), Publisher: IEEE, Pages: 536-544, ISSN: 2473-9936
Robust principal component analysis (RPCA) is currently the method of choice for recovering a low-rank matrix from sparse corruptions that are of unknown value and support by decomposing the observation matrix into low-rank and sparse matrices. RPCA has many applications including background subtraction, learning of robust subspaces from visual data, etc. Nevertheless, the application of SVD in each iteration of optimisation methods renders the application of RPCA challenging in cases when data is large. In this paper, we propose the first, to the best of our knowledge, multilevel approach for solving convex and non-convex RPCA models. The basic idea is to construct lower dimensional models and perform SVD on them instead of the original high dimensional problem. We show that the proposed approach gives a good approximate solution to the original problem for both convex and non-convex formulations, while being many times faster than original RPCA methods in several real world datasets.
Campos JS, Parpas P, 2018, A multigrid approach to SDP relaxations of sparse polynomial optimization problems, SIAM Journal on Optimization, Vol: 28, Pages: 1-29, ISSN: 1052-6234
We propose a multigrid approach for the global optimization of polynomial optimization problems with sparse support. The problems we consider arise from the discretization of infinite dimensional optimization problems, such as PDE optimization problems, boundary value problems, and some global optimization applications. In many of these applications, the level of discretization can be used to obtain a hierarchy of optimization models that capture the underlying infinite dimensional problem at different degrees of fidelity. This approach, inspired by multigrid methods, has been successfully used for decades to solve large systems of linear equations. However, multigrid methods are difficult to apply to semidefinite programming (SDP) relaxations of polynomial optimization problems. The main difficulty is that the information between grids is lost when the original problem is approximated via an SDP relaxation. Despite the loss of information, we develop a multigrid approach and propose prolongation operators to relate the primal and dual variables of the SDP relaxation between lower and higher levels in the hierarchy of discretizations. We develop sufficient conditions for the operators to be useful in practice. Our conditions are easy to verify, and we discuss how they can be used to reduce the complexity of infeasible interior point methods. Our preliminary results highlight two promising advantages of following a multigrid approach compared to a pure interior point method: the percentage of problems that can be solved to a high accuracy is much greater, and the time necessary to find a solution can be reduced significantly, especially for large scale problems.
Parpas P, Ralph D, Wiesemann W, 2017, Special issue: Optimization models and algorithms for data science, Mathematical Programming, Vol: 167, Pages: 1-3, ISSN: 0025-5610
Parpas P, 2017, A multilevel proximal gradient algorithm for a class of composite optimization problems, SIAM Journal on Scientific Computing, Vol: 39, Pages: S681-S701, ISSN: 1095-7197
Composite optimization models consist of the minimization of the sumof a smooth (not necessarily convex) function and a non-smooth convex function.Such models arise in many applications where, in addition to the composite natureof the objective function, a hierarchy of models is readily available. It is commonto take advantage of this hierarchy of models by first solving a low fidelity modeland then using the solution as a starting point to a high fidelity model. We adoptan optimization point of view and show how to take advantage of the availability ofa hierarchy of models in a consistent manner. We do not use the low fidelity modeljust for the computation of promising starting points but also for the computa-tion of search directions. We establish the convergence and convergence rate ofthe proposed algorithm. Our numerical experiments on large scale image restora-tion problems and the transition path problem suggest that, for certain classes ofproblems, the proposed algorithm is significantly faster than the state of the art.
Parpas P, Rustem B, Wiesemann W, 2017, Guest Editorial, Optimization Methods and Software, Vol: 32, Pages: 669-669, ISSN: 1055-6788
Menke R, Abraham E, Parpas P, et al., 2017, Extending the envelope of demand response provision though variable Speed pumps, 18th Water Distribution System Analysis Conference, WDSA2016, Publisher: Elsevier, Pages: 584-591, ISSN: 1877-7058
Changes in power generation and supply and changes in water distribution systems are creating new opportunities for water utilities to enhance operational efficiency and income through the use of advanced control and optimisation. First, the increase in renewables penetration into the grid is causing a growth in energy storage schemes. Second, variable speed pumps are now fitted to most new systems and many existing water distribution systems are being retrofitted with variable speed pumps to improve the efficiency of the operation. We study how these trends can be jointly exploited to provide energy storage from a water distribution system. We investigate how variable speed drive pumps can enhance the ability of a water distribution network to provide demand response energy to the grid. We show that demand response provision from water distribution systems can be improved through the use of variable speed pumps. We also demonstrate that a network equipped with variable speed pumps can provide demand response profitably across a wider range of operating scenarios compared to a network equipped with only fixed-speed pumps. The results highlight another potential benefit of variable speed pumps in water distribution systems.
Howe S, Parpas P, 2017, Error bounds on the solution to an optimal control problem over clustered consensus networks, Pages: 25-32
In this paper, we obtain a bound on the error term of the solution to a control constrained, linear-quadratic optimal control problem over a clustered consensus network. For large scale systems, the solution may be regarded as com- putationally infeasible due to the increase in dimensionality. However, the two time-scale property of the network that arises from the cluster formation indicates that the optimal control problem can be written in standard singularly per- turbed form. Thus, we are able to obtain a reduced dimen- sion optimal control problem over a reduced dimension net- work where individual nodes within a cluster are collapsed into an aggregate node. The solution to the reduced problem can be shown to be asymptotically equivalent in the singular perturbation parameter to the solution of the original prob- lem. However, for many values of this asymptotic result may fail to be of practical use. We improve on this result by applying a duality theory to the clustered network and derive an upper bound u and lower bound l on the solution to the optimal control problem that holds for arbitrary and, furthermore, satisfies the inequality j u-l-j = O as 0.
Radu Baltean-Lugojany, Parpas P, 2016, Robust numerical calibration for implied volatility expansion models, SIAM Journal on Financial Mathematics, Vol: 7, Pages: 917-946, ISSN: 1945-497X
Implied volatility expansions allow calibration of sophisticated volatility models. They provide anaccurate t and parametrization of implied volatility surfaces that is consistent with empirical ob-servations. Fine-grained higher order expansions o er a better t but pose the challenge of nding arobust, stable and computationally tractable calibration procedure due to a large number of marketparameters and nonlinearities. We propose calibration schemes for second order expansions that takeadvantage of the model's structure via exact parameter reductions and recoveries, reuse and scalingbetween expansion orders where permitted by the model asymptotic regime and numerical iterationover bounded signi cant parameters. We perform a numerical analysis over 12 years of real S&P 500index options data for both multiscale stochastic and general local-stochastic volatility models. Ourmethods are validated empirically by obtaining stable market parameters that meet the qualitativeand numerical constraints imposed by their functional forms and model asymptotic assumptions.
Menke RM, Abraham EA, Stoianov IS, et al., 2016, Exploring optimal pump scheduling in water distribution networks with branch and bound methods, Water Resources Management, Vol: 30, Pages: 5333-5349, ISSN: 0920-4741
Water utilities can achieve signi cant savings in operating costs by optimising pump scheduling to improve efficiency and shift electricity consumption to low-tari periods. Due to the complexityof the optimal scheduling problem, heuristic methods that cannot guarantee global optimality are often applied. This paper investigates formulations of the pump scheduling problem solved using a branch and bound method. Piecewise linear component approximations outperform non-linear approximationswithin application driven accuracy bounds and demand uncertainties. It is shown that the reduction of symmetry through the grouping of pumps signi cantly reduces the computational e ort, whereas loopsin the network have the opposite e ect. The computational e ort of including convex, non-linear pump operating, and maintenance cost functions is investigated. Using case studies, it is shown that linear and xed-cost functions can be used to nd schedules which, when simulated in a full hydraulic simulation, have performances that are within the solver optimality gap and the uncertainty of demand forecasts.
Malki K, Tosto MG, Mouriño-Talín H, et al., 2016, Highly polygenic architecture of antidepressant treatment response: Comparative analysis of SSRI and NRI treatment in an animal model of depression, American Journal of Medical Genetics Part B-Neuropsychiatric Genetics, Vol: 174, Pages: 235-250, ISSN: 1552-485X
Response to antidepressant (AD) treatment may be a more polygenic trait than previously hypothesized, with many genetic variants interacting in yet unclear ways. In this study we used methods that can automatically learn to detect patterns of statistical regularity from a sparsely distributed signal across hippocampal transcriptome measurements in a large-scale animal pharmacogenomic study to uncover genomic variations associated with AD. The study used four inbred mouse strains of both sexes, two drug treatments, and a control group (escitalopram, nortriptyline, and saline). Multi-class and binary classification using Machine Learning (ML) and regularization algorithms using iterative and univariate feature selection methods, including InfoGain, mRMR, ANOVA, and Chi Square, were used to uncover genomic markers associated with AD response. Relevant genes were selected based on Jaccard distance and carried forward for gene-network analysis. Linear association methods uncovered only one gene associated with drug treatment response. The implementation of ML algorithms, together with feature reduction methods, revealed a set of 204 genes associated with SSRI and 241 genes associated with NRI response. Although only 10% of genes overlapped across the two drugs, network analysis shows that both drugs modulated the CREB pathway, through different molecular mechanisms. Through careful implementation and optimisations, the algorithms detected a weak signal used to predict whether an animal was treated with nortriptyline (77%) or escitalopram (67%) on an independent testing set. The results from this study indicate that the molecular signature of AD treatment may include a much broader range of genomic markers than previously hypothesized, suggesting that response to medication may be as complex as the pathology. The search for biomarkers of antidepressant treatment response could therefore consider a higher number of genetic markers and their interactions. Through predominat
Parpas P, Rustem, Duy VN Luong, et al., 2016, A weighted Mirror Descent algorithm for nonsmooth convex optimization problem, Journal of Optimization Theory and Applications, Vol: 170, Pages: 900-915, ISSN: 1573-2878
Large scale nonsmooth convex optimization is a common problemfor a range of computational areas including machine learning and computer vision. Problems in these areas contain special domain structures and characteristics. Special treatment of such problem domains, exploiting their structures, can significantly reduce the computational burden. In this paper, we consider a Mirror Descent method with a special choice of distance function for solving nonsmooth optimization problems over a Cartesian product of convex sets. We propose to use a nonlinear weighted distance in the projectionstep. The convergence analysis identifies optimal weighting parameters that, eventually, lead to the optimally weighted step-size strategy for every projection on a corresponding convex set. We show that the optimality bound of the Mirror Descent algorithm using the weighted distance is either an improvement to, or in the worst-case as good as, the optimality bound of the Mirror Descent using unweighted distances. We demonstrate the efficiency of the algorithm by solving the Markov Random Fields (MRF) optimization problem. In order to exploit the domain of the MRF problem, we use a weighted logentropy distance and a weighted Euclidean distance. Promising experimentalresults demonstrate the effectiveness of the proposed method.
Menke R, Abraham E, Parpas P, et al., 2016, Demonstrating demand response from water distribution system through pump scheduling, Applied Energy, Vol: 170, Pages: 377-387, ISSN: 0306-2619
Significant changes in the power generation mix are posing new challenges for the balancing systems of the grid. Many of these challenges are in the secondary electricity grid regulation services and could be met through demand response (DR) services. We explore the opportunities for a water distribution system (WDS) to provide balancing services with demand response through pump scheduling and evaluate the associated benefits. Using a benchmark network and demand response mechanisms available in the UK, these benefits are assessed in terms of reduced green house gas (GHG) emissions from the grid due to the displacement of more polluting power sources and additional revenues for water utilities. The optimal pump scheduling problem is formulated as a mixed-integer optimisation problem and solved using a branch and bound algorithm. This new formulation finds the optimal level of power capacity to commit to the provision of demand response for a range of reserve energy provision and frequency response schemes offered in the UK. For the first time we show that DR from WDS can offer financial benefits to WDS operators while providing response energy to the grid with less greenhouse gas emissions than competing reserve energy technologies. Using a Monte Carlo simulation based on data from 2014, we demonstrate that the cost of providing the storage energy is less than the financial compensation available for the equivalent energy supply. The GHG emissions from the demand response provision from a WDS are also shown to be smaller than those of contemporary competing technologies such as open cycle gas turbines. The demand response services considered vary in their response time and duration as well as commitment requirements. The financial viability of a demand response service committed continuously is shown to be strongly dependent on the utilisation of the pumps and the electricity tariffs used by water utilities. Through the analysis of range of water demand scenarios a
Hovhannisyan V, Parpas P, Zafeiriou S, 2016, MAGMA: Multilevel Accelerated Gradient Mirror Descent Algorithm for Large-Scale Convex Composite Minimization, SIAM JOURNAL ON IMAGING SCIENCES, Vol: 9, Pages: 1829-1857, ISSN: 1936-4954
- Author Web Link
- Open Access Link
- Cite
- Citations: 8
Wright R, Abraham E, Parpas P, et al., 2015, Control of water distribution networks with dynamic DMA topology using strictly feasible sequential convex programming, Water Resources Research, Vol: 51, Pages: 9925-9941, ISSN: 0043-1397
The operation of water distribution networks (WDN) with a dynamic topology is a recently pioneered approach for the advanced management of district metered areas (DMA) that integrates novel developments in hydraulic modelling, monitoring, optimization and control. A common practice for leakage management is the sectorization of WDNs into small zones, called DMAs, by permanently closing isolation valves. This facilitates water companies to identify bursts and estimate leakage levels by measuring the inlet flow for each DMA. However, by permanently closing valves, a number of problems have been created including reduced resilience to failure and suboptimal pressure management. By introducing a dynamic topology to these zones, these disadvantages can be eliminated whilst still retaining the DMA structure for leakage monitoring. In this paper, a novel optimization method based on sequential convex programming (SCP) is outlined for the control of a dynamic topology with the objective of reducing average zone pressure (AZP). A key attribute for control optimization is reliable convergence. To achieve this, the SCP method we propose guarantees that each optimization step is strictly feasible, resulting in improved convergence properties. By using a null space algorithm for hydraulic analyses, the computations required are also significantly reduced. The optimized control is actuated on a real WDN operated with a dynamic topology. This unique experimental programme incorporates a number of technologies set up with the objective of investigating pioneering developments in WDN management. Preliminary results indicate AZP reductions for a dynamic topology of up to 6.5% over optimally controlled fixed topology DMAs.
Menke R, Abraham E, Parpas P, et al., 2015, Approximation of System Components for Pump Scheduling Optimisation, Proc. 13th Int. Conference on Computing and Control in the Water Industry (CCWI), Publisher: Elsevier, Pages: 1059-1068, ISSN: 1877-7058
The operation of pump systems in water distribution systems (WDS) is commonly the most expensive task for utilities with upto 70% of the operating cost of a pump system attributed to electricity consumption. Optimisation of pump scheduling could save10-20% by improving efficiency or shifting consumption to periods with low tariffs.Due to the complexity of the optimal control problem, heuristic methods which cannot guarantee optimality are often applied.To facilitate the use of mathematical optimisation this paper investigates formulations of WDS components. We show that linearapproximations outperform non-linear approximations, while maintaining comparable levels of accuracy.
Wright R, Abraham E, Parpas P, et al., 2015, Optimized Control of Pressure Reducing Valves in Water Distribution Networks With Dynamic Topology, Publisher: Procedia Engineering, Elsevier
Parpas P, Ustun B, Webster MD, et al., 2015, Importance sampling in stochastic programming: A Markov chain Monte Carlo approach, Informs Journal on Computing, Vol: 27, Pages: 358-377, ISSN: 1526-5528
Stochastic programming models are large-scale optimization problems that are used to facilitate decision making under uncertainty. Optimization algorithms for such problems need to evaluate the expected future costs of current decisions, often referred to as the recourse function. In practice, this calculation is computationally difficult as it requires the evaluation of a multidimensional integral whose integrand is an optimization problem. In turn, the recourse function has to be estimated using techniques such as scenario trees or Monte Carlo methods, both of which require numerous functional evaluations to produce accurate results for large-scale problems with multiple periods and high-dimensional uncertainty. In this work, we introduce an importance sampling framework for stochastic programming that can produce accurate estimates of the recourse function using a small number of samples. Our framework combines Markov chain Monte Carlo methods with kernel density estimation algorithms to build a nonparametric importance sampling distribution, which can then be used to produce a lower-variance estimate of the recourse function. We demonstrate the increased accuracy and efficiency of our approach using variants of well-known multistage stochastic programming problems. Our numerical results show that our framework produces more accurate estimates of the optimal value of stochastic programming models, especially for problems with moderate variance, multimodal, or rare-event distributions.
Wright R, Herrera M, Parpas P, et al., 2015, Hydraulic resilience index for the critical link analysis of multi-feed water distribution networks, Computing and Control for the Water Industry (CCWI2015)- Sharing the Best Practice in Water Management, Publisher: ELSEVIER SCIENCE BV, Pages: 1249-1258, ISSN: 1877-7058
- Author Web Link
- Cite
- Citations: 11
Wright R, Parpas P, Stoianov I, 2015, Experimental investigation of resilience and pressure management in water distribution networks, Computing and Control for the Water Industry (CCWI2015)- Sharing the Best Practice in Water Management, Publisher: ELSEVIER SCIENCE BV, Pages: 643-652, ISSN: 1877-7058
- Author Web Link
- Cite
- Citations: 2
Ho CP, Parpast P, 2015, On using spectral graph theory to infer the structure of multiscale Markov processes, Pages: 228-235
Multiscale Markov processes are used to model and control stochastic dynamics across different scales in many applications areas such as electrical engineering, finance, and material science. A commonly used mathematical representation that captures multiscale stochastic dynamics is that of singularly perturbed Markov processes. Dimensionality reductions techniques for this class of stochastic optimal control problems have been studied for many years. However, it is typically assumed that the structure of perturbed process and its dynamics are known. In this paper, we show how to infer the structure of a singularly perturbed Markov process from data. We propose a measure of similarity for the different states of the Markov process and then use techniques from spectral graph theory to show that the perturbed structure can be obtained by looking at the spectrum of a graph defined on the proposed similarity matrix.
Ho CP, Parpas P, 2014, Singularly perturbed markov decision processes: a multiresolution algorithm, SIAM Journal on Control and Optimization, Vol: 52, Pages: 3854-3886, ISSN: 0363-0129
Singular perturbation techniques allow the derivation of an aggregate model whose solution is asymptotically optimal for Markov decision processes with strong and weak interactions. We develop an algorithm that takes advantage of the asymptotic optimality of the aggregate model in order to compute the solution of the original model. We derive conditions for which the proposed algorithm has better worst case complexity than conventional contraction algorithms. Based on our complexity analysis, we show that the major benefit of aggregation is that the reduced order model is no longer ill conditioned. The reduction in the number of states (due to aggregation) is a secondary benefit. This is a surprising result since intuition would suggest that the reduced order model can be solved more efficiently because it has fewer states. However, we show that this is not necessarily the case. Our theoretical analysis and numerical experiments show that the proposed algorithm can compute the optimal solution with a reduction in computational complexity and without any penalty in accuracy.
Wright R, Stoianov I, Parpas P, et al., 2014, Adaptive Water Distribution Networks with Dynamically Reconfigurable Topology, Journal of Hydroinformatics
This paper presents a novel concept of adaptive water distribution networks withdynamically reconfigurable topology for optimal pressure control, leakage management and improved system resilience. The implementation of District Meter Areas (DMAs) has greatly assisted water utilities in reducing leakage. DMAs segregate water networks into small areas; the flow in and out of each area is monitored and thresholds are derived from the minimum night flow to trigger the leak localisation. A major drawback of the DMA approach is the reduced redundancy in network connectivity which has a severe impact on network resilience, incident management and water quality deterioration. The presented approach for adaptively reconfigurable networks integrates the benefits of DMAs for managing leakage with the advantages of large scale looped networks for increased redundancy in connectivity, reliability and resilience. Self-powered multi-function network controllers are designed and integrated with novel telemetry tools for high-speed time-time synchronised monitoring of the dynamic hydraulic conditions. A robust and computationally efficient optimization method based on sequential convex programming is developed and applied for the dynamic and adaptive reconfiguration of water distribution networks. An investigation is carried out using an operational network to evaluate the benefits of the proposed method for dynamically configurable water supply networks.
This data is extracted from the Web of Science and reproduced under a licence from Thomson Reuters. You may not copy or re-distribute this data in whole or in part without the written consent of the Science business of Thomson Reuters.