Treatment of nonconvexities using homotopy

Using homotopy, a convex optimization problem can be continuously deformed into a non-convex problem.

class rtctools.optimization.homotopy_mixin.HomotopyMixin

Bases: rtctools.optimization.optimization_problem.OptimizationProblem

Adds homotopy to your optimization problem. A homotopy is a continuous transformation between two optimization problems, parametrized by a single parameter \(\theta \in [0, 1]\).

Homotopy may be used to solve non-convex optimization problems, by starting with a convex approximation at \(\theta = 0.0\) and ending with the non-convex problem at \(\theta = 1.0\).

Note

It is advised to look for convex reformulations of your problem, before resorting to a use of the (potentially expensive) homotopy process.

homotopy_options(self)

Returns a dictionary of options controlling the homotopy process.

Option Type Default value
delta_theta_0 float 1.0
delta_theta_min float 0.01
homotopy_parameter string theta

The homotopy process is controlled by the homotopy parameter in the model, specified by the option homotopy_parameter. The homotopy parameter is initialized to 0.0, and increases to a value of 1.0 with a dynamically changing step size. This step size is initialized with the value of the option delta_theta_0. If this step size is too large, i.e., if the problem with the increased homotopy parameter fails to converge, the step size is halved. The process of halving terminates when the step size falls below the minimum value specified by the option delta_theta_min.

Returns:A dictionary of homotopy options.