分片线性规划及应用

提出通过分片线性逼近和分片线性规划,将非线性优化问题转化为一系列的线性规划进行求解的方法。讨论了分片线性规划的性质,证明了分片线性规划问题可以通过有限次线性规划得到求解,同时,给出了分片线性规划问题局部最优解的充要条件,并基于此构造了求解分片线性规划问题的下降算法。该算法与自适应链接超平面模型相结合,成功地对离心式冷水机组的工作点进行了优化。通过优化,机组的能耗比之当前工作点有了明显的下降,表明通过分片线性规划求解非线性优化问题的有效性。     

基于滑动平均与分段线性回归的时间序列相似性

针对时间序列相似性度量中欧氏距离对异常数据敏感以及DTW距离算法效率低的问题,提出基于滑动平均与分段线性回归的时间序列相似性方法。首先,使用初始可变滑动平均算法以及分段线性回归对原始时间序列进行数据变换,并将分段线性回归的参数(截距与距离)集作为时间序列的特征,以实现时间序列的特征提取和数据降维;然后,利用动态时间弯曲距离进行距离计算。该方法在时间序列相似性上与DTW算法的性能相近,但是在算法效率上几乎提高了96%。实验结果验证了该方法的有效性与准确性。     

Piecewise linear solution paths with application to direct weight optimization

Recently, pathfollowing algorithms for parametric optimization problems with piecewise linear solution paths have been developed within the field of regularized regression. This paper presents a generalization of these algorithms to a wider class of problems. It is shown that the approach can be applied to the nonparametric system identification method, Direct Weight Optimization (DWO), and be used to enhance the computational efficiency of this method. The most important design parameter in the DWO method is a parameter (λ) controlling the bias-variance trade-off, and the use of parametric optimization with piecewise linear solution paths means that the DWO estimates can be efficiently computed for all values of λ simultaneously. This allows for designing computationally attractive adaptive bandwidth selection algorithms. One such algorithm for DWO is proposed and demonstrated in two examples.     

Piecewise regression for fuzzy input–output data with automatic change-point detection by quadratic programming

To handle the large variation issues in fuzzy input–output data, the proposed quadratic programming (QP) method uses a piecewise approach to simultaneously generate the possibility and necessity models, as well as the change-points. According to Tanaka and Lee [H. Tanaka, H. Lee, Interval regression analysis by quadratic programming approach, IEEE Transactions on Fuzzy Systems 6 (1998) 473–481], the QP approach gives more diversely spread coefficients than linear programming (LP) does. However, their approach only deals with crisp input and fuzzy output data. Moreover, their method is weak in handling fluctuating data. So far, no method has been developed to cope with the large variation problems in fuzzy input–output data. Hence, we propose a piecewise regression for fuzzy input–output data with a QP approach. There are three advantages in our method. First, the QP technique gives a more diversely spread coefficient than does a linear programming technique. Second, the piecewise approach is used to detect the change-points in the estimated model automatically, and handle the large variation data such as outliers well. Third, the possibility and necessity models with better fitness in data processing are obtained at the same time. Two examples are presented to demonstrate the merits of the proposed method.     

快速的多项式平滑型支持向量顺序回归算法

支持向量顺序回归是一种重要的有监督排序学习算法.尽管其优化问题规模与样本数呈线性关系,但在学习大容量数据集时,训练速度仍过慢.为此,提出一种支持二次误差的多项式平滑型支持向量顺序回归(psSVOR)算法,其优化方法包括3个步骤:用两个分段多项式函数分别近似(1+x)+和(1-x)+,优化目标转变为二次可微的无约束问题,从而由Newton-YUAN方法直接求平行的多个决策超平面.给出了分段多项式平滑函数的3个性质及psSVOR的收敛定理.另外引入简约核提高非线性psSVOR的优化速度.多个公开数据集及LETOR OSHUMED的实验表明,与传统方法相比,psSVOR的顺序回归性能并不逊色,而训练速度显著快.     

Dynamic particle swarm optimizer with escaping prey for solving constrained non-convex and piecewise optimization problems

This paper presents a novel meta-heuristic algorithm, dynamic particle swarm optimizer with escaping prey (DPSOEP), for solving constrained non-convex and piecewise optimization problems. In DPSOEP, the particles developed from two different species are classified into three different types, consisting of preys, strong particles and weak particles, to simulate the behavior of hunting and escaping characteristics observed in nature. Compared to other variants of particle swarm optimizer (PSO), the proposed algorithm takes account of an escaping mechanism for the preys to circumvent the problem of local optimum and also develops a classification mechanism to cope with different situations in the search space so as to achieve a good balance between its global exploration and local exploitation abilities. Simulation results obtained based on thirteen benchmark functions and two practical economic dispatch problems prove the effectiveness and applicability of the DPSOEP to deal with non-convex and piecewise optimization problem, considering the integration of linear equality and inequality constraints.     

一种基于信息熵的时间序列分段线性表示方法

针对部分时间序列具有高维、大数据量及数据更新速度较快的特点, 导致在原始时间序列上难以进行数据挖掘的问题, 提出一种基于信息熵的时间序列分段线性表示方法——PLR_IE。该算法利用信息熵作为评判重要点数量的性能指标, 从序列中提取重要分段点的数量分布情况, 利用重要点组成的序列重新拟合原始时间序列, 为下一步数据挖掘提供基础。实验结果表明, 该方法能高效地提取出序列主要特征、拟合原始序列。     

意愿计算的股市突变点预测方法

由于传统分段线性表示方法没有考虑股市数据分布变化导致分段不合理,同时股市突变点相关特征的局部性导致突变点难以有效预测,所以在分段线性表示方法的基础上提出一种意愿计算的股市突变点预测方法(WC-WSVM)。首先,给出一种波动率分布变化的分段线性表示(V-PLR)方法,通过波动率分布变化自适应地优化PLR分段阈值;然后,提取与主力买卖股票意愿相关的股市特征并进行量化,利用逻辑回归(LR)对于所提取的特征进行融合得到意愿计算结果;最后,将意愿计算结果与PLR-WSVM算法输入特征共同代入到WSVM中,进行突变点预测。在真实数据上的实验结果表明,算法具有强适应性,预测精度得到有效提升。     

On the numerical treatment of an ordinary differential equation arising in one-dimensional non-Fickian diffusion problems

In a recent study, Chen and Liu [Comput. Phys. Comm. 150 (2003) 31] considered a one-dimensional, linear non-Fickian diffusion problem with a potential field, which, upon application of the Laplace transform, resulted in a second-order linear ordinary differential equation which was solved by means of a control-volume finite difference method that employs exponential shape functions. It is first shown that this formulation does not properly account for the spatial dependence of the drift forces and results in oscillatory solutions near the left boundary when these forces are large. A piecewise linearized method that provides piecewise analytical solutions, is exact in exact arithmetic for constant coefficients, homogeneous, second-order linear ordinary differential equations and results in three-point finite difference equations is then proposed. Numerical simulations indicate that the piecewise linearized method is free from unphysical oscillations and more accurate than that of Chen and Liu, especially for large drift forces. The method is then applied to non-Fickian diffusion problems with non-constant drift forces in order to determine the effects of the potential field on the concentration distribution.     

Output feedback controller design for uncertain piecewise linear systems

This paper proposes output feedback controller design methods for uncertain piecewise linear systems based on piecewise quadratic Lyapunov function. The α-stability of closed-loop systems is also considered. It is shown that the output feedback controller design procedure of uncertain piecewise linear systems with α-stability constraint can be cast as solving a set of bilinear matrix inequalities （BMIs）. The BMIs problem in this paper can be solved iteratively as a set of two convex optimization problems involving linear matrix inequalities （LMIs） which can be solved numerically efficiently. A numerical example shows the effectiveness of the proposed methods.     

Piecewise linear polynomial functions and applications to analysis and parameter identification

The operational matrix of piecewise linear polynomial functions is derived. Then the problems of analysis and parameter identification are studied on this piecewise linear polynomial basis. The algorithms proposed are analogous to those derived for the orthogonal functions. The piecewise polynomial basis has certain advantages and convenience over other orthogonal functions. Illustrative examples are given for demonstration. The satisfactory results are obtained owing to the rapid convergence property of the piecewise linear polynomial functions.     

Popov–Belevitch–Hautus type controllability tests for linear complementarity systems

It is well-known that checking certain controllability properties of very simple piecewise linear systems are undecidable problems. This paper deals with the controllability problem of a class of piecewise linear systems, known as linear complementarity systems. By exploiting the underlying structure and employing the results on the controllability of the so-called conewise linear systems, we present a set of inequality-type conditions as necessary and sufficient conditions for controllability of linear complementarity systems. The presented conditions are of Popov–Belevitch–Hautus type in nature.     

Free knot splines for logistic models and threshold selection

The logistic regression model has been in use in statistical analysis for many years. The paper introduces a spline model to remove the linear restriction on logit function. By considering knot locations as free variables, spline approximation of data is improved. The number of knots and the degree of the spline functions can still be determined by using a model selection procedure. Moreover, a knot, seen as a free parameter for a piecewise linear spline, represents a break point in the logit function which may be interpreted as a threshold value. This method is applied to a clinical trial for an in vitro fertilization program.     

基于模糊聚类的PWA系统的模型辨识

针对一类分段仿射结构的离散时间混杂系统，其模型辨识可等价成对系统数据的分类、分类边界的优化及分类数据的线性回归问题.利用改进的G-K 模糊聚类算法，克服聚类迭代过程出现的非数值解问题；以综合性能指标最优确定最佳的子模型个数，从而获得最佳的分类数据; 以隶属度为权值，采用加权最小二乘算法提高子模型辨识精度；通过聚类中心最短法则确定两两相邻的子数据集，利用支持向量机思想，构造出一个标准的二次规划问题，得到凸多面体的方程系数. 仿真结果验证了该方法的有效性和实用性.     

Learning the stress function pattern of ordered weighted average aggregation using DBSCAN clustering

Ordered weighted average (OWA) operator provides a parameterized class of mean type operators between the minimum and the maximum. It is an important tool that can reflect the strategy of a decision maker for decision-making problems. In this study, the idea of obtaining the stress function from OWA weights has been put forward to generalize and characterize OWA weights. The main idea in this paper is mainly constructed on the basis that, generally, stress functions can be constructed using a mixture of constant and linear components. So, we can consider the stress function as a piecewise linear function. For obtaining stress functions as piecewise linear functions, we present a clustering-based approach for OWA weight generalization. This generalization is made using the DBSCAN algorithm as the learning method of a stress function associated with known OWA weights. In the learning process, the whole data set is divided into clusters, and then linear functions are obtained via a least squares estimator.     

不确定离散时滞分段系统的广义H2弹性控制

针对一类不确定离散时滞分段系统,研究了广义H2稳定性分析和带有时滞的状态反馈弹性控制器设计问题.通过构造适当的离散分段二次李亚普诺夫函数,利用分段二次李亚普诺夫稳定性理论,给出了对于所有的容许参数不确定性,闭环系统是广义H2稳定的充分条件;在此基础上,基于线性矩阵不等式(LMI)处理方法,提出了带有时滞的状态反馈弹性控制器增益阵的设计方案.仿真实例验证了所提方法的有效性.     

基于最优空间重采样的图像压缩算法

给出了一种基于最优空间重采样模型的图像压缩算法。该算法通过对图像像素的重采样,以还原误差最小化为准则选择性地保存图像中的部分像素来以达到压缩的目的,并通过分段线性插值来估计被删除的像素灰度完成还原。图像压缩实验证明其压缩性能接近JPEG2000,对复杂纹理图像的压缩稍差,对低码率和带噪图像的压缩还原结果在边界保持和视觉效果上要优于JPEG2000。     

Multilevel projection algorithm for solving obstacle problems

Obstacle problems are nonlinear free boundary problems and the computation of approximate solutions can be difficult and expensive. Little work has been done on effective numerical methods of such problems. This paper addresses some aspects of this issue. Discretizing the problem in a continuous piecewise linear finite element space gives a quadratic programming problem with inequality constraints. A new method, called the multilevel projection (MP) method, is established in this paper. The MP algorithm extends the multigrid method for linear equations to nonlinear obstacle problems. The convergence theorems of this method are also proved. A numerical example presented shows our error estimate is sharp and the MP algorithm is robust.     

An adaptive,multi-level method for elliptic boundary value problems

Subroutine PLTMG is a Fortran program for solving self-adjoint elliptic boundary value problems in general regions ofR ². It is based on a piecewise linear triangle finite element method, an adaptive grid refinement procedure, and a multi-level iterative method to solve the resulting sets of linear equations. In this work we describe the method and present some numerical results and comparisons.     

Approximate explicit constrained linear model predictive control via orthogonal search tree

Solutions to constrained linear model predictive control problems can be precomputed off-line in an explicit form as a piecewise linear state feedback on a polyhedral partition of the state-space, avoiding real-time optimization. We suggest an algorithm that can determine an approximate explicit piecewise linear state feedback by imposing an orthogonal search tree structure on the partition. This leads to a real-time computational complexity that is logarithmic in the number of regions in the partition, and the algorithm yields guarantees on the suboptimality, asymptotic stability and constraint fulfillment.