不联贯离散规划的一类新的松弛方法.pdfVIP

2015年1月 四川师范大学学报(自然科学版) Jan．。2015 ofSichuanNomal V01．38．No．1 第38卷第1期 Jo啪al University(NaturalScience) 不联贯离散规划的一类新的松弛方法 张琳翎． 冯志国+ (重庆师范大学数学学院，重庆400047) 摘要：讨论离散规划问题，其中离散集可以是不联贯的．首先，介绍基础集的概念．然后通过基础集把这 个问题转化为一个等价的优化问题．接着引进一个新的松弛方法将问题转化成一个连续性优化问题，然后 提出一种新的梯度下降法对其求解，也通过实现数值例子来检验了该方法． 关键词：离散规划；stiefel流型；不联贯离散集 中图分类号：0178 文献标志码：A 文章编号：100l一8395(2015)叭一0084—04 doi：10．3969／j．i髂n．1∞l一犯95．2015．01．014 1预备知识 集，定义x的一个基础集如下． 定义2．1如果以下条件成立，则以8称为x的 在实际中，优化问题¨。o的应用是非常广泛 阶为d的基础集． 的．其中，离散规划问题尤其困难，因为它是NP(非 1)x中的任何元素都可以被表示成A。中d个 确定性多项式)难的．由于决策变量不是连续变量， 不同的元素的和． 不能运用传统的优化方法求解．目前，比较常用的 2)A4中任何d个不同的元素的和都是x中的 是各种离散有哪些信誉好的足球投注网站方法H山J，但有哪些信誉好的足球投注网站的复杂性取决于 一个元素． J． 优化问题的特性．另一种方法采取的是松弛法’7 假定基础集表示为以4={A。，A：…，A。}，其中 在这种情况下，离散变量转换为连续型变量来考 m是基础集的元素总个数，由(1)式知：对于任意的 虑，然后就可以采用梯度下降法来求解．在文献中 y∈x，都可以找到至少一个m维向量^(这个向量 还有很多各种各样的方法能解决这个问题，如二次 中有d个元素等于1，其它元素等于0)，使得 函数、半定规划等其它方法旧。10】．对于离散规划问 y=AT^， (2) 题，通过对目标函数添加罚函数使得变量得以保持 其中 离散形式，文献[11—13]就使用了各种罚函数．本 A=(A】，A2，…，A。)1． 文采取一种新的松弛方法解决离散规划问题． 可以看出，任何一个向量^都对应着x中的一个元 2问题的构造 素．但它不是一一对应的，即对于x中的某些元素， 可能同时存在几个向量^满足(2)式． 离散规划问题