Dynamic Spatial Auction Market Models with General Cost Mappings

The deregulation of electricity markets in Europe has deeply changed the organization of this sector. Vertically integrated generating companies have been unbundled to create competition and to increase the competitiveness of electricity markets. Directive 96/92/EC was issued by the European Commission to liberalize electricity markets and to pave the way for the creation of the Internal Electricity Market. In particular, this Directive aimed at promoting the competition in the activities of electricity generation and wholesale through the creation of a “marketplace” and the maximization of transparency and efficiency. Competition in European day-ahead electricity markets has been established through auction markets where electricity producers and consumers offer/bid prices and volumes. This paper suggests a dynamic equilibrium model for a system of auction markets linked by transmission lines and subject to energy balance and transmission constraints, such as those characterizing restructured electricity markets. This model is treated as a system of variational inequalities with arbitrary monotone mappings. An inexact splitting type method is proposed to find its solution. Numerical experiments are conducted on the Italian day-ahead electricity market.     

Adaptive Auction Framework for Spectrum Market in Cognitive Radio Networks

For the recent decade, cognitive radio networks have received much attention as an alternative to the traditional static spectrum allocation policy since the licensed spectrum channels are not being used efficiently. The most critical issue of the cognitive radio networks is how to distribute the idle spectrum channels to the secondary users opportunistically. The auction-based market is desirable for the trade of idle spectrum channels since the secondary users can purchase a channel in timely manner and the licensed primary users can earn the additional profit while not using the channels. Among the auction algorithms proposed for the spectrum market, we focus on the TASG framework, which consists of two nested auction algorithms, because it enables the group-buying of spectrum channels for the secondary users with limited budgets, and possesses many positive properties such as budget-balance, individual rationality and truthfulness. However, the TASG framework is not very attractive to the market participants since the seller earns the small revenue and the buyer has the low utility. In this paper, we propose a new auction framework for the spectrum markets, called aDaptive and Economically robust Auction-based Leasing (DEAL), that keeps all the benefits of TASG while improving the utility (or revenue) of the participants. To this end, we develop an enhanced inner-auction algorithm, called the Global Auction algorithm in our DEAL framework, and adapt the involved parameters dynamically based on the previous bids from the potential buyers. Simulation results demonstrate that our framework significantly outperforms the previous TASG.     

Degree Constrained Node-Connectivity Problems

We consider Degree Constrained Survivable Network problems. For the directed Degree Constrained k -Edge-Outconnected Subgraph problem, we slightly improve the best known approximation ratio, by a simple proof. Our main contribution is giving a framework to handle node-connectivity degree constrained problems with the iterative rounding method. In particular, for the degree constrained versions of the Element-Connectivity Survivable Network problem on undirected graphs, and of the k -Outconnected Subgraph problem on both directed and undirected graphs, our algorithm computes a solution J of cost O(logk) times the optimal, with degrees O(2 ^k )?b(v). Similar result are obtained for the k -Connected Subgraph problem. The latter improves on the only degree approximation O(klogn)?b(v) in O(n ^k ) time on undirected graphs by Feder, Motwani, and Zhu.     

针对带约束非线性规划问题的遗传算法

研究了针对带约束非线性规划问题的遗传算法(CNP-GA),设计了相应的适应度函数及处理约束的方法,结合了排挤和排序选择以保证群体的多样性,通过邻域搜索和变异算子进行联合演化,并利用多个群体的竞争得到全局解,对非线性限制规划例子的测试证明本算法是有效而可行的。     

A Splitting Method for Orthogonality Constrained Problems

Orthogonality constrained problems are widely used in science and engineering. However, it is challenging to solve these problems efficiently due to the non-convex constraints. In this paper, a splitting method based on Bregman iteration is represented to tackle the optimization problems with orthogonality constraints. With the proposed method, the constrained problems can be iteratively solved by computing the corresponding unconstrained problems and orthogonality constrained quadratic problems with analytic solutions. As applications, we demonstrate the robustness of our method in several problems including direction fields correction, noisy color image restoration and global conformal mapping for genus-0 surfaces construction. Numerical comparisons with existing methods are also conducted to illustrate the efficiency of our algorithms.     

Local Search Techniques for Constrained Portfolio Selection Problems

We consider the problem of selecting a portfolio of assets that provides theinvestor a suitable balance of expected return and risk. With respect to theseminal mean-variance model of Markowitz, we consider additionalconstraints on the cardinality of the portfolio and on the quantity ofindividual shares. Such constraints better capture the real-world tradingsystem, but make the problem more difficult to be solved with exact methods.We explore the use of local search techniques, mainly tabu search, for theportfolio selection problem. We compare the combine previous work on portfolioselection that makes use of the local search approach and we propose newalgorithms that combine different neighborhood relations. In addition, we showhow the use of randomization and of a simple form of adaptiveness simplifiesthe setting of a large number of critical parameters. Finally, we show how ourtechniques perform on public benchmarks.     

广义齐型Besov范数约束下的图像分解

为了将图像分解为分片光滑的结构部分和振荡部分,提出一种新的变分图像分解模型.该模型利用第二代曲波和局部余弦基分别表征含噪图像中的结构分量和纹理分量,并采用全变差半范约束分片光滑部分的结构性;同时利用 Meyer 所建议的广义齐型 Besov 范数对噪声分量进行约束;最后利用基追踪去噪算法对新模型进行迭代求解.理论分析和实验结果表明,该算法对噪声具有较强的鲁棒性,并使边缘和细小的纹理信息保持稳定.     

Current Approaches for Solving Over-Constrained Problems

We summarize existing approaches to model and solve overconstrained problems. These problems are usually formulated as combinatorial optimization problems, and different specific and generic formalisms are discussed, including the special case of multi-objective optimization. Regarding solving methods, both systematic and local search approaches are considered. Finally we review a number of case studies on overconstrained problems taken from the specialized literature.     

KD-TSS:精确隐私空间分割方法

基于KD-树与差分隐私保护的空间数据分割得到了研究者的广泛关注,空间数据的大小与拉普拉斯噪音的多少直接制约着空间分割的精度。针对现有基于KD-树分割方法难以有效兼顾大规模空间数据与噪音量不足的问题,提出了一种满足差分隐私的KD-树分割方法 SKD-Tree(sampling-based KD-Tree)。该方法利用满足差分隐私的伯努利随机抽样技术,抽取空间样本作为分割对象,然而却没有摆脱利用树高度控制拉普拉斯噪音。启发式设定合适的树高度非常困难,树高度过大,导致结点的噪音值过大;树高度过小,导致空间分割粒度太粗劣。为了弥补SKD-Tree方法的不足,提出了一种基于稀疏向量技术(sparse vector technology,SVT)的空间分割方法 KD-TSS(KD-Tree with sampling and SVT)。该方法通过SVT判断树中结点是否继续分割,不再依赖KD-树高度来控制结点中的噪音值。SKD-Tree、KD-TSS与KD-Stand、KD-Hybrid在真实的大规模空间数据集上实验结果表明,其分割精度以及响应范围查询效果优于同类算法。     

求解约束优化问题的一种复合形遗传算法

研究约束优化问题是科学和工程应用领域经常会遇到的一类数学规划问题.现有的约束优化进化算法,通常的解决办法是将等式约束条件转化为成对的不等式约束条件来处理,转换会使得可行域的拓扑结构变化显著,直接影响了算法性能和解的精度.为解决上述问题,提出了一种改进的处理约束优化问题的新算法.新算法将约束优化问题转化为多目标优化问题,把复合形法嵌入到遗传算法中,通过将全局搜索和局部搜索机制有机地结合,利用遗传算法全局性好和复合形法快速高效的特点,以加快最优解的搜索进程.仿真结果表明,方法既有复合形法快速高效的特点,又有遗传算法全局性好的特点.与标准遗传算法相比,方法具有良好的求解约束优化性能和精度效果.     

Spatial Models for Wide-Area Visual Surveillance: Computational Approaches and Spatial Building-Blocks

Spatial models play a key role when interpreting a dynamic and uncertain world for a wide-area surveillance application. This paper presents two different views to illustrate the range of spatial models. First, we take a top-down look, where we survey various work relevant to the development of spatial models and how they have been used in AI applications. Then we take a more bottom-up look, starting with a promising spatial primitive to identify a useful foundation that can support visual surveillance applications.     

一种求解约束优化问题的线性进化算法

提出一种基于实数编码处理约束优化问题的线性算法,并对其复杂度和收敛性进行分析.该算法将约束优化问题的高维搜索空间通过线性变换映射到二维空间,在二维空间中探索原优化问题的解,从数学分析的角度给出一种线性适应度函数.算法中融入一种基于密度函数的交叉算子和变异算法,采用基于分级聚类的平均联接方式以维持Pareto最优解集个体数目.3组典型优化问题的测试表明,该算法是可行和有效的,解集分布的均匀性与多样性均较理想.     

解约束最优化问题的一个新的多目标进化算法

把约束函数作为目标函数,将约束优化问题转化为多目标规划问题。对这个多目标规划,根据带权极小极大策略构造了一个同进化代数有关的变适应值函数。利用广义球面坐标变换和均匀设计法来选择权重,使得由此权重确定的适应值函数能使种群中的容许解逐渐增加并且保持其多样性。用均匀设计法构造的带有自适应性的变异算子增强了算法的局部搜索能力。该方法能有效处理约束,特别是紧约束。计算机仿真显示了该方法是有效的。     

求解约束优化问题的改进元胞遗传算法

针对约束优化问题,提出一种改进元胞遗传算法.将自适应ε约束处理技术与元胞遗传算法结合,对于自适应ε约束处理技术中的截断进化代数,在其前期提出偏好性指标概念,随机选取满足约束条件较好的个体引导种群快速向可行域逼近,在其后期采用改进柯西变异算子避免陷入局部最优.基于一组标准测试函数进行测试,与其它算法进行对比,结果表明算法...     

Decomposition Method for Solving Three-Index Transportation Problems

A decomposition method based on the sequential modification of the optimality criterion is used for solving the classical three-index transportation problem. The method consists of a sequence of solutions of local problems with three constraints. A monotonic (in the optimality criterion) process that converges to the solution of the original problem is constructed. The solutions of the transportation problem with a linear and quadratic objective function are considered and the numerical results are presented.     

约束非线性规划问题的辅助函数算法

研究有不等式约束的非线性规划问题,构造了一种新的两阶段算法:(1)利用传统优化方法求出原问题的一个局部极小点x*;(2)基于当前局部极小点和“准”罚函数的思想构造了一个辅助函数,该辅助函数连续可微、有界并且是凸的,该函数的局部极小点y*很容易求得,并且y*位于比x*更低的盆域中,从而y*可以作为第一阶段中的初始点,从而找到另一个更好的局部极小点.两个阶段不断循环,只要原问题具有有限个局部极小点,就可以找到它的全局极小点.为了测试算法的性能,对几个测试问题进行了求解.结果表明算法有效的,可以快捷的跳出局部极小点达到全局极小点.     

解约束多目标优化问题的一种鲁棒的进化算法

将约束条件与目标函数融合在一起,对有约束的多目标优化问题(MOP)建立了一种新的偏序关系,引入了约束占优的定义,并证明了在新的偏序关系意义下的Pareto最优集就是满足约束条件的Pareto最优集,从而在对种群中的个体进行评估或排序时,并不需要特别去关心个体是否可行,避免了罚函数选择参数的困难,尝试应用有限Markov链的有关理论证明了此进化算法的收敛性,用较复杂的Benchmark函数进行了大量的数值实验,测试结果表明新算法在解集分布的均匀性、多样性以及快速收敛性均较理想。     

一种新的求解约束多目标优化问题的遗传算法

由于采用罚函数法将有约束多目标优化问题转化为无约束多目标优化问题会使求解不合理,因此,文章首先在无约束Pareto排序遗传算法的基础上,提出了一个简单、实用的能分别考虑目标函数和约束函数,而又可以避免采用罚函数的全新排序方法。接着,针对小生境技术在遗传后期依旧会出现遗传漂移现象和共享半径不易确定等缺陷,提出了一种易于实现的超量惩罚策略来替代小生境技术,用以改进种群的多样性。此外,还采用了Pareto解集过滤器、邻域变异和群体重组等策略对算法的寻优能力进行改进,并最终形成了一种求解有约束多目标优化问题的Pareto遗传算法(CMOPGA),还给出了具体的算法流程图。最后采用两个数值算例对算法的求解性能进行了测试。数值试验表明,采用CMOPGA可方便地求得问题的Pareto前沿,并能使求得的Pareto最优解集具有可靠、均布、多样等特点。