Supervised dimensionality reduction via sequential semidefinite programming

Many dimensionality reduction problems end up with a trace quotient formulation. Since it is difficult to directly solve the trace quotient problem, traditionally the trace quotient cost function is replaced by an approximation such that the generalized eigenvalue decomposition can be applied. In contrast, we directly optimize the trace quotient in this work. It is reformulated as a quasi-linear semidefinite optimization problem, which can be solved globally and efficiently using standard off-the-shelf semidefinite programming solvers. Also this optimization strategy allows one to enforce additional constraints (for example, sparseness constraints) on the projection matrix. We apply this optimization framework to a novel dimensionality reduction algorithm. The performance of the proposed algorithm is demonstrated in experiments by several UCI machine learning benchmark examples, USPS handwritten digits as well as ORL and Yale face data.     

Variational density matrix optimization using semidefinite programming

We discuss how semidefinite programming can be used to determine the second-order density matrix directly through a variational optimization. We show how the problem of characterizing a physical or N-representable density matrix leads to matrix-positivity constraints on the density matrix. We then formulate this in a standard semidefinite programming form, after which two interior point methods are discussed to solve the SDP. As an example we show the results of an application of the method on the isoelectronic series of Beryllium.     

A primal–dual semidefinite programming algorithm tailored to the variational determination of the two-body density matrix

The quantum many-body problem can be rephrased as a variational determination of the two-body reduced density matrix, subject to a set of N-representability constraints. The mathematical problem has the form of a semidefinite program. We adapt a standard primal–dual interior point algorithm in order to exploit the specific structure of the physical problem. In particular the matrix-vector product can be calculated very efficiently. We have applied the proposed algorithm to a pairing-type Hamiltonian and studied the computational aspects of the method. The standard N-representability conditions perform very well for this problem.     

Global optimization in protein docking using clustering,underestimation and semidefinite programming

The underestimation of data points by a convex quadratic function is a useful tool for approximating the location of the global minima of potential energy functions that arise in protein-ligand docking problems. Determining the parameters that define the underestimator can be formulated as a convex quadratically constrained quadratic program and solved efficiently using algorithms for semidefinite programming (SDP). In this paper, we formulate and solve the underestimation problem using SDP and present numerical results for active site prediction in protein docking.     

A new SQP algorithm based on semidefinite programming

The paper gives a new filter-SQP algorithm of the semidefinite programming through combining the sequence nonlinear algorithm of solving the semidefinite programming, low rank conversion, and filter method, which, under certain conditions, proves that the algorithm is global convergence.     

Barrier certificates for nonlinear model validation

Methods for model validation of continuous-time nonlinear systems with uncertain parameters are presented in this paper. The methods employ functions of state-parameter-time, termed barrier certificates, whose existence proves that a model and a feasible parameter set are inconsistent with some time-domain experimental data. A very large class of models can be treated within this framework; this includes differential-algebraic models, models with memoryless/dynamic uncertainties, and hybrid models. Construction of barrier certificates can be performed by convex optimization, utilizing recent results on the sum of squares decomposition of multivariate polynomials.     

Estimation of the disturbance structure from data using semidefinite programming and optimal weighting

Designing a state estimator for a linear state-space model requires knowledge of the characteristics of the disturbances entering the states and the measurements. In [Odelson, B. J., Rajamani, M. R., & Rawlings, J. B. (2006). A new autocovariance least squares method for estimating noise covariances. Automatica, 42(2), 303-308], the correlations between the innovations data were used to form a least-squares problem to determine the covariances for the disturbances. In this paper we present new and simpler necessary and sufficient conditions for the uniqueness of the covariance estimates. We also formulate the optimal weighting to be used in the least-squares objective in the covariance estimation problem to ensure minimum variance in the estimates. A modification to the above technique is then presented to estimate the number of independent stochastic disturbances affecting the states. This minimum number of disturbances is usually unknown and must be determined from data. A semidefinite optimization problem is solved to estimate the number of independent disturbances entering the system and their covariances.     

Low-rank exploitation in semidefinite programming for control

Many control-related problems can be cast as semidefinite programs. Even though there exist polynomial time algorithms and excellent publicly available solvers, the time it takes to solve these problems can be excessive. What many of these problems have in common, in particular in control, is that some of the variables enter as matrix-valued variables. This leads to a low-rank structure in the basis matrices which can be exploited when forming the Newton equations. In this article, we describe how this can be done, and show how our code, called STRUL, can be used in conjunction with the semidefinite programming solver SDPT3. The idea behind the structure exploitation is classical and is implemented in LMI Lab, but we show that when using a modern semidefinite programming framework such as SDPT3, the computational time can be significantly reduced. Finally, we describe how the modelling language YALMIP has been changed in such a way that our code, which can be freely downloaded, can be interfaced using standard YALMIP commands. This greatly simplifies modelling and usage.     

Model reduction of uncertain systems retaining the uncertainty structure

Model reduction of high order linear-in-parameters discrete-time systems is considered. The main novelty of the paper is that the coefficients of the original system model are assumed to be known only within given intervals, and the coefficients of the derived reduced order model are also obtained in intervals, such that the complex value sets of the uncertain original and reduced models will be optimally close to each other on the unit circle. The issue of inclusion of one value set in another is also addressed in the paper. The meaning of model reduction is defined for linear-in-parameters systems. The algorithm for obtaining the value sets of such systems is derived in the paper. Then, applying a novel approach, the infinity norm of “distance” between two polygons representing the original and the reduced uncertain systems is minimized. A noteworthy point is that by a special definition of this distance the problem is formulated as a linear semi-infinite programming problem with linear constraints, thus reducing significantly the computational complexity. Numerical example is provided.     

基于双指标带权线性规划的公交车调度模型研究

公交车辆调度系统的优化可以提高公交车辆的运营效率,缓解城市交通压力,改善交通环境.针对公交车辆调度的现状,首先引入了公交车载客率和乘客不满率两个指标,并为这两个指标建立了带权优化模型;然后求得每个时间段最佳公交车发车数量,获得最优解;最后通过带入最优解,求得封闭线路（有来回）的最少备车数.通过代入数据验证,所得解在允许误差范围内符合实际结果,因此模型准确可靠,且基于本模型算法实现的程序能够应用于公交车调度系统.     

The component connection model and structure preserving model order reduction

This paper uses the component connection model as a setting for model order reduction. The actual reduction occurs on the component level as opposed to the composite system level. A theorem with proof is given relating the component level reduction to the established singular perturbation method. Concepts of system structure preservation and nonstructure preservation are discussed using the framework of the component connection model. An example is presented where a single machine-infinite bus power system is reduced using the techniques presented in this paper.     

A nonlinear functional approach to LFT model validation

Model validation provides a useful means of assessing the ability of a model to account for a specific experimental observation, and has application to modeling, identification and fault detection. In this paper, we consider a new approach to the model validation problem by deploying quadratic functionals, and more generally nonlinear functionals, to specify noise and dynamical perturbation sets. Specifically, we consider a general linear fractional transformation framework for the model structure, and use constraints involving nonlinear functional inequalities to specify model non-linearities and unknown perturbations, and characteristics of noise and disturbance signals. Sufficient conditions for invalidation of such models are provided in terms of semidefinite programming problems.     

A two-step approach for model reduction in flexible multibody dynamics

In this work, a two-step approach for model reduction in flexible multibody dynamics is proposed. This technique is a combination of the Krylov-subspace method and a Gramian matrix based reduction approach that is particularly suited if a small reduced-order model of a system charged with many force-inputs has to be generated. The proposed methodology can be implemented efficiently using sparse matrix techniques and is therefore applicable to large-scale systems too. By a numerical example, it is demonstrated that the suggested two-step approach has very good approximation capabilities in the time as well as in the frequency domain and can help to reduce the computation time of a numerical simulation significantly.     

On the balanced truncation and coprime factors reduction of Markovian jump linear systems

The paper deals with the balanced truncation and coprime factors reduction of Markovian jump linear (MJL) systems, which can have mode-varying state, input, and output dimensions. We develop machinery for balancing mean square stable MJL system realizations using generalized Gramians and strict Lyapunov inequalities, and provide an improved a priori upper bound on the error induced in the balanced truncation process. We also generalize the coprime factors reduction method and, in doing so, extend the applicability of the balanced truncation technique to the class of mean square stabilizable and detectable MJL systems. We provide tools to establish mean square stabilizability and detectability of the considered MJL systems. In addition, a notion of right-coprime factorization of MJL systems and methods to construct such factorizations are given. The error measure in the coprime factors reduction approach, while still norm-based, does not directly capture the mismatch between the nominal system and the reduced-order model, as is the case in the balanced truncation approach where mean square stable models are considered. Instead, the error measure is given in terms of the distance between the coprime factors realizations, and thus has an interpretation in terms of robust feedback stability. The paper concludes with an illustrative example which demonstrates how to apply the coprime factors model reduction approach.     

Comparison of model reduction techniques for large mechanical systems

Model reduction is a necessary procedure for simulating large elastic systems, which are mostly modeled by the Finite Element Method (FEM). In order to reduce the system’s large dimension, various techniques have been developed during the last decades, many of which share some common characteristics (Guyan, Dynamic, CMS, IRS, SEREP). A fact remains that many reduction approaches do not succeed in reducing the system’s dimension without damaging the dynamical properties of the model. The mathematical field of control theory offers alternative reduction methods, which can be applied to second order Ordinary Differential Equations (ODEs), derived by the FE-discretization of large elastic Multi Body Systems (MBS), e.g., Krylov subspace method or balanced truncation. In this paper, some of these methods are applied to the elastic piston rod. The validity of the reduced models is checked by applying Modal Correlation Criteria (MCC), since only the eigenfrequency comparison is not sufficient. Diagonal Perturbation is proposed as an efficient method for iteratively solving ill-conditioned large sparse linear systems (A x=b, A: ill-conditioned) when direct methods fail due to memory capacity problems. This is the case of FE-discretized systems, when tolerance failure occurs during the discretization procedure.     

Structured coprime factor model reduction based on LMIs

In this paper we discuss dynamic model reduction methods which preserve a certain structure in the underlying system. Specifically, we consider the situation where the reduction must be consistent with a partition of the system states. This is motivated, for instance, in situations where state variables are associated with the topology of a networked system, and the reduction should preserve this. We build on the observation that imposing block structure to generalized controllability and observability gramians automatically yields such state-partitioned model reduction. The difficulty lies in ensuring feasibility of the resulting Lyapunov inequalities, which is in general very restrictive. To overcome this, we consider coprime factor model reduction. We derive an LMI characterization of expansive and contractive coprime factorizations that preserve structure, and use this to build a more flexible method for structured model reduction. An example is given to illustrate the method.     

基于遗传规划的作业车间调度算法研究

遗传规划很少应用于解决调度问题,对此,研究一种进化算法--遗传规划算法在作业车间调度中的应用,并对其做了改进.结合Read线性编码和基于工序的编码设计了新的编码策略,使编码后的个体更容易进行遗传操作,大大提高了运算效率;同时对交叉算子进行了改进,以防子代中非法解的产生.通过对作业车间调度问题标准测试集的求解.所得结果验证了该算法求解作业车间调度问题的有效性.