ROW: Algorithms in Polynomial Time for Convex Optimization

ROW：多项式时间凸优化算法

• 批准号: 8709795
• 负责人: Ariela Sofer
• 金额: $ 20.69万
• 依托单位: George Mason University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1988
• 资助国家: 美国
• 起止时间: 1988-04-01 至 1992-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8709795&HistoricalAwards=false
• 关键词: ROW; Algorithms; Polynomial; Time; Convex

The proposed research is to establish a class of polynomially bounded algorithms for solving convex programming problems efficiently. The work is to focus on classical barrier methods, such as the Sequential Unconstrained Minimization Technique (SUMT) and it's variants. Specifically, " Projective SUMT " is one such variant that is derived from the barrier function method by utilizing the differential equation characterizing the trajectory of unconstrained minimizers. The assumptions for convergence of these barrier-type methods are considerably weaker than those proposed by Karmarkar. The concept of factorable functions wil be used in the analysis of running time. Representation of a function as factorable enables the automatic calculation of higher order derivatives, and can be useful for encoding the data and function calculations. The running time also depends upon the time required to solve a system of equations with respect to the Hessian of the suitable factorable barrier function, the solution of an approximate step-size problem, and the number of iterations required to find the solution to prescribed accuracy. These issues will be explored in the research.

提出的研究是建立一类多项式有界的 算法有效地解决凸规划问题。 的 工作的重点是经典的障碍方法，如顺序 无约束最小化技术（SUMT）及其变体。 具体地，“投影SUMT“是一个这样的变体，其被导出为： 从障碍函数法，利用微分 描述无约束极小化器轨迹的方程。 这些障碍型方法收敛的假设是 比Karmarkar提出的要弱。 可因式分解函数的概念将用于分析 运行时间。 将函数表示为可因式分解的， 自动计算高阶导数，可以是有用的 用于编码数据和函数计算。 运行时间 也取决于求解方程组所需的时间 关于合适的可因式分解障碍的Hessian 函数，近似步长问题的解决方案，以及 找到规定的解决方案所需的迭代次数 精度 这些问题将在研究中进行探讨。