Complexity of min-max subsequence problems

We determine the computational complexity of the problem of ordering a set of n numbers, either into a sequence or a cycle, such that the maximum sum of any k successive numbers is minimal. Both problems are easy for k=2 and strongly NP-hard for any k?3. However, the two problems allow a polynomial-time approximation scheme that is linear in n.     

Automatic training of a min-max neural network for function approximation by using a second feed forward network

This research is concerned with a gradient descent training algorithm of a min-max network which we will refer to as the target network. Training makes use of a helper feed-forward network (FFN) to represent the performance function used in training the target network. A helper FFN is trained because the mathematical form of the performance function for the target network in terms of its trainable parameters, p, is not differentiable. Values for the parameter vector, p, of the target network are generated randomly and performance values are determined to produce the data for training the helper FFN with its own connection matrices. Thus we find an approximation to the mathematical relationship between performance values and p by training an FFN. The input to this FFN is a value for p and the output is a performance measure. The transfer function of the helper FFN provides a differentiable function for the performance function of the parameter vector, p, for the target network allowing gradient search methods for finding the optimum p for the target network. The method is successfully tried in approximating a given function and also on training data produced by a randomly selected min-max network.     

On discrete dynamic output feedback min-max controllers

The paper considers output feedback min-max controllers for non-square discrete time uncertain linear systems. Based on previous work, it is demonstrated that static output feedback min-max controllers are only realizable for a specific class of systems. To broaden this class, a compensator based framework is proposed to introduce additional degrees of freedom. The conditions for the existence of such dynamic output feedback min-max controllers are given and are shown to be relatively mild. Furthermore, a simple parameterization of the available design freedom is proposed. An explicit procedure is described which shows how a Lyapunov matrix, which satisfies both a discrete Riccati inequality and a structural constraint, can be obtained using Linear matrix inequality optimization. This Lyapunov matrix is used to calculate the robustness bounds associated with the closed-loop system. A simple aircraft example is provided to demonstrate the efficacy of the design approach.     

Min-max MPC using a tractable QP problem

Min-max model predictive controllers (MMMPC) suffer from a great computational burden that is often circumvented by using approximate solutions or upper bounds of the worst possible case of a performance index. This paper proposes a computationally efficient MMMPC control strategy in which a close approximation of the solution of the min-max problem is computed using a quadratic programming problem. The overall computational burden is much lower than that of the min-max problem and the resulting control is shown to have a guaranteed stability. A simulation example is given in the paper.     

机器人关节跟踪带死区的变参数EW-RLS算法研究

提出一种带死区的变参数EW-RLS算法,提出误差级的概念,并给出基于鲁棒极小极大原理选择误差级的准则。在机器人关节上进行的实验验证了该改进算法的良好性能。利用该算法,用最优PID控制器进行机器人轨迹跟踪研究。     

多元LDPC码Min-max自适应译码算法

为了降低多元低密度奇偶校验(Low-density parity check,LDPC)码Min-max译码算法的运算量,提出一种自适应Min-max(Adaptive Min-max,AMM)译码算法.该方法以Min-max算法为基础,以每次迭代后的校验节点错误率(Check-node Error Rate,CER)为调节参数,采用自适应算法对变量节点的向量长度进行截短,去除置信度较低的分量,仅对置信度较高的分量进行更新.当CER降低到一定程度时,对校验节点个数进行自适应截短,仅对不满足校验方程的校验节点进行消息迭代更新,进一步降低AMM算法的复杂度.仿真结果表明,在相同误码性能条件下,AMM算法运算量较固定长度截短的Min-max算法减少20％.     

OPTIMALITY CHARACTERISTICS OF PI/PID CONTROLLERS: A COMBINED MIN-MAX/ISE INTERPRETATION

This communication addresses the tuning of PI and PID controllers on the basis of the IMC approach. The tuning is based upon a first order plus time delay (FOPTD) model and aims to achieve a step response specification. Through analysis it has been found that by using the IMC approach we get a PI or a PID depending on the rational approximation used for the time delay term. This article raises the question that the use of a PID instead of a PI controller should be based on another reason more related to the control objectives rather than the use of a better approximation for the time delay. An alternative tuning is presented here, from within the IMC formulation, based on a min-max optimization. From the tuning rule provided by this approach the optimum settings from an integral squared error criterion point of view are derived. The optimal controller results in being a PI controller. From this optimal controller as the starting point, the introduction of the derivative action can be seen as a detuning procedure that can increase the robustness of the controller. This approach provides further insight into the tuning of PI and PID controllers giving the (alternative) parameters a precise engineering meaning.     

一种基于感知器的样本空间划分方法

二类分类问题是机器学习中的最基本的一类重要问题.目前广泛使用的,也是最为有效的学习算法是支持向量机 (SVM).然而对于某些非线性分类问题,SVM 还不能给出令人满意的解,因此希望能找到一种方法对 SVM 解决非线性分类问题的能力加以改进.对二类分类问题,提出一种基于感知器的样本空间划分方法.该方法首先用感知器提取样本的分布信息,将整体问题划分为局部空间中的分类问题,而后使用 SVM 求出各个局部问题的最优分界面,并用最小最大模块化网络对局部分界面进行综合,得到问题的全局解.仿真实验表明,新方法能够有效地分析样本空间,提取样本分布信息,在测试数据上得到了比原有方法更好的准确率.新方法实现了预期的目标,提高了分类器处理非线性分类问题的能力.     

一种改进的最小最大割算法

最小最大割算法(Mcut)能满足聚类算法的一般准则,但在实际求解过程中,通常把Mcut算法的目标函数松弛转换为标准分割算法(Ncut)的目标函数进行求解,而未充分使用Mcut的聚类性能。为此,利用子空间技术,提出一种改进的Mcut算法(SMcut),设计基于图像分块的SMcut算法(BSMcut),以提高SMcut算法的分割速度。实验结果表明,SMcut和BSMcut算法均具有较好的分割性能,且BSMcut算法的计算复杂度较低。     

Identification of dynamical systems with a robust interval fuzzy model

In this paper we present a new method of interval fuzzy model identification. The method combines a fuzzy identification methodology with some ideas from linear programming theory. On a finite set of measured data, an optimality criterion that minimizes the maximal estimation error between the data and the proposed fuzzy model output is used. The idea is then extended to modelling the optimal lower and upper bound functions that define the band that contains all the measurement values. This results in a lower and an upper fuzzy model or a fuzzy model with a set of lower and upper parameters. The model is called the interval fuzzy model (INFUMO). The method can be used when describing a family of uncertain nonlinear functions or when the systems with uncertain physical parameters are observed. We believe that the fuzzy interval model can be very efficiently used, especially in fault detection and in robust control design.