Constrained optimization problems are encountered in numerous domains, such as protein folding, Magnetic Resonance Image reconstruction, and radiation therapy. In this problem, we are given with an objective function which is to be minimized or maximized with respect to constraints on some variables. The constraints can either be soft constraints or hard constraints, which can be specified by boolean operators, such as equality, relational, and conditional operators.

This post provides insight on how to model constraints using lambda expressions, and how to pass a varying number of constraints to a function using variadic templates. Before moving on with the C++ implementation, it will be helpful to review how variadic functions are used in C and how they differ from the current standard.

C-style variadic functions

Support for variadic macros was introduced in C as part of the C99 standard. This allowed users to define functions that could take a varying number of arguments. A common example of this is the printf library function, which can be used to print an arbitrary number of values.

The cstdarg header file defines the necessary macros to create variadic functions. The syntax requires specifying the function name followed by its arguments. The last argument is always the ellipsis ... operator. An example of this is shown below:

void print_arguments(int nargs, ...) { // (1)
  va_list vl;                          // (2)
  va_start(vl, nargs);                 // (3)

  for (int i = 0; i < nargs; ++i)
    printf("%s", va_arg(vl, char*));   // (4)

  va_end(vl);                          // (5)
}

Calling the above function as print_arguments(5, "h", "e", "l", "l", "o") will produce the output hello. Let's go over the function definition step-by-step:

1. nargs is the first argument which, in this case, specifies the argument count this function should expect. The ellipsis ... operator specifies an arbitrary number of arguments.
2. An object of va_list is created to hold information about the variable arguments.
3. The variable argument list vl is initialized using the va_start macro. Here nargs specifies the number of arguments.
4. va_arg retrieves the next argument. Each call to this macro modifies the state of vl to point to the next element. Notice that we had to explicitly pass the function type, so this function is not type agnostic.
5. The va_end macro should be invoked before the function returns. It performs cleanup of the va_list object so that it's no longer usable.

Drawbacks

There are several drawbacks using the above function. Firstly, we have to specify the number of arguments as part of the function call, although, this is not necessary, as we could also pass a token specifying argument end, such as the NULL operator. The printf function does this by looking at the formatting specifiers (%s in this case). This is why it fails if the format string does not match the argument list.

Another major drawback is that we have to know, in advance, the type of data we're passing. Passing an incorrect type to va_arg can result in a segmentation fault. This makes it cumbersome to process data with varying types. Finally, the types are evaluated at run-time, which can be a performance overhead.

C-style variadic functions are discouraged in C++ as they are not type safe, apart from other issues that are mentioned above. In C++, we have the ability to define variadic templates, which are strongly typed. These are discussed in the following section.

Variadic templates in C++

Variadic templates became part of the C++ standard in August 2011, commonly known as C++11. They allow a way of writing functions that take a varying number of arguments in a type safe way using pack expansion. Another advantage they have over the traditional variadic functions is that all argument handling logic is performed at compile-time, which leads to better performance.

The example below defines a variadic function template which returns the number of arguments passed to it:

template<typename... Types>        // (1)
std::size_t nargs(Types... args) { // (2)
  return sizeof... (args);         // (3)
}

Calling nargs(1, "2", 3.5) will return 3. The function details are described below:

1. We first specify a variadic template using typename... Types, the contents of which are called parameter packs.
2. The parameters packs are unpacked inside the function header. So, in the above case, calling nargs(1, "2", 3.5) will generate:

template<int, const char*, double>
std::size_t nargs(int param1, const char* param2, double param3);

3. The sizeof… operator queries the number of arguments in a parameter pack.

Now let's look at an example which makes use of pack expansion. The function below returns true if all the arguments passed to it are true, that is, it performs an AND operation.

// The base case: just return the passed argument.
template <typename T>
bool isTrue(T t) {
  return t;
}

// The recursive case: perform an AND operation. 
template <typename T, typename... Args>
bool isTrue(T t, Args... args) {
  return t && isTrue(args...);
}

It is important to mention that we cannot use the iterative C++ style here. More precisely, we cannot loop over the passed arguments. Instead, variadic templates require functions to be written recursively, thus a separate function for the base case, and the recursive case, as shown above.

Let's trace the above function with the isTrue(true, false, true) call:

1. Since the number of arguments are greater that one, the second overloaded function, that is, the recursive case is called.
2. The compiler deduces the template type to be bool, so the parameter pack becomes T = bool; Args = {bool, bool}.
3. We now use pack expansion ... with isTrue(args...). The compiler translates this into isTrue(false, true).
4. The header generated above isTrue(false, true) again calls the recursive case.
5. The compiler deduces the type to be T = bool; Args = {bool}.
6. This time isTrue(args...) is translated into isTrue(true).
7. Since there is only one argument passed to isTrue we have reached the base case, and the recursion is finished.

This can be confirmed by using the __PRETTY_FUNCTION__ macro, which generates the call stack as listed below:

bool isTrue(T, Args ...) [with T = bool; Args = {bool, bool}]
bool isTrue(T, Args ...) [with T = bool; Args = {bool}]
bool isTrue(T) [with T = bool]

Note: Variadic recursion differs from traditional recursion. In traditional recursion a function calls itself a number of times using the same signature, until it reaches its base case. However, in variadic recursion the function signature is always changing, as the number of arguments are decreasing with each call, so the compiler generates a different function header for each call.

Constrained optimization problems: a practical use-case

A practical use-case where variadic templates can be employed are constrained optimization problems. They require the state to satisfy certain constraints for them to be considered eligible. Constraints can be of many types, such as boundary constraints, which can be specified by equality, inequality, and relational operators.

Let's consider the constrained variant of particle swarm optimization (PSO). The details of this algorithm are beyond the scope of this post. Briefly, PSO tries to find the local or global minimum from a given a set of problems, which must satisfy certain constraints. Suppose there is a class PSO which provides this implementation. We need to create a convenient API through which a user can pass constraints to a class method, say PSO::optimize. One option is by passing each constraint as an argument to the class method. However, the number of constraints are arbitrary, and can vary from problem to problem. This can be solved using variadic templates.

Lambda expressions

Ideally, a constraint should be a function which takes data as input and returns a boolean, which indicates whether the given data satisfies the constraint or not. This can be conveniently specified using a lambda expression, which was introduced in C++11.

A lambda expression is an inline anonymous function that is simple to read and interpret. It can be specified as follows:

auto constraint = [](int x) { return x > 7; };

The auto specifier is also part of the C++11 standard. It allows the compiler to deduce expression type from the return statement. [] is the capture list which can take a comma separated list of captures, such as by reference & or by value =. In this case, we don't capture anything, so the list is empty. The argument list and function body are similar to standard C++ functions.

Variadic template with lambda expressions

We now have to define a variadic template that can take arbitrary number of lambda expressions and return true if all the constraints are satisfied. This is similar to what we defined above:

template<typename Constraint>
bool evaluateConstraints(int x, Constraint constraint) {
  return constraint(x);
}

template<typename T, typename... Args>
bool evaluateConstraints(int x, T constraint, Args... constraints) {
  return constraint(x) &&
         evaluateConstraints(x, constraints...);
}

The first parameter x is the value on which we want to enforce our constraints. Our class method can now take a varying number of constraints (lambda expressions) using pack expansion and call the evaluateConstraints function. For the sake of demonstration, this could look something like:

template<typename... Args>
inline void PSO::optimize(Args... constraints) {
  // In actual implementation the initial starting
  // point can be specified by the user.
  int x = 7;

  while(!evaluateConstraints(x, constraints...)) {
    // Perform optimization.

    // Update x.
  }
}

In conclusion, this post discussed:

• Drawbacks of C-style variadic functions which are defined using va_list, va_start, va_arg, and va_end macros.
• C++ varaidic templates require writing a base case and a recursive case. They are also type safe and provide better performance due to compile time computation.
• Expressing constraints as lambda expressions in constrained optimizations problems.
• Combining variadic templates with lambda expressions for handling multiple constraints.