The projective method for solving linear matrix inequalities

Numerous problems in control and systems theory can be formulated in terms of linear matrix inequalities (LMI). Since solving an LMI amounts to a convex optimization problem, such formulations are known to be numerically tractable. However, the interest in LMI-based design techniques has really surged with the introduction of efficient interior-point methods for solving LMIs with a polynomial-time complexity. This paper describes one particular method called the Projective Method. Simple geometrical arguments are used to clarify the strategy and convergence mechanism of the Projective algorithm. A complexity analysis is provided, and applications to two generic LMI problems (feasibility and linear objective minimization) are discussed.     

Measure change techniques in optimal control

Fully and partially observed stochastic control of systems with nonlinear dynamics and terminal and running costs are considered. Measure changes are introduced which allow both state and observation dynamics to be thought of as linear. In the case when the terms of the cost have a special form the measure change transformation “cancels out” the nonlinearities and changes the original nonlinear problem into a classical LQG one and standard results can be applied. We also consider unnormalized conditional densities of the whole path as state variables and obtain dynamic programming and verification results. R. J. Elliott wishes to acknowledge support of the Natural Sciences and Engineering Research Council of Canada, Grant A7964.     

Control Policy for a Manufacturing System with Random Yield and Rework

We develop a production policy that controls work-in-process (WIP) levels and satisfies demand in a multistage manufacturing system with significant uncertainty in yield, rework, and demand. The problem addressed in this paper is more general than those in the literature in three aspects: (i) multiple products are processed at multiple workstations, and the capacity of each workstation is limited and shared by multiple operations; (ii) the behavior of a production policy is investigated over an infinite-time horizon, and thus the system stability can be evaluated; (iii) the representation of yield and rework uncertainty is generalized. Generalizing both the system structure and the nature of uncertainty requires a new mathematical development in the theory of infinite-horizon stochastic dynamic programming. The theoretical contributions of this paper are the existence proofs of the optimal stationary control for a stochastic dynamic programming problem and the finite covariances of WIP and production levels under the general expression of uncertainty. We develop a simple and explicit sufficient condition that guarantees the existence of both the optimal stationary control and the system stability. We describe how a production policy can be constructed for the manufacturing system based on the propositions derived.     

用于非均匀介质重建的选代算法收敛性的研究

研究轴对称二维非均匀介质重建迭代算法的收敛性问题。首先借助于玻恩近似将非线性积分方程线性化，然后，利用玻恩迭代法和变形玻恩迭代法，由散射场数据对轴对称二维非均匀介质进行重建。通过几个例子研究了影响迭代算法收敛性的几种因素，如送代算法本身、积分离散化后的网格划分、正则化方法中的正则化参数选取等。     

Efficient Sequential Quadratic Programming Implementations for Equality-Constrained Discrete-Time Optimal Control

Efficient sequential quadratic programming (SQP) implementations are presented for equality-constrained, discrete-time, optimal control problems. The algorithm developed calculates the search direction for the equality-based variant of SQP and is applicable to problems with either fixed or free final time. Problem solutions are obtained by solving iteratively a series of constrained quadratic programs. The number of mathematical operations required for each iteration is proportional to the number of discrete times N. This is contrasted by conventional methods in which this number is proportional to N ³. The algorithm results in quadratic convergence of the iterates under the same conditions as those for SQP and simplifies to an existing dynamic programming approach when there are no constraints and the final time is fixed. A simple test problem and two application problems are presented. The application examples include a satellite dynamics problem and a set of brachistochrone problems involving viscous friction.     

Volumetric path following algorithms for linear programming

We consider the construction of small step path following algorithms using volumetric, and mixed volumetric-logarithmic, barriers. We establish quadratic convergence of a volumetric centering measure using pure Newton steps, enabling us to use relatively standard proof techniques for several subsequently needed results. Using a mixed volumetric-logarithmic barrier we obtain an O(n ^1/4 m ^1/4 L) iteration algorithm for linear programs withn variables andm inequality constraints, providing an alternative derivation for results first obtained by Vaidya and Atkinson. In addition, we show that the same iteration complexity can be attained while holding the work per iteration to O(n ² m), as opposed to O(nm ²), operations, by avoiding use of the true Hessian of the volumetric barrier. Our analysis also provides a simplified proof of self-concordancy of the volumetric and mixed volumetric-logarithmic barriers, originally due to Nesterov and Nemirovskii. This paper was first presented at the 1994 Faculty Research Seminar “Optimization in Theory and Practice”, at the University of Iowa Center for Advanced Studies.     

A Modified SQP Method and Its Global Convergence

The sequential quadratic programming method developed by Wilson, Han andPowell may fail if the quadratic programming subproblems become infeasibleor if the associated sequence of search directions is unbounded. In [1], Hanand Burke give a modification to this method wherein the QP subproblem isaltered in a way which guarantees that the associated constraint region isnonempty and for which a robust convergence theory is established. In thispaper, we give a modification to the QP subproblem and provide a modifiedSQP method. Under some conditions, we prove that the algorithm eitherterminates at a Kuhn–Tucker point within finite steps or generates aninfinite sequence whose every cluster is a Kuhn–Tucker point.Finally, we give some numerical examples.     

Fractional programming and characterization of some vertices of the feasible region

This paper considers a problem of nonlinear programming in which the objective function is the ratio of two linear functions and the constraints define a bounded and connected feasible region. Using a coordinate transformation, this problem is transformed into a simpler one, whose geometric interpretation is of particular significance. The transformation leads to a characterization of some special vertices of the feasible region from both the theoretical and operational points of view.     

Balance constraints reduction of large-scale linear programming problems

This paper describes a method and the corresponding algorithms for simplification of large-scale linear programming models. It consists of the elimination of the balance constraints (i.e. constraints with zero RHS term). The idea is to apply some linear transformations to the original problem in order to nullify the balance constraints. These transformations are able to simultaneously eliminate more balance rows. The core of this contribution is the introduction of the reduction matrix and the associated theorems on the equivalent linear programs (original and reduced). The numerical experiments with this method of simplification proved this approach to be beneficial for a large class of LP problems.This research work was done while the first author was at Duisburg University, Mess-, Steuer und Regelungstechnik, Germany, under the greatly appreciated financial assistance given by the Alexander-von-Humboldt Foundation.     

一类求解线性约束非线性规划问题的可行方向法

Wilson,Han和Powell提出的序列二次规划方法(简称SQP方法)是求解非线性规划问题的一个著名方法,这种方法每次迭代的搜索方向是通过求解一个二次规划子问题得到的,本文受[1]启发,得到二次规划子问题的一个近似解,进而给出了一类求解线性约束非线性规划问题的可行方向法,在约束集合满足正则性的条件下,证明了该算法对五种常用线性搜索方法具有全局收敛性。