Search

A new search method is presented for unconstrained optimization. The method requires the evaluation of first and second derivatives and defines a curve along which a undimensional step takes place. For large step-size, the method performs as Newton's method, but it does not fail where the latter fails. For small step-size, the method behaves as the gradient method.

Interpolation methods fit a model to a given objective function by evaluating the objective function at, say, M points of a grid. If the model has, say, N independent coefficients which have to be determined, they are found by solving a set of M linear simultaneous equations in N unknowns.In this paper the effect on these methods is tested of enlarging the size of the grid (M) to include more than N points. Numerical results show that the optimal data grid size tends to occur when M = N.

Recently, an algorithm for function minimization was presented, based upon an homogeneous, rather than upon a quadratic, model. Numerical experiments with this algorithm indicated that it rapidly minimizes the standard test functions available in the literature. Although it was proved that the algorithm produces function values which continually descend, no proof of convergence was supplied. In this paper, the homogeneous algorithm is modified primarily by replacing the cubic interpolation routine by Armijo's step size rule. Although not quite as fast as the original version on the standard test functions, this modified form has the advantage that a proof of convergence follows from a general theorem of Polak.

It is known that the optimal controller for a linear dynamic system disturbed by additive, independently distributed in time, not necessarily Gaussian, noise is a linear function of the state variables if the performance criterion is the expected value of a quadratic form. This result is known to hold also when the noise is Gaussian and is multiplied by a linear function of the state and/or control variables. In this paper it is proved that the optimal controller for a discrete-time linear dynamic system with quadratic performance criterion is a linear function of the state variables when the additive random vector is a nonlinear function of the state and/or control variables and not necessarily Gaussian noise which is independently distributed in time, provided only that the mean value of the random vector is zero (there is no loss of generality in assuming this) and the covariance matrix of the random vector is a quadratic function of the state and/or control variables. The above-mentioned known results emerge as special cases and certain nonlinear other special cases are exhibited.

Fuzzy set theory has developed significantly in a mathematical direction during the past several years but few applications have emerged. This paper investigates the role of fuzzy set theory in certain optimal control formulations. In particular, it is shown that the well-known quadratic performance criterion in deterministic optimal control is equivalent to the exponential membership function of a certain fuzzy decision (set). In a stochastic setting, similar equivalences establish new definitions for “confluence of goals” and “maximizing decision” in fuzzy set theory. These and other definitions could lead to the development of a more applicable theory of fuzzy sets.

The non-negativity of quadratic functionals not subject to inequality constraints has been much studied in the past because of its role in deducing sufficient conditions for optimality in optimal control problems. In this paper we extend known results by deriving sufficient conditions for the non-negativity of quadratic and non-quadratic functionals subject to inequality constraints on the state and control variables. In the quadratic case a novel Riccati differential equation arises while in the non-quadratic case a set of constrained quadratic functionals is tested for non-negativity. An alternative approach yields a more tractable solution for the constrained non-quadratic case, which is illustrated by means of a non-trivial example.

A symmetric matrix C is called copositive if the quadratic form x′Cx is nonnegative for all nonnegative values of the variables ( x 1 , x 2 ,…, x n )= x ′. A known sufficient condition for a quadratic form x′Qx to be positive unless x =0, subject to the linear inequality constraints Ax ⩾0, is that there should exist a copositive matrix C such that Q − A′CA is positive definite. The main result of this paper establishes the necessity of this condition. For x'Qx to be merely nonnegative subject to Ax ⩾ 0, the situation is less straightforward. The necessity of the existence of a copositive matrix C such that Q − A′CA is positive semidefinite is proved only under various additional hypotheses regarding the size or rank of A , and counterexamples are given to show that, in general, no such matrix may exist, even when Slater's constraint qualification holds. Our approach to these existence questions also furnishes certain tests for positivity or mere nonnegativity of x′Qx subject to Ax ⩾0, in which specific symmetric matrices, constructed by rational operations from A and Q and depending upon a single real parameter v , must be tested for positive definiteness or strict copositivity for large values of v . This technique is illustrated by several examples.

A method of designing a feedback controller for a linear dynamic system disturbed by additive white noise treats the noise as a maximizing (vindictive) opponent and minimaximizes a quadratic performance criterion which is the difference between the original criterion, for the system performance, and a quadratic function of the maximizing player (noise). This procedure, though well known, is viewed with some suspicion as it appears to be a very pessimistic design method in that it assumes that the noise will “conspire” to oppose the controller in the most perverse way. We show, however, in this paper that the controller obtained in this manner is the same as that obtained by minimizing the expected value of an exponential function of the given quadratic performance criterion. When looked at from this viewpoint the “worst case design” does not appear to be too pessimistic since the exponential criterion is rather appealing. Of theoretical interest is the fact that existence of a solution to the zero sum differential game (which arises in the worst case formulation) implies and is implied by existence of the expected value of the exponential performance criterion.

In a previous study of human locomotion, an important aspect of our mathematical modelling was the decomposition of the complex body dynamics into two parts: one describes the lower extremity motion; the other pertains to the motion of the upper trunk. The generation of gait patterns via optimal programming was studied in that paper. In the present study the torso motion is considered. This involves as investigation of the unstable equilibrium of the torso about its upright position. A multidimensional “inverted pendulum” model is derived to study this behavior. To stabilize the motion, a linear feedback law coupled with an on-off perturbation is proposed. A Liapunov function is then constructed to show that such a control mechanism provides effective stabilization of the torso for all initial configurations of motion. Significance of the control law is discussed and a possible EMG-photographic experiment is suggested on the basis of this theoretical study.

Research to date toward an understanding of human biped locomotion has been primarily experimental in nature, largely due to the complexity of the process. In view of the new, exciting possibilities of programmed electrostimulation of paralyzed extremities to restore locomotion, a critical study at the theoretical level is greatly warranted. Optimal programming and modern control theory offer a new approach to the study. First, it is proposed that normal walking obeys a certain “principle of optimality.” Next, at the dynamic level, modern control theory is used to derive the optimal moment profiles that actuate the locomotor elements to synthesize the observed patterns of the normal gait. Development of the problem structure relies closely on the functional characteristic of the biped gait, particularly the ideas of distinct phasic activities and the associated temporal patterns of a walking cycle. The result is a multiarc programming problem with three stages. Each stage involves dynamic constraints that reflect the particular nature of the phasic activity. Activity in the stance phase is described by equality constraints on the “states,” whereas the swing phase is characterized by inequality state constraints. A novelty of the approach is that the theory could be used to study walking behavior under different environmental conditions, such as walking upstairs or over a hole. Joining of the arcs is arranged in such a way as to maintain continuity of certain trajectories as well as repeatability of motion. A distinct feature of the present approach that differs from other studies is the presence of a minimizing performance criterion. Based on external characteristics of muscles and certain assumptions regarding normal locomotion, a simple quadratic type of performance index is proposed. This performance criterion is meaningful in that it is shown to be proportional to the mechanical work done during normal walking. Invoking the necessary conditions of optimal control theory, a multipoint boundary value problem is obtained. A penalty function technique is then employed for iterative numerical solution on a digital computer. Using the parameters available in the literature, simulation results are obtained that agree well with the experimental studies performed by Eberhart and his associates. Furthermore, certain refined features are obtained that are not available in previous studies. Success in applying optimal programming techniques to human locomotion could yield better design procedures for prostheses and could allow eventual realization of the dream of programmed stimulation of many paralyzed persons.

A symmetric matrix C is said to be copositive if its associated quadratic form is nonnegative on the positive orthant. Recently it has been shown that a quadratic form x'Qx is positive for all x that satisfy more general linear constraints of the form Ax ⩾0, x ≠0 iff Q can be decomposed as a sum Q = A'CA +S, with C strictly copositive and S positive definite. However, if x'Qx is merely nonnegative subject to the constraints Ax ⩾0, it does not follow that Q admits such a decomposition with C copositive and S positive semidefinite. In this paper we give a characterization of those matrices A for which such a decomposition is always possible.

Research on copositive quadratic forms has produced the result that every positive semidefinite, nonnegative matrix has a nonnegative factorization (i.e., is completely positive) if and only if n ⩽ 4. Furthermore, necessary and sufficient conditions for a matrix to have a triangular, nonnegative factorization for all n are known. In this paper interesting connections are established between M -matrices, completely positive matrices, and triangular, nonnegative factorizations.

Sufficient conditions are given for the optimal feedback controller to be linear, in the problem of minimizing a quadratic performance criterion subject to a dynamic system constraint of quadratic and bilinear terms. The cases of free terminal state infinite-time, and fixed terminal state specified terminal time, are considered. In addition, a two-dimensional example is presented.