A convex relaxation approach to set-membership identification of LPV systems

Identification of linear parameter varying models is considered in this paper, under the assumption that both the output and the scheduling parameter measurements are affected by bounded noise. First, the problem of computing parameter uncertainty intervals is formulated in terms of nonconvex optimization. Then, on the basis of the analysis of the regressor structure, we present an ad hoc convex relaxation scheme for computing parameter bounds by means of semidefinite optimization.     

On finding the minimum possible peak value of multi-inputinfinite-horizon steering controls

A computational method for the infinite-dimensional optimization problem of finding the minimum possible peak value of a multi-input infinite-horizon steering control is presented. It is shown that the problem is equivalent to a convex program in a finite-dimensional Euclidean space. The convex program is approximated by a sequence of linear programs, the objective values of which converge to the objective of the convex program. A bound above and below are given for the error between the objective value of the convex program and the objective of any linear program in the approximating sequence. The bounds show convergence and are geometric with ratio given by the minimum modulus over all unstable plant poles     

具有闭环极点和方差约束的不确定离散系统鲁棒控制

对一类具有范数有界不确定性的离散时间系统,研究了使得闭环系统的所有极点位于一给定圆盘,且稳定状态方差不超过给定上界的状态反馈鲁棒方差控制律设计问题,基于线性矩阵不等式的处理方法,导出了鲁棒方差控制律的存在条件,并用一组线性矩阵不等式的珂行解给出了鲁棒方差控制律的一个参数化表示,进而,通过建立和求解一个凸优化问题,给出了具有最泸控制能量的鲁棒方差控制律设计方法。     

On optimization of finite-difference time-domain (FDTD) computation on heterogeneous and GPU clusters

A model for the computational cost of the finite-difference time-domain (FDTD) method irrespective of implementation details or the application domain is given. The model is used to formalize the problem of optimal distribution of computational load to an arbitrary set of resources across a heterogeneous cluster. We show that the problem can be formulated as a minimax optimization problem and derive analytic lower bounds for the computational cost. The work provides insight into optimal design of FDTD parallel software. Our formulation of the load distribution problem takes simultaneously into account the computational and communication costs. We demonstrate that significant performance gains, as much as 75%, can be achieved by proper load distribution.     

能效最优准则下的无人机中继系统的功率分配算法

由于无人机（Unmanned aerial vehicle,UAV）机动性好且部署简单,基于无人机中继的传输技术受到了广泛关注。功率作为通信系统的重要资源,其分配问题直接影响各条链路的性能和整个通信系统的能量效率。本文以莱斯衰落信道为背景,提出了一种在系统能效准则下的无人机中继通信系统的功率分配算法。首先在双跳放大转发（Amplify-and-forward,AF）中继传输模型的基础上建立功率分配的优化模型,将功率分配问题转化为求解最大系统能效的优化问题。在最优功率分配的求解过程中,先固定发射信号功率,获得波束形成优化方案;然后通过大信噪比区间近似,将非凸优化问题转化为凸优化问题;最后利用KKT（Karush-Kuhn-Tucker）条件,计算得出功率分配方案的闭式解。仿真实验表明,本文算法相对于迭代算法降低了算法复杂度。     

New bin packing fast lower bounds

In this paper, we address the issue of computing fast lower bounds for the Bin Packing problem, i.e., bounds that have a computational complexity dominated by the complexity of ordering the items by non-increasing values of their volume. We introduce new classes of fast lower bounds with improved asymptotic worst-case performance compared to well-known results for similar computational effort. Experimental results on a large set of problem instances indicate that the proposed bounds reduce both the deviation from the optimum and the computational effort.     

Computation of piecewise quadratic Lyapunov functions for hybridsystems

This paper presents a computational approach to stability analysis of nonlinear and hybrid systems. The search for a piecewise quadratic Lyapunov function is formulated as a convex optimization problem in terms of linear matrix inequalities. The relation to frequency domain methods such as the circle and Popov criteria is explained. Several examples are included to demonstrate the flexibility and power of the approach     

Single-machine scheduling to minimize total convex resource consumption with a constraint on total weighted flow time

In this paper, we consider single-machine scheduling problem in which processing time of a job is described by a convex decreasing resource consumption function. The objective is to minimize the total amount of resource consumed subject to a constraint on total weighted flow time. The optimal resource allocation is obtained for any arbitrary job sequence. The computational complexity of the general problem remains an open question, but we present and analyze some special cases that are solvable by using polynomial time algorithms. For the general problem, several dominance properties and some lower bounds are derived, which are used to speed up the elimination process of a branch-and-bound algorithm proposed to solve the problem. A heuristic algorithm is also proposed, which is shown by computational experiments to perform effectively and efficiently in obtaining near-optimal solutions. The results show that the average percentage error of the proposed heuristic algorithm from optimal solutions is less than 3%.     

关联动态时滞系统的分散镇定

针对一类关联时滞系统,通过建立一个凸优化问题,提出一种具有较小反馈增益参数的分散稳定化控制器的设计方法,数值例子表明了该方法的有效性。     

Delay‐dependent Stability and Static Output Feedback Control of 2‐D Discrete Systems with Interval Time‐varying Delays

This paper is concerned with the problems of delay‐dependent stability and static output feedback (SOF) control of two‐dimensional (2‐D) discrete systems with interval time‐varying delays, which are described by the Fornasini‐Marchesini (FM) second model. The upper and lower bounds of delays are considered. Applying a new method of estimating the upper bound on the difference of Lyapunov function that does not ignore any terms, a new delay‐dependent stability criteria based on linear matrix inequalities (LMIs) is derived. Then, given the lower bounds of time‐varying delays, the maximum upper bounds in the above LMIs are obtained through computing a convex optimization problem. Based on the stability criteria, the SOF control problem is formulated in terms of a bilinear matrix inequality (BMI). With the use of the slack variable technique, a sufficient LMI condition is proposed for the BMI. Moreover, the SOF gain can be solved by LMIs. Numerical examples show the effectiveness and advantages of our results.     

Optimization strategies for discrete multi-material stiffness optimization

Design of composite laminated lay-ups are formulated as discrete multi-material selection problems. The design problem can be modeled as a non-convex mixed-integer optimization problem. Such problems are in general only solvable to global optimality for small to moderate sized problems. To attack larger problem instances we formulate convex and non-convex continuous relaxations which can be solved using gradient based optimization algorithms. The convex relaxation yields a lower bound on the attainable performance. The optimal solution to the convex relaxation is used as a starting guess in a continuation approach where the convex relaxation is changed to a non-convex relaxation by introduction of a quadratic penalty constraint whereby intermediate-valued designs are prevented. The minimum compliance, mass constrained multiple load case problem is formulated and solved for a number of examples which numerically confirm the sought properties of the new scheme in terms of convergence to a discrete solution.     

A parametric extension of mixed time/frequency robustidentification

A parametric extension to the time/frequency robust identification framework is presented. The results can be applied to stable linear time-invariant systems on which time and/or frequency experiments have been performed. The parametric portion of the model should be affine in the unknown parameters, which includes practical applications such as flexible structures. The consistency problem is cast as a constrained finite-dimensional convex optimization problem that can be formulated as a linear matrix inequality. The proposed procedure provides an interpolating identification algorithm, convergent and optimal up to a factor of two (with respect to central algorithms)     

Supervised pattern recognition by parallel feature partitioning

In the present paper the supervised pattern recognition problem is considered. For solving the problem a mathematical model based on parallel feature partitioning is proposed. The solution is obtained by partitioning the feature space to a minimal number of nonintersecting regions. This is achieved by solving an integer-valued optimization problem, which leads to the construction of minimal covering. Since the classes do not intersect it follows that the solution of the formulated problem exists. Computational complexity of the model and computational procedures are discussed. Geometrical interpretation of the solution is given.     

Bridging the gap between the linear and nonlinear predictive control: Adaptations for efficient building climate control

The linear model predictive control which is frequently used for building climate control benefits from the fact that the resulting optimization task is convex (thus easily and quickly solvable). On the other hand, the nonlinear model predictive control enables the use of a more detailed nonlinear model and it takes advantage of the fact that it addresses the optimization task more directly, however, it requires a more computationally complex algorithm for solving the non-convex optimization problem. In this paper, the gap between the linear and the nonlinear one is bridged by introducing a predictive controller with linear time-dependent model. Making use of linear time-dependent model of the building, the newly proposed controller obtains predictions which are closer to reality than those of linear time invariant model, however, the computational complexity is still kept low since the optimization task remains convex. The concept of linear time-dependent predictive controller is verified on a set of numerical experiments performed using a high fidelity model created in a building simulation environment and compared to the previously mentioned alternatives. Furthermore, the model for the nonlinear variant is identified using an adaptation of the existing model predictive control relevant identification method and the optimization algorithm for the nonlinear predictive controller is adapted such that it can handle also restrictions on discrete-valued nature of the manipulated variables. The presented comparisons show that the current adaptations lead to more efficient building climate control.     

鲁棒最小二乘支持向量回归机

针对最小二乘支持向量回归机(LS-SVR)对异常值较敏感的问题,通过设置异常值所造成的损失上界,提出一种非凸的Ramp损失函数。该损失函数导致相应的优化问题的非凸性,利用凹凸过程(CCCP)将非凸优化问题转化为凸优化问题。给出Newton算法进行求解并分析了算法的计算复杂度。数据集测试的结果表明,与最小二乘支持向量回归机相比,该算法对异常值具有较强的鲁棒性,获得了更优的泛化能力,同时在运行时间上也具有明显优势。     

An artificial bee colony algorithm with feasibility enforcement and infeasibility toleration procedures for cardinality constrained portfolio optimization

One of the most studied variant of portfolio optimization problems is with cardinality constraints that transform classical mean–variance model from a convex quadratic programming problem into a mixed integer quadratic programming problem which brings the problem to the class of NP-Complete problems. Therefore, the computational complexity is significantly increased since cardinality constraints have a direct influence on the portfolio size. In order to overcome arising computational difficulties, for solving this problem, researchers have focused on investigating efficient solution algorithms such as metaheuristic algorithms since exact techniques may be inadequate to find an optimal solution in a reasonable time and are computationally ineffective when applied to large-scale problems. In this paper, our purpose is to present an efficient solution approach based on an artificial bee colony algorithm with feasibility enforcement and infeasibility toleration procedures for solving cardinality constrained portfolio optimization problem. Computational results confirm the effectiveness of the solution methodology.     

On minimax-regret Huff location models

We address the following single-facility location problem: a firm is entering into a market by locating one facility in a region of the plane. The demand captured from each user by the facility will be proportional to the users buying power and inversely proportional to a function of the user-facility distance. Uncertainty exists on the buying power (weight) of the users. This is modeled by assuming that a set of scenarios exists, each scenario corresponding to a weight realization. The objective is to locate the facility following the Savage criterion, i.e., the minimax-regret location is sought. The problem is formulated as a global optimization problem with objective written as difference of two convex monotonic functions. The numerical results obtained show that a branch and bound using this new method for obtaining bounds clearly outperforms benchmark procedures.     

An efficient bi-objective optimization framework for statistical chip-level yield analysis under parameter variations

With shrinking technology, the increase in variability of process, voltage, and temperature (PVT) parameters significantly impacts the yield analysis and optimization for chip designs. Previous yield estimation algorithms have been limited to predicting either timing or power yield. However, neglecting the correlation between power and delay will result in significant yield loss. Most of these approaches also suffer from high computational complexity and long runtime. We suggest a novel bi-objective optimization framework based on Chebyshev affine arithmetic (CAA) and the adaptive weighted sum (AWS) method. Both power and timing yield are set as objective functions in this framework. The two objectives are optimized simultaneously to maintain the correlation between them. The proposed method first predicts the guaranteed probability bounds for leakage and delay distributions under the assumption of arbitrary correlations. Then a power-delay bi-objective optimization model is formulated by computation of cumulative distribution function (CDF) bounds. Finally, the AWS method is applied for power-delay optimization to generate a well-distributed set of Pareto-optimal solutions. Experimental results on ISCAS benchmark circuits show that the proposed bi-objective framework is capable of providing sufficient trade-off information between power and timing yield.     

Time complexity and model complexity of fast identification ofcontinuous-time LTI systems

The problem of fast identification of continuous-time systems is formulated in the metric complexity theory setting. It is shown that the two key steps to achieving fast identification, i.e., optimal input design and optimal model selection, can be carried out independently when the true system belongs to a general a priori set. These two optimization problems can be reduced to standard Gel'fand and Kolmogorov n-width problems in metric complexity theory. It is shown that although arbitrarily accurate identification can be achieved on a small time interval by reducing the noise-signal ratio and designing the input carefully, identification speed is limited by the metric complexity of the a priori uncertainty set when the noise/signal ratio is fixed