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(**kwargs)[source]

Bases: 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() Dict[str, str | float][source]

Returns a dictionary of options controlling the homotopy process.

Option

Type

Default value

theta_start

float

0.0

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 theta_start, 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.