The objective of this post is to introduce fundamental concepts in computational optimization for design applications. This tutorial was part of the Advanced Topics in Digital Design and Fabrication 2016. In this tutorial we will look at situations where we need to minimize/maximize objective functions of a multi-dimensional continuous problems.
In similar fashion as with the previous installment of this series we will focus on fundamental concepts in optimization, to first gain a sort of intuition on iterative processes of search, and then we will enhance the methodology, and computational performance, using mathematical concepts and techniques.
We will start with a basic tutorial using a two-dimensional setup which can be expanded to multiple dimensions with some moderate work in abstraction. We will use a NURBS surface as a form of terrain which starting from any given initial location we need to locate the lowest point. This is commonly known as hill climbing, either upwards to find peaks or downwards to locate basins.
Starting from a point (p) on the surface at parametric coordinates (u, v) we can evaluate the normal vector (n). The normal contains some very interesting information apart from the direction perpendicular to the surface at that point such as we can use it to derive the direction of ascent/descent. We just need some geometric notions to see that taking w = ( n × Z ) × n, where (×) is the cross product and Z is the world (0, 0, 1) direction, produces a direction that it is first square to both the normal and the vertical, thus horizontal, and in the second step becomes the desired up/down hill direction, up to rearrangement of the vectors. You may convince yourself that this works by applying the principle on a triangle defined by any three points in 3-space.
From this simple rule of the thumb, also known as heuristic, we can march forward by a certain amount along the downhill direction to a new location. Thus the new position is the old position plus the translation vector scaled by the step/radius size. However, following an arbitrary direction on the tangent plane will most likely land us above or below the surface. We thus need to project the updated point back onto the surface using the closest point method to derrive a new u, v coordinate pair and repeat the process until we hit the bottom. The code below captures the logic explained above.
private void RunScript(
Point3d Origin, double Radius,
int Iterations, ref object Geometry)
//-- Initialize Surface Coordinates by Projection
double u, v;
Terrain.ClosestPoint(Origin, out u, out v);
//-- Path Location Tracking
var polyline = new Polyline();
//-- Hill-Climbing Iteration
for( var iteration = 0; iteration < Iterations; iteration++ )
//-- Compute Point and Normal
var p = Terrain.PointAt(u, v);
var n = Terrain.NormalAt(u, v);
//-- Steepest Descent Direction
var h = Vector3d.CrossProduct(n, Vector3d.ZAxis);
var w = Vector3d.CrossProduct(n, h); w.Unitize();
//-- Store Location
//-- Move Downhill and Project
var q = p + w * Radius;
Terrain.ClosestPoint(q, out u, out v);
Geometry = polyline;
So given this basic scenario it is interesting to observe what happens when we replace the original point selected from the model with a grid of points. In other words sample uniformly the entire domain of the surface. The results produced could be interpreted as a field of water pathways or up/down hill geodesics. Mildly interesting.
What appears at first as a rather simplistic approach to optimization of the function S( u, v ) = p.Z, where (S) is the surface and (p) is the point at domain coordinates (u, v), it does capture most key principles of numerical optimization in multiple dimensions; a particular family of methods that use the same line-search approach that is. Here are some important points to note before we move on to alternatives:
- The objective function is typically defined as f ( x1, x2, x3, …, xn ) → ( y1, y2, y3, …, ym ). In other words, we evaluate an input vector of size (n) into an output vector of size (m). We then typically need to extract or combine the output vector into a decision/cost value. In the example above we extracted the (Z) coordinate of the point but we could have made a scalar value by using a Euclidean distance etc. The sum of squares of the output vector is a very common cost metric as it doesn’t allow the variables/coordinates to compensate one another.
- Following a vector as a guideline to find a path towards the solution (line-search) is one of the most common in numerical optimization techniques. The variations of this family of algorithms are in the logic of direction and magnitude of step selection. What we developed earlier encapsulates some interesting ideas such using the normal vector and some basic vector geometry to obtain the gradient. While this happened in a few lines of code, internally we evaluated the NURBS function and its first partial derivatives of the surface at the point to obtain the normal vector.
- Computational/numerical methods typically operate on quantizations of space/time instead of notionally infinitely smooth functions. As a result we need to take care of side effects which present themselves as numerical errors. Issues such as overshoots when discretization/steps sizes are too large, oscillations in basins, rounding errors due to finite precision etc are some typical problems. Additionally, there are mathematical nuances such as saddle points where more than one direction can be followed, multiplicities of solution, local minima etc. Additional types of problems we have not seen yet are related to boundary conditions and constraints.
- Multivariate problems are far more difficult to comprehend because it is very difficult to picture in our mind as the number of parameters increases. In this example and previous univariate search tutorial it was quite easy to plot out the objective function and observe its behaviour. We thus need additional tools such as creating partial or composite visualization that may assist in gaining intuition.
Randomized & Bioinspired