Polyhedral Techniques for Fast Sparse Nonlinear Optimization and their Application to Nonsmooth Optimal Control

新的计算算法被开发用于解决稀疏优化问题。这些都是科学、工程和工业中出现的大型复杂问题，其目标是以有效的方式操作大型互连系统。 应用范围从电网到空中交通管制系统，再到计算机芯片的制造。该项目的一个目标领域是最佳控制，这是一种用途广泛的技术，包括太空飞行机动、空气动力学形状的最佳设计、制造过程的最佳设计和生物技术;例如，制定有效的疫苗接种和疾病治疗计划。优化算法的目标是稀疏的问题，经常出现时，不断演变的动态过程中的时间，如机器人的手臂的运动，被取代的离散运动，是计算上容易处理的。 算法比以前更快，并实现更高的准确性。这项研究通过培训具有性别和种族多样性的学生，对人力资源的开发产生了影响。为了最大限度地发挥研究的影响力，将开发高质量的软件并广泛提供，将基于一种新的多面体约束问题的快速鲁棒精确求解器开发一种新的框架来解决大规模稀疏约束非线性优化问题。同时，新的优化框架的发展，它将被用于一个新的方法来解决最优控制问题的基础上hp-正交配置。 优化研究将集中在扩展技术解决多面体约束优化问题的处理一般的非线性约束。求解器将只需要一阶信息，并将围绕一个新的紧界的错误，在一个解决方案的优化问题的违反一阶最优性条件。 在整个求解过程中，将利用约束的稀疏性。 求解器的第一阶段寻求识别活动约束，而第二阶段则使用基于梯度的方法（如共轭梯度法）寻求超线性收敛。 两个相位之间的切换由误差估计器控制。 新的优化框架将用于继续发展的hp-正交配置技术解决最优控制问题。 特别是，快速和准确的优化方案是有用的HP技术，因为更好的估计误差的离散近似的控制问题产生一个更好的选择的网格，和一个更快的解决方案的控制问题。与网格细化技术相反，网格放置技术将用于进一步改进网格。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

New computational algorithms are developed for solving sparse optimization problems. These are large, complex problems that arise in science, engineering, and industry where the goal is to operate a large interconnected system in an efficient way. Applications range from power grids to air traffic control systems to the fabrication of computer chips. A target area in the project is optimal control, a technology which has a wide array of uses that include space flight maneuvers, the optimal design of aerodynamic shapes, the optimal design of manufacturing processes, and biotechnology; for example, the development of effective vaccination and treatment plans for a disease. The optimization algorithms are targeted to sparse problems which often arise when a dynamic process which evolves continuously in time, such as the motion of a robot's arm, is replaced by discrete movements that are computationally tractable. The algorithms are faster and achieve greater accuracy than was previously possible. The research has impact on the development of human resources through the training of students with both gender and ethnic diversity. To maximize the impact of the research, high-quality software will be developed and made widely available.A new framework will be developed for solving large-scale sparse constrained nonlinear optimization problems based on a new fast robust accurate solver for polyhedral constrained problems. At the same time that the new optimization framework is developed, it will be used in a new approach for solving optimal control problems based on hp-orthogonal collocation. The optimization research will focus on the extension of techniques for solving polyhedral constrained optimization problems to the treatment of general nonlinear constraints. The solver will require only first-order information and will be built around a new tight bound for the error in a solution to an optimization problem in terms of the violation in the first-order optimality conditions. Sparsity in the constraints will be exploited throughout the solution process. Phase one of the solver seeks to identify active constraints, while phase two strives for superlinear convergence using a gradient-based method such as the conjugate gradient method. The switch between the two phases is controlled by the error estimator. The new optimization framework will be used to continue the development of hp-orthogonal collocation techniques for solving optimal control problems. In particular, the fast and accurate optimization scheme is instrumental in the hp-techniques since better estimates for the error in the discrete approximation to the control problem yield a better choice for the mesh, and a much faster solution of the control problem. Mesh placement techniques, as opposed to mesh refinement techniques, will be used to further improve the mesh.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.