This thesis examines several problems related to singly-constrained Monotropic Network Flow Problems. In the first part, a linear time algorithm that reduces the solution of a monotropic network flow problem with an additional linear equality constraint to the solution of lower dimensional subproblems is presented. Of the subproblems, at most one is a singly-constrained monotropic network flow problem while the others are unconstrained. If none of the subproblems is constrained, the algorithm provides a linear-time transformation of constrained to unconstrained monotropic network flow problems. Extensions to nonlinear and inequality constraints are given. In the second part the qualitative theory of sensitivity analysis for Unconstrained Minimum-Cost Flow Problems presented by Granot and Veinott [GV85] is extended to Minimum-Cost Flow Problems with one additional linear constraint. The departure from the unconstrained network structure is shown to have a profound effect on computational issues. Two natural extensions of the "less-dependent-on" partial ordering of the arcs given in [GV85] are presented. One is decidable in linear time while the other yields more information but is NP-complete in general. The Ripple Theorem gives upper bounds on the absolute value of optimal-flow variations as a function of variations in the problem parameter. Moreover, it shows how changes may "ripple down" throughout the network, decreasing in magnitude as one gets "further away" from the arc whose parameter initiated the change. The Theory of Substitutes and Complements presents necessary and sufficient conditions for optimal-flow changes to consistently have the same (or the opposite) sign in two given arcs. The complexity of determining Substitutes and Complements is shown to be NP-complete in general. However, for all intractable problems, families of cases arise from easily recognizable graph structures and can be computed in linear time. The Monotonicity Theory links the changes in the value of the parameters to the change in the optimal arc-flows. Bounds on the rates of changes are discussed. We further provide a number of practical situations where our theory may apply. We discuss some Multi-Period Multi-Product Inventory-Production models that can be formulated as nonlinear parametric network flow problems with one additional linear constraint. We then apply our theory to help decision makers understand qualitatively how to respond to changes in the environment such as machine breakdown, strike or variations in inventory carrying costs without additional computation. In a second example, we show how a Cash-Flow Management model can be formulated as a nonlinear parametric network flow problem with one additional linear constraint. The theory is then recommended as a method by which a decision maker could understand qualitatively how to respond to changes in the environment such as variations in interest rates, taxes or asset prices without any additional computation. / Business, Sauder School of / Graduate

This thesis presents the formulation and solution of a new problem in systems and control theory, called the Network Realization Problem. Its relationship to other problems, such as State Realization and Structural Identifiability, is shown. The motivation for this work is the desire to completely quantify the conditions for transitioning between different mathematical representations of linear time-invariant systems. The solution to this problem is useful for theorists because it lays a foundation for quantifying the information cost of identifying a system's complete network structure from the transfer function.

No description available.

In the study of linear time-invariant systems, a number of definitions, such as controllability, observability, not having decentralized fixed modes, minimum phase, etc., have been made. These definitions are highly useful in obtaining existence results for solving various types of control problems, but a drawback to these definitions is that they are binary, which simply determines whether a system is, for instance, either controllable or uncontrollable. In practical situations, however, there are many uncertainties in a system’s parameters caused by linearization, modelling errors, discretizations, and other numerical approximations and/or errors. So knowing that a system is controllable can sometimes be misleading if the controllable system is actually "almost" uncontrollable as a result of such uncertainties. Since an "almost" uncontrollable system poses significant difficulty in designing a quality controller, a continuous measure of controllability, called a controllability radius, is more desirable to use and has been widely studied in the past. The main focus of this thesis is to extend the development behind the controllability radius, with an emphasis on real parametric perturbations, to other definitions, replacing the traditional binary 'yes/no' metrics with continuous measures. We study four topics related to this development. First, we generalize the concept of real perturbation values of a matrix to the cases of matrix pairs and matrix triplets. By doing so, we are able to deal with more general perturbation structures and subsequently study, in addition to standard LTI systems, other types of systems such as LTI descriptor and time-delay systems. Second, we introduce the real decentralized fixed mode (DFM) radius, the real transmission zero at s radius, and the real minimum phase radius, which respectively measure how "close" i) a decentralized LTI system is to having a DFM, ii) a centralized system is to having a transmission zero at a particular point s in the complex plane, and iii) a minimum phase system is to being a nonminimum phase system. These radii are defined in terms of real parametric perturbations, and computable formulas for these radii are derived using a characterization based on real perturbation values and the aforementioned generalizations. Third, we present two efficient algorithms to i) solve the general real perturbation value problem, and ii) evaluate the various real LTI robustness radii introduced in this thesis. Finally as the last topic, we study the ability of a LTI system to achieve high performance control, and characterize the difficulty of achieving high performance control using a new continuous measure called the Toughness Index. A number of examples involving the various measures are studied in this thesis.

In the study of linear time-invariant systems, a number of definitions, such as controllability, observability, not having decentralized fixed modes, minimum phase, etc., have been made. These definitions are highly useful in obtaining existence results for solving various types of control problems, but a drawback to these definitions is that they are binary, which simply determines whether a system is, for instance, either controllable or uncontrollable. In practical situations, however, there are many uncertainties in a system’s parameters caused by linearization, modelling errors, discretizations, and other numerical approximations and/or errors. So knowing that a system is controllable can sometimes be misleading if the controllable system is actually "almost" uncontrollable as a result of such uncertainties. Since an "almost" uncontrollable system poses significant difficulty in designing a quality controller, a continuous measure of controllability, called a controllability radius, is more desirable to use and has been widely studied in the past. The main focus of this thesis is to extend the development behind the controllability radius, with an emphasis on real parametric perturbations, to other definitions, replacing the traditional binary 'yes/no' metrics with continuous measures. We study four topics related to this development. First, we generalize the concept of real perturbation values of a matrix to the cases of matrix pairs and matrix triplets. By doing so, we are able to deal with more general perturbation structures and subsequently study, in addition to standard LTI systems, other types of systems such as LTI descriptor and time-delay systems. Second, we introduce the real decentralized fixed mode (DFM) radius, the real transmission zero at s radius, and the real minimum phase radius, which respectively measure how "close" i) a decentralized LTI system is to having a DFM, ii) a centralized system is to having a transmission zero at a particular point s in the complex plane, and iii) a minimum phase system is to being a nonminimum phase system. These radii are defined in terms of real parametric perturbations, and computable formulas for these radii are derived using a characterization based on real perturbation values and the aforementioned generalizations. Third, we present two efficient algorithms to i) solve the general real perturbation value problem, and ii) evaluate the various real LTI robustness radii introduced in this thesis. Finally as the last topic, we study the ability of a LTI system to achieve high performance control, and characterize the difficulty of achieving high performance control using a new continuous measure called the Toughness Index. A number of examples involving the various measures are studied in this thesis.

In this paper, the gap metric is introduced to study the robustness of the stability of feedback systems. A relation between the gap metric and coprime fractions is also investigated. It is shown that the stability radius of the controller in the gap metric is equal to the stability margin of the controller. In the loop-shaping design procedure in the £h-gap metric, it is practically hard to formulate an ideal controller. Finally, this paper studied the conservatism of the gap metric, and proposed some properties that can help for control design and analysis.

The Best MPhil Thesis in the Faculties of Dentistry, Engineering, Medicine and Science (University of Hong Kong), Li Ka Shing Prize,2009-2010 / published_or_final_version / Electrical and Electronic Engineering / Master / Master of Philosophy

This thesis studies the indirect adaptive control for discrete linear time invariant systems. The adaptive control strategy is based on the linear quadratic regulator that places the closed loop poles such that an infinite stage quadratic cost function is minimized. The plant parameters are identified recursively using a projection algorithm. / First, we study the effect of the model over-parametrization. For this purpose, we introduce an algorithm to generate the controller parameters recursively. This asymptotic reformulation is shown to overcome situations in which the pole-zero cancellation is a limit point of the identification algorithm. We also show that the algorithm will generate a unique control sequence that converges asymptotically to the solution of the Diophantine (pole assignment) equation. / Next, we study the stability of the proposed adaptive scheme in both deterministic and stochastic cases. We show that the global stability of the resulting adaptive scheme is obtained with no implicit assumptions about parameter convergence or the nature of the external input. Then the global convergence of the adaptive algorithm is obtained if the external input is "persistently exciting". By convergence we mean that the adaptive control will converge to the optimal control of the system. / The performance of the adaptive algorithm in the presence of deterministic disturbances is also considered, where we show that the adaptive controller performs relatively well if the model order is high enough to include a description of the disturbances.

Thesis (Ph.D.)--University of Western Australia, 2007.

Thesis (Ph. D.)--University of Texas at Austin, 1998. / Vita. Includes bibliographical references (leaves 102-108). Available also in a digital version from Dissertation Abstracts.