（应用数学专业论文）基于变分不等式的网络广告超网络模型研究.pdf

中文摘要 摘要 对于自然界大量的复杂的系统都可以通过形形色色的网络加以描述。以a n n a n a g u r n e y 教授为首的以超网络结构模型为研究中心的一批批研究者利用变分不等 式研究网络的均衡模型，将交通网络均衡模型的有关原理运用到供应链超网络、 知识超网络、金融超网络、人口转移超网络等多种网络中，超网络模型显示了不 凡的作用。变分不等式作为变分原理的主要推广，是数学上的一个重要分支。近 年来，经典的变分不等式理论已被大量地用于应用数学、优化控制理论、力学与 热学、线性与非线性规划、经济与金融、交通与运输平衡等各个领域。特别是网 络模型框架结合变分理论算法，使得模型解的精确程度和求解的速度有很大的改 善与提高。 网络广告是新生事物，最早起源于美国，作为一种新的营销手段已成为广告 界的热点；但是对网络广告资源分配的认识刚开始，一些模型的建立只以点击量 为目标量，没有引入现实网络广告中的转化量，这样就不能真实反映广告效果， 就会造成决策者决策失误。本文通过引入点击量、转化量和用显示概率作为权值 的展示量，采用超网络模型、变分不等式算法解决网络广告资源优化问题，通过 理论论证和实例分析进一步说明了该模型理论的正确性与实际的可用性。 关键词：点击置；转化量；显示概率；超网络模型；变分不等式 英文摘要 r e s e a r c ho ft h en e t w o r ka d v e r t i s e m e n ts u p e r - n e t w o r km o d e l b a s e do nt h ev a r i a t i o n a li n e q u a l i t i e s a b s t r a c t al a r g en u m b e ro f c o m p l e xs y s t e m si nn a t u r ec a nb ed e s c r i b e di nv a r i o u sn e t w o r k s m o d e l s h e a d e db yp r o f e s s o ra n n an a g u r n e y , t h es c h o l a r sc o n c e n t r a t et h e i ra t t e n t i o n s t ot h er e s e a r c ho fs u p e r - n e t w o r km o d e l u s i n gv a r i a t i o n a li n e q u a l i t i e st or e s e a r c h n e t w o r ke q u i l i b r i u mm o d e l t h e yh a v ea p p l i e dt h ep r i n c i p l e so ft r a f f i cn e t w o r kt ot h e s u p p l yc h a i ns u p e m c t w o r k s ，f i n a n c es u p e r n e t w o r k s ，k n o w l e d g es u p e m e t w o r k sa n ds o o ns u c c e s s f u l l y s u p e m e t w o r km o d e lh a sb e e ns h o w i n gi t se x t r a o r d i n a r yr o l e a st h e e x t e n s i o no fv a r i a t i o n a lt h e o r y ，t h ev a r i a t i o n a li n e q u a l i t yi sa ni m p o r t a n tb r a n c ho f m a t h e m a t i c s i nr e c e n ty e a r s ，i th a sb e e nu s e dt om a n yf i e l d s ，s u c ha s a p p l i e d m a t h e m a t i c s ，p h y s i c s ，l i n e a ra n dn o n l i n e a rp r o g r a m m i n gp r o b l e m ，e c o n o m i c s ，f i n a n c e ， t r a n s p o r t s p e c i a l l y ，t h ei n t e g r a t i o nb e t w e e nt h ef r a m e w o r ko fs u p e m e t w o r ka n d v a r i a t i o n a l i n e q u a l i t yh a si m p r o v e dt h ee f f i c i e n c y o fs o l v i n gam o l l ，i n c l u d i n g p r e c i s i o na n ds p e e d n e t w o r ka d v e r t i s e m e n ta san e wt h i n g ，i th a sm o r ea n dm o r el i f e f o r o ea n dh a s d r a w ni n c r e a s i n gc o n c e r n , b u tr e s e a r c h e so nr e s o u r c ea l l o c a t i o na r es t i l lo ns e e d t i m e s o m em o d e l so n l yu s ec l i c k - t h r o u g ha s t h eo b j e c t i v er e f e r e n c e b u tl o s es i g h to f c o n v e r s i o n s t h u st h e s ec a i ln o tr e f l e c tt h ee f f e c to fn e ta d v e r t i s e m e n te x a c t l ya n dw i l l r e s u l ti nd e c i s i o n - m a k i n ge i t o r sf o rp o l i c ym a k e r s b a s e do nt h ep r e v i o u sr e s e a r c h e s a n dp r a c t i c e s ，w ed e v e l o paf r a m e w o r k ，w h i c ha d o p t s 跚p 咖r km o d e la n d v a r i a t i o n a li n e q u a l i t yt os o l v et h eo p t i m a lr e s o u r c ea l l o c a t i o no f n e ta d v e r t i s e m e n t t h i s m o d e li n v o l v e sn o to n l yc l i c k - t h r o u g ha n dc o n v e r s i o n sb u ta l s ow e i g h t e de x p o s u r e s w i t hi m p r e s s i o np r o b a b i l i t yt h a tr e v i s e st h ee x p r e s s i o n c o m p u t e rs i m u l a t i o nw i t ha n u m e r i c a le x a m p l ei su s e dt ov a l i d a t et h ef e a s i b i l i t yo f t h em o d e la n dt h ea l g o r i t h m k e y w o r d ：c l i c k - t h r o u g h ；c o n v e r s i o n ；i m p r e s s i o np r o b a b i l i t y ；s n p e r n e t w o r k ； v a r i a t i o n a li n e q u a l i t y 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文：基王銮盆丕笠式的圆终亡壹超圆终搓型班究：。除论文 中已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文 中以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公 开发表或未公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名：闻羔互 御年1 1 月? 。臼 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法”，同意大连海事大学保留并向国家有关部门或机构送交学位 论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或 扫描等复制手段保存和汇编学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于：保密口 不保密医y ( 请在以上方框内打“4 ”) 论文作者勰问蔓墨 导师签名彩留 日期：多7 年1 1 月弓日 基于变分不等式的网络广告超网络模型研究 第1 章绪论 1 1 课题背景及意义 现实世界中的很多系统可归结为网络系统。网络给我们的社会、经济、科学 和商业、科技、社会体系和教育等诸多方面的发展提供了工具。网络是一些经济 和社会活动的基础，具体体现在：运输网络、通信网络、能源网络、金融网络等 方面。 运输网络给我们提供了跨越实际距离的多种途径，给我们提供食物和消费产 品的市场销路，并且可以通过多种方式到达目的地，如：陆地运输、空中运输、 铁路运输和水路运输等。 通信网络让我们信息共享，可以与其它的院校进行交流，还可以指导对生活 的必要处理。 能源网络能够为交通网络和通信网络的许多方面提供能量。 金融网络给商业扩大、革新提供资源，从而可满足消费者的需求。 随着计算机、通讯技术、因特网等这些网络的出现和发展，我们在生活、工 作和掌管经济等方式上也有了很大的改变。 经典网络中的点可以和实际空间的位置相对应，线又能将实际中的这些点连 接起来。超网络是网络中的网络，它是基于决策的形象化而又高于现存的网络系 统，有时候它是抽象的，由一些点、链和相关流组成。超网络可以由多分层、多 标准的网络构成，它的流量可以是多维的。 超网络起源于对交通网络的研究，而现在超网络已涉及到交通运输网络、经 济金融网络、电子通讯网络、知识协作网络、供应量网络、物流网络，能源网络 等等方面。超网络的应用很多，此处介绍三个，以便我们能更好的了解超网络模 型。 1 远程终端工作与通勤决策网络 根据m o k h t a r i a n 1 的论述：远程终端工作可能替代通勤的很大一部分。这也就 是说由于电讯的发展，远程终端工作将潜在地造成出行( 通勤) 数量的缩减。 作为决策者的出行人，他们决定从起点到目的地所需要的最优路。在超网络 框架下，一个链可以相当于物理交通连接，或者是相应的虚拟远程终端工作连接， 第1 章绪论 这时超网络模型可研究这样的问题：一条路可能由很多链构成，这些链相应于物 理的或虚拟的路径选择。而此时也可能会出现这样的情况：一个工作者从居住地 先到一个工作中心，在这个中心可以进行远程工作。在附录中的图a ，提供了这 种思想模型。 出行人是模型框架中的决策者，因此路流和链流分别相应于对选择不同路和 链的出行者的数量。 在实际应用中，模型标准的选择要满足决策的合理性。第一个多标准交通网 络模型可追溯到s c h n e i d e r l 2 ，考虑了两个标准，即出行时间和费用；d a f c r m o s 【3 】 等同样考虑了这两个标准，但他们涉及到了拥塞问题；n a g u m e y , d o n g ，和 m o k h t a r i a n 4 1 考虑了整合的多标准网络平衡模型，第一次考虑了远程终端工作与通 勤问题，涉及到三个标准：出行时间、出行费用和机会成本。 不同类型的出行者选择从起点到终点的路，要权衡不同的标准从而使总代价 最小。 2 远程终端购物与购物决策网络 这里提出的远程终端购物与购物决策模型，主要归纳自文献【5 】，附录中图b 是模型框架图。 远程终端购物是一个比较新的概念，但己开始受到关注。现在很多目光都集 中在了因特网上，随着电子购物的增多，便形成了电子商务中的b 2 c 形式。 假设消费者以不同形式从事购物活动，他们可以买一件或多件产品；也可以 假设有虚拟的和物理的地点，虚拟地点可通过因特网或电信完成相关活动，物理 地点相应于与购物活动相关的商场等，它需要实际到达才能完成。 一旦在虚拟的或现实的地点进行了选择，消费者就会订购或购买产品或服务， 订购者的产品要被运送到其要求的地点，而直接购买者则需用交通工具把产品与 自己一同运到目的地。 把以上提到的问题转变成相应的网络元素便得到附录中图b 。其中一条路代表 了消费者的一系列可能选择，流反映了一个特别的类中实际上选择路和链的消费 者的数目。当然如果一个路上的流为0 则相当于没有消费者选择那个链列。在这 个应用中相关的决策标准可以是：时间、成本、机会成本、安全风险。相对于远 程终端应用，时间不能限制在出行时间上，它依赖于相关联的链，可能包括交易 基于变分不等式的网络广告超网络模型研究 时间；另外成本不能限制于出行成本，它也依赖于相关联的链，可包括交易成本、 产品价格、运送价格。 此模型的行为假设是：一个消费者选择与点对相关的路时要求总路代价最小。 在文献【6 ，7 1 中使用了一系列方法，可以得到对于不同选择的决策的数量和总的 成本，同时可以确定不同选择的相对人数。 3 供应链网络 现阶段对供应链网络的研究很多，这里只作一个简述。 由于不同的决策者如供应商、生产商、分销商、零售商之间关系复杂，而且 产品有效的流动在实际活动中非常重要， 非常有意义；供应链包含了生产、运输、 跨领域跨学科的；就供应链的应用来说， 因此通过网络模型分析计算供应链模型 零售与市场营销等，这样它本质上又是 电子商务的引人为其提供了新的机会。 供应链网络可以是多层的，如：第一层是原材料商，第二层是生产商，第三 层是零售商，第四层是消费者。决策者进行决策可以在给定层中独立进行，也可 以各个层间相互合作决策。 文献嘲应用超网络模型研究了电子商务供应链，预测了层之间的商品流和价 格，他们假设生产者和零售商的行为是追求最大利益而消费者是最小化与购买产 品有关的一切费用，这个模型可以确定产品的交易数量。 2 0 0 2 年文献【9 】中，为了确定产品运送流、金融流和信息流，给出了多水平的 供应链网络，其中加入金融网和物理运输网。物流网络会影响实际交通网络中的 流；而有支付形式的交易完成就会出现金融流：信息流则以需求、价格和数据流 的形式出现。 明显地，在供应链网络中，特别是全球供应链网络中，存在更多的风险与不 确定性。很多学者继续前人的研究，把风险和不确定性整合到供应链网络，建立 了很多不同的超网络模型，可以说它们的应用在目前的经济和政治情况下是极其 重要的。 研究超网络的主要方法是变分不等式。 变分原理是数学的一个重要分支，用它来解释数学、物理原理，既简单又优 美。把交通网络的平衡条件用变分不等式形式表达出来，便能够利用变分原理和 比较成熟的变分算法对问题进行有效的求解。这样，鉴于变分不等式在平衡问题 第1 章绪论 中的有用性，使得它很快地发展起来，并更广泛地应用于网络平衡问题，如：一 般经济情况下的市场垄断问题，金融网络平衡问题、一般的供应链平衡问题、多标 准的供应链平衡问题、动态系统的空间价格平衡问题、城市电力供应网络平衡问 题等。 网络广告起源于美国，作为一种新的营销手段已成为广告界的热点。从实质 上讲，网络广告的主要目的是建立品牌效应、传播信息和销售。它有广阔发展前 景，己渗透到商业、人们生活的各个方面。网络市场的多样性，可提供的多重选 择性，及有多种的可能决策使网络市场越来越复杂并具有竞争性。同时消费者的 点击和某种广告是否成功，不再是某单一广告努力的结果，而是各种网络媒介广 告努力集合的结果。这样就需要一个最优化决策的工具，来确定联系性很大的网 络市场的最优化广告资源分配策略。对于一个含有网络结构的复杂问题的模型化 和求解，网络最优模型及相关算法是一个强有力工具。 最早提出广告资源优化模型的是l a n 曲e i 】1 r i c h 等【1 0 l ，模型是以最大化广告点击 次数总和为目标的线性规划问题；随后，a b e 等】对网页属性进行了聚类分析，用 以减小模型规模；l a nz h a o 等在2 0 0 5 年的文献【1 2 1 中引入网络流模型，以最大化点 击量为目标探讨了网络广告资源优化配置问题。所有这些都是用点击量、点击率 来衡量广告效果的或者说为建模参数的，而随着广告应用的不断发展，点击率等 传统的效果评价指标已不能完全说明其效果，对网络广告效果的评价应由点击的 和未点击的两部分组成，即点击量和转化量，同时后者是不容忽视的。 本文在以上基础上，以超网络思想为出发点，引入点击量、转化量，显示概 率等，用变分不等算法，解决网络广告资源优化问题，并用实例验证其可行性。 一方面拓广了超网络理论的应用；另一方面对于网络广告资源分配问题，超 网变分不等式算法的引入能快且准的求解最优方案，以至于公司有效分配资金、 选择网站，同时网站拥有最大收益。及时将决策应用于各层系统，可极大程度的改 善业务决策，进而更加灵活的决策；也可以减少业务系统的运营成本，因此本文有 广泛的应用前景。 1 2 文章组织结构 本文是从基础理论知识着手，由浅入深，逐步对本课题进行探讨研究的，具 基于变分不等式的网络广告超网络模型研究 体内容组织如下： 第l 章主要介绍超网络、网络广告的背景、意义和文章结构，指出了研究本 课题的依据及现实有用性，并结合3 个常见的网络实例加以分析。 第2 章主要是超网络的理论基础，包括超网络、变分不等式和优化理论。 第3 章主要是网络广告介绍，包括网络广告的发展、网络广告特点、网络广 告主要形式、网络广告的付费模式以及网络广告发展前景和以后应当解决的主要 问题。 第4 章是对网络广告资源分配超网模型的研究，主要涉及网络广告资源分配 问题的所用变量的选取，网络模型的选择与建立及合理性分析论证，模型实例的 模拟分析和模型实际可用性研究。 第5 章结论与展望部分，详细总结本文内容，并探讨将来的研究动向。 第2 章超网络的基本理论 第2 章超网络的基本理论 自然界中大量的复杂系统可以通过形形色色的网络加以描述，作为研究工具 的网络理论技术的发展加深了人们对复杂系统本质的认识，另一方面也加强了人 们对系统运作的操控能力。 一个典型的网络是由许多节点与连接两个节点之间的一些边组成，其中节点 用来代表真实系统中不同的个体，而边则用来表示个体之间的关系，通常是当两 个节点之间具有某种特定的关系时连一条边，反之则不连边。 数学家和物理学家在考虑网络的时候，往往只关心节点之间有没有边相连， 至于节点到底在什么位置，边是长还是短，是弯曲还是平直，有没有相交等等都 是他们不在意的。在这里把网络不依赖于节点的具体位置和边的具体形态就能表 现出来的性质叫做网络的拓扑性质，相应的结构叫做网络的拓扑结构。 什么样的拓扑结构比较适用于描述真实的系统呢? 两百多年来，可以说对这 个问题的研究经历了：规则网络、随机网络、复杂网络、超网络四个阶段。 对超网络的研究刚开始，它是基于决策的形象化而又高于现存网络的网络系 统：它由一些点、链和相关流组成。特别是超网络与变分不等式理论的结合更使 得超网络模型框架的应用领域从数学、计算机科学、工程科学发展到了金融科学 甚至生物工程科学。超网络模型及工具己被商业、工业、政府大量利用。 2 1 超网络思想 超网络起源于对交通网络的研究。1 9 5 2 年w a r d r o p jg 在文献 1 3 1 中，1 9 7 2 年 d a f e r m o s s 在文献【1 4 l 中都涉及超网络思想；1 9 7 8 年s h e f f i 用h y p e r - n c t w o r k 来描述 交通规划问题 1 5 】，19 8 0 年s h e m 和d a g a n z o 正式在【6 1 中使用s u p e r - n e t w o r k 。 研究超网络的主要方法是变分不等式法，利用变分不等式研究各种超网络模 型的均衡问题，并可将交通网络均衡【1 7 1 的有关理论运用到其它多种网络模型当中。 利用变分不等式建模的优点在于，它提供了研究均衡问题的手段，从决策角度来 看，它实现了从独立决策到交互式决策的转变。这不仅在研究方法上进行了改进， 更从理论上进行了创新。 在现存的复杂的网络基础上，信息技术改变了个体的生活、工作等行为方式。 基于变分不等式的网络广告超网络模型研究 由于多种选择的存在，决策过程本身也发生了改变，例如决策者可以在家工作、 在工作时购物，像类似空间位置这种决策障碍已基本不存在了。的确，我们生活 在充满选择的时代：我们应在哪里生活? 哪里工作? 什么时候工作? 应该怎么出 行? 怎样交流? 和谁交流? 应在哪里购物? 怎样购物? 可以不夸张的说我们每个 人每天都面对着各种各样的选择。在科技发达的今天，商家们应怎样调整才能适 应信息技术的发展与需求? 什么样的供应链网络结构更有利于生产力的提高? 公 司什么时间和谁合作有利于其发展? 在新的网络经济中所做的决策对环境和它的 可持续发展的影响是什么? 以上这些问题都是超网络涉及到的研究课题。 超网络在范围上是概念性的、在视觉上是图形性的、在理论上具有本质的预 见性。超网框架可以用统一的形式表现不同实体如消费者与生产者所面对的不同 决策标准，可以通过区分不同的流来模型化个体决策者的行为及相互作用性。 2 2 超网络研究现状 交通网络、生产与物流网络、通讯网络、供应链网络是比较经典的网络，这 些网络中的点可以相对应于空间中的位置，链是点的连接。 基本的网络问题是：最短路，即一个决策者寻求从起点到终点的最有效的路； 最大流，在链的现实限制下决策者从一个起点发送最大的流量到终点的问题；最 小代价流，决策者在满足链限制、终点需求限制下最小化总代价。例如：交通运 输网络与通讯网络领域的最短路问题；工厂生产线和计算机网络的最大流问题； 从仓库存储、货物分发到运输规划涉及到最小代价问题。 从现在对不同领域的研究来看，应用网络模型这一方法确实能解决诸如金融、 知识生产与传播等很多复杂问题，因此网络模型比其它模型更具备的优势是： l 当今社会的物质、资金、信息等具有跨时空性，它们很多涉及到流问题，成 为网络理论的理想应用领域。 2 网络可以提供不同问题的图形视觉描述。 3 通过问题基本的网络结构可以容易鉴别不同问题的相似和不同之处。 4 可用有效的网络算法求解问题，例如车辆流、商品流、金融流、信息流等 问题。 如今网络现状特性是：网络的大标度性和拓扑的复杂性：拥塞性；网络用户 第2 章超网络的基本理论 行为的可选择性；网络之间错综复杂的相互作用。多选择性和复杂的相互作用性 这里不进行说明，详细介绍前两个特性。 本质的大标度性和复杂性：如今的网络都具有大标度性和复杂性，如芝加哥 本地交通网络有1 2 9 8 2 个点、3 9 0 1 8 个链、2 2 9 7 9 4 5 个o d 起始点对【1 8 】；南部加里 亚政府机构有3 2 1 7 个点对、2 5 4 2 8 个结点、9 9 2 4 0 个链、及6 个不同用户层【1 9 】； a t & t 公司国内网络有1 0 0 0 0 0 起点与终点点对，这里电话号码是节点，电话呼叫 是边，这样有3 0 亿结点和4 亿边【2 0 1 。 拥塞性：拥塞性不仅存在于交通运输网络中而且存在于在电子通讯等网络中， 如美国交通网，每年拥塞导致损失1 0 0 亿美元，欧洲估计有1 5 0 亿；对于因特网， 现有2 8 亿用户，日益增加的网络用户会产生新的瓶颈阻碍技术的进一步发展【2 1 1 。 2 3 变分不等式 变分不等式的英文为“v a r i m i o n a li n e q u a l i t y ”，也有人译为“变分不等方 程”。 变分不等式起源于对数学物理问题和非线性规划问题的研究，目前已在物理 力学、工程、经济等领域中得到广泛应用。 数学物理中最早的变分不等式出现于2 0 世纪6 0 年代初；特别是在1 9 6 4 年， 得到了变分不等式的第一个解的存在唯一性定理。其后，j l l i o n s 、h l e w y 、h b r e w s 等【2 2 1 人发表了一系列文章，为变分不等式理论奠定了初步的基础：2 0 世纪 7 0 年代，变分不等式在最优控制闯题、弹性问题、弹塑性问题及渗流问题等领域 中得到了成功的应用；2 0 世纪8 0 年代以来，作为现代偏微分方程理论重要部分的 变分不等式理论得到深入发展，至今已较为成熟。另一方面，2 0 世纪6 0 年代中期， 在非线性规划的研究中出现了线性和非线性互补问题，它们进一步发展成为有限 维空间中的变分不等式。2 0 世纪9 0 年代，m a t h p r o g r a m m i n g 杂志出版了非线性 互补问题与变分不等式的专辑，标志着变分不等式已成为非线性规划的一个重要 研究领域。 变分不等式起初主要用来解决动力学中的问题，后来鉴于变分不等式在平衡 问题中的有用性，使得它很快地发展起来，并广泛地应用于网络平衡问题。 通常所说的变分不等式理论的基本内容就是研究各种类型的变分不等式解的 基于变分不等式的网络广告超网络模型研究 存在性和唯一性条件，解( 或解集) 的性状及其逼近问题，以及各种问题的应用，因 此，变分不等式的基本问题之一就是解的存在性问题。 本部分关于变分不等式采用的是其标准形式即2 1 式，当然在不同实际应用中 还可以采用其它形式。关于交分不等式的解、性质及与最优化问题的关系的理论 的论证，已经有许多理论性的结果，我们此处不详尽说明。最大化优化问题可以 转化为最小化的问题来求解，相应的还有凸函数和凹函数间的转化问题，这里就 不再赘述。 先给出变分不等式的标准定义。 定义2 1 叫有限维的变分不等式问题，v i ( f ，幻，就是求解一个向量k 满 足： ( f ( x ) ，x f ) 0 ， k ， ( 2 1 ) 其中，k 是闭凸集，f ：k r “是连续函数，( ，) 表示定义在r 。上的内积。 下面给出变分不等式的一些性质。特别地，要讨论一下解的存在性与唯一性。 定理2 1 1 2 3 1 解存在定理 假设k c r “是紧凸集，又设f ：k 斗( r ”) 是连续函数，其中 ”) 是掣的对偶 空间，则变分不等式问题玎( f ，酌至少存在一个解。 如果k 是有界的，上面的定理给出变分不等式问题v ( f ，彪) 解的存在性，另 一方面，要注意变分不等式问题不一定总有解。 下面的定理给出了解存在的重要条件。 定理2 2 【2 3 1 给定凸集k ，令酶= k n r ，其中r 是半径为r ，中心在o e 的闭球，k c 且”是紧凸集，且，：k 一( r ) 7 是连续的，则( f ( x + ) ，x x ) o 有 解的充要条件是存在r o ，使( ，( x + ) ，z 一矿) o 的解满足l i o 飞x ，x 1 k ，x x 1q 因此弄清楚推论的条件及那些蕴涵唯一性的条件对无限维问题的存在性研究 是很有用的。给出一个定义： 定义2 2 口3 1 若对v 瓦，五k ，有( f ( 墨) 一f ( 五) ，五一x 2 ) - 0 ，则f ( x ) 是定 义在足上的单调函数。 定义2 3 吲喁，k ，有( f ( 五) 一f ( x 2 ) ，五一x 2 ) o ，则f ( x ) 是定义在 k 上的严格单调函数。 定义2 4 田1 若对a o ，五k ，有( f ( 五) 一f ( x 2 ) ，托一也) 口1 1 五一x 2 1 i ， 则f ( x ) 是定义在足上的强单调函数。 现在，我们讨论一下解的唯一性。 定理2 3 2 3 】解的唯一性定理f ( x ) ：k 哼( r ”) 是严格单调的，若有一个解 满足( f ( ) ，一x ) 0 ，则这个解是唯一的。 我们将讨论变分不等式算法解变分不等式，求变分不等式的最优值；而变分 不等式算法的效率主要是与循环迭代相关，迭代算法问题可用程序来计算完成， 这样可以达到较好的效果。而超网络问题就是在这些的基础上考虑的。 首先来看一下与算法有关的两个定义。 定义2 5 【2 3 】设f ( x ) ：k 专( r ”) ，若存在一个常数工 0 ，使得 0 f ( 蜀) 一f ( 五) 忙圳墨一恐8 ，v x , ，五e k ( 2 3 ) 则称f ( x ) 是l i p s c h i t z 连续的，上称为l i p s c h i t z 常数。 定义2 6 2 3 1 假设k 是定义在胄上的闭凸集，则对锻e r ”， y e k 满足 4 x - y l l - l l x - 4 ，觇k 其中，y 是x 在k 上的正交投影的欧几里得范数： 存在唯一的 ( 2 4 ) 基于变分不等式的网络广告超网络模型研究 y = p r x = a r g 鼍孥肛一z u ( 2 5 ) 投影算法可以很好地解决变分不等式问题，尤其是二次规划中的变分不等式 问题。一些交通网络平衡问题和超网络平衡问题的求解算法就是在这些基础上进 彳亍的。对于此文主要给出与本文算例相关的投影算法。 ( 1 ) 一般投影算法 对于变分不等式2 1 来说如果函数l i p s c h i t z 连续的且如2 1 l 强单调，求解步 骤为： 步0 ：选定初始可行解x o e k ，给定精度f ，且给定常数( 0 卢 2 瑾，r ) ， 令k ：o ； 步l ：x “1 = & 一妒( x 。) ) 其中( z 一p f ( x ) ) 为点z 一p f ( x ) 在k 上的投影； 步2 ：计算0 互+ 。一j 如果眵。一以0 s ，算法终止； 步3 ：如果f 阪。一以| | 占，则k 把换成k + l ，返回到l 。 此算法的完整证明过程参考文献 2 4 1 。 以上的投影方法的收敛性要求较强的假设，函数要l i p s e h i t z 连续的且强单调 在，这些限制了投影算法的应用；后来k - 0 r p e k 椭h 嘲创立了外梯度投影算法，它 的收敛仅需l i p s e h i t z 连续，但执行过程中要进行多次的投影计算从而增大了算法 的运算量；与上述方法不同，d h a r t 提出一个混合的推广近似点算法闭每一步迭 代只需要执行一次到可行集c 上的投影。在以上基础上，本文给出改进的具体的 投影算法，很大程度上其步长的选取、解的精确度、运算量都有较大的进步。 ( 2 ) 一种改进的投影算法口7 捌： 步0 ：取参数，旯( 0 ，1 ) ，= 【1 2 ，佃】，占为容许误差。任取一个初始 点z oe k ，令k ：= o 。 步1 ：选取段【1 1 2 ，翻和半正定矩阵瓯= ，( z ) ，求解下列关于z 的线性 方程组( 2 6 ) 得到试探点岩k 。 f ( x i ) + ( g k 4 - ir ，) ( r 一r 2 ) = 0 ( 2 6 ) 步2 ：求= 石+ t k ( x 一x ) ，t t = ”t 其中是使( 2 7 ) 式成立的最 小非负整数。 ( f ( p ) ，z 。一牙) 五以0 x 一牙1 1 2 步3 ： 计算x “1 = 只【z 一o ；k f ( y i ) ，其中步长 2 1 f ( y k , y (z 一) 而& 【z 一吼f ( y ) 】表示z 一a k f ( y ) 在k 上的投影。 步4 ：如果0 k 。一以0 o q k ，吩q w , j ( 2 2 0 ) 第3 章网络广告 第3 章网络广告 网络广告又被称作在线广告、互联网广告等，它主要是指利用电子计算机联 结而形成的信息通讯网络作为广告媒体，采用相关的电子多媒体技术设计制作， 并通过电脑网络传播的广告形式。 作为一种新兴的广告形式，网络广告最近几年获得了很快的发展，它已经成 为了西方广告业发达国家最热门的广告形式。网络广告是随着信息产业的发展而 兴起的，未来几年，网络广告必将占据更加重要的地位。 信息产业的发展极大地改变着人们生活的方方面面，其中广告业也受到了这 场革命浪潮的极大冲击。这种冲击是来自多方面的：一方面，新兴广告形式的出 现极大地改变了传统广告业的固有格局，越来越多的广告业者开始尝试利用新的 广告形式来进行广告业务；另一方面，传统广告业的转变也带来了新的机遇，一 些改变传统广告理念的做法获得了成功。在这场新旧广告大战之中，网络广告 ( n e t w o r ka d v e r t i s e m e n t ( n e t a d ) ) 成为最为关键的因素。 。 3 1 网络广告发展历程 传统的广告业从诞生到现在已经有一百多年的历史了。而实际上，网络广告 的历史却非常短，它是伴随着互联网的成熟而成长起来的。在它整个发展历程当 中，可以将其分为四个阶段： 发展初期：这是网络广告诞生之后经历的最初阶段。主要的网络广告提供商 是p r o d i g y 公司。他们作为网络广告的拓荒者，做了许多非常重要的工作。在早期 阶段，网络广告主要与在线销售结合起来，美国著名的电脑厂商c o m p u s e r v e 从 1 9 9 5 年开始就通过网络广告销售产品。而a o l 也在当年开始运作网络广告业务。 而更多的广告商在其发展初期只是采取了观望的态度，并没有大规模跟进。 挫折时期：由于发展初期的一些问题，网络广告缺乏有效的管理，出现了混 乱无章的局面。这对网络广告具有破坏作用，网络广告的声誉也一落干丈。互联 网上甚至掀起了反网络广告的运动，网络广告的发展遭遇了重大挫折。 认同时期：反对之后对广告开始重新支持，最早是连线( w i r e d ) 杂志推 出的h o t w - n ：e d t o m 。他们推出了新型网络广告工具h o t w i r e d ，这是第一种规范的 基于变分不等式的网络广告超网络模型研究 网络广告形式。1 9 9 4 年4 月，h o t w t r e d e o m 与a t & t 签订了第一份广告合同，而 1 0 月1 4 日，第一份网络广告在该站点发布。当天h o t w i r e d t o m 的首页上出现了 a t & t 等1 4 家客户的横幅广告。后来，在h o t w i r e d e o m 做网络广告的客户越来越 多，其中包括了宝洁、m m 等知名企业。于是，在其发展初期对网络广告持观望 态度的那些美国广告业者开始关注这片新兴的地带。 初步繁荣时期：随着网络经济的发展，尤其是电子商务和网上购物的成熟， 网络广告进入了初步繁荣时期。各个商业网站都推出了自己的广告服务，更多的 网站通过广告生存了下来。截至1 9 9 9 年上半年，全世界约有1 1 0 0 多家专门从事 网络广告业务的公司。2 0 0 0 年，美国网络广告年营业收入为约4 0 亿美元，2 0 0 2 年的收入是这个数字的两倍。 我国最早的网络广告是1 9 9 7 年3 月c h i n a b y t e 推出的一幅横幅广告。此后一 段时间，我国的广告商也认识到了网络广告的明朗前景，于是网络广告也逐渐在 我国的网站中出现。特别是2 0 0 2 、2 0 0 3 、2 0 0 4 这几年我国多个主要网站的广告收 入不断创造新高，广告费用成了网络公司的经济支撑主体，增长速度远远高于传 统媒体口”。种种迹象表明，网络广告市场庞大，发展态势强劲。 目前我国网络广告的客户也开始趋向多元化，汽车、房地产、医药、日用消费 品进入网络广告领域，这也标志着我国网络广告逐渐成熟起来。 网络广告的飞速发展，我们可以总结出以下原因： l 网络作为媒体自身的发展。目前网络已经被联合国教科文组织正是确立为 “第四媒体”，其发展的态势异常迅猛。作为网络广告的载体，网络的发展也带动了 网络广告的进步。 2 网络媒体的商业化和网络经济的发展。全球商业化环境为网络广告的进步创 造了条件。而且以电子商务为代表的网络经济的进一步升温，改变了传统的商业 模式，迫使厂商在互联网上采取新的营销方式，这也为网络广告发展创造了条件。 3 传统广告产业的持续发展。这是网络广告发展的大背景。随着经济和社会的 进一步发展，广告产业也获得了前所未有的机遇。网络广告从传统广告产业当中 吸取了养分，同样促进了自身的发展。 4 网络广告对比传统广告所体现出来的优势。网络广告比起传统广告而言，具 有传播范围更广、成本更低、较少受时空限制、形式多样、具有交互性等优势， 第3 章网络广告 这也大大推动了网络广告的发展。 3 2 网络广告特点与形式 实质上网络广告是计算机、通信等多种网络技术和多媒体技术的合成形式。 网络广告的传播内容是通过数字技术进行艺术加工和处理的信息，社会广告活动 主体通过互联网传播广告信息，从而使人们对产品、服务或观念等得以认同和接 受，以达到推销其产品、服务和观念的目的。 网络广告主要特点在于以下几个方面：