Randomized Extended Kaczmarz For Solving Least Squares

We present a randomized iterative algorithm that exponentially converges in the mean square to the minimum l(2)-norm least squares solution of a given linear system of equations. The expected number of arithmetic operations required to obtain an estimate of given accuracy is proportional to the squared condition number of the system multiplied by the number of nonzero entries of the input matrix. The proposed algorithm is an extension of the randomized Kaczmarz method that was analyzed by Strohmer and Vershynin.

Quotient-method Algorithms for Input-affine Single-input Nonlinear Systems

Willson Sudarsandhari Shibani

Many real-world systems are intrinsically nonlinear. This thesis proposes various algorithms for designing control laws for input-affine single-input nonlinear systems. These algorithms, which are based on the concept of quotients used in nonlinear control design, can break down a single-input system into cascade of smaller subsystems of reduced dimension. These subsystems are well defined for feedback-linearizable systems. However, approximations are required to handle non-feedback-linearizable systems. The method proceeds iteratively and consists of two stages. During the forward stage, an equivalence relationship is defined to isolate the states that are not directly affected by the input, which reduces the dimension of the system. The resulting system is an input-affine single-input system controlled by a pseudo-input which represents a degree of freedom in the algorithm. The pseudo-input is a complementary state required to complete the diffeomorphism. This procedure is repeated (n − 1) times to give a one-dimensional system, where n is the dimension of the system. The backward stage begins with the one-dimensional system obtained at the end of the forward stage. It iteratively builds the control law required to stabilize the system. At every iteration, a desired profile of the pseudo-input is computed. In this next iteration, this desired profile is used to define an error that is driven asymptotically to zero using an appropriate control law. The quotient method is implemented through two algorithms, with and without diffeomorphism. The algorithm with diffeomorphism clearly depicts the dimension reduction at every iteration and provides a clear insight into the method. In this algorithm, a diffeomorphism is synthesized in order to obtain the normal form of the input vector field. The pseudo-input is the last coordinate of the new coordinate system. A normal projection is used to reduce the dimension of the system. For the algorithm to proceed without any approximation, it is essential that the last coordinate appears linearly in the projection of the transformed drift vector field. Necessary and sufficient conditions to achieve linearity in the last coordinate are given. Having the pseudo-input appearing linearly enables to represent the projected system as an input-affine system. Hence, the whole procedure can be repeated (n−1) times so as to obtain a one-dimensional system. In the second algorithm, a projection function based on the input vector field is defined that imitates both operators, the push forward operater and the normal projection operator of the previous algorithm. Due to the lack of an actual diffeomorphism, there is no apparent dimension reduction. Moreover, it is not directly possible to separate the drift vector field from the input vector field in the projected system. To overcome this obstacle, a bracket is defined that commutes with the projection function. This bracket provides the input vector field of the projected system. This enables the algorithm to proceed by repeating this procedure (n−1) times. As compared with the algorithm with diffeomorphism, the computational effort is reduced. The mathematical tools required to implement this algorithm are presented. A nice feature of these algorithms is the possibility to use the degrees of freedom to overcome singularities. This characteristic is demonstrated through a field-controlled DC motor. Furthermore, the algorithm also provides a way of approximating a non-feedback-linearizable system by a feedback-linearizable one. This has been demonstrated in the cases of the inverted pendulum and the acrobot. On the other hand, the algorithm without diffeomorphism has been demonstrated on the ball-on-a-wheel system. The quotient method can also be implemented whenever a simulation platform is available, that is when the differential equations for the system are not available in standard form. This is accomplished numerically by computing the required diffeomorphism based on the data available from the simulation platform. Two versions of the numerical algorithm are presented. One version leads to faster computations but uses approximation at various steps. The second version has better accuracy but requires considerably more computational time.

EPFL2012

Finite Dimensional Methods for Differential Flatness

Basile Graf

In Control System Theory, the study of continuous-time, finite dimensional, underdetermined systems of ordinary differential equations is an important topic. Classification of systems in different categories is a natural initial step to the analysis of a given control problem. Systems of equations can often be “transformed” into other “equivalent” ones. Then, a control system is associated to a set of equivalent equations. In this setting, a property of a control system can be defined as a property that has to be satisfied by some arbitrary system of equations in the set representing the control system. Assessing such a property can be a difficult task. In this thesis, we review and study a number of ways to determine whether a multi-input nonlinear system is flat, i.e. whether it is equivalent to a linear system after some dynamical extension and change of coordinates. This is a difficult as well as a well studied problem. Therefore, coming up with some altogether new approach or solution is to a certain extent illusory. A substantial part of the text is devoted to describing existing approaches and sometimes to propose either an original alternative or an original point of view. Another part of the thesis is dedicated to the study of a drastically reduced version of the problem, where more can be said in an algorithmic way. Nonlinear control systems are first modeled as the embedding of some fibered bundle to the first jet of the time-and-state-variables manifold. The exterior system, or Pfaffian system, corresponding to the ODE then arises naturally. Input prolongations are then introduced as lifts of the previously mentioned embedding. Various filtration techniques and their applications to static feedback linearization are discussed next. A full chapter is devoted to the infinite dimensional approach involving matrix differential operators. A now classical theorem, linking integrability of the basis of a differential module after application of one such an operator, and the flatness property is discussed. The relations obtained can be decomposed in an equivalent set of differentially closed equations. We state a version of the resulting theorem where the “curvature equations” are trivial. A subproblem that has attracted the attention of researchers is the question whether a given system — subject to some state constraints — is flat. In this setting, useful concepts are that of a covering of a system by another one and the accompanying result stating that a flat system can cover only a flat system. Hence, if a “large” linear system is given together with a set of nonlinear constraints, flatness of the constrained system is assessed if the unconstrained system can be shown to cover the constrained one. Starting with the classical notion of controlled invariance and a generalized notion coined dynamic controlled invariance, sufficient conditions are discussed which also involve the notion of right invertibility and the dynamic extension algorithm. Modeling of mechanical systems by free moving point masses subject to some control forces and quadratic constraints is often effective. The resulting unconstrained equations are linear and bilinear in the state and control/Lagrangian multiplier variables. We propose a relative derived flag that leads to a filtration with guaranteed integrability at each stage. This leads to a very effective sufficient condition for the flatness of the unconstrained model. The algorithm, together with the test described in the previous section, is used to show flatness of some generalized pendulum-like equations. They are also shown to specialize to the non-holonomic car equations and to the VTOL/pendulum equations when some specific parameters are suitably chosen.

EPFL2013

Locating Faults on Untransposed, Meshed Transmission Networks Using a Limited Number of Synchrophasor Measurements

Sadegh Azizi, Mario Paolone

The method of symmetrical components is not effective for fault location in the case of untransposed lines, due to potential couplings between the sequence circuits. This paper proposes a non-iterative algorithm in the phase-coordinates for wide-area fault location on untransposed transmission networks. In doing so, first, an improved two-terminal method is suggested to accurately locate faults on untransposed lines. Next, an algorithm is proposed to infer voltage and current phasors at the faulted line ends without direct measurements, by taking advantage of the data provided by phasor measurement units (PMUs). Accordingly, the adverse effect of close instrument transformers transients on the estimation accuracy is minimized. Being highly nonlinear in terms of fault distance and impedance, the fault equations are derived and made linear in this paper by defining six suitable auxiliary variables. The resulting system of equations is solved using the least-squares method to obtain three-phase voltages and currents at the faulted line ends. A main feature of the proposed algorithm is that it only requires a limited number of current and voltage synchrophasors. An additional advantage of the proposed algorithm is that the faulted line is not required to be known a-priori. The proposed algorithm is validated using extensive simulation studies on the New England 39-bus test system, accounting for different fault locations, types and resistances.