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

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

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.