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
- DOI:
10.1002/9781118032701 - 发表时间:
1997-08 - 期刊:
- 影响因子:3.6
- 作者:
Yinyu Ye - 通讯作者:
Yinyu Ye
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)}}的其他基金
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