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.