Paranormal operator on a Hilbert space

In this thesis an extensive study is made of the set P of all paranormal operators in B(H), the set of all bounded endomorphisms on the complex Hilbert space H. T ϵ B(H) is paranormal if for each z contained in the resolvent set of T, d(z, σ(T))//(T-zI)^-1 = 1 where d(z, σ(T)) is the distance from z to σ(T), the spectrum of T. P contains the set N of normal operators and P contains the set of hyponormal operators. However, P is contained in L, the set of all T ϵ B(H) such that the convex hull of the spectrum of T is equal to the closure of the numerical range of T. Thus, N≤P≤L.

If the uniform operator (norm) topology is placed on B(H), then the relative topological properties of N, P, L can be discussed. In Section IV, it is shown that: 1) N P and L are arc-wise connected and closed, 2) N, P, and L are nowhere dense subsets of B(H) when dim H ≥ 2, 3) N = P when dimH ˂ ∞ , 4) N is a nowhere dense subset of P when dimH ˂ ∞ , 5) P is not a nowhere dense subset of L when dimH ˂ ∞ , and 6) it is not known if P is a nowhere dense subset of L when dimH ˂ ∞.

The spectral properties of paranormal operators are of current interest in the literature. Putnam [22, 23] has shown that certain points on the boundary of the spectrum of a paranormal operator are either normal eigenvalues or normal approximate eigenvalues. Stampfli [26] has shown that a hyponormal operator with countable spectrum is normal. However, in Theorem 3.3, it is shown that a paranormal operator T with countable spectrum can be written as the direct sum, N ⊕ A, of a normal operator N with σ(N) = σ(T) and of an operator A with σ(A) a subset of the derived set of σ(T). It is then shown that A need not be normal. If we restrict the countable spectrum of T ϵ P to lie on a C²-smooth rectifiable Jordan curve G_o, then T must be normal [see Theorem 3.5 and its Corollary]. If T is a scalar paranormal operator with countable spectrum, then in order to conclude that T is normal the condition of σ(T) ≤ G_o can be relaxed [see Theorem 3.6]. In Theorem 3.7 it is then shown that the above result is not true when T is not assumed to be scalar. It was then conjectured that if T ϵ P with σ(T) ≤ G_o, then T is normal. The proof of Theorem 3.5 relies heavily on the assumption that T has countable spectrum and cannot be generalized. However, the corollary to Theorem 3.9 states that if T ϵ P with σ(T) ≤ G_o, then T has a non-trivial lattice of invariant subspaces. After the completion of most of the work on this thesis, Stampfli [30, 31] published a proof that a paranormal operator T with σ(T) ≤ G_o is normal. His proof uses some rather deep results concerning numerical ranges whereas the proof of Theorem 3.5 uses relatively elementary methods.

A Direct Approach to Robustness Optimization

This dissertation reformulates and streamlines the core tools of robustness analysis for linear time invariant systems using now-standard methods in convex optimization. In particular, robust performance analysis can be formulated as a primal convex optimization in the form of a semidefinite program using a semidefinite representation of a set of Gramians. The same approach with semidefinite programming duality is applied to develop a linear matrix inequality test for well-connectedness analysis, and many existing results such as the Kalman-Yakubovich--Popov lemma and various scaled small gain tests are derived in an elegant fashion. More importantly, unlike the classical approach, a decision variable in this novel optimization framework contains all inner products of signals in a system, and an algorithm for constructing an input and state pair of a system corresponding to the optimal solution of robustness optimization is presented based on this information. This insight may open up new research directions, and as one such example, this dissertation proposes a semidefinite programming relaxation of a cardinality constrained variant of the H ∞ norm, which we term sparse H ∞ analysis, where an adversarial disturbance can use only a limited number of channels. Finally, sparse H ∞ analysis is applied to the linearized swing dynamics in order to detect potential vulnerable spots in power networks.

A generalized Hausdorff dimension for functions and sets

Let E be a compact subset of the n-dimensional unit cube, 1_n, and let C be a collection of convex bodies, all of positive n-dimensional Lebesgue measure, such that C contains bodies with arbitrarily small measure. The dimension of E with respect to the covering class C is defined to be the number

d_C(E) = sup(β:H_{β, C}(E) > 0),

where H_{β, C} is the outer measure

inf(Ʃm(C_i)^β:UC_i Ↄ E, C_i ϵ C) .

Only the one and two-dimensional cases are studied. Moreover, the covering classes considered are those consisting of intervals and rectangles, parallel to the coordinate axes, and those closed under translations. A covering class is identified with a set of points in the left-open portion, 1’_n, of 1_n, whose closure intersects 1_n - 1’_n. For n = 2, the outer measure H_{β, C} is adopted in place of the usual:

Inf(Ʃ(diam. (C_i))^β: UC_i Ↄ E, C_i ϵ C),

for the purpose of studying the influence of the shape of the covering sets on the dimension d_C(E).

If E is a closed set in 1₁, let M(E) be the class of all non-decreasing functions μ(x), supported on E with μ(x) = 0, x ≤ 0 and μ(x) = 1, x ≥ 1. Define for each μ ϵ M(E),

d_C(μ) = lim/c → inf/0 log ∆μ(c)/log c , (c ϵ C)

where ∆μ(c) = v/x (μ(x+c) – μ(x)). It is shown that

d_C(E) = sup (d_C(μ):μ ϵ M(E)).

This notion of dimension is extended to a certain class Ӻ of sub-additive functions, and the problem of studying the behavior of d_C(E) as a function of the covering class C is reduced to the study of d_C(f) where f ϵ Ӻ. Specifically, the set of points in 1₁,

(*) {d_B(F), d_C(f)): f ϵ Ӻ}

is characterized by a comparison of the relative positions of the points of B and C. A region of the form (*) is always closed and doubly-starred with respect to the points (0, 0) and (1, 1). Conversely, given any closed region in 1₂, doubly-starred with respect to (0, 0) and (1, 1), there are covering classes B and C such that (*) is exactly that region. All of the results are shown to apply to the dimension of closed sets E. Similar results can be obtained when a finite number of covering classes are considered.

In two dimensions, the notion of dimension is extended to the class M, of functions f(x, y), non-decreasing in x and y, supported on 1₂ with f(x, y) = 0 for x · y = 0 and f(1, 1) = 1, by the formula

d_C(f) = lim/s · t → inf/0 log ∆f(s, t)/log s · t , (s, t) ϵ C

where

∆f(s, t) = V/x, y (f(x+s, y+t) – f(x+s, y) – f(x, y+t) + f(x, t)).

A characterization of the equivalence d_C1(f) = d_C2(f) for all f ϵ M, is given by comparison of the gaps in the sets of products s · t and quotients s/t, (s, t) ϵ C_i (I = 1, 2).

Two and Three Finger Caging of Polygons and Polyhedra

Multi-finger caging offers a rigorous and robust approach to robot grasping. This thesis provides several novel algorithms for caging polygons and polyhedra in two and three dimensions. Caging refers to a robotic grasp that does not necessarily immobilize an object, but prevents it from escaping to infinity. The first algorithm considers caging a polygon in two dimensions using two point fingers. The second algorithm extends the first to three dimensions. The third algorithm considers caging a convex polygon in two dimensions using three point fingers, and considers robustness of this cage to variations in the relative positions of the fingers.

This thesis describes an algorithm for finding all two-finger cage formations of planar polygonal objects based on a contact-space formulation. It shows that two-finger cages have several useful properties in contact space. First, the critical points of the cage representation in the hand’s configuration space appear as critical points of the inter-finger distance function in contact space. Second, these critical points can be graphically characterized directly on the object’s boundary. Third, contact space admits a natural rectangular decomposition such that all critical points lie on the rectangle boundaries, and the sublevel sets of contact space and free space are topologically equivalent. These properties lead to a caging graph that can be readily constructed in contact space. Starting from a desired immobilizing grasp of a polygonal object, the caging graph is searched for the minimal, intermediate, and maximal caging regions surrounding the immobilizing grasp. An example constructed from real-world data illustrates and validates the method.

A second algorithm is developed for finding caging formations of a 3D polyhedron for two point fingers using a lower dimensional contact-space formulation. Results from the two-dimensional algorithm are extended to three dimension. Critical points of the inter-finger distance function are shown to be identical to the critical points of the cage. A decomposition of contact space into 4D regions having useful properties is demonstrated. A geometric analysis of the critical points of the inter-finger distance function results in a catalog of grasps in which the cages change topology, leading to a simple test to classify critical points. With these properties established, the search algorithm from the two-dimensional case may be applied to the three-dimensional problem. An implemented example demonstrates the method.

This thesis also presents a study of cages of convex polygonal objects using three point fingers. It considers a three-parameter model of the relative position of the fingers, which gives complete generality for three point fingers in the plane. It analyzes robustness of caging grasps to variations in the relative position of the fingers without breaking the cage. Using a simple decomposition of free space around the polygon, we present an algorithm which gives all caging placements of the fingers and a characterization of the robustness of these cages.

The global optimization of phase-incoherent signals

The problem of global optimization of M phase-incoherent signals in N complex dimensions is formulated. Then, by using the geometric approach of Landau and Slepian, conditions for optimality are established for N = 2 and the optimal signal sets are determined for M = 2, 3, 4, 6, and 12.

The method is the following: The signals are assumed to be equally probable and to have equal energy, and thus are represented by points ṡ_i, i = 1, 2, …, M, on the unit sphere S₁ in C^N. If W_ik is the halfspace determined by ṡ_i and ṡ_k and containing ṡ_i, i.e. W_ik = {ṙϵC^N:| ≥ | ˂ṙ, ṡ_k˃|}, then the Ʀ_i = ∩/k≠i W_ik, i = 1, 2, …, M, the maximum likelihood decision regions, partition S₁. For additive complex Gaussian noise ṅ and a received signal ṙ = ṡ_ie^jϴ + ṅ, where ϴ is uniformly distributed over [0, 2π], the probability of correct decoding is P_C = 1/π^N ∞/ʃ/0 r^2N-1e^-(r2+1)U(r)dr, where U(r) = 1/M M/Ʃ/i=1 Ʀ_i ʃ/∩ S₁ I₀(2r | ˂ṡ, ṡ_i˃|)dσ(ṡ), and r = ǁṙǁ.

For N = 2, it is proved that U(r) ≤ ʃ/C_α I₀(2r|˂ṡ, ṡ_i˃|)dσ(ṡ) – 2K/M. h(1/2K [Mσ(C_α)-σ(S₁)]), where C_α = {ṡϵS₁:|˂ṡ, ṡ_i˃| ≥ α}, K is the total number of boundaries of the net on S₁ determined by the decision regions, and h is the strictly increasing strictly convex function of σ(C_α∩W), (where W is a halfspace not containing ṡ_i), given by h = ʃ/C_α∩W I₀ (2r|˂ṡ, ṡ_i˃|)dσ(ṡ). Conditions for equality are established and these give rise to the globally optimal signal sets for M = 2, 3, 4, 6, and 12.

Distributed Control and Optimization for Communication and Power Systems

We are at the cusp of a historic transformation of both communication system and electricity system. This creates challenges as well as opportunities for the study of networked systems. Problems of these systems typically involve a huge number of end points that require intelligent coordination in a distributed manner. In this thesis, we develop models, theories, and scalable distributed optimization and control algorithms to overcome these challenges.

This thesis focuses on two specific areas: multi-path TCP (Transmission Control Protocol) and electricity distribution system operation and control. Multi-path TCP (MP-TCP) is a TCP extension that allows a single data stream to be split across multiple paths. MP-TCP has the potential to greatly improve reliability as well as efficiency of communication devices. We propose a fluid model for a large class of MP-TCP algorithms and identify design criteria that guarantee the existence, uniqueness, and stability of system equilibrium. We clarify how algorithm parameters impact TCP-friendliness, responsiveness, and window oscillation and demonstrate an inevitable tradeoff among these properties. We discuss the implications of these properties on the behavior of existing algorithms and motivate a new algorithm Balia (balanced linked adaptation) which generalizes existing algorithms and strikes a good balance among TCP-friendliness, responsiveness, and window oscillation. We have implemented Balia in the Linux kernel. We use our prototype to compare the new proposed algorithm Balia with existing MP-TCP algorithms.

Our second focus is on designing computationally efficient algorithms for electricity distribution system operation and control. First, we develop efficient algorithms for feeder reconfiguration in distribution networks. The feeder reconfiguration problem chooses the on/off status of the switches in a distribution network in order to minimize a certain cost such as power loss. It is a mixed integer nonlinear program and hence hard to solve. We propose a heuristic algorithm that is based on the recently developed convex relaxation of the optimal power flow problem. The algorithm is efficient and can successfully computes an optimal configuration on all networks that we have tested. Moreover we prove that the algorithm solves the feeder reconfiguration problem optimally under certain conditions. We also propose a more efficient algorithm and it incurs a loss in optimality of less than 3% on the test networks.

Second, we develop efficient distributed algorithms that solve the optimal power flow (OPF) problem on distribution networks. The OPF problem determines a network operating point that minimizes a certain objective such as generation cost or power loss. Traditionally OPF is solved in a centralized manner. With increasing penetration of volatile renewable energy resources in distribution systems, we need faster and distributed solutions for real-time feedback control. This is difficult because power flow equations are nonlinear and kirchhoff's law is global. We propose solutions for both balanced and unbalanced radial distribution networks. They exploit recent results that suggest solving for a globally optimal solution of OPF over a radial network through a second-order cone program (SOCP) or semi-definite program (SDP) relaxation. Our distributed algorithms are based on the alternating direction method of multiplier (ADMM), but unlike standard ADMM-based distributed OPF algorithms that require solving optimization subproblems using iterative methods, the proposed solutions exploit the problem structure that greatly reduce the computation time. Specifically, for balanced networks, our decomposition allows us to derive closed form solutions for these subproblems and it speeds up the convergence by 1000x times in simulations. For unbalanced networks, the subproblems reduce to either closed form solutions or eigenvalue problems whose size remains constant as the network scales up and computation time is reduced by 100x compared with iterative methods.

On the Cesari fixed point method in a Banach space

In a paper published in 1961, L. Cesari [1] introduces a method which extends certain earlier existence theorems of Cesari and Hale ([2] to [6]) for perturbation problems to strictly nonlinear problems. Various authors ([1], [7] to [15]) have now applied this method to nonlinear ordinary and partial differential equations. The basic idea of the method is to use the contraction principle to reduce an infinite-dimensional fixed point problem to a finite-dimensional problem which may be attacked using the methods of fixed point indexes.

The following is my formulation of the Cesari fixed point method:

Let B be a Banach space and let S be a finite-dimensional linear subspace of B. Let P be a projection of B onto S and suppose Г≤B such that pГ is compact and such that for every x in PГ, P^-1x∩Г is closed. Let W be a continuous mapping from Г into B. The Cesari method gives sufficient conditions for the existence of a fixed point of W in Г.

Let I denote the identity mapping in B. Clearly y = Wy for some y in Г if and only if both of the following conditions hold:

(i) Py = PWy.

(ii) y = (P + (I - P)W)y.

Definition. The Cesari fixed paint method applies to (Г, W, P) if and only if the following three conditions are satisfied:

(1) For each x in PГ, P + (I - P)W is a contraction from P^-1x∩Г into itself. Let y(x) be that element (uniqueness follows from the contraction principle) of P^-1x∩Г which satisfies the equation y(x) = Py(x) + (I-P)Wy(x).

(2) The function y just defined is continuous from PГ into B.

(3) There are no fixed points of PWy on the boundary of PГ, so that the (finite- dimensional) fixed point index i(PWy, int PГ) is defined.

Definition. If the Cesari fixed point method applies to (Г, W, P) then define i(Г, W, P) to be the index i(PWy, int PГ).

The three theorems of this thesis can now be easily stated.

Theorem 1 (Cesari). If i(Г, W, P) is defined and i(Г, W, P) ≠0, then there is a fixed point of W in Г.

Theorem 2. Let the Cesari fixed point method apply to both (Г, W, P₁) and (Г, W, P₂). Assume that P₂P₁=P₁P₂=P₁ and assume that either of the following two conditions holds:

(1) For every b in B and every z in the range of P₂, we have that ‖b=P₂b‖ ≤ ‖b-z‖

(2)P₂Г is convex.

Then i(Г, W, P₁) = i(Г, W, P₂).

Theorem 3. If Ω is a bounded open set and W is a compact operator defined on Ω so that the (infinite-dimensional) Leray-Schauder index i_LS(W, Ω) is defined, and if the Cesari fixed point method applies to (Ω, W, P), then i(Ω, W, P) = i_LS(W, Ω).

Theorems 2 and 3 are proved using mainly a homotopy theorem and a reduction theorem for the finite-dimensional and the Leray-Schauder indexes. These and other properties of indexes will be listed before the theorem in which they are used.

Distributed Optimal Control of Cyber-Physical Systems: Controller Synthesis, Architecture Design and System Identification

The centralized paradigm of a single controller and a single plant upon which modern control theory is built is no longer applicable to modern cyber-physical systems of interest, such as the power-grid, software defined networks or automated highways systems, as these are all large-scale and spatially distributed. Both the scale and the distributed nature of these systems has motivated the decentralization of control schemes into local sub-controllers that measure, exchange and act on locally available subsets of the globally available system information. This decentralization of control logic leads to different decision makers acting on asymmetric information sets, introduces the need for coordination between them, and perhaps not surprisingly makes the resulting optimal control problem much harder to solve. In fact, shortly after such questions were posed, it was realized that seemingly simple decentralized optimal control problems are computationally intractable to solve, with the Wistenhausen counterexample being a famous instance of this phenomenon. Spurred on by this perhaps discouraging result, a concerted 40 year effort to identify tractable classes of distributed optimal control problems culminated in the notion of quadratic invariance, which loosely states that if sub-controllers can exchange information with each other at least as quickly as the effect of their control actions propagates through the plant, then the resulting distributed optimal control problem admits a convex formulation.

The identification of quadratic invariance as an appropriate means of "convexifying" distributed optimal control problems led to a renewed enthusiasm in the controller synthesis community, resulting in a rich set of results over the past decade. The contributions of this thesis can be seen as being a part of this broader family of results, with a particular focus on closing the gap between theory and practice by relaxing or removing assumptions made in the traditional distributed optimal control framework. Our contributions are to the foundational theory of distributed optimal control, and fall under three broad categories, namely controller synthesis, architecture design and system identification.

We begin by providing two novel controller synthesis algorithms. The first is a solution to the distributed H-infinity optimal control problem subject to delay constraints, and provides the only known exact characterization of delay-constrained distributed controllers satisfying an H-infinity norm bound. The second is an explicit dynamic programming solution to a two player LQR state-feedback problem with varying delays. Accommodating varying delays represents an important first step in combining distributed optimal control theory with the area of Networked Control Systems that considers lossy channels in the feedback loop. Our next set of results are concerned with controller architecture design. When designing controllers for large-scale systems, the architectural aspects of the controller such as the placement of actuators, sensors, and the communication links between them can no longer be taken as given -- indeed the task of designing this architecture is now as important as the design of the control laws themselves. To address this task, we formulate the Regularization for Design (RFD) framework, which is a unifying computationally tractable approach, based on the model matching framework and atomic norm regularization, for the simultaneous co-design of a structured optimal controller and the architecture needed to implement it. Our final result is a contribution to distributed system identification. Traditional system identification techniques such as subspace identification are not computationally scalable, and destroy rather than leverage any a priori information about the system's interconnection structure. We argue that in the context of system identification, an essential building block of any scalable algorithm is the ability to estimate local dynamics within a large interconnected system. To that end we propose a promising heuristic for identifying the dynamics of a subsystem that is still connected to a large system. We exploit the fact that the transfer function of the local dynamics is low-order, but full-rank, while the transfer function of the global dynamics is high-order, but low-rank, to formulate this separation task as a nuclear norm minimization problem. Finally, we conclude with a brief discussion of future research directions, with a particular emphasis on how to incorporate the results of this thesis, and those of optimal control theory in general, into a broader theory of dynamics, control and optimization in layered architectures.

Solar flare particle propagation--comparison of a new analytic solution with spacecraft measurements

A new analytic solution has been obtained to the complete Fokker-Planck equation for solar flare particle propagation including the effects of convection, energy-change, corotation, and diffusion with ĸ_r = constant and ĸ_Ɵ ∝ r². It is assumed that the particles are injected impulsively at a single point in space, and that a boundary exists beyond which the particles are free to escape. Several solar flare particle events have been observed with the Caltech Solar and Galactic Cosmic Ray Experiment aboard OGO-6. Detailed comparisons of the predictions of the new solution with these observations of 1-70 MeV protons show that the model adequately describes both the rise and decay times, indicating that ĸ_r = constant is a better description of conditions inside 1 AU than is ĸ_r ∝ r. With an outer boundary at 2.7 AU, a solar wind velocity of 400 km/sec, and a radial diffusion coefficient ĸ_r ≈ 2-8 x 10²⁰ cm²/sec, the model gives reasonable fits to the time-profile of 1-10 MeV protons from "classical" flare-associated events. It is not necessary to invoke a scatter-free region near the sun in order to reproduce the fast rise times observed for directly-connected events. The new solution also yields a time-evolution for the vector anisotropy which agrees well with previously reported observations.

In addition, the new solution predicts that, during the decay phase, a typical convex spectral feature initially at energy T_o will move to lower energies at an exponential rate given by T_KINK = T_oexp(-t/Ƭ_KINK). Assuming adiabatic deceleration and a boundary at 2.7 AU, the solution yields Ƭ_KINK ≈ 100h, which is faster than the measured ~200h time constant and slower than the adiabatic rate of ~78h at 1 AU. Two possible explanations are that the boundary is at ~5 AU or that some other energy-change process is operative.

Kinematics and Local Motion Planning for Quasi-static Whole-body Mobile Manipulation

This thesis studies mobile robotic manipulators, where one or more robot manipulator arms are integrated with a mobile robotic base. The base could be a wheeled or tracked vehicle, or it might be a multi-limbed locomotor. As robots are increasingly deployed in complex and unstructured environments, the need for mobile manipulation increases. Mobile robotic assistants have the potential to revolutionize human lives in a large variety of settings including home, industrial and outdoor environments.

Mobile Manipulation is the use or study of such mobile robots as they interact with physical objects in their environment. As compared to fixed base manipulators, mobile manipulators can take advantage of the base mechanism’s added degrees of freedom in the task planning and execution process. But their use also poses new problems in the analysis and control of base system stability, and the planning of coordinated base and arm motions. For mobile manipulators to be successfully and efficiently used, a thorough understanding of their kinematics, stability, and capabilities is required. Moreover, because mobile manipulators typically possess a large number of actuators, new and efficient methods to coordinate their large numbers of degrees of freedom are needed to make them practically deployable. This thesis develops new kinematic and stability analyses of mobile manipulation, and new algorithms to efficiently plan their motions.

I first develop detailed and novel descriptions of the kinematics governing the operation of multi- limbed legged robots working in the presence of gravity, and whose limbs may also be simultaneously used for manipulation. The fundamental stance constraint that arises from simple assumptions about friction and the ground contact and feasible motions is derived. Thereafter, a local relationship between joint motions and motions of the robot abdomen and reaching limbs is developed. Baseeon these relationships, one can define and analyze local kinematic qualities including limberness, wrench resistance and local dexterity. While previous researchers have noted the similarity between multi- fingered grasping and quasi-static manipulation, this thesis makes explicit connections between these two problems.

The kinematic expressions form the basis for a local motion planning problem that that determines the joint motions to achieve several simultaneous objectives while maintaining stance stability in the presence of gravity. This problem is translated into a convex quadratic program entitled the balanced priority solution, whose existence and uniqueness properties are developed. This problem is related in spirit to the classical redundancy resoxlution and task-priority approaches. With some simple modifications, this local planning and optimization problem can be extended to handle a large variety of goals and constraints that arise in mobile-manipulation. This local planning problem applies readily to other mobile bases including wheeled and articulated bases. This thesis describes the use of the local planning techniques to generate global plans, as well as for use within a feedback loop. The work in this thesis is motivated in part by many practical tasks involving the Surrogate and RoboSimian robots at NASA/JPL, and a large number of examples involving the two robots, both real and simulated, are provided.

Finally, this thesis provides an analysis of simultaneous force and motion control for multi- limbed legged robots. Starting with a classical linear stiffness relationship, an analysis of this problem for multiple point contacts is described. The local velocity planning problem is extended to include generation of forces, as well as to maintain stability using force-feedback. This thesis also provides a concise, novel definition of static stability, and proves some conditions under which it is satisfied.