On the inversion problem for nonlinear systems

A new homology technique is applied to the inversion problemfor nonlinear systems, both in the input—output and state-spaceformulations.     

A simplicial algorithm for the nonlinear complementarity problem

A triangulation of the nonnegative orthant and a special labeling of the vertices lead to a combinatorial procedure for seeking solutions or approximate solutions to the nonlinear complementarity problem under coercive-like assumptions on the problem functions. Derivatives are not required. Convergence is proved, computational considerations are discussed, and some preliminary applications to convex programming and saddle point computation, along with numerical results, are presented.     

On the Cauchy problem for nonlinear dissipative systems

The large-time asymptotic behavior of solutions of the Cauchy problem for a system of nonlinear evolutionary equations with dissipation is studied. The approach used in the case of small initial data is based on the construction of solutions by the method of contracting mappings. In the case of large initial data, we will obtain the large-time asymptotics of solutions with a certain symmmetry of a nonlinear term taken into account. In the critical case, it is proved that if the initial data has a nonzero total mass, then the principal term of the large-time asymptotics of a solution is given by the self-similar solution uniquely determined by the total mass of the initial data. __________ Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 29, Voronezh Conference-1, 2005.     

An algorithm for the mixed-integer nonlinear bilevel programming problem

The bilevel programming problem (BLPP) is a two-person nonzero sum game in which play is sequential and cooperation is not permitted. In this paper, we examine a class of BLPPs where the leader controls a set of continuous and discrete variables and tries to minimize a convex nonlinear objective function. The follower's objective function is a convex quadratic in a continuous decision space. All constraints are assumed to be linear. A branch and bound algorithm is developed that finds global optima. The main purpose of this paper is to identify efficient branching rules, and to determine the computational burden of the numeric procedures. Extensive test results are reported. We close by showing that it is not readily possible to extend the algorithm to the more general case involving integer follower variables.This work was supported by a grant from the Advanced Research Program of the Texas Higher Education Coordinating Board.     

On Tamir's algorithm for solving the nonlinear complementarity problem

Some comments concerning Tamir's algorithm for solving the nonlinear complementarity problem are given. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A simple Marquardt algorithm for the nonlinear least-squares problem

A new implementation of the Marquardt method for the nonlinear least-squares problem is presented. The algorithm is very simple but its performance with nine test functions is at least comparable with either Davidon-Fletcher-Powell's method or Moré's adaptive Marquardt method.     

A linear eigenvalue algorithm for the nonlinear eigenvalue problem

The Arnoldi method for standard eigenvalue problems possesses several attractive properties making it robust, reliable and efficient for many problems. The first result of this paper is a characterization of the solutions to an arbitrary (analytic) nonlinear eigenvalue problem (NEP) as the reciprocal eigenvalues of an infinite dimensional operator denoted ${\mathcal {B}}$ . We consider the Arnoldi method for the operator ${\mathcal {B}}$ and show that with a particular choice of starting function and a particular choice of scalar product, the structure of the operator can be exploited in a very effective way. The structure of the operator is such that when the Arnoldi method is started with a constant function, the iterates will be polynomials. For a large class of NEPs, we show that we can carry out the infinite dimensional Arnoldi algorithm for the operator ${\mathcal {B}}$ in arithmetic based on standard linear algebra operations on vectors and matrices of finite size. This is achieved by representing the polynomials by vector coefficients. The resulting algorithm is by construction such that it is completely equivalent to the standard Arnoldi method and also inherits many of its attractive properties, which are illustrated with examples.     

The controllability problem for nonlinear Volterra systems

We discuss the controllability of systems whose dynamics are governed by a large class of nonlinear Volterra integral equations. The property of controllability is shown to be equivalent to the existence of a fixed point of a certain set-valued map. We show that convexity and seminormality conditions intimately related to those assumed in proofs of existence theorems for optimal controls are sufficient to guarantee controllability. Approximate controllability results are obtained by first introducing generalized solutions and then showing, under only mild additional restrictions, that ordinary solutions are dense in this broader class of trajectories.Dedicated to L. CesariTu se' lo mio maestro e il mio autore: Tu se' solo colui, da cui io tolsi Lo bello stile che m' ha fatto onore. Dante, Canto I: 85–87This work was written while the author was on leave to the Institut für Numerische und Angewandte Mathematik, Universität Göttingen, Göttingen, West Germany.     

On the terminal control problem for nonlinear discrete-time systems

The solvability of the synthesis problem for a control transferring a nonlinear discrete-time system of order m from the zero state into any given state in m + 1 steps is proved.     

A dynamic programming algorithm for the bilevel knapsack problem

We propose an efficient dynamic programming algorithm for solving a bilevel program where the leader controls the capacity of a knapsack, and the follower solves the resulting knapsack problem. We propose new recursive rules and show how to solve the problem as a sequence of two standard knapsack problems.     

一种求解非线性互补问题的filter内点算法

利用Armijio条件和信赖域方法,构造新的价值函数.首次将内点算法与filter技术结合起来,提出一种求解非线性互补问题的新算法,即filter内点算法.在主算法中使用Armijio型线搜索求取步长,在修复算法中使用信赖域方法进行适当控制以保证算法的收敛性.文章还讨论了算法的全局收敛性.最后用数值实验表明了该方法是有效的.     

A dynamic programming algorithm for the tree mapping problem

In the graph mapping problem two graphs and a cost function are given as input and the goal is to find a minimum cost mapping of the vertex set of one graph into the vertex set of the other graph. In this paper we introduce a dynamic programming algorithm for the tree mapping problem (i.e., the variant of the problem in which the input graphs are trees), which is still NP-hard, and evaluate its performance with computational experiments.     

Optimal input system identification for nonlinear dynamic systems

The estimation accuracy for nonlinear dynamic system identification is known to be maximized by the use of optimal inputs. Few examples of the design of optimal inputs for nonlinear dynamic systems are given in the literature, however. The performance criterion is selected such that the sensitivity of the measured state variables to the unknown parameters is maximized. The application of Pontryagin's maximum principle yields a nonlinear two-point boundary-value problem. In this paper, the boundary-value problem for a simple nonlinear example is solved using two different methods, the method of quasilinearization and the Newton-Raphson method. The estimation accuracy is discussed in terms of the Cramer-Rao lower bound.     

On the general nonlinear self-adjoint spectral problem for differential-algebraic systems

We consider a general self-adjoint spectral problem, nonlinear with respect to the spectral parameter, for linear differential-algebraic systems of equations. Under some assumptions, we present a method for reducing such a problem to a general self-adjoint nonlinear spectral problem for a system of differential equations. In turn, this permits one to pass to a problem for a Hamiltonian system of ordinary differential equations. In particular, in this way, one can obtain a method for computing the number of eigenvalues of the original problem lying in a given range of the spectral parameter.     

An algorithm portfolio for the dynamic maximal covering location problem

The location of facilities (antennas, ambulances, police patrols, etc) has been widely studied in the literature. The maximal covering location problem aims at locating the facilities in such positions that maximizes certain notion of coverage. In the dynamic or multi-period version of the problem, it is assumed that the nodes’ demand changes with the time and as a consequence, facilities can be opened or closed among the periods. In this contribution we propose to solve dynamic maximal covering location problem using an algorithm portfolio that includes adaptation, cooperation and learning. The portfolio is composed of an evolutionary strategy and three different simulated annealing methods (that were recently used to solve the problem). Experiments were conducted on 45 test instances (considering up to 2500 nodes and 200 potential facility locations). The results clearly show that the performance of the portfolio is significantly better than its constituent algorithms.     

Numerical approximations for nonlinear stochastic systems with delays

We extend the numerical methods of [Kushner, H.J. and Dupuis, P., 1992 Kushner, H.J. and Dupuis, P. 2001. Numerical Methods for Stochastic Control Problems in Continuous Time, 2nd ed., Berlin and New York: Springer-Verlag. [Crossref] , [Google Scholar], Numerical Methods for Stochastic Control Problems in Continuous Time, 2nd ed., 2001 (Berlin and New York: Springer Verlag], known as the Markov chain approximation methods, to controlled general nonlinear delayed reflected diffusion models. Both the path and the control can be delayed. For the no-delay case, the method covers virtually all models of current interest. The method is robust, the approximations have physical interpretations as control problems closely related to the original one, and there are many effective methods for getting the approximations, and for solving the Bellman equation for low-dimensional problems. These advantages carry over to the delay problem. It is shown how to adapt the methods for getting the approximations, and the convergence proofs are outlined for the discounted cost function. Extensions to all of the cost functions of current interest as well as to models with Poisson jump terms are possible. The paper is particularly concerned with representations of the state and algorithms that minimize the memory requirements.     

A derivative-free algorithm for systems of nonlinear inequalities

Recently a new derivative-free algorithm has been proposed for the solution of linearly constrained finite minimax problems. This derivative-free algorithm is based on a smoothing technique that allows one to take into account the non-smoothness of the max function. In this paper, we investigate, both from a theoretical and computational point of view, the behavior of the minmax algorithm when used to solve systems of nonlinear inequalities when derivatives are unavailable. In particular, we show an interesting property of the algorithm, namely, under some mild conditions regarding the regularity of the functions defining the system, it is possible to prove that the algorithm locates a solution of the problem after a finite number of iterations. Furthermore, under a weaker regularity condition, it is possible to show that an accumulation point of the sequence generated by the algorithm exists which is a solution of the system. Moreover, we carried out numerical experimentation and comparison of the method against a standard pattern search minimization method. The obtained results confirm that the good theoretical properties of the method correspond to interesting numerical performance. Moreover, the algorithm compares favorably with a standard derivative-free method, and this seems to indicate that extending the smoothing technique to pattern search algorithms can be beneficial.     

The controllability problem for certain nonlinear intergro-differential volterra systems

The controllability property is proved for so-called "triangular" control systems of integro-differential Volterra equations. This result generalizes the previous results obtained for the case of control systems of ordinary differential equations. Two special cases, when the tools developed for the differential systems work without using the general result of this paper are considered.