Topics in Parametric Optimization

参数化问题是那些输入连续依赖于一个或多个值的问题。该奖项支持两个基本领域的非参数优化工作。第一种是定维优化，特别强调目标函数可以在任意点通过性能良好的算法有效地求值的问题。例如，在拉格朗日弛豫中就出现了这类问题。在Megiddo的参数搜索方法的背景下，主要问题是确定评估与全局优化一样容易的条件。第二个要研究的领域是参数空间分解的构造，对所有参数值产生最优解。一个问题是得到分解的区域数目的界限。这将在一个框架内进行部分研究，该框架捕捉了稳定婚姻和进化树结构等各种问题的本质。另一个问题是，是否可以通过利用相邻区域之间的结构相似性来加速分解的构建。

TITLE: Topics in Parametric OptimizationID: 9988348PI: David Fernandez-BacaABSTRACT Parametric problems are those whose input depends continuously on one ormore values. This award supports work in two fundamental areas inparametric optimization. The first is fixed-dimensional optimization,with special emphasis on problems whose objective function can beefficiently evaluated at any point by a well-behaved algorithm. Problemsof this sort arise, for example, in Lagrangian relaxation. The mainquestion is to determine the conditions under which evaluation is as easyas global optimization, within the context of Megiddo's method ofparametric search. The second area to be investigated is the constructionof parameter space decompositions yielding optimal solutions for allparameter values. One issue is obtaining bounds on the number of regionsof the decomposition. This will be studied in part within a frameworkthat captures the essence of problems as diverse as stable marriage andevolutionary tree construction. Another question is whether one canaccelerate the construction of the decomposition by exploiting structuralsimilarities between adjacent regions.