Interior-point Algorithms - Complexity Issues and Practical Concerns

内点算法 - 复杂性问题和实际问题

基本信息

  • 批准号:
    9207347
  • 负责人:
  • 金额:
    $ 14.86万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    1992
  • 资助国家:
    美国
  • 起止时间:
    1992-09-01 至 1996-08-31
  • 项目状态:
    已结题

项目摘要

The goal of this project is to develop and analyze interior- point algorithms for solving large-scale linear programs (LP), quadratic programs (QP), linear complementarity problems (LCP). This research is a continuation of previous work and is motivated by the desire to resolve several theoretical and practical issues concerning interior-point algorithms: (1) Algorithm Termination: to develop efficient termination techniques to "purify" an approximate optimal solution to an (exact) optimal solution, and to improve the complexity result for a class of optimization problems. (2) Average Complexity: to analyze the complexity of interior-point algorithms for solving random problems, and to probabilisticly explain the excellent practical behavior of interior-point algorithms. (3) Asymptotic Convergence: to develop and analyze superlinearly convergent interior-point algorithms, and to improve the algorithms' global and asymptotic complexity results. (4) Decomposition and Column Generation: to develop various decomposition and column generation schemes for solving large-scale practical problems using interior-point algorithms. This project will strengthen some of the results from prior NSF research and explore new techniques and tools for analyzing and improving interior-point algorithms. It will also include developing computer routines for solving application problems arisen in production scheduling and resource allocation.
该项目的目标是开发和分析内部- 求解大规模线性规划(LP)的点算法, 二次规划(QP),线性互补问题(LCP)。 本研究是前人工作的延续, 通过解决几个理论和实践问题的愿望, 关于边界点算法:(1)算法终止: 开发有效的终止技术来“纯化” 近似最优解到(精确)最优解,以及 为了改善一类优化问题的复杂性结果, 问题 (2)平均复杂度:分析 解决随机问题的邻域点算法, 很可能解释了 邻域点算法(3)渐近收敛:发展 分析超线性收敛的邻域点算法, 提高算法的全局和渐近复杂度 结果 (4)分解和列生成:开发 用于求解的各种分解和列生成方案 大规模的实际问题,使用邻域点算法。 该项目将加强先前NSF的一些结果 研究和探索新的技术和工具, 改进邻近点算法。 它还将包括 开发解决应用问题的计算机程序 在生产调度和资源分配中出现。

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Yinyu Ye其他文献

Linear operators and positive semidefiniteness of symmetric tensor spaces
对称张量空间的线性算子和半正定性
  • DOI:
    10.1007/s11425-014-4930-z
  • 发表时间:
    2015
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Ziyan Luo;Liqun Qi;Yinyu Ye
  • 通讯作者:
    Yinyu Ye
Extended ADMM and BCD for nonseparable convex minimization models with quadratic coupling terms: convergence analysis and insights
  • DOI:
    DOI 10.1007/s10107-017-1205-9
  • 发表时间:
  • 期刊:
  • 影响因子:
  • 作者:
    Caihua Chen;Min Li;Xin Li;Yinyu Ye
  • 通讯作者:
    Yinyu Ye
Scalable Approximate Optimal Diagonal Preconditioning
可扩展的近似最佳对角线预处理
  • DOI:
  • 发表时间:
    2023
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Wenzhi Gao;Zhaonan Qu;Madeleine Udell;Yinyu Ye
  • 通讯作者:
    Yinyu Ye
Interior point algorithms: theory and analysis
Identifying an optimal basis in linear programming
  • DOI:
    10.1007/bf02206830
  • 发表时间:
    1996-12-01
  • 期刊:
  • 影响因子:
    4.500
  • 作者:
    Stephen A. Vavasis;Yinyu Ye
  • 通讯作者:
    Yinyu Ye

Yinyu Ye的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Yinyu Ye', 18)}}的其他基金

GOALI: Region Partitioning
目标:区域划分
  • 批准号:
    0800151
  • 财政年份:
    2008
  • 资助金额:
    $ 14.86万
  • 项目类别:
    Standard Grant
Exchange Market Equilibrium and Auction Pricing
交易市场均衡与拍卖定价
  • 批准号:
    0604513
  • 财政年份:
    2006
  • 资助金额:
    $ 14.86万
  • 项目类别:
    Standard Grant
Markov Decision Problem and Linear Programming
马尔可夫决策问题和线性规划
  • 批准号:
    0306611
  • 财政年份:
    2003
  • 资助金额:
    $ 14.86万
  • 项目类别:
    Standard Grant
Semidefinite Programming and Approximation Algorithms
半定规划和近似算法
  • 批准号:
    0231600
  • 财政年份:
    2002
  • 资助金额:
    $ 14.86万
  • 项目类别:
    Continuing Grant
Semidefinite Programming and Approximation Algorithms
半定规划和近似算法
  • 批准号:
    9908077
  • 财政年份:
    1999
  • 资助金额:
    $ 14.86万
  • 项目类别:
    Continuing Grant
Linear Programming: Condition, Knowledge & Complexity
线性规划:条件、知识
  • 批准号:
    9703490
  • 财政年份:
    1997
  • 资助金额:
    $ 14.86万
  • 项目类别:
    Standard Grant
Interior-Point Algorithms: Theories and Applications
内点算法:理论与应用
  • 批准号:
    9522507
  • 财政年份:
    1995
  • 资助金额:
    $ 14.86万
  • 项目类别:
    Standard Grant
A Potential Reduction Algorithm Allowing Column Generation
允许生成列的潜在减少算法
  • 批准号:
    8922636
  • 财政年份:
    1990
  • 资助金额:
    $ 14.86万
  • 项目类别:
    Continuing Grant

相似国自然基金

单片三维相变存储器高速高可靠读取技术研究
  • 批准号:
    61904186
  • 批准年份:
    2019
  • 资助金额:
    26.0 万元
  • 项目类别:
    青年科学基金项目
解大型非对称鞍点(Saddle Point) 问题的有效算法的研究
  • 批准号:
    60573157
  • 批准年份:
    2005
  • 资助金额:
    20.0 万元
  • 项目类别:
    面上项目

相似海外基金

Interior-point algorithms for conic optimization with sparse matrix cone constraints
具有稀疏矩阵圆锥约束的圆锥优化的内点算法
  • 批准号:
    1115963
  • 财政年份:
    2011
  • 资助金额:
    $ 14.86万
  • 项目类别:
    Standard Grant
Interior point algorithms and applications
内点算法及应用
  • 批准号:
    227650-2004
  • 财政年份:
    2008
  • 资助金额:
    $ 14.86万
  • 项目类别:
    Discovery Grants Program - Individual
Interior point algorithms and applications
内点算法及应用
  • 批准号:
    227650-2004
  • 财政年份:
    2007
  • 资助金额:
    $ 14.86万
  • 项目类别:
    Discovery Grants Program - Individual
Interior point algorithms and applications
内点算法及应用
  • 批准号:
    227650-2004
  • 财政年份:
    2006
  • 资助金额:
    $ 14.86万
  • 项目类别:
    Discovery Grants Program - Individual
Development of numerically stable primal-dual interior point algorithms for solving nonlinear semidefinite programming problems
开发数值稳定的原对偶内点算法来解决非线性半定规划问题
  • 批准号:
    18560052
  • 财政年份:
    2006
  • 资助金额:
    $ 14.86万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Interior point algorithms and applications
内点算法及应用
  • 批准号:
    227650-2004
  • 财政年份:
    2005
  • 资助金额:
    $ 14.86万
  • 项目类别:
    Discovery Grants Program - Individual
Interior point algorithms and applications
内点算法及应用
  • 批准号:
    227650-2004
  • 财政年份:
    2004
  • 资助金额:
    $ 14.86万
  • 项目类别:
    Discovery Grants Program - Individual
A study on interior-point algorithms and robust optimization for Ill-conditioned optimization problems
病态优化问题的内点算法和鲁棒优化研究
  • 批准号:
    15510144
  • 财政年份:
    2003
  • 资助金额:
    $ 14.86万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Geometric aspects of interior-point algorithms of optimization
优化内点算法的几何方面
  • 批准号:
    0102628
  • 财政年份:
    2001
  • 资助金额:
    $ 14.86万
  • 项目类别:
    Standard Grant
Interior-Point Algorithms: Theories and Applications
内点算法:理论与应用
  • 批准号:
    9522507
  • 财政年份:
    1995
  • 资助金额:
    $ 14.86万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了