在线分配问题的核心是：在量的某种类型的限制下，完成对质的优化。

因为有量的限制，它是一个constrained optimization（受限优化）的问题，最早google提出的是AdWords Problem。

目标函数，是把一次展示（）分给一个(Ad, a）产生的收益（bid * ctr, b，即eCPM），是指一次展示（）是否分给了一个广告（Ad, a），这个值只能为0或是1，因为一次展示只能或是分配给一个广告，或是没分配。sum(i, a)也就是整个系统的收益，max sum(i,a)即是优化的核心问题：如何最大化整个系统的收益。它的限制是：对每个广告商来讲，有一个budget，每个广告商所消耗的资金应该小于他的budget，即式中。

后来研究者把这个问题推广到display problem，display problem中有很多CPM的campaign，它希望优化的是每一个CPM的效果。

效果即是它收获到的点击量，点击量的计算方法为把所有的展示的乘上点击率起来就是点击量。优化目标有两个constrain，一个是称之为Demand Constrain，它是指每一个广告商来讲，他需要次展示，那么媒体提供的展示数应该小于等于，注意这里是NGD的问题，广告系统提供的展示次数可以小于需求的量，另一个Constrain是Supply Constrain，是对于任何展示，加起来小于等于1，可以小于是因为这次广告也可以不分配给任何广告，它可以交给下游的其它变现手段。

使用拉格朗日对偶解决这个问题。