Theory and algorithms for solving bilevel optimization and other important nonsmooth and/or nonconvex optimization problems

解决双层优化和其他重要的非光滑和/或非凸优化问题的理论和算法

• 批准号: RGPIN-2018-03709
• 负责人: Ye, Jane
• 金额: $ 3.13万
• 依托单位: University of Victoria
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=712005
• 关键词: Theory; algorithms; solving; bilevel; optimization

My program of research focuses on studying theories and algorithms for solving some very important problems arising in Economics, Engineering, Operations Research and Management Science. (1) The bilevel program is a sequence of two optimization problems, where the constraint region of the upper level problem is determined implicitly by the solution set to the lower level problem. Recently, the bilevel programming methodology has been applied to more and more areas. I plan to study optimality conditions with weaker and verifiable constraint qualifications, and plan to design efficient algorithms for solving them. In particular, I will focus on certain bilevel programs with some structures. (2) The principal-agent problem is a fundamental problem that frequently occurs in economics, management science and political science. It can be viewed as a bilevel program involving uncertainty. The principal-agent problem treats the difficulties that arise under conditions of incomplete and asymmetric information when a principal hires an agent to pursue the principal's interests, but the agent's actions are unobservable to the principal. It focuses on designing an incentive scheme with which the principal seeks to motivate the agent to choose activities in a manner advantageous to the principal. I will try to develop necessary and sufficient optimality conditions specially designed for such problems using assumptions which are reasonable in Economics. I will also try to find efficient numerical algorithms for solving the principal-agent problem. (3) The Stackelberg differential game model is a bilevel problem where both levels are optimal control problems. In recent years, it has been used to model the applications in management science such as the supply chain and marketing channels management in order to model conflicts and coordination issues. For such a problem, I will try to derive optimality conditions and design efficient algorithms. (4) In recent years, optimization with sparsity-inducing penalties has received increasing attention in various application areas. To cope with the rapidly growing size of datasets, recent research has been focusing on first-order methods for solving these problems. In particular, it has been recognized that a non-convex or even non-Lipschitz penalty induces sparser solutions than convex counterparts. Using recent developments in variational analysis, I will try to derive verifiable sufficient conditions for error bounds for the first order necessary optimality system for such a nonsmooth and nonconvex problem. Such a condition is key to the successful study of the convergence and/or the convergence rate of various first order methods for solving these problems. I believe that my research will significantly advance our knowledge of the four proposed problems, and that the success of my research will benefit Canada and impact the world at large.

我的研究计划侧重于研究理论和算法，以解决经济学，工程学，运筹学和管理科学中出现的一些非常重要的问题。 (1)双层规划是由两个优化问题组成的序列，其中上层问题的约束区域由下层问题的解集隐式确定。近年来，双层规划方法在越来越多的领域得到了应用。我计划研究具有较弱和可验证的约束资格的最优性条件，并计划设计有效的算法来解决它们。特别是，我将集中在某些双层程序与一些结构。 (2)委托代理问题是经济学、管理学和政治学中经常出现的一个基本问题。它可以被看作是一个包含不确定性的双层规划。委托代理问题是指在信息不完全和不对称的条件下，委托人雇用代理人来追求委托人的利益，但代理人的行为对委托人来说是不可观察的。它侧重于设计一个激励机制，委托人试图激励代理人选择有利于委托人的活动。我将尝试开发必要的和充分的最优性条件，专门为这些问题设计，使用经济学中合理的假设。我也将试图找到有效的数值算法来解决委托代理问题。 (3)Stackelberg微分对策模型是一个两层问题，其中两层都是最优控制问题。近年来，它已被用来模拟管理科学中的应用，如供应链和营销渠道管理，以模拟冲突和协调问题。对于这样的问题，我将尝试推导最优性条件并设计有效的算法。 (4)近年来，具有稀疏诱导惩罚的优化在各个应用领域受到越来越多的关注。为了科普快速增长的数据集规模，最近的研究一直集中在解决这些问题的一阶方法。特别地，已经认识到，非凸的或甚至非Lipschitz罚比凸的对应物诱导更稀疏的解。利用变分分析的最新发展，我将试图推导出一阶必要的最优性系统，这样一个非光滑和非凸问题的误差界可验证的充分条件。这样的条件是关键的成功研究的收敛性和/或收敛速度的各种一阶方法来解决这些问题。 我相信我的研究将大大提高我们对这四个问题的认识，我的研究的成功将使加拿大受益，并影响整个世界。