Cybernetic causality II: Causal recursion in goal-directed systems,with applications to evolution dynamics and economics

Causal recursion, the fundamental concept of cybernetic causality, is shown to be more general than the concept of continuous,dynamical system, there being three types of causal recursions corresponding to continuous, reducibly discontinuous, and irreducibly discontinuous dynamical systems, respectively. Yet the topological language developed in the theory of continuous systems can be applied to an analysis of the important distinction between the ‘tasks’, performed by systems with a nilpotent causal recursion, and the ‘goals’ pursued by goal-directed systems, and to a characterization of the different categories of goals. It is shown that the self-regulating causal recursion underlying population dynamics defines a reducibly discontinuous dynamical system, and that the effects of discontinuity are essential in the survival or destruction of ecosystems. The concepts of turnpike and relative stability in the theory of economic growth are shown to be special cases of linear and nonlinear self-steering systems, respectively, and a general theorem on orbital convergence is proved.     

Optimal Feedback Control for Linear Systems with Input Delays Revisited

The design problem of optimal feedback control for linear systems with input delays is very important in many engineering applications. Usually, the linear systems with input delays are firstly converted into linear systems without delays, and then all the design procedures are based on the delay-free linear systems. In this way, the feedback controllers are not designed in terms of the original states. This paper presents some new closed-form formula in terms of the original states for the delayed optimal feedback control of linear systems with input delays. We firstly reveal the essential role of the input delay in the optimal control design of the linear system with a single input delay: the input delay postpones the action of the optimal control only. Based on this fact, we calculate the delayed optimal control and find that the optimal state can be represented by a simple closed-form formula, so that the delayed optimal feedback control can be obtained in a simple way. We show that the delayed feedback gain matrix can be “smaller” than that for the controlled system with zero input delay, which implies that the input delay can be considered as a positive factor. In addition, we give a general formula for the delayed optimal feedback control of time-variant linear systems with multiple input delays. To show the effectiveness and advantages of the main results, we present five illustrative examples with detailed numerical simulation and comparison.     

Orthogonal polynomials and semi-iterative methods for the Drazin-inverse solution of singular linear systems

Summary. In this work we present a novel class of semi-iterative methods for the Drazin-inverse solution of singular linear systems, whether consistent or inconsistent. The matrices of these systems are allowed to have arbitrary index and arbitrary spectra in the complex plane. The methods we develop are based on orthogonal polynomials and can all be implemented by 4-term recursion relations independently of the index. We give all the computational details of the associated algorithms. We also give a complete convergence analysis for all methods. Received June 28, 2000 / Revised version received May 23, 2001 / Published online January 30, 2002     

The discrete linear restricted Chebyshev approximation

A numerically stable simplex algorithm for calculating the restricted Chebyshev solution of overdetermined systems of linear equations is described. In this algorithm minimum computer storage is required and no conditions are imposed on the coefficient matrix or on the right hand side of the system of equations. Also a new way of implementing a triangular decomposition method to the basis matrix is used. The ordinary Chebyshev solution, the one-sided Chebyshev solutions and the Chebyshev approximation by non-negative functions are obtained as special cases in this algorithm. Numerical results are given.     

Limited risk control of the ornstein-uhleeck process

We consider the problem of steering a system described by a simple one dimensional: linear stochastic differential equation in such a way as to maximize the upper allowable limit that is exceeded by the final state with a prescribed probability. The optimal controls are computed by applying the maximum principle to an equivalent deterministic problem.. This model can be used among other things to find optimal strategies for specific advertising. activities of a firm.     

Differential equations and solution of linear systems

Many iterative processes can be interpreted as discrete dynamical systems and, in certain cases, they correspond to a time discretization of differential systems. In this paper, we propose to derive iterative schemes for solving linear systems of equations by modeling the problem to solve as a stable state of a proper differential system; the solution of the original linear problem is then computed numerically by applying a time marching scheme. We discuss some aspects of this approach, which allows to recover some known methods but also to introduce new ones. We give convergence results and numerical illustrations. AMS subject classification 65F10, 65F35, 65L05, 65L12, 65L20, 65N06     

Controller design for stabilizing bilinear systems with state-based switching

Some nonlinear systems can be approximated by switching bilinear systems. In this paper, we proposed a method to design state-based stabilizing controller for switching bilinear systems. Based on the similarity between switching bilinear systems and switching linear systems, corresponding switching linear systems are obtained for switching bilinear systems by applying state-based feedback control laws. Instead, we consider asymptotically stabilizing the corresponding switching linear system through solving a number of relaxed LMI conditions. Stabilizing controllers for switching bilinear systems can be derived based on the results of the corresponding switching linear systems. The stability of the controller is proved step by step through the decreasing of the multiple Lyapunov functions along the state trajectory. The effectiveness of the method is demonstrated by both a theoretical example and an example of urban traffic network with traffic signals.     

Completeness of two systems of illative combinatory logic for first-order propositional and predicate calculus

Illative combinatory logic consists of the theory of combinators or lambda calculus extended by extra constants (and corresponding axioms and rules) intended to capture inference. The paper considers 4 systems of illative combinatory logic that are sound for first-order propositional and predicate calculus. The interpretation from ordinary logic into the illative systems can be done in two ways: following the propositions-as-types paradigm, in which derivations become combinators, or in a more direct way, in which derivations are not translated. Both translations are closely related in a canonical way. In a preceding paper, Barendregt, Bunder and Dekkers, 1993, we proved completeness of the two direct translations. In the present paper we prove completeness of the two indirect translations by showing that the corresponding illative systems are conservative over the two systems for the direct translations. In another version, DBB (1997), we shall give a more direct completeness proof. These papers fulfill the program of Church and Curry to base logic on a consistent system of -terms or combinators. Hitherto this program had failed because systems of ICL were either too weak (to provide a sound interpretation) or too strong (sometimes even inconsistent). Received: February 15, 1996     

Correction of improper linear programming problems in canonical form by applying the minimax criterion

Given an inconsistent system of linear algebraic equations, necessary and sufficient conditions are established for the solvability of the problem of its matrix correction by applying the minimax criterion with the assumption that the solution is nonnegative. The form of the solution to the corrected system is presented. Two formulations of the problem are considered, specifically, the correction of both sides of the original system and correction with the right-hand-side vector being fixed. The minimax-criterion correction of an improper linear programming problem is reduced to a linear programming problem, which is solved numerically in MATLAB.     

Newton Generalized Hessenberg method for solving nonlinear systems of equations

In this paper, we give and analyze a Finite Difference version of the Generalized Hessenberg (FDGH) method. The obtained results show that applying this method in solving a linear system is equivalent to applying the Generalized Hessenberg method to a perturbed system. The finite difference version of the Generalized Hessenberg method is used in the context of solving nonlinear systems of equations using an inexact Newton method. The local convergence of the finite difference versions of the Newton Generalized Hessenberg method is studied. We obtain theoretical results that generalize those obtained for Newton-Arnoldi and Newton-GMRES methods. Numerical examples are given in order to compare the performances of the finite difference versions of the Newton-GMRES and Newton-CMRH methods. This revised version was published online in June 2006 with corrections to the Cover Date.     

Optimization of Discrete-Continuous Dynamic Systems Based on Disjunctive Programming

In this contribution, a novel approach for the modeling and optimization of discrete-continuous dynamic systems based on a disjunctive problem formulation is proposed. It will be shown that a disjunctive model representation, which constitutes an alternative to mixed-integer model formulations, provides a very flexible and intuitive way to formulate discrete-continuous dynamic optimization problems. Moreover, the structure and properties of the disjunctive process models can be exploited for an efficient and robust numerical solution by applying generalized disjunctive programming techniques. The proposed modeling and optimization approach will be illustrated by means of an optimal control problem that embeds a linear discretecontinuous dynamic system. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Parallel distributed-memory simplex for large-scale stochastic LP problems

We present a parallelization of the revised simplex method for large extensive forms of two-stage stochastic linear programming (LP) problems. These problems have been considered too large to solve with the simplex method; instead, decomposition approaches based on Benders decomposition or, more recently, interior-point methods are generally used. However, these approaches do not provide optimal basic solutions, which allow for efficient hot-starts (e.g., in a branch-and-bound context) and can provide important sensitivity information. Our approach exploits the dual block-angular structure of these problems inside the linear algebra of the revised simplex method in a manner suitable for high-performance distributed-memory clusters or supercomputers. While this paper focuses on stochastic LPs, the work is applicable to all problems with a dual block-angular structure. Our implementation is competitive in serial with highly efficient sparsity-exploiting simplex codes and achieves significant relative speed-ups when run in parallel. Additionally, very large problems with hundreds of millions of variables have been successfully solved to optimality. This is the largest-scale parallel sparsity-exploiting revised simplex implementation that has been developed to date and the first truly distributed solver. It is built on novel analysis of the linear algebra for dual block-angular LP problems when solved by using the revised simplex method and a novel parallel scheme for applying product-form updates.     

如何利用单纯形表上的信息

本文分析了求解线性规划的基本方法－－单纯形法所使用的单纯形表，将表中所提供的信息分为直接信息和间接信息两类，论述了如何充分利用这些信息的方法。例如如何由最终表求原问题、如何利用表中的数据互相推演和校正等。这是一篇教学经验的总结，对初学者可能有一定的帮助。     

A partitioning and bounded variable algorithm for linear programming

An interesting new partitioning and bounded variable algorithm (PBVA) is proposed for solving linear programming problems. The PBVA is a variant of the simplex algorithm which uses a modified form of the simplex method followed by the dual simplex method for bounded variables. In contrast to the two-phase method and the big M method, the PBVA does not introduce artificial variables. In the PBVA, a reduced linear program is formed by eliminating as many variables as there are equality constraints. A subproblem containing one ‘less than or equal to’ constraint is solved by executing the simplex method modified such that an upper bound is placed on an unbounded entering variable. The remaining constraints of the reduced problem are added to the optimal tableau of the subproblem to form an augmented tableau, which is solved by applying the dual simplex method for bounded variables. Lastly, the variables that were eliminated are restored by substitution. Differences between the PBVA and two other variants of the simplex method are identified. The PBVA is applied to solve an example problem with five decision variables, two equality constraints, and two inequality constraints. In addition, three other types of linear programming problems are solved to justify the advantages of the PBVA.     

Progress in the dual simplex method for large scale LP problems: practical dual phase 1 algorithms

The dual simplex algorithm has become a strong contender in solving large scale LP problems. One key problem of any dual simplex algorithm is to obtain a dual feasible basis as a starting point. We give an overview of methods which have been proposed in the literature and present new stable and efficient ways to combine them within a state-of-the-art optimization system for solving real world linear and mixed integer programs. Furthermore, we address implementation aspects and the connection between dual feasibility and LP-preprocessing. Computational results are given for a large set of large scale LP problems, which show our dual simplex implementation to be superior to the best existing research and open-source codes and competitive to the leading commercial code on many of our most difficult problem instances.     

相对不可约合作系统解的单调性

合作系统是一类重要的动力系统,本世纪八十年代Hirsch曾就不可约合作系统给出了一系列重要结论,但在实际问题中有许多合作系统不是不可约的却具有不可约合作系统的性质,本文提出了比不可约性更广的相对不可约概念,指出这类系统的解与严格不可约系统的解同样具有强单调性,并给出严格的证明,从而将Hirsch的结果做了进一步推广,最后介绍凝血系统中相对不可约合作系统的应用实例。     

Linear Programming with Special Ordered Sets

Concave objective functions which are both piecewise linear and separable are often encountered in a wide variety of management science problems. Provided the constraints are linear, problems of this kind are normally forced into a linear programming mould and solved using the simplex method. This paper takes another look at the associated linear programs and shows that they have special structural features which are not exploited by the simplex algorithm. It suggests that their variables can be divided into special ordered sets which can then be used to guide the pivoting strategies of the simplex algorithm with a resultant reduction in basis changes.     

A Simplex Approach for Finding Local Solutions of a Linear Bilevel Program by Equilibrium Points

In this paper, a linear bilevel programming problem (LBP) is considered. Local optimality conditions are derived. They are based on the notion of equilibrium point of an exact penalization for LBP. It is described how an equilibrium point can be obtained with the simplex method. It is shown that the information in the simplex tableaux can be used to get necessary and sufficient local optimality conditions for LBP. Based on these conditions, a simplex type algorithm is proposed, which attains a local solution of LBP by moving in equilibrium points. A numerical example illustrates how the algorithm works. Some computational results are reported.     

On Analyses of the Solution to a Linear Programming Problem

Many complex problem situations in various contexts have been represented in recent years by the linear programming model. The simplex method can then be used to give the optimal values of the variables corresponding to a given set of values of the parameters. However, in many situations it is useful to have the solution to many other related problems which differ from the original problem only in the values of some of the parameters. This paper presents procedures by which the solutions to the changed problems can be derived from the simplex solution tableau corresponding to the original problem. The method will be illustrated by means of an example problem, and it will be shown how quantitative information obtained from such analyses can aid management in decision making.