Method of moving asymptotes

Last updated December 14, 2023

The Method of Moving Asymptotes (MMA) is an optimization algorithm developed by Krister Svanberg in the 1980s. It's primarily used for solving non-linear programming problems, particularly those related to structural design and topology optimization.^[1]

History

MMA was introduced by Krister Svanberg in a 1987 paper titled, "The method of moving asymptotes—a new method for structural optimization."^[2] The method was proposed as an alternative to traditional optimization methods, offering an approach that could handle large-scale problems, especially in the realm of structural design. Another paper was published in 1993 by Svanberg which added some extensions to the method, including mini-max formulations and first and second order dual methods to solve subproblems.^[3] Another version that is globally convergent was proposed by Zillober.^[4]

Algorithm overview

The Method of Moving Asymptotes functions as an iterative scheme. The key idea behind MMA is to approximate the original non-linear constraints and objective function with a simpler, convex approximation. This approximation is represented by linear constraints and a convex objective function.^[2]

Starting from an initial guess, each iteration consists of the following steps:

Step I: Given an iteration point $x^{(k)}$ , calculate $f_{i}(x^{(k)})$ and the gradients $\nabla f_{i}(x^{(k)})$ for $i=0,1,\dots ,m$ .
Step II: Generate a subproblem $P^{(k)}$ by replacing, in $P$ , the (usually implicit) functions $f_{i}$ by approximating explicit functions $f_{i}^{(k)}$ , based on the calculations from Step I.
Step III: Solve $P^{(k)}$ and let the optimal solution of this subproblem be the next iteration point $x^{(k+1)}$ . Let $k=k+1$ and return to Step I until convergence.

The moving asymptotes serve as an adaptive mechanism. They shift and change with each iteration, progressively closing in on the optimal solution. This ensures that the approximations become increasingly accurate as the algorithm progresses.^[2]

Applications

The Method of Moving Asymptotes has been widely applied in various fields including:^[1]

Structural optimization: Design of truss structures, beams, plates, and shells.
Aeroelastic optimization: Design of aircraft wings and other components to reduce drag, weight, and ensure structural integrity.
Material design: Topology optimization for designing materials with desired mechanical properties.
Mechanical component design: Optimization of machine parts for weight reduction, durability, and performance.

Related Research Articles

In computational mathematics, an iterative method is a mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the n-th approximation is derived from the previous ones.

Mathematical optimization or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfields: discrete optimization and continuous optimization. Optimization problems arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.

In computer animation and robotics, inverse kinematics is the mathematical process of calculating the variable joint parameters needed to place the end of a kinematic chain, such as a robot manipulator or animation character's skeleton, in a given position and orientation relative to the start of the chain. Given joint parameters, the position and orientation of the chain's end, e.g. the hand of the character or robot, can typically be calculated directly using multiple applications of trigonometric formulas, a process known as forward kinematics. However, the reverse operation is, in general, much more challenging.

In calculus, Newton's method (also called Newton–Raphson) is an iterative method for finding the roots of a differentiable function $F$ , which are solutions to the equation $F (x) = 0$ . As such, Newton's method can be applied to the derivative $f'$ of a twice-differentiable function $f$ to find the roots of the derivative (solutions to $f'(x) = 0$ ), also known as the critical points of $f$ . These solutions may be minima, maxima, or saddle points; see section "Several variables" in Critical point (mathematics) and also section "Geometric interpretation" in this article. This is relevant in optimization, which aims to find (global) minima of the function $f$ .

In optimization, line search is a basic iterative approach to find a local minimum $of an objective function . It first finds a descent direction along which the objective function will be reduced, and then computes a step size that determines how far should move along that direction. The descent direction can be computed by various methods, such as gradient descent or quasi-Newton method. The step size can be determined either exactly or inexactly.$

Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets. Many classes of convex optimization problems admit polynomial-time algorithms, whereas mathematical optimization is in general NP-hard. With recent advancements in computing and optimization algorithms, convex programming is nearly as straightforward as linear programming.

In mathematical optimization, a trust region is the subset of the region of the objective function that is approximated using a model function. If an adequate model of the objective function is found within the trust region, then the region is expanded; conversely, if the approximation is poor, then the region is contracted.

The Frank–Wolfe algorithm is an iterative first-order optimization algorithm for constrained convex optimization. Also known as the conditional gradient method, reduced gradient algorithm and the convex combination algorithm, the method was originally proposed by Marguerite Frank and Philip Wolfe in 1956. In each iteration, the Frank–Wolfe algorithm considers a linear approximation of the objective function, and moves towards a minimizer of this linear function.

In mathematical optimization, the ellipsoid method is an iterative method for minimizing convex functions. The ellipsoid method generates a sequence of ellipsoids whose volume uniformly decreases at every step, thus enclosing a minimizer of a convex function.

In mathematics, preconditioning is the application of a transformation, called the preconditioner, that conditions a given problem into a form that is more suitable for numerical solving methods. Preconditioning is typically related to reducing a condition number of the problem. The preconditioned problem is then usually solved by an iterative method.

Limited-memory BFGS is an optimization algorithm in the family of quasi-Newton methods that approximates the Broyden–Fletcher–Goldfarb–Shanno algorithm (BFGS) using a limited amount of computer memory. It is a popular algorithm for parameter estimation in machine learning. The algorithm's target problem is to minimize $over unconstrained values of the real-vector where is a differentiable scalar function.$

In mathematics, the relaxation of a (mixed) integer linear program is the problem that arises by removing the integrality constraint of each variable.

Sequential quadratic programming (SQP) is an iterative method for constrained nonlinear optimization which may be considered a quasi-Newton method. SQP methods are used on mathematical problems for which the objective function and the constraints are twice continuously differentiable, but not necessarily convex.

Quasi-Newton methods are methods used to either find zeroes or local maxima and minima of functions, as an alternative to Newton's method. They can be used if the Jacobian or Hessian is unavailable or is too expensive to compute at every iteration. The "full" Newton's method requires the Jacobian in order to search for zeros, or the Hessian for finding extrema. Some iterative methods that reduce to Newton's method, such as SLSQP, may be considered quasi-Newtonian.

Subgradient methods are iterative methods for solving convex minimization problems. Originally developed by Naum Z. Shor and others in the 1960s and 1970s, subgradient methods are convergent when applied even to a non-differentiable objective function. When the objective function is differentiable, sub-gradient methods for unconstrained problems use the same search direction as the method of steepest descent.

The finite element method (FEM) is a popular method for numerically solving differential equations arising in engineering and mathematical modeling. Typical problem areas of interest include the traditional fields of structural analysis, heat transfer, fluid flow, mass transport, and electromagnetic potential.

Augmented Lagrangian methods are a certain class of algorithms for solving constrained optimization problems. They have similarities to penalty methods in that they replace a constrained optimization problem by a series of unconstrained problems and add a penalty term to the objective, but the augmented Lagrangian method adds yet another term designed to mimic a Lagrange multiplier. The augmented Lagrangian is related to, but not identical with, the method of Lagrange multipliers.

Sequential linear-quadratic programming (SLQP) is an iterative method for nonlinear optimization problems where objective function and constraints are twice continuously differentiable. Similarly to sequential quadratic programming (SQP), SLQP proceeds by solving a sequence of optimization subproblems. The difference between the two approaches is that:

The Barzilai-Borwein method is an iterative gradient descent method for unconstrained optimization using either of two step sizes derived from the linear trend of the most recent two iterates. This method, and modifications, are globally convergent under mild conditions, and perform competitively with conjugate gradient methods for many problems. Not depending on the objective itself, it can also solve some systems of linear and non-linear equations.

References

1 2 Bendsøe, M. P., & Sigmund, O. (2003). Topology optimization: theory, methods, and applications. Berlin: Springer.
1 2 3 Svanberg, K. (1987). The method of moving asymptotes—a new method for structural optimization. International Journal for Numerical Methods in Engineering, 24(2), 359-373.
↑ Svanberg, K. (1993), Rozvany, G. I. N. (ed.), "The Method of Moving Asymptotes (MMA) with Some Extensions", Optimization of Large Structural Systems, NATO ASI Series, Dordrecht: Springer Netherlands, pp. 555–566, doi:10.1007/978-94-010-9577-8_26, ISBN 978-94-010-9577-8 , retrieved 2023-09-01
↑ Zillober, C. (1993-09-01). "A globally convergent version of the method of moving asymptotes". Structural Optimization. 6 (3): 166–174. doi:10.1007/BF01743509. ISSN 1615-1488. S2CID 54187414.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[:0-1] 1 2 Bendsøe, M. P., & Sigmund, O. (2003). Topology optimization: theory, methods, and applications. Berlin: Springer.

[:1-2] 1 2 3 Svanberg, K. (1987). The method of moving asymptotes—a new method for structural optimization. International Journal for Numerical Methods in Engineering, 24(2), 359-373.

[3] Svanberg, K. (1993), Rozvany, G. I. N. (ed.), "The Method of Moving Asymptotes (MMA) with Some Extensions", Optimization of Large Structural Systems, NATO ASI Series, Dordrecht: Springer Netherlands, pp. 555–566, doi:10.1007/978-94-010-9577-8_26, ISBN 978-94-010-9577-8 , retrieved 2023-09-01

[4] Zillober, C. (1993-09-01). "A globally convergent version of the method of moving asymptotes". Structural Optimization. 6 (3): 166–174. doi:10.1007/BF01743509. ISSN 1615-1488. S2CID 54187414.

[1]

[2]

[3]

[4]