无线通信中的最优资源分配―复杂性分析与算法设计

最优资源分配问题是无线通信系统设计中的基本问题之一.最优地分配功率、传输波形和频谱等资源能够极大地提高整个通信系统的传输性能.目前,相对于通信技术在现实生活中的蓬勃发展,通信系统优化的数学理论和方法显得相对滞后,在某些方面已经成为影响其发展和应用的关键因素.无线通信中的最优资源分配问题常常可建模为带有特殊结构的非凸非线性约束优化问题.一方面,这些优化问题常常具有高度的非线性性,一般情况下难于求解;另一方面,它们又有自身的特殊结构,如隐含的凸性和可分结构等.本文着重考虑多用户干扰信道中物理层资源最优分配问题的复杂性刻画,以及如何利用问题的特殊结构设计有效且满足分布式应用等实际要求的计算方法.     

灾情巡视问题的蚁群两目标优化算法研究

分析目前灾情巡视问题求解方法存在的缺陷,归纳出灾情巡视问题两目标优化模型.针对灾情巡视问题模型特点,引入蚁群算法和多目标优化理论,提出两个灾情巡视问题的蚁群两目标优化算法:算法1将灾情巡视问题的道路网络转化为完全图,增加m-1个(m为巡视组数)虚拟巡视起点,将灾情巡视两目标优化问题转化为单旅行商两目标优化问题,然后使用蚁群算法和多目标优化理论进行迭代求解.算法2使用一只蚂蚁寻找一个子回路,m个子回路构成一个灾情巡视可行方案,采用罚函数法和多目标优化理论构建增广两目标优化评价函数,使用g组,共g×m只蚂蚁共同协作来发现灾情巡视问题的最优解.算法特点:①算法1将灾情巡视两目标优化问题转化为单旅行商两目标优化问题,可以充分利用已有蚁群算法求解单旅行商问题的研究成果;②两个算法引入蚁群算法,提高了算法效率;③两个算法克服目前灾情巡视问题的求解方法不严密性缺陷;④两目标优化算法可以为用户提供多个满足约束条件的Pareto组合解,扩大了用户选择范围,增强了算法的适用性.算法测试表明:灾情巡视问题的蚁群两目标优化算法是完全可行和有效的.     

求解弱线性双层规划问题的一种全局优化方法

双层规划在经济、交通、生态、工程等领域有着广泛而重要的应用.目前对双层规划的研究主要是基于强双层规划和弱双层规划.然而,针对弱双层规划的求解方法却鲜有研究.研究求解弱线性双层规划问题的一种全局优化方法,首先给出弱线性双层规划问题与其松弛问题在最优解上的关系,然后利用线性规划的对偶理论和罚函数方法,讨论该松弛问题和它的罚问题之间的关系.进一步设计了一种求解弱线性双层规划问题的全局优化方法,该方法的优势在于它仅仅需要求解若干个线性规划问题就可以获得原问题的全局最优解.最后,用一个简单算例说明了所提出的方法是可行的.     

电力系统多目标优化运营研究

针对智能电网系统的安全与经济运行问题,建立了一个同时考虑经济、环境和安全指标的电网系统多目标优化模型,并运用理想点法对电网系统的多目标优化运营问题进行了相应的决策性分析,然后使用了一种新型的智能计算方法——标杆管理优化算法对该模型进行了求解计算.仿真实例表明,本文提出的决策分析和求解计算方法是切实可行的,具有一定的实用性和灵活性.此外,在计算过程中对一些相关的技术性问题,如对协调模型中的两类不同的控制变量、基因链的构造、约束条件的处理以及目标函数的选取等问题做了一些研究和探讨.     

数据驱动下的声学器件音质优化

音质是声学器件声音表现的重要衡量标准.但音质的优化过程需要对大量频点的响应进行协同优化,造成优化问题的可求解性较差.该文提出了一种数据驱动下的声学通道拓扑优化设计方法,可实现声-结构系统中的声频响快速预测,进而借助显式拓扑优化技术实现声学器件的音质优化.通过人工神经网络对结构几何参数、激励频率与声频响之间的非线性关系进行建模,以可移动变形组件(moving morphable components, MMC)法中的结构几何参数、激励频率为输入变量,以声压频响作为输出变量,通过训练多层前馈网络建立了声频响的人工神经网络模型.所得结果可以有效地将目标频带内的声压级范围差从44.89 dB缩小至6.49 dB,相较于传统优化方法,求解速度约为之前的16.3倍,表明了当前方法对音质优化问题的快速求解具有明显效果.     

张量分析和多项式优化的若干进展

张量分析 (也称多重数值线性代数) 主要包括张量分解和张量特征值的理论和算法,多项式优化主要包括目标和约束均为多项式的一类优化问题的理论和算法. 主要介绍这两个研究领域中若干新的研究结果. 对张量分析部分,主要介绍非负张量H-特征值谱半径的一些性质及求解方法,还介绍非负张量最大 (小) Z-特征值的优化表示及其解法;对多项式优化部分,主要介绍带单位球约束或离散二分单位取值、目标函数为齐次多项式的优化问题及其推广形式的多项式优化问题和半定松弛解法. 最后对所介绍领域的发展趋势做了预测和展望.     

支持向量机中一种参数优化选取方法

本文给出一种支持向量机中的参数优化选取方法. 它是通过遗传算法和确定性算法相结合解平衡约束优化问题,求出二分类支持向量机(SVM)中的正则参数C,本文将C作为优化问题中的变量来处理.遗传算法用来求解以C为变量的优化问题, 而确定性算法对每一个C值求解约束.数值计算的结果表明,用文中所述的方法求得的C值能明显提高支持向量机的泛化性能.     

模糊投资组合选择问题的改进帝企鹅优化算法

模糊投资组合选择问题是在基本投资组合模型中引入模糊集理论,使所建立的模型与实际市场更加吻合,但同时也增加了模型求解难度.因此,本文针对两种不同的模糊投资组合模型,提出一种改进帝企鹅优化算法.算法首先引入可行性准则,处理模糊投资组合模型中的约束.其次,算法中加入变异机制,平衡算法的开发和探索能力,引导种群向最优个体收敛.通过对CEC 2006中的13个标准测试问题及两个模糊投资组合问题实例进行数值实验,并与其他群智能优化算法进行结果比较,发现本文所提出的算法具有较好的优化性能,并且对于求解模糊投资组合选择问题是有效的.     

一种求解约束优化问题的改进差分进化算法

针对在处理约束优化问题时约束条件难以处理的问题,提出了一种求解约束优化问题的改进差分进化算法.即在每代进化前将群体分为可行个体和不可行个体两类,对不可行个体,用差量法将其逐个转化为可行个体,并保持种群规模不变,经过一序列的进化后,计算所有可行个体的适应度并找到问题的最优解.对5个经典函数进行了优化测试,测试结果表明提出的算法对求解约束优化问题是有效的.     

基于对偶二次规划的大型框架结构优化方法

将准则法和数学规划相结合,对于不同的约束采用不同的处理方法:应力约束作为局部性约束,用0阶近似进行处理,借助满应力准则将其转化为动态尺寸下限;位移约束作为全局性约束,根据单位虚载荷法将其显式化,从而建立了满足应力和位移约束的框架结构截面优化的显式模型．为了提高模型的求解效率,根据对偶理论将大规模的框架结构优化问题转化为仅仅几个对偶变量的对偶问题,采用二次规划方法求解,算例证明该方法能极大的提高模型的求解效率．采用近似射线步既能减小计算量又能使迭代过程更加平稳,采用删除无效约束技术能减小优化模型的规模. 以MSC/Nastran软件为结构分析的求解器,以MSC/Patran软件为开发平台,完成了满足刚度和强度的多工况、多变量的框架截面优化软件．算例结果表明上述程序算法的高效性．     

Applications of convex optimization in signal processing and digital communication

 In the last two decades, the mathematical programming community has witnessed some spectacular advances in interior point methods and robust optimization. These advances have recently started to significantly impact various fields of applied sciences and engineering where computational efficiency is essential. This paper focuses on two such fields: digital signal processing and communication. In the past, the widely used optimization methods in both fields had been the gradient descent or least squares methods, both of which are known to suffer from the usual headaches of stepsize selection, algorithm initialization and local minima. With the recent advances in conic and robust optimization, the opportunity is ripe to use the newly developed interior point optimization techniques and highly efficient software tools to help advance the fields of signal processing and digital communication. This paper surveys recent successes of applying interior point and robust optimization to solve some core problems in these two fields. The successful applications considered in this paper include adaptive filtering, robust beamforming, design and analysis of multi-user communication system, channel equalization, decoding and detection. Throughout, our emphasis is on how to exploit the hidden convexity, convex reformulation of semi-infinite constraints, analysis of convergence, complexity and performance, as well as efficient practical implementation. Received: January 22, 2003 / Accepted: April 29, 2003 Published online: May 28, 2003 RID="*" ID="*" This research was supported in part by the Natural Sciences and Engineering Research Council of Canada, Grant No. OPG0090391, and by the Canada Research Chair program. New address after April 1, 2003: Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455, USA     

Two basic problems in reliability-based structural optimization

Optimization of structures with respect to performance, weight or cost is a well-known application of mathematical optimization theory. However optimization of structures with respect to weight or cost under probabilistic reliability constraints or optimization with respect to reliability under cost/weight constraints has been subject of only very few studies. The difficulty in using probabilistic constraints or reliability targets lies in the fact that modern reliability methods themselves are formulated as a problem of optimization. In this paper two special formulations based on the so-called first-order reliability method (FORM) are presented. It is demonstrated that both problems can be solved by a one-level optimization problem, at least for problems in which structural failure is characterized by a single failure criterion. Three examples demonstrate the algorithm indicating that the proposed formulations are comparable in numerical effort with an approach based on semi-infinite programming but are definitely superior to a two-level formulation.     

Chromatic scheduling polytopes coming from the bandwidth allocation problem in point-to-multipoint radio access systems

Point-to-Multipoint systems are a kind of radio systems supplying wireless access to voice/data communication networks. Such systems have to be run using a certain frequency spectrum, which typically causes capacity problems. Hence it is, on the one hand, necessary to reuse frequencies but, on the other hand, no interference must be caused thereby. This leads to a combinatorial optimization problem, the bandwidth allocation problem, a special case of so-called chromatic scheduling problems. Both problems are NP-hard and it is known that, for these problems, there exist no polynomial time algorithms with a fixed approximation ratio. Algorithms based on cutting planes have shown to be successful for many other combinatorial optimization problems. In order to apply such methods, knowledge on the associated polytopes is required. The present paper contributes to this issue, exploring basic properties of chromatic scheduling polytopes and several classes of facet-defining inequalities. J. L. Marenco: This work supported by UBACYT Grant X036, CONICET Grant 644/98 and ANPCYT Grant 11-09112. A. K. Wagler: This work supported by the Deutsche Forschungsgemeinschaft (Gr 883/9–1).     

On a class of algorithms from experimental design theory

The theory of optimal (approximate) linear regression design has produced several iterative methods to solve a special type of convex minimization problems. The present paper gives a unified and extended theoretical treatment of the methods. The emphasis is on the mathematical structures relevant for the optimization process, rather than on the statistical background of experimental design. So the main body of the paper can be read independently from the experimental design context. Applications are given to a special class of extremum problems arising in statistics. The numerical results obtained indicate that the methods are of practical interest     

Subset simulation for unconstrained global optimization

Global optimization problem is known to be challenging, for which it is difficult to have an algorithm that performs uniformly efficient for all problems. Stochastic optimization algorithms are suitable for these problems, which are inspired by natural phenomena, such as metal annealing, social behavior of animals, etc. In this paper, subset simulation, which is originally a reliability analysis method, is modified to solve unconstrained global optimization problems by introducing artificial probabilistic assumptions on design variables. The basic idea is to deal with the global optimization problems in the context of reliability analysis. By randomizing the design variables, the objective function maps the multi-dimensional design variable space into a one-dimensional random variable. Although the objective function itself may have many local optima, its cumulative distribution function has only one maximum at its tail, as it is a monotonic, non-decreasing, right-continuous function. It turns out that the searching process of optimal solution(s) of a global optimization problem is equivalent to exploring the process of the tail distribution in a reliability problem. The proposed algorithm is illustrated by two groups of benchmark test problems. The first group is carried out for parametric study and the second group focuses on the statistical performance.     

Scalarization of the fuzzy optimization problems

Scalarization of the fuzzy optimization problems using the embedding theorem and the concept of convex cone (ordering cone) is proposed in this paper. Two solution concepts are proposed by considering two convex cones. The set of all fuzzy numbers can be embedded into a normed space. This motivation naturally inspires us to invoke the scalarization techniques in vector optimization problems to solve the fuzzy optimization problems. By applying scalarization to the optimization problem with fuzzy coefficients, we obtain its corresponding scalar optimization problem. Finally, we show that the optimal solution of its corresponding scalar optimization problem is the optimal solution of the original fuzzy optimization problem.     

Aspects of mathematical modelling related to optimization

Many practical optimization problems involved mathematical models of complex real-world phenomena. This paper discusses some aspects of modelling that influence the performance of optimization methods. Information and advice are given concerning the construction of smooth models, the transformation of an optimization problem from one category to another, scaling, formulation of constraints, and techniques for special types of models.     

Covering a plane with ellipses

Abstract

This paper is devoted to the construction of regular min-density plane coverings with ellipses of one, two and three types. This problem is relevant, for example, to power-efficient surface sensing by autonomous above-grade sensors. A similar problem, for which discs are used to cover a planar region, has been well studied. On the one hand, the use of ellipses generalizes a mathematical problem; on the other hand, it is necessary to solve these types of problems in real applications of wireless sensor networks. This paper both extends some previous results and offers new regular covers that use a small number of ellipses to cover each regular polygon; these covers are characterized by having minimal known density in their classes and give the new upper bounds for densities in these classes as well.     

Solving dual problems using a coevolutionary optimization algorithm

In solving certain optimization problems, the corresponding Lagrangian dual problem is often solved simply because in these problems the dual problem is easier to solve than the original primal problem. Another reason for their solution is the implication of the weak duality theorem which suggests that under certain conditions the optimal dual function value is smaller than or equal to the optimal primal objective value. The dual problem is a special case of a bilevel programming problem involving Lagrange multipliers as upper-level variables and decision variables as lower-level variables. Another interesting aspect of dual problems is that both lower and upper-level optimization problems involve only box constraints and no other equality of inequality constraints. In this paper, we propose a coevolutionary dual optimization (CEDO) algorithm for co-evolving two populations—one involving Lagrange multipliers and other involving decision variables—to find the dual solution. On 11 test problems taken from the optimization literature, we demonstrate the efficacy of CEDO algorithm by comparing it with a couple of nested smooth and nonsmooth algorithms and a couple of previously suggested coevolutionary algorithms. The performance of CEDO algorithm is also compared with two classical methods involving nonsmooth (bundle) optimization methods. As a by-product, we analyze the test problems to find their associated duality gap and classify them into three categories having zero, finite or infinite duality gaps. The development of a coevolutionary approach, revealing the presence or absence of duality gap in a number of commonly-used test problems, and efficacy of the proposed coevolutionary algorithm compared to usual nested smooth and nonsmooth algorithms and other existing coevolutionary approaches remain as the hallmark of the current study.