Optimization Using A Geodesic

Introduction

A continuous optimization problem can be formulated in terms of a minimum-length geodesic on a manifold. The parametric model is a constraint manifold on which a metric tensor and Christoffel symbols are computed. The objective function gradient is projected on this manifold. The steepest-decent algorithm is equivalent to computing a minimum-length geodesic on the manifold. EleSoft Research extends this in two ways:

• The salient assemblage representation extends a given multidimensional parametric representation with recursion and deformation. For example, recursive salients (bumps) can be appended to the n-sphere, n-ellipsoid, or n-torus computed by EleNTorus™ software.
• Minimum-length geodesic computation is based on software EleGeodesic.

Multidimensional, Recursive, Deforming Manifold

In this discussion, a representation means a parametric description of a manifold (surface). A well-known example is the representation of the 2-sphere with radius . It is

Such a representation can be generalized to capture multidimensional recursion and deformation. For example, a parent surface can be deformed by drawing out salient bumps recursively. These salients meet rules about location, size, shape, dihedral angle, alignment with principal directions on the parent, surface area, and volume. The representation is

where is a given representation, like the sphere above. Summation is implied over m and h_j. The formula is recursive, since the left-hand side can be substituted for the first term on the right-hand side. Variables define location, size, direction, and shape. Salients blend asymptotically. Formula complexity is handled by a computer. A prototypical two-dimensional assemblage of three salients is shown in the following figure.

What is the importance of this representation? It is useful in modeling recursive parametric systems. Besides geometric objects for which the model is obvious, there are social and economic systems. For example, a decision in a large organization is made in the context of all previous decisions. Thus a decision is a recursive operation. A decision to optimize one or a few variables typically affects many correlated variables. Consequently, an assemblage of salients can represent the results of many sequential interdependent decisions. A natural question is how an organization can transition efficiently from one state (point) to another. The answer is a transition path that coincides with a minimum-length geodesic.

Minimum-Length Geodesic Computation

A shortest path between two given points is always a geodesic. For nonlinear problems, there are usually many geodesics, and the task is finding a minimum-length geodesic. The latter need not be unique, as when endpoints are symmetrically located on a symmetric geometry.

Geodesic computation uses Christoffel symbols, coefficients of surface path tangential curvature. Although traditionally called symbols, they are actually a matrix-valued function of position. By definition, a geodesic is a solution of the system of nonlinear ordinary differential equations

whereis the Christoffel symbol of the second kind and summation is implied over j and k. Typically, there are many solutions.

The EleGeodesic software computes minimum-length geodesics from this equation. It uses a relaxation method. It computes overall arc length and saves the shortest geodesic found. It has several performance options to control convergence. There are three principal inputs to EleGeodesic software:

1. The representation of the manifold (e.g. constraint manifold) under study.
2. The metric tensor (e.g. objective function) that describes cost in all directions at every point.
3. Endpoint(s) for the geodesic to be calculated.

EleGeodesic output is the shortest path found. This is an approximation of a minimum-length geodesic.

Suppose objective function f(x,y,z)=x+y+z must be maximized on each constraint surface below. Function f(x,y,z) defines a optimization metric. Search path begins at an approximation point and proceeds along the geodesic in the direction of the projected objective function gradient.

On the sphere below, search begins at point on the left and converges on extremum (0.9553,0.7855).

Close-up of convergence on extremum (0.9553,0.7855).

Manifold curvature can be decisive in determining path. On the torus below, the path is determined by objective function gradient alone.

However, the actual minimum-length geodesic is

On the salient assemblage below, the search begins at lowest point and converges on local extremum.

Same search path in parameter space.

Efficient convergence is not always assured. For such cases, EleGeodesic provides performance controls like acceleration factor, convergence epsilon, and maximum iterations.

Although, most optimization problems are multidimensional, their principle characteristics are illustrated on 2D surfaces. EleGeodesic computes geodesics on multidimensional manifolds.

Conclusion

In summary, multidimensional, recursive, and bumpy, parametric systems can be modeled. A minimum-length geodesic has a direct optimization interpretation. Of course, these ideas have many interesting details. A generalized Fourier series can control salient shape.

The method's limitations are:

• In regions of high curvature, salient shape control is difficult, but possible. Of course, this limitation is only applies to problems that need shape control.
• Global minimum-length geodesic computation involves heuristic selection of the shortest geodesic from many geodesic solutions. Simple heuristics are satisfactory, but there are probably better rules that can be inferred from the problem's specific representation and metric tensor.
• There is the generic problem of numerically solving a system of nonlinear ordinary differential equations. Robust solution methods are difficult.

EleSoft Research Software Tools

EleSoft Research software can be applied to optimization problems.

• The salient assemblage representation extends a given multidimensional parametric representation with recursion and deformation. For example, recursive salients can be appended to the n-sphere, n-ellipsoid, or n-torus computed by EleNTorus™ software.
• Minimum-length geodesic computation is based on software EleGeodesic.

If you have an optimization problem and believe it might benefit from a geodesic formulation, contact EleSoft Research.