Topic overview
Topic snapshot
Next steps
The graph preview below keeps the nearby papers, people and communities visible in the same reading flow.
Topic graph
Inspect nearby papers, researchers, institutions and communities without opening a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Papers in this area
This paper presents new results for the modulus of families of walks on a graph---a discrete analog of the modulus of curve families due to Beurling and Ahlfors. Particular attention is paid to the dependence of the modulus on its parameters. Modulus is shown to generalize (and interpolate among) three important quantities in graph theory: shortest path, effective resistance, and max-flow or min-cut.
The alternating direction method of multipliers (ADM or ADMM) breaks a complex optimization problem into much simpler subproblems. The ADM algorithms are typically short and easy to implement yet exhibit (nearly) state-of-the-art performance for large-scale optimization problems. To apply ADM, we first formulate a given problem into the "ADM-ready" form, so the final algorithm depends on the formulation. A problem like $\mbox{minimize}_\mathbf{x} u(\mathbf{x}) + v(\mathbf{C}\mathbf{x})$ has six different "ADM-ready" formulations. They can be in the primal or dual forms, and they differ by how dummy variables are introduced. To each "ADM-ready" formulation, ADM can be applied in two different orders depending on how the primal variables are updated. Finally, we get twelve different ADM algorithms! How do they compare to each other? Which algorithm should one choose? In this paper, we show that many of the different ways of applying ADM are equivalent. Specifically, we show that ADM applied to a primal formulation is equivalent to ADM applied to its Lagrange dual; ADM is equivalent to a primal-dual algorithm applied to the saddle-point formulation of the same problem. These results are surprising since the primal and dual variables in ADM are seemingly treated very differently, and some previous work exhibit preferences in one over the other on specific problems. In addition, when one of the two objective functions is quadratic, possibly subject to an affine constraint, we show that swapping the update order of the two primal variables in ADM gives the same algorithm. These results identify the few truly different ADM algorithms for a problem, which generally have different forms of subproblems from which it is easy to pick one with the most computationally friendly subproblems.
The $\ell_1$-synthesis model and the $\ell_1$-analysis model recover structured signals from their undersampled measurements. The solution of former is a sparse sum of dictionary atoms, and that of the latter makes sparse correlations with dictionary atoms. This paper addresses the question: when can we trust these models to recover specific signals? We answer the question with a condition that is both necessary and sufficient to guarantee the recovery to be unique and exact and, in presence of measurement noise, to be robust. The condition is one--for--all in the sense that it applies to both of the $\ell_1$-synthesis and $\ell_1$-analysis models, to both of their constrained and unconstrained formulations, and to both the exact recovery and robust recovery cases. Furthermore, a convex infinity--norm program is introduced for numerically verifying the condition. A comprehensive comparison with related existing conditions are included.
This paper analyzes a steady state matching model interrelating the education and labor sectors. In this model, a heterogeneous population of students match with teachers to enhance their cognitive skills. As adults, they then choose to become workers, managers, or teachers, who match in the labor or educational market to earn wages by producing output. We study the competitive equilibrium which results from the steady state requirement that the educational process replicate the same endogenous distribution of cognitive skills among adults in each generation (assuming the same distribution of student skills). We show such an equilibrium can be found by solving an infinite-dimensional linear program and its dual. We analyze the structure of our solutions, and give sufficient conditions for them to be unique. Whether or not the educational matching is positive assortative turns out to depend on convexity of the equilibrium wages as a function of ability, suitably parameterized; we identity conditions which imply this convexity. Moreover, due to the recursive nature of the education market, it is a priori conceivable that a pyramid scheme leads to greater and greater discrepancies in the wages of the most talented teachers at the top of the market. Assuming each teacher teaches $N$ students, and contributes a fraction $θ\in]0,1[$ to their cognitive skill, we show a phase transition occurs at $Nθ=1$, which determines whether or not the wage gradients of these teachers remain bounded as market size grows, and make a quantitative prediction for their asymptotic behaviour in both regimes: $Nθ\ge 1$ and $Nθ<1$.
Fix probability densities $f$ and $g$ on open sets $X \subset \mathbf{R}^m$ and $Y \subset \mathbf{R}^n$ with $m\ge n\ge1$. Consider transporting $f$ onto $g$ so as to minimize the cost $-s(x,y)$. We give a non-degeneracy condition (a) on $s \in C^{1,1}$ which ensures the set of $x$ paired with [$g$-a.e.] $y\in Y$ lie in a codimension $n$ submanifold of $X$. Specializing to the case $m>n=1$, we discover a nestedness criteria relating $s$ to $(f,g)$ which allows us to construct a unique optimal solution in the form of a map $F:X \longrightarrow \overline Y$. When $s\in C^2 \cap W^{3,1}$ and $\log f$ and $\log g$ are bounded, the Kantorovich dual potentials $(u,v)$ satisfy $v \in C^{1,1}_{loc}(Y)$, and the normal velocity $V$ of $F^{-1}(y)$ with respect to changes in $y$ is given by $V(x) = v"(f(x))-s_{yy}(x,f(x))$. Positivity (b) of $V$ locally implies a Lipschitz bound on $f$; moreover, $v \in C^2$ if ${F^{-1}(y)}$ intersects $\partial X \in C^1$ transversally (c). On subsets where (a)-(c) can be be quantified, for each integer $r \ge1$ the norms of $u,v \in C^{r+1,1}$ and $F \in C^{r,1}$ are controlled by these bounds, $||\log f,\log g, \partial X ||_{C^{r-1,1}}, ||\partial X||_{C^{1,1}}$, $||s||_{C^{r+1,1}}$, and the smallness of $F^{-1}(y)$. We give examples showing regularity extends from $X$ to part of $\bar X$, but not from $Y$ to $\bar Y$. We also show that when $s$ remains nested for all $(f,g)$, the problem in $\mathbf{R}^m \times \mathbf{R}$ reduces to a supermodular problem in $\mathbf{R} \times \mathbf{R}$.
Shifted combinatorial optimization is a new nonlinear optimization framework which is a broad extension of standard combinatorial optimization, involving the choice of several feasible solutions at a time. This framework captures well studied and diverse problems ranging from so-called vulnerability problems to sharing and partitioning problems. In particular, every standard combinatorial optimization problem has its shifted counterpart, which is typically much harder. Already with explicitly given input set the shifted problem may be NP-hard. In this article we initiate a study of the parameterized complexity of this framework. First we show that shifting over an explicitly given set with its cardinality as the parameter may be in XP, FPT or P, depending on the objective function. Second, we study the shifted problem over sets definable in MSO logic (which includes, e.g., the well known MSO partitioning problems). Our main results here are that shifted combinatorial optimization over MSO definable sets is in XP with respect to the MSO formula and the treewidth (or more generally clique-width) of the input graph, and is W[1]-hard even under further severe restrictions.
The Lobula Giant Movement Detector (LGMD) is a an identified neuron of the locust that detects looming objects and triggers its escape responses. Understanding the neural principles and networks that lead to these fast and robust responses can lead to the design of efficient facilitate obstacle avoidance strategies in robotic applications. Here we present a neuromorphic spiking neural network model of the LGMD driven by the output of a neuromorphic Dynamic Vision Sensor (DVS), which has been optimised to produce robust and reliable responses in the face of the constraints and variability of its mixed signal analogue-digital circuits. As this LGMD model has many parameters, we use the Differential Evolution (DE) algorithm to optimise its parameter space. We also investigate the use of Self-Adaptive Differential Evolution (SADE) which has been shown to ameliorate the difficulties of finding appropriate input parameters for DE. We explore the use of two biological mechanisms: synaptic plasticity and membrane adaptivity in the LGMD. We apply DE and SADE to find parameters best suited for an obstacle avoidance system on an unmanned aerial vehicle (UAV), and show how it outperforms state-of-the-art Bayesian optimisation used for comparison.
The notion of $p$-modulus of a family of objects on a graph is a measure of the richness of such families. We develop the notion of minimal subfamilies using the method of Lagrangian duality for $p$-modulus. We show that minimal subfamilies have at most $|E|$ elements and that these elements carry a weight related to their "importance" in relation to the corresponding $p$-modulus problem. When $p=2$, this measure of importance is in fact a probability measure and modulus can be thought as trying to minimize the expected overlap in the family.
A monopolist wishes to maximize her profits by finding an optimal price policy. After she announces a menu of products and prices, each agent $x$ will choose to buy that product $y(x)$ which maximizes his own utility, if positive. The principal's profits are the sum of the net earnings produced by each product sold. These are determined by the costs of production and the distribution of products sold, which in turn are based on the distribution of anonymous agents and the choices they make in response to the principal's price menu. In this paper, we provide a necessary and sufficient condition for the convexity or concavity of the principal's (bilevel) optimization problem, assuming each agent's disutility is a strictly increasing but not necessarily affine (i.e. quasilinear) function of the price paid. Concavity when present, makes the problem more amenable to computational and theoretical analysis; it is key to obtaining uniqueness and stability results for the principal's strategy in particular. Even in the quasilinear case, our analysis goes beyond previous work by addressing convexity as well as concavity, by establishing conditions which are not only sufficient but necessary, and by requiring fewer hypotheses on the agents' preferences.
In today's literature "Model-Free Control," or MFC, and "Active Disturbance Rejection Control," or ADRC, are the most prominent approaches in order to keep the benefits of PID controllers, that are so popular in the industrial world, and in the same time for attenuating their severe shortcomings. After a brief review of MFC and ADRC, several examples show the superiority of MFC, which permits to tackle most easily a much wider class of systems.
Recent years have witnessed the surge of asynchronous parallel (async-parallel) iterative algorithms due to problems involving very large-scale data and a large number of decision variables. Because of asynchrony, the iterates are computed with outdated information, and the age of the outdated information, which we call delay, is the number of times it has been updated since its creation. Almost all recent works prove convergence under the assumption of a finite maximum delay and set their stepsize parameters accordingly. However, the maximum delay is practically unknown. This paper presents convergence analysis of an async-parallel method from a probabilistic viewpoint, and it allows for large unbounded delays. An explicit formula of stepsize that guarantees convergence is given depending on delays' statistics. With $p+1$ identical processors, we empirically measured that delays closely follow the Poisson distribution with parameter $p$, matching our theoretical model, and thus the stepsize can be set accordingly. Simulations on both convex and nonconvex optimization problems demonstrate the validness of our analysis and also show that the existing maximum-delay induced stepsize is too conservative, often slowing down the convergence of the algorithm.
The theory of $n$-fold integer programming has been recently emerging as an important tool in parameterized complexity. The input to an $n$-fold integer program (IP) consists of parameter $A$, dimension $n$, and numerical data of binary encoding length $L$. It was known for some time that such programs can be solved in polynomial time using $O(n^{g(A)}L)$ arithmetic operations where $g$ is an exponential function of the parameter. In 2013 it was shown that it can be solved in fixed-parameter tractable (FPT) time using $O(f(A)n^3L)$ arithmetic operations for a single-exponential function $f$. This, and a faster algorithm for a special case of combinatorial $n$-fold IP, have led to several very recent breakthroughs in the parameterized complexity of scheduling, stringology, and computational social choice. In 2015 it was shown that it can be solved in strongly polynomial time using $O(n^{g(A)})$ arithmetic operations. Here we establish a result which subsumes all three of the above results by showing that $n$-fold IP can be solved in strongly polynomial FPT time using $O(f(A)n^3)$ arithmetic operations. In fact, our results are much more general, briefly outlined as follows. - There is a strongly polynomial algorithm for ILP whenever a so-called Graver-best oracle is realizable for it. - Graver-best oracles for the large classes of multi-stage stochastic and tree-fold ILPs can be realized in FPT time. Together with the previous oracle algorithm, this newly shows two large classes of ILP to be strongly polynomial; in contrast, only few classes of ILP were previously known to be strongly polynomial. - We show that ILP is FPT parameterized by the largest coefficient $\|A\|_\infty$ and the primal or dual treedepth of $A$, and that this parameterization cannot be relaxed, signifying substantial progress in understanding the parameterized complexity of ILP.
In this paper, we extend the methodology developed for Support Vector Machines (SVM) using $\ell_2$-norm ($\ell_2$-SVM) to the more general case of $\ell_p$-norms with $p\ge 1$ ($\ell_p$-SVM). The resulting primal and dual problems are formulated as mathematical programming problems; namely, in the primal case, as a second order cone optimization problem and in the dual case, as a polynomial optimization problem involving homogeneous polynomials. Scalability of the primal problem is obtained via general transformations based on the expansion of functionals in Schauder spaces. The concept of Kernel function, widely applied in $\ell_2$-SVM, is extended to the more general case by defining a new operator called multidimensional Kernel. This object gives rise to reformulations of dual problems, in a transformed space of the original data, which are solved by a moment-sdp based approach. The results of some computational experiments on real-world datasets are presented showing rather good behavior in terms of standard indicators such a \textit{accuracy index} and its ability to classify new data.
Nonlinear model predictive control has become a popular approach to deal with highly nonlinear and unsteady state systems, the performance of which can however deteriorate due to unaccounted uncertainties. Model predictive control is commonly used with states from a state estimator in place of the exact states without consideration of the error. In this paper an approach is proposed by incorporating the unscented Kalman filter into the NMPC problem, which propagates uncertainty introduced from both the state estimate and additive noise from disturbances forward in time. The feasibility is maintained through probabilistic constraints based on the Gaussian approximations of the state distributions. The concept of robust horizon is introduced to limit the open loop covariances, which otherwise grow too large and lead to conservativeness and infeasibility of the MPC problem. The effectiveness of the approach was tested on a challenging semi batch reactor case study with an economic objective.
This paper presents a family of new methods for locating/fitting hyperplanes with respect to a given set of points. We introduce a general framework for a family of aggregation criteria of different distance-based errors. The most popular methods found in the specialized literature can be cast within this family as particular choices of the errors and the aggregation criteria. Mathematical programming formulations for these methods are stated and some interesting cases are analyzed. It is also proposed a new goodness of fitting index which extends the classical coefficient of determination. A series of illustrative examples and extensive computational experiments implemented in R are provided to show the performances of some of the proposed methods.
In this paper, we present a novel approach to construct multiclass classifiers by means of arrangements of hyperplanes. We propose different mixed integer (linear and non linear) programming formulations for the problem using extensions of widely used measures for misclassifying observations where the \textit{kernel trick} can be adapted to be applicable. Some dimensionality reductions and variable fixing strategies are also developed for these models. An extensive battery of experiments has been run which reveal the powerfulness of our proposal as compared with other previously proposed methodologies.
The question of controllability of natural and man-made network systems has recently received considerable attention. In the context of the human brain, the study of controllability may not only shed light into the organization and function of different neural circuits, but also inform the design and implementation of minimally invasive yet effective intervention protocols to treat neurological disorders. While the characterization of brain controllability is still in its infancy, some results have recently appeared and given rise to scientific debate. Among these, [1] has numerically shown that a class of brain networks constructed from DSI/DTI imaging data are controllable from one brain region. That is, a single brain region is theoretically capable of moving the whole brain network towards any desired target state. In this note we provide evidence supporting controllability of brain networks from a single region as discussed in [1], thus contradicting the main conclusion and methods developed in [2].
Supply chain management and inventory control provide most exciting examples of control systems with delays. Here, Smith predictors, model-free control and new time series forecasting techniques are mixed in order to derive an efficient control synthesis. Perishable inventories are also taken into account. The most intriguing "bullwhip effect" is explained and attenuated, at least in some important situations. Numerous convincing computer simulations are presented and discussed.
The time evolution of a collisionless plasma is modeled by the Vlasov-Maxwell system which couples the Vlasov equation (the transport equation) with the Maxwell equations of electrodynamics. We only consider a 'two-dimensional' version of the problem since existence of global, classical solutions of the full three-dimensional problem is not known. We add external currents to the system, in applications generated by coils, to control the plasma in a proper way. After considering global existence of solutions to this system, differentiability of the control-to-state operator is proved. In applications, on the one hand, we want the shape of the plasma to be close to some desired shape. On the other hand, a cost term penalizing the external currents shall be as small as possible. These two aims lead to minimizing some objective function. We restrict ourselves to only such control currents that are realizable in applications. After that, we prove existence of a minimizer and deduce first order optimality conditions and the adjoint equation.
Sign information is the key to overcoming the inevitable saturation error in compressive sensing systems, which causes information loss and results in bias. For sparse signal recovery from saturation, we propose to use a linear loss to improve the effectiveness from existing methods that utilize hard constraints/hinge loss for sign consistency. Due to the use of linear loss, an analytical solution in the update progress is obtained, and some nonconvex penalties are applicable, e.g., the minimax concave penalty, the $\ell_0$ norm, and the sorted $\ell_1$ norm. Theoretical analysis reveals that the estimation error can still be bounded. Generally, with linear loss and nonconvex penalties, the recovery performance is significantly improved, and the computational time is largely saved, which is verified by the numerical experiments.
The reduced level of system inertia in low-carbon power grids increases the need for alternative frequency services. However, simultaneously optimising the provision of these services in the scheduling process, subject to significant uncertainty, is a complex task given the challenge of linking the steady-state optimisation with frequency dynamics. This paper proposes a novel frequency-constrained Stochastic Unit Commitment (SUC) model which, for the first time, co-optimises energy production along with the provision of synchronised and synthetic inertia, Enhanced Frequency Response (EFR), Primary Frequency Response (PFR) and a dynamically-reduced largest power infeed. The contribution of load damping is modelled through a linear inner approximation. The effectiveness of the proposed model is demonstrated through several case studies for Great Britain's 2030 power system, which highlight the synergies and conflicts among alternative frequency services, as well as the significant economic savings and carbon reduction achieved by simultaneously optimising all these services.
The problem of feed-forward control of overhead crane system is discussed. By combining the Kalman's controllability theory and Hartman-Grobman theorem from dynamical system theory, a linear, continuous state feedback-based feed-forward controller that stabilizes the crane system at the desired end position of payload is designed. The efficacy of proposed controller is demonstrated by comparing the simulation experiment results for overhead crane with/without time-varying length of hoisting rope.
It is a very challenging task to identify the objectives on which a certain decision was based, in particular if several, potentially conflicting criteria are equally important and a continuous set of optimal compromise decisions exists. This task can be understood as the inverse problem of multiobjective optimization, where the goal is to find the objective vector of a given Pareto set. To this end, we present a method to construct the objective vector of a multiobjective optimization problem (MOP) such that the Pareto critical set contains a given set of data points or decision vectors. The key idea is to consider the objective vector in the multiobjective KKT conditions as variable and then search for the objectives that minimize the Euclidean norm of the resulting system of equations. By expressing the objectives in a finite-dimensional basis, we transform this problem into a homogeneous, linear system of equations that can be solved efficiently. There are many important potential applications of this approach. Besides the identification of objectives (both from clean and noisy data), the method can be used for the construction of surrogate models for expensive MOPs, which yields significant speed-ups. Both applications are illustrated using several examples.
We consider the problem of overbounding and underbounding both the backward and forward reachable set for a given polynomial vector field, nonlinear in both state and input, with a given semialgebriac set of initial conditions and with inputs constrained pointwise to lie in a semialgebraic set. Specifically, we represent the forward reachable set using the value function which gives the optimal cost to go of an optimal control problems and if smooth satisfies the Hamilton-Jacobi- Bellman PDE. We then show that there exist polynomial upper and lower bounds to this value function and furthermore, these polynomial sub-value and super-value functions provide provable upper and lower bounds to the forward reachable set. Finally, by minimizing the distance between these sub-value and super-value functions in the L1-norm, we are able to construct inner and outer bounds for the reachable set and show numerically on several examples that for relatively small degree, the Hausdorff distance between these bounds is negligible.
People in this topic
Researcher
Yang Liu contributes to research discovery and scholarly infrastructure.
Open to collaborateResearcher
Y. Zhang contributes to research discovery and scholarly infrastructure.
Open to collaborateResearcher
Lei Zhang contributes to research discovery and scholarly infrastructure.
Open to collaborateResearcher
Wei Wang contributes to research discovery and scholarly infrastructure.
Open to collaborateResearcher
Wei Zhang contributes to research discovery and scholarly infrastructure.
Open to collaborateResearcher
Hao Wang contributes to research discovery and scholarly infrastructure.
Open to collaborateResearcher
Rui Wang contributes to research discovery and scholarly infrastructure.
Open to collaborateResearcher
Meng Wang contributes to research discovery and scholarly infrastructure.
Open to collaborateResearcher
Bo Li contributes to research discovery and scholarly infrastructure.
Open to collaborateResearcher
Yang Zhang contributes to research discovery and scholarly infrastructure.
Open to collaborateResearcher
Yang Li contributes to research discovery and scholarly infrastructure.
Open to collaborateResearcher
C. Chen contributes to research discovery and scholarly infrastructure.
Open to collaborate