Penalized and Constrained Optimization: An Application to High-Dimensional Website Advertising

Firms are increasingly transitioning advertising budgets to Internet display campaigns, but this transition poses new challenges. These campaigns use numerous potential metrics for success (e.g., reach or click rate), and because each website represents a separate advertising opportunity, this is also an inherently high-dimensional problem. Further, advertisers often have constraints they wish to place on their campaign, such as targeting specific sub-populations or websites. These challenges require a method flexible enough to accommodate thousands of websites, as well as numerous metrics and campaign constraints. Motivated by this application, we consider the general constrained high-dimensional problem, where the parameters satisfy linear constraints. We develop the Penalized and Constrained optimization method (PaC) to compute the solution path for high-dimensional, linearly constrained criteria. PaC is extremely general; in addition to internet advertising, we show it encompasses many other potential applications, such as portfolio estimation, monotone curve estimation, and the generalized lasso. Computing the PaC coefficient path poses technical challenges, but we develop an efficient algorithm over a grid of tuning parameters. Through extensive simulations, we show PaC performs well. Finally, we apply PaC to a proprietary dataset in an exemplar Internet advertising case study and demonstrate its superiority over existing methods in this practical setting. Supplementary materials for this article, including a standardized description of the materials available for reproducing the work, are available as an online supplement.企业正日益将广告预算转向互联网展示广告投放，但这一转型也带来了全新挑战。这类投放活动采用诸多潜在的成功衡量指标（例如触达率或点击率），且由于每个网站均为独立的广告投放机会，该问题本质上属于高维优化场景。此外，广告主通常会为投放活动设置各类约束条件，例如定向特定细分人群或特定网站。此类挑战亟需一种足够灵活的方法，以适配数千个网站、海量衡量指标以及广告投放约束。受此应用场景启发，我们研究了一类通用的带约束高维优化问题，其中模型参数满足线性约束。我们提出了带惩罚与约束优化方法（Penalized and Constrained optimization，PaC），用于求解高维线性约束准则下的解路径。PaC具有极强的通用性：除互联网广告场景外，我们证明其可覆盖诸多其他潜在应用，例如投资组合估计、单调曲线估计以及广义Lasso（generalized lasso）。求解PaC的系数路径存在技术难点，但我们在调参参数网格上开发了一种高效算法。通过大量仿真实验，我们验证了PaC的优异性能。最后，我们将PaC应用于一个典型互联网广告案例研究中的专有数据集，并证明了该方法在实际场景中相较于现有方法的优越性。本文的补充材料（包括可复现研究的标准化材料说明）可作为在线补充材料获取。