Multilevel Methods for Large-Scale Nonlinear Optimization

大规模非线性优化问题的求解是科学计算的核心。结构占据最小约束势能的位置，投资者的目标是在控制风险的同时实现利润最大化，公用事业运行输电网络以满足最低成本的需求，制药公司希望以最小的药物剂量靶向病原体。所有这些问题都很大，要么是因为数学模型涉及许多参数，要么是因为它们实际上是一些连续问题的有限离散，其中变量是函数。本研究的目的是支持非线性优化新算法的设计，分析和开发，特别是针对大规模情况，特别是那些涉及（常或偏）微分方程离散化产生的约束。不同程度的离散导致不同的，但相关的，原始问题的描述-精细离散导致精确的近似，这可能是昂贵的解决，而粗离散可能不太准确，更便宜的解决。多层次方法在不同的离散之间移动，从粗糙的解中提炼解，以便为更精细的解提供良好的开始猜测。这通常会导致一个非常有效的解决方法。虽然这种方法在多级离散可用时是合适的，但在许多问题中并非如此。在我们的研究中，我们的目标是通过使用代数方法递归地识别隐藏的多层次或显性结构来解决这一困难。最终，我们的目标是自动检测这种结构，以便对通用约束优化软件的用户透明。

The solution of large-scale nonlinear optimization - -minimization ormaximization - problems lies at the heart of scientificcomputation. Structures take up positions of minimal constrainedpotential energy, investors aim to maximize profit while controllingrisk, public utilities run transmission networks to satisfy demand atleast cost, and pharmaceutical companies desire minimal drug doses totarget pathogens. All of these problems are large either because themathematical model involves many parameters or because they are actuallyfinite discretisations of some continuous problem for which thevariables are functions.The purpose of this research is to support the design, analysis anddevelopment of new algorithms for nonlinear optimization that areparticularly aimed at the large-scale case, and most especially thoseinvolving constraints arising from the discretisation of (ordinary orpartial) differential equations. Different levels of discretisationlead to different, but related, descriptions of the original problem - afine discretisation leads to an accurate approximation which may beexpensive to solve, while a coarse discretisation may be less accurateby cheaper to solve. Multi-level methods move between differentdiscretisations, refining solutions from the coarse ones so that theyprovide good starting guesses for solutions on the finer ones. This then often leads to a very effective solution method.While such methods are appropriate when multilevel discretisations areavailable, in many problems this is not the case. In our research, weaim to address this difficulty by using algebraic methods recursively toidentify hidden multi-level or dominant structures. Ultimately, ouraim is to automate the detection of such structure so that this istransparent to the users of general-purpose constrained-optimizationsoftware.