58 research outputs found
Recommended from our members
Long-Only Minimum Variance Portfolios Composition for Factor Models
No full textThe capital asset pricing model (CAPM) is widely used in finance to evaluate the performance of investments portfolios. Its main ingredient, the Markowitz portfolio selection problem, poses portfolio construction as an optimization problem balancing returns and “risk”, which is measured by variance. In practice, it is necessary to impose constraints on portfolios that violate many assumptions of the CAPM. The prime example is the long-only (optimization) constraint, which says that the investor must only hold nonnegative asset allocations. The first chapter of this thesis, we survey the optimization techniques that efficiently compute long-only Markowitz portfolios in the presence of a risk factor covariance model. The latter assumption is widely accepted as consistent with our empirical knowledge of financial markets. These algorithms fit within the broader field of convex optimization, which both emerged at a similar time to and partially because of the Markowitz portfolio problem.The second chapter of the thesis investigates the structure and composition of long-only minimum variance (Markowitz) portfolios mathematically, under a factor risk assumption. We prove a characterization of these portfolios in terms of the fixed point of a certain low dimensional mapping. The dimension of this mapping is equal to the number of risk factors in the model, and the portfolio has a closed form solution in terms of this fixed point. This approach facilitates highly efficient computation of both the portfolio weights and, because the fixed-point is differentiable, the sensitivities of these weights with respect to any risk model parameter. To compute the portfolio, we develop and analyze a new optimization method referred to as the fast fixed point (FFP) algorithm. We prove the convergence of its iterations for the single index (CAPM) model, and prove the equivalence of the FFP iterates to those of Newton’s method applied to a related root-finding problem.The last chapter concerns limit theorems for the number of active (i.e., strictly positive) weights of a long only minimum variance portfolio. More precisely, we determine the fraction of assets held as the portfolio size grows to infinity. These limit theorems, derived in the setting of a single (CAPM) index model, elucidate the dependence of the number of active weights on the distribution of the stock betas, which are assumed to be i.i.d. in our risk model. From these results we can infer the effective dimension of a portfolio, which is typically far smaller than the full portfolio size. This has implications for both investment practice and statistical modeling. For example, we show that the inclusion of negative beta stocks lead to more diversified (larger effective dimension) long-only portfolios than models with only positive stock betas. We confirm our theoretical findings on an empirical (WRDS) data set using a principal component based risk model, comparing them with another well known measure of portfolio concentration, the Herfindahl Index. With these results on effective dimension of a portfolio we derive asymptotics on both the estimated and true variance of a given long-only portfolio, and can characterize the limits of both in terms of the model’s parameters. We show that, in the limit, the estimated variance of the portfolio vanishes, but the true variance does not. 
Reachability-guided sampling for planning under differential constraints
No full textRapidly-exploring random trees (RRTs) are widely used to solve large planning problems where the scope prohibits the feasibility of deterministic solvers, but the efficiency of these algorithms can be severely compromised in the presence of certain kinodynamics constraints. Obstacle fields with tunnels, or tubes are notoriously difficult, as are systems with differential constraints, because the tree grows inefficiently at the boundaries. Here we present a new sampling strategy for the RRT algorithm, based on an estimated feasibility set, which affords a dramatic improvement in performance in these severely constrained systems. We demonstrate the algorithm with a detailed look at the expansion of an RRT in a swing up task, and on path planning for a nonholonomic car.United States. Defense Advanced Research Projects Agency (Learning Locomotion program (AFRL contract # FA8650-05-C-7262)
Path planning in 1000+ dimensions using a task-space Voronoi bias
No full textThe reduction of the kinematics and/or dynamics of a high-DOF robotic manipulator to a low-dimension ldquotask spacerdquo has proven to be an invaluable tool for designing feedback controllers. When obstacles or other kinodynamic constraints complicate the feedback design process, motion planning techniques can often still find feasible paths, but these techniques are typically implemented in the high-dimensional configuration (or state) space. Here we argue that providing a Voronoi bias in the task space can dramatically improve the performance of randomized motion planners, while still avoiding non-trivial constraints in the configuration (or state) space. We demonstrate the potential of task-space search by planning collision-free trajectories for a 1500 link arm through obstacles to reach a desired end-effector position.United States. Defense Advanced Research Projects Agency (Learning Locomotion program (AFRL contract # FA8650-05-C-7262)
Sample-based motion planning in high-dimensional and differentially-constrained systems
No full textThesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010.This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.Cataloged from student submitted PDF version of thesis.Includes bibliographical references (p. 115-124).State of the art sample-based path planning algorithms, such as the Rapidly-exploring Random Tree (RRT), have proven to be effective in path planning for systems subject to complex kinematic and geometric constraints. The performance of these algorithms, however, degrade as the dimension of the system increases. Furthermore, sample-based planners rely on distance metrics which do not work well when the system has differential constraints. Such constraints are particularly challenging in systems with non-holonomic and underactuated dynamics. This thesis develops two intelligent sampling strategies to help guide the search process. To reduce sensitivity to dimension, sampling can be done in a low-dimensional task space rather than in the high-dimensional state space. Altering the sampling strategy in this way creates a Voronoi Bias in task space, which helps to guide the search, while the RRT continues to verify trajectory feasibility in the full state space. Fast path planning is demonstrated using this approach on a 1500-link manipulator. To enable task-space biasing for underactuated systems, a hierarchical task space controller is developed by utilizing partial feedback linearization. Another sampling strategy is also presented, where the local reachability of the tree is approximated, and used to bias the search, for systems subject to differential constraints. Reachability guidance is shown to improve search performance of the RRT by an order of magnitude when planning on a pendulum and non-holonomic car. The ideas of task-space biasing and reachability guidance are then combined for demonstration of a motion planning algorithm implemented on LittleDog, a quadruped robot. The motion planning algorithm successfully planned bounding trajectories over extremely rough terrain.by Alexander C. Shkolnik.Ph.D
Recommended from our members
Sparse and Low-rank Matrix Decomposition – Application in Finance
No full textThe field of machine learning is witnessing a rapid expansion in the literature that explores techniques and applications of sparse and low-rank matrix decompositions. Typically formulated as an optimization problem involving nuclear norm minimization, this paradigm offers computational efficiency and robust statistical recovery guarantees, contrasting with the NP-hard nature of rank-based objectives. This thesis dedicates attention to the development of new methodology (Chapter 2) and also its application to finance (Chapter 3), as described below. Chapter 1 furnishes the necessary background and conducts a comprehensive survey of the related literature.Chapter 2 concerns dimensionality reduction methods such as principal component analysis (PCA) and factor analysis, which are central to many problems in data science. There are, however, serious and well-understood challenges to finding robust low dimensional approximations for data with significant heteroscedastic noise. This Chapter introduces a relaxed version of Minimum Trace Factor Analysis (MTFA), a convex optimization method with roots dating back to the work of Ledermann in 1940. This relaxation is particularly effective at not overfitting to heteroskedastic perturbations and addresses the commonly cited Heywood cases in factor analysis and the recently identified ``curse of ill-conditioning" for existing spectral methods. We provide theoretical guarantees on the accuracy of the resulting low rank subspace and the convergence rate of the proposed algorithm to compute that matrix. We develop a number of interesting connections to existing methods, including Hetero PCA, Lasso, and Soft-Impute, to fill an important gap in the already large literature on low rank matrix estimation. Numerical experiments benchmark our results against several recent proposals for dealing with heteroskedastic noise.In Chapter 3, we shift focus to factor analysis applied to security returns. Traditionally, commercially successful factor analysis relies on fundamental models, despite a rich academic literature exploring statistical models. Traditional statistical approaches like PCA and maximum likelihood exhibit success but suffer from drawbacks, such as a lack of robustness and insensitivity to narrow factors. To address these limitations, we propose convex optimization methods inspired by the techniques from Chapter 2. These methods aim to decompose a security return covariance matrix into its low-rank and sparse components. The low-rank component captures broad factors affecting most securities, while the sparse component accounts for narrow factors and security-specific effects. We illustrate the efficacy of this approach by measuring the variance forecasting accuracy of a low-rank plus sparse covariance matrix estimator through simulations and an empirical analysis of global equity data, showcasing improvements over PCA-based methods
Bounding on Rough Terrain with the LittleDog Robot
No full textA motion planning algorithm is described for bounding over rough terrain with the LittleDog robot. Unlike walking gaits, bounding is highly dynamic and cannot be planned with quasi-steady approximations. LittleDog is modeled as a planar five-link system, with a 16-dimensional state space; computing a plan over rough terrain in this high-dimensional state space that respects the kinodynamic constraints due to underactuation and motor limits is extremely challenging. Rapidly Exploring Random Trees (RRTs) are known for fast kinematic path planning in high-dimensional configuration spaces in the presence of obstacles, but search efficiency degrades rapidly with the addition of challenging dynamics. A computationally tractable planner for bounding was developed by modifying the RRT algorithm by using: (1) motion primitives to reduce the dimensionality of the problem; (2) Reachability Guidance, which dynamically changes the sampling distribution and distance metric to address differential constraints and discontinuous motion primitive dynamics; and (3) sampling with a Voronoi bias in a lower-dimensional “task space” for bounding. Short trajectories were demonstrated to work on the robot, however open-loop bounding is inherently unstable. A feedback controller based on transverse linearization was implemented, and shown in simulation to stabilize perturbations in the presence of noise and time delays.United States. Defense Advanced Research Projects Agency. Learning Locomotion Program (AFRL contract # FA8650-05-C-7262
Asymptotically-optimal path planning for manipulation using incremental sampling-based algorithms
No full textA desirable property of path planning for robotic manipulation is the ability to identify solutions in a sufficiently short amount of time to be usable. This is particularly challenging for the manipulation problem due to the need to plan over high-dimensional configuration spaces and to perform computationally expensive collision checking procedures. Consequently, existing planners take steps to achieve desired solution times at the cost of low quality solutions. This paper presents a planning algorithm that overcomes these difficulties by augmenting the asymptotically-optimal RRT* with a sparse sampling procedure. With the addition of a collision checking procedure that leverages memoization, this approach has the benefit that it quickly identifies low-cost feasible trajectories and takes advantage of subsequent computation time to refine the solution towards an optimal one. We evaluate the algorithm through a series of Monte Carlo simulations of seven, twelve, and fourteen degree of freedom manipulation planning problems in a realistic simulation environment. The results indicate that the proposed approach provides significant improvements in the quality of both the initial solution and the final path, while incurring almost no computational overhead compared to the RRT algorithm. We conclude with a demonstration of our algorithm for single-arm and dual-arm planning on Willow Garage's PR2 robot
ICEF2005-1221 HIGH EFFICIENCY HYBRID CYCLE ENGINE
No full textABSTRACT A "High Efficiency Hybrid Cycle" (HEHC) thermodynamic cycle is explored. This four-stroke cycle borrows elements from Otto, Diesel, Atkinson, and Rankine cycles. Air is compressed into an isolated combustion chamber, allowing for true isochoric combustion, and extended duration for combustion to proceed until completion. Combustion products expand into a chamber with greater volume than intake. We provide details of a compact HEHC design implementation using rotary pistons and isolated rotating combustion chambers. Two Pistons simultaneously rotate and reciprocate and are held in position by two roller bearings. One Piston performs intake and compression, while the other performs exhaust and expansion. We predict a reduction of energy losses, moving part counts, weight and size over conventional engines
- …
