Infinite-dimensional quadratic optimization: Interior-point methods and control applications

An infinite-dimensional convex optimization problem with the linear-quadratic cost function and linear-quadratic constraints is considered. We generalize the interior-point techniques of Nesterov-Nemirovsky to this infinite-dimensional situation. The complexity estimates obtained are similar to finite-dimensional ones. We apply our results to the linear-quadratic control problem with quadratic constraints. It is shown that for this problem the Newton step is basically reduced to the standard LQ problem. This research was supported in part by the Cooperative Research Centre for Robust and Adaptive Systems while the first author visited the Australian National University and by NSF Grant DMS 94-23279.     

Fast simulation of buffer overflows in tandem networks ofGI/GI/1 queues

Simply because of their rarity, the estimation of the statistics of buffer overflows in well-dimensioned queueing networks via direct simulation is extremely costly. One technique that can be used to reduce this cost is importance sampling, and it has been shown previously that large deviations theory can be used in conjunction with importance sampling to minimize the required simulation time. In this paper, we obtain results on the fast simulation of tandem networks of queues, and derive an analytic solution to the problem of finding an optimal simulation system for a class of tandem networks ofGI/GI/1 queues.Work supported by Australian Telecommunications and Electronics Research Board (ATERB). The authors wish to acknowledge the funding of the activities of the Cooperative Research Centre for Robust and Adaptive Systems by the Australian Commonwealth Government under the Cooperative Research Centres Program.     

Feedback control in LQCP with a terminal inequality constraint

This paper considers the linear-quadratic control problem (LQCP) for systems defined by evolution operators with a terminal state inequality constraint. It is shown that, under suitable assumptions, the optimal control exists, is unique, and has a closed-loop structure. The synthesis of the feedback control requires one to solve the integral Riccati equation for the unconstrainted LQCP and a linear integral equation whose solution depends on a real parameter satisfying an additional condition.This work was completed while the author was visiting the Control Theory Centre, University of Warwick, Coventry, England.     

On asymptotic optimization of a class of nonlinear stochastic hybrid systems

We consider the problem of control for continuous time stochastic hybrid systems in finite time horizon. The systems considered are nonlinear: the state evolution is a nonlinear function of both the control and the state. The control parameters change at discrete times according to an underlying controlled Markov chain which has finite state and action spaces. The objective is to design a controller which would minimize an expected nonlinear cost of the state trajectory. We show using an averaging procedure, that the above minimization problem can be approximated by the solution of some deterministic optimal control problem. This paper generalizes our previous results obtained for systems whose state evolution is linear in the control.This work is supported by the Australian Research Council. All correspondence should be directed to the first author.     

Differential stability of solutions to constrained optimization problems

In this paper the differential stability of solutions to constrained optimization problems is investigated. The form of right-derivatives of optimal solutions to such problems, with respect to a real parameter, is derived. The right-derivative of the optimal control with respect to parameter for an optimal control problem for parabolic equation is obtained in the form of the optimal solution to an auxiliary optimal control problem. A method for determination of the second right-derivative of the optimal solutions to constrained optimization problems is proposed. Several examples are provided.This research has been supported by INRIA, in the framework of a collaboration between the project Théorie des Systèmes and the Systems Research Institute of the Polish Academy of Sciences.     

Shift products and factorizations of wavelet matrices

A class of so-called shift products of wavelet matrices is introduced. These products are based on circulations of columns of orthogonal banded block circulant matrices arising in applications of discrete orthogonal wavelet transforms (or paraunitary multirate filter banks) or, equivalently, on augmentations of wavelet matrices by zero columns (shifts). A special case is no shift; a product which is closely related to the Pollen product is then obtained. Known decompositions using factors formed by two blocks are described and additional conditions such that uniqueness of the factorization is guaranteed are given. Next it is shown that when nonzero shifts are used, an arbitrary wavelet matrix can be factorized into a sequence of shift products of square orthogonal matrices. Such a factorization, as well as those mentioned earlier, can be used for the parameterization and construction of wavelet matrices, including the costruction from the first row. Moreover, it is also suitable for efficient implementations of discrete orthogonal wavelet transforms and paraunitary filter banks.and Cooperative Research Centre for Sensor Signal and Information ProcessingThis author is an Overseas Postgraduate Research Scholar supported by the Australian Government.     

A Hybrid Robust Adaptive Sliding Mode Controller for partially modelled systems: Discrete-time Lyapunov stability analysis and application

This work presents a new discrete-time Hybrid Robust Adaptive Sliding Mode Controller, developed from the union of a Robust Model Reference Adaptive Controller, an Adaptive Sliding Mode Controller, and an Adaptive One Sample Ahead Preview Controller in an unique control structure. Robust Model Reference Adaptive Controller is an adequate direct adaptive control strategy to control partially known plants, but can present slow closed-loop response to ensure global stability. Therefore, an adaptive One Sample Ahead Preview controller is incorporated to accelerate transient regimes, once it tries to track reference signal in one sample. Furthermore, an adaptive Sliding Mode Controller is also merged in the controller structure to help controller performance in transient regime and it also improves relevantly the steady state response in a scenario of several unmodelled dynamics Stability analysis of this controller using Lyapunov criterion and its robustness proof are provided, considering the plant subjected to unmodelled dynamics, which provides controller design constraints. These proofs show the controller is globally stable, and the tracking error tends to a residual set in steady state, even in the presence of matched and unmatched dynamics. Numerical simulations of the Hybrid Robust Adaptive Sliding Mode Controller applied on an unstable nonminimum-phase plant are presented, where only part of the overall plant is take into consideration for controller design. Results corroborate the feasibility and robustness of the developed control strategy and the performance superiority when compared to an adaptive One Sample Ahead Preview controller, with a 75% tracking error reduction in a scenario of several unmodelled dynamics.     

Factorizations and construction of linear phase paraunitary filter banks and higher multiplicity wavelets

It is known that paraunitary matrices can be factorized into shift products of orthogonal matrices or linear factors. When the number of rows of such a matrix (i.e. the number of channels of a paraunitary filter bank) is even, the symmetry constraints corresponding to the linear phase property of the filter bank can be expressed as restrictions on factors — except the very first one, all must be centrosymmetric. For odd numbers of rows the situation is more complicated. It turns out that paraunitary matrices comprising an even number of square blocks do not exist and quadratic centrosymmetric factors have to be used in the 0-shift product factorization. The centrosymmetric linear and quadratic factors can be easily obtained from partitions of centrosymmetric orthogonal matrices. Their parameterizations are also described.The characterizations of paraunitary matrices obtained from these factorizations are complete; the question of the number of free parameters is discussed. Furthermore, the proposed factorizations also allow us to derive lattice structures for linear phase paraunitary filter banks and, since the basic regularity conditions can be incorporated as a constraint on the first factor, they can be used also for the construction of symmetric higher multiplicity wavelets.and Cooperative Research Centre for Sensor Signal and Information ProcessingThe author is an Overseas Postgraduate Research Scholar supported by the Australian Government.     

A framework for group decision support systems: Combining AI tools and OR techniques

Work on the implementation of Group Decision Support Systems has to exploit recent advancements of computer science. Existing frameworks for single-user Decision Support Systems, based on well-established Operations Research methods such as Multicriteria Decision Making techniques, have to be integrated with successful technical developments in electronic communication and computing. Starting from the presentation of the related Operations Research background, this paper proceeds by discussing challenges coming from the areas of Computer-Supported Cooperative Work and Information Systems on the World Wide Web platform. Based on this discussion, a framework for an ‘open’, computer-mediated Group Decision Support System is proposed. The term ‘open’ is related to a platform-independent system, which can efficiently support alternative types of goals and control protocols between its users.     

Small penalty control of the end temperature in a long rod

The problem considered is that of maintaining the end temperature of a long rod near a prescribed level over a fixed time interval. Control is achieved via the heat flux at the near end, and it is optimal in the sense that it minimizes a given performance index of quadratic form. The performance index contains a penalty parameter associated with the magnitude of the control. Particular attention is given to the determination of the optimal control when the penalty parameter is small (i.e., cheap control). This gives rise to a singularly perturbed integral equation, which is solved asymptotically by a methodology which has recently been developed for a related class of problems.The work of the first author was supported by the Applied Mathematical Sciences Subprogram, Office of Energy Research, US Department of Energy under Contract W-7405-ENG-82. The work of the second author was supported by NSF under Grant DMS-87-00962.     

Nuclear power plant optimal control by successive linear programming

An attempt to find optimal controls for an extremely load-following nuclear power plant during large load pick-ups is reported in this paper. The choice of the numerical method to solve this highly constrained dynamic optimization problem is discussed. The results reported demonstrate the efficacy of the successive linear programming method in tackling this problem without recourse to model linearization.The first author wishes to express his gratitude for many helpful discussions with Prof. S. L. Mehndiratta, Indian Institute of Technology, Bombay and Mr. B. F. Chamany, Bhabha Atomic Research Centre, Bombay, India.     

Epi-convergent discretization of the generalized Bolza problem in dynamic optimization

The paper is devoted to well-posed discrete approximations of the so-called generalized Bolza problem of minimizing variational functionals defined via extended-real-valued functions. This problem covers more conventional Bolza-type problems in the calculus of variations and optimal control of differential inclusions as well of parameterized differential equations. Our main goal is find efficient conditions ensuring an appropriate epi-convergence of discrete approximations, which plays a significant role in both the qualitative theory and numerical algorithms of optimization and optimal control. The paper seems to be the first attempt to study epi-convergent discretizations of the generalized Bolza problem; it establishes several rather general results in this direction. Research of B. S. Mordukhovich was partially supported by the USA National Science Foundation under grants DMS-0304989 and DMS-0603846 and by the Australian Research Council under grant DP-0451168. Research of T. Pennanen was supported by the Finnish Academy of Sciences under contract No. 3385.     

Higher-order quadratures for circulant preconditioned Wiener-Hopf equations

In this paper, we consider solving matrix systems arising from the discretization of Wiener-Hopf equations by preconditioned conjugate gradient (PCG) methods. Circulant integral operators as preconditioners have been proposed and studied. However, the discretization of these preconditioned equations by employing higher-order quadratures leads to matrix systems that cannot be solved efficiently by using fast Fourier transforms (FFTs). The aim of this paper is to propose new preconditioners for Wiener-Hopf equations. The discretization of these preconditioned operator equations by higher-order quadratures leads to matrix systems that involve only Toeplitz, circulant and diagonal matrix-vector multiplications and hence can be computed efficiently by FFTs in each iteration. We show that with the proper choice of kernel functions of Wiener-Hopf equations, the resulting preconditioned operators will have clustered spectra and therefore the PCG method converges very fast. Numerical examples are given to illustrate the fast convergence of the method and the improvement of the accuracy of the computed solutions with using higher-order quadratures.Research supported by the Cooperative Research Centre for Advanced Computational Systems.Research supported in part by Lee Ka Shing scholarship.     

Solving some optimal control problems using the barrier penalty function method

In this paper we present a new approach to solve a two-level optimization problem arising from an approximation by means of the finite element method of optimal control problems governed by unilateral boundary-value problems. The problem considered is to find a minimum of a functional with respect to the control variablesu. The minimized functional depends on control variables and state variablesx. The latter are the optimal solution of an auxiliary quadratic programming problem, whose parameters depend onu.Our main idea is to replace this QP problem by its dual and then apply the barrier penalty method to this dual QP problem or to the primal one if it is in an appropriate form. As a result we obtain a problem approximating the original one. Its good property is the differentiable dependence of state variables with respect to the control variables. Furthermore, we propose a method for finding an approximate solution of a penalized lower-level problem if the optimal solution of the original QP problem is known. We apply the result obtained to some optimal shape design problems governed by the Dirichlet-Signorini boundary-value problem.This research was supported by the Academy of Finland and the Systems Research Institute of the Polish Academy of Sciences.     

Path planning for robots under stochastic uncertainty *

In order to reduce large online measurement and correction expenses, the a priori informations on the random variations of the model parameters of a robot and its working environment are taken into account already at the planning stage. Thus, instead of solving a deterministic path planning problem with a fixed nominal parameter vector, here, the optimal velocity profile along a given trajectory in work space is determined by using a stochastic optimization approach. Especially, the standard polygon of constrained motion-depending on the nominal parameter vector-is replaced by a more general set of admissible motion determined by chance constraints or more general risk constraints. Robust values (with respect to stochastic parameter variations) of the maximum, minimum velocity, acceleration, deceleration, resp., can be obtained then by solving a univariate stochastic optimization problem Considering the fields of extremal trajectories, the minimum-time path planning problem under stochastic uncertainty can be solved now by standard optimal deterministic path planning methods     

User-model interaction in decision support systems for risk management

This paper describes and evaluates three different approaches to building decision support systems: the Operations Research/Management Science approach, the Decision Analysis/Multiattribute Utility approach, and the Artificial Intelligence/Expert Systems approach. It evaluates the usefulness of the three approaches for risk management. In particular, it defines evaluation objectives of risk analysts, risk managers, and laypeople and provides a subjective assessment how the three approaches stack up against their objectives. The paper concludes that for most risk management applications a combination of the three approaches would be most desirable.This paper was written under contract No. 2709-85-05 ED ISP D of the European Atomic Energy Community, Commission of the European Communities, Joint Research Centre, Ispra Establishment, Ispra, Italy to the Gemeinschaft für Entscheidungs- und Risikoanalyse, Berlin, West Germany. It was prepared for presentation at the Conference on Operations Research and Multiattribute Decision Analysis held in Passau, April 20–26, 1986. The views and opinions expressed in this paper are solely those of the author.     

Directional derivatives of the solution of a parametric nonlinear program

Consider a parametric nonlinear optimization problem subject to equality and inequality constraints. Conditions under which a locally optimal solution exists and depends in a continuous way on the parameter are well known. We show, under the additional assumption of constant rank of the active constraint gradients, that the optimal solution is actually piecewise smooth, hence B-differentiable. We show, for the first time to our knowledge, a practical application of quadratic programming to calculate the directional derivative in the case when the optimal multipliers are not unique.This author's research was supported by the Australian Research Council.     

Recursive mesh refinement on hypercubes

Adaptive methods for PDEs can be viewed as a graph problem. An efficient parallel implementation of adaptive PDE methods then requires distributing the nodes of the associated graph uniformly across the processors so that the resulting cost of communication between processors is low.We solve this problem in two phases: labeling of graph nodes and subsequent mapping of these labels onto processors. We describe a new form of Gray-code which we call aninterleaved Gray-code that allows easy labeling of graph nodes when the maximal level of refinement is unknown, allows easy determination of nearby nodes in the graph, is completely deterministic, and often (in a well-defined sense) distributes the graph uniformly across a hypercube. The theoretical results are supported by computational experiments on the Connection Machine.The work presented in this paper was supported by the Office of Naval Research under contract N00014-85-K-0461, by the Army Research Office under contract DAAL03-86-K-0158, by the Office of Naval Research under contract number N00014-86-K-0310 and the National Science Foundation under contract number DCR 8521451. Part of this work was performed while the second author was in residence at the Computer Science and Systems Division of Harwell Laboratory, United Kingdom.     

Necessary conditions of the minimum in an impulse optimal control problem

The paper is devoted to studying the impulse optimal control problem with inequality-type state constraints and geometric control constraints defined by a measurable multivalued mapping. The author obtains necessary optimality conditions in the form of the Pontryagin maximum principle and nondegeneracy conditions for the latter. __________ Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 24, Dynamical Systems and Optimization, 2005.     

Periodic maintenance and repair rate control in stochastic manufacturing systems

In this paper, we consider a periodic preventive maintenance, repair, and production model of a flexible manufacturing system with failure-prone machines, where the control variables are the repair rate and production rate. We use periodic preventive maintenance to reduce the machine failure rates and improve the productivity of the system. One of the distinct features of the model is that the repair rate is adjustable. Our objective is to choose a control process that minimizes the total cost of inventory/shortage, production, repair, and maintenance. Under suitable conditions, we show that the value function is locally Lipschitz and satisfies an Hamilton-Jacobi-Bellman equation. A sufficient condition for optimal control is obtained. Since analytic solutions are rarely available, we design an algorithm to approximate the optimal control problem. To demonstrate the performance of the numerical method, an example is presented.Research of this author was supported by the Natural Sciences and Engineering Research Council of Canada, Grant OGP0036444.Research of this author was supported in part by the University of Georgia.Research of this author was supported in part by the National Science Foundation, Grant DMS-92-24372.