Topics in Parametric Optimization

标题：参数优化中的主题ID：9988348PI：David Fernandez-BacaABSTRACT参数问题是指其输入连续依赖于一个或多个值的主题。该奖项支持在参数优化的两个基本领域的工作。第一种是定维优化，特别强调目标函数可以通过良好的算法在任何点有效地计算的问题。例如，这类问题出现在拉格朗日松弛中。主要问题是在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.