Nonlinear Optimization: Algorithms, Software, Applications

非线性优化：算法、软件、应用

• 批准号: 0430504
• 负责人: Stephen Wright
• 金额: $ 25万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-12-15 至 2009-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0430504&HistoricalAwards=false
• 关键词: Nonlinear; Optimization; Algorithms; Software; Applications

Nonlinear programming (the minimization of a smooth nonlinear function subject to smooth(possibly) nonlinear constraints) is a touchstone problem in optimization. The problem continuesto excite strong interest among optimization researchers for many reasons, among them newdevelopments in algorithms and software (especially of the interior-point variety), the study ofmathematical programs with equilibrium constraints (MPEC), and the discovery of new applicationareas.The broad scope of the nonlinear programming paradigm admits a great many pathologies inthe geometric nature of the problem and in its algebraic speci.cation. It is impossible to designalgorithms that converge reliably in all circumstances. Local convergence theory for most algorithmsdepends on regularity and strict complementarity assumptions, and problems for whichthese assumptions are not satis.ed (degenerate problems) are the cause of undesirable and awkwardbehavior in most algorithms and codes.This project will investigate some approaches to nonlinear programming, related to approachescurrently in use, that have the potential for improved performance on degenerate and large-scaleproblems. These techniques will be theoretically rigorous and practical, in that the marginalcomputational cost of handling degeneracy will not be too great and in that they will behave welleven when implemented in .oating-point arithmetic. Particular attention will be given to MPECs,which exhibit degeneracy of a speci.c type. Extensions to degenerate complementary problemsand variational inequalities will also be investigated. Special attention will be paid to the numericalaspects of implementing these algorithms, an important issue because of the ill conditioning thatmay be present in the subproblems at each iteration. All this research will be carried out in acoordinated manner, coupling theoretical advances with computational experiments using bothprototype software and modi.cations to production software.Work on applications of nonlinear programming, performed in collaboration with domain scientistsand engineers, will be the second key contribution of the proposal. Interdisciplinary research ofthis type plays a key role in any research program in algorithmic optimization. The PI has ongoingcollaborations in such areas as engineering control, statistics, and cancer treatment planning.The intellectual merit of the proposed work lies in improvements to our understanding ofnonlinear programs and of the algorithms that solve these problems, in the construction of betteralgorithms and software that are robust in the face of degeneracy, and in the impact of theseadvances on many application areas including those described in the proposal.The work will have a wider impact on users of optimization technology, ultimately bene.tingmany of those who use optimization software packages to solve problems in an extremely widerange of applications. Domain scientists and engineers in the areas highlighted in the proposal willbene.t especially.

非线性规划（在光滑（可能）非线性约束下最小化光滑非线性函数）是优化中的试金石问题。这个问题继续激发强烈的兴趣之间的优化研究人员有很多原因，其中包括新的发展，在算法和软件（特别是边界点品种），研究数学规划与平衡约束（MPEC），并发现新的应用areas.The广泛的范围内的非线性规划范式承认了很多病理学的几何性质的问题，并在其代数specification.cation。设计出在所有情况下都能可靠收敛的算法是不可能的。大多数算法的局部收敛理论依赖于正则性和严格互补性假设，而这些假设并不萨蒂斯的问题。艾德（退化问题）是大多数算法和代码中不希望的和笨拙的行为的原因。本项目将研究一些非线性规划的方法，这些方法与目前使用的方法有关，具有改进退化和大规模问题性能的潜力。这些技术在理论上是严格和实用的，因为处理简并的边际计算成本不会太大，而且在浮点运算中实现时，它们会表现得很好。特别注意的是，将给予MPEC，表现出退化的一个speci.c类型。退化互补问题和变分不等式的扩展也将被调查。特别注意将支付给numericalaspects实现这些算法，一个重要的问题，因为病态，可能会出现在子问题在每次迭代。所有这些研究都将以协调的方式进行，将理论进步与使用原型软件和生产软件的修改的计算实验相结合。与领域科学家和工程师合作进行的非线性规划应用工作将是该提案的第二个关键贡献。这种类型的跨学科研究在算法优化的任何研究计划中起着关键作用。PI在工程控制、统计学和癌症治疗计划等领域有着持续的合作。拟议工作的智力价值在于改善我们对非线性程序和解决这些问题的算法的理解，构建更好的算法和软件，这些算法和软件在面对退化时是鲁棒的，以及这些进步对许多应用领域的影响，包括提案中所描述的那些领域。这项工作将对优化技术的用户产生更广泛的影响，最终使许多使用优化软件包解决极其广泛的应用问题的人受益。提案中强调的领域的科学家和工程师将特别受益。