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.