Version: v0.7.0 beta

Solver Interfaces

This chapter introduces the solver interfaces of OPTIMake. The solver interface takes problem, option, and workspace as input, and returns solve_status and output. Below is the pseudocode for the solve interface:

[solve_status, output] = solve(problem, option, workspace)

warning

Before the first solve, you must call the initialization function to initialize problem, option, and workspace. For consecutive solves, initialization only needs to be done before the first solve. The initialization function performs the following:

Sets the parameters in problem (including stage-independent and stage-dependent parameters) to -0.0
Initializes user-defined data in problem, such as interpolation tables
Sets the valid stage count in problem to the maximum stage count N
Sets the initial guess of primal variables in workspace to -0.0; and zeros out other parts that the solver needs to clear
Sets option to default values

You can determine whether a parameter or initial guess has been explicitly set by the user by checking whether its value is -0.0

Problem Settings

Through the problem struct, you can set the following:

Stage-independent parameters and stage-dependent parameters defined in the model (see Modeling Interfaces > Parameter Definition), set via param and param_stage respectively
The valid number of stages, set via valid_dim_N

Parameter Settings

Below is example code for setting parameters:

/* mass */
problem.param[VEHICLE_PARAM_MASS] = 2500.0;
/* length */
problem.param[VEHICLE_PARAM_LENGTH] = 2.2;
for (i = 0; i < VEHICLE_DIM_N; i++) {
    /* xLowerBound */
    problem.param_stage[i][VEHICLE_PARAM_STAGE_XLOWERBOUND] = i;
}

info

Enum variables such as VEHICLE_PARAM_MASS, VEHICLE_PARAM_LENGTH are automatically generated in the prob.h header file during code generation. Additionally, enum values for optimization variable indices and various dimension information are also included in this header file. You need to include this header file when using them (e.g., the vehicle model needs to include vehicle_prob.h).

Valid Number of Stages

Below is example code for setting the valid number of stages:

/* set valid stage number */
problem.valid_dim_N = 5;

info

The terminal equality constraint $f_e$ or the additional objective at the terminal $l_e$ applies to the last valid stage rather than the maximum stage
When the optimization problem has equality constraint $f_e$ or equality constraint $f$ , the valid number of stages must be greater than or equal to 2
The valid number of stages must be less than or equal to the maximum number of stages N

Option Settings

Solver parameters, which can be divided into general options and solving algorithm-specific options.

General Options

print_level: Print information level, int type

0: No printing
1: Print error messages and final solving status (default)
2: In addition to level 1, print iteration process
3: In addition to level 2, print more solving information

max_stepsize: Maximum iteration step size, double type, 0~1, default value is automatically set based on problem type

auto scaling

obj_scaling_method: Objective scaling method, int type, default value is automatically set based on problem type

0: No scaling
1: User-specified scaling factor, the value is provided via obj_scaling_factor in option
2: Automatic scaling based on Hessian values

obj_scaling_factor: Objective scaling factor, double type, non-negative, only effective when obj_scaling_method is set to 1, default value is 1.0

regularization

reg_hessian: Hessian regularization, double type, non-negative, default value is automatically set based on problem type

reg_eq: Regularization of Lagrange multipliers for equality constraints, double type, non-negative, default value is automatically set based on problem type

reg_ineq: Regularization of Lagrange multipliers for inequality constraints, double type, non-negative, default value is automatically set based on problem type

tolerance

The solver considers the current solution optimal and terminates iteration when all of the following conditions are satisfied.

tol_eq: Tolerance for equality constraints, double type, non-negative, default value is automatically set based on the code generation option default_tolerance_level

tol_ineq: Tolerance for inequality constraints, double type, non-negative, default value is automatically set based on the code generation option default_tolerance_level

tol_stat: Tolerance for stationarity condition, double type, non-negative, default value is automatically set based on the code generation option default_tolerance_level

tol_comp: Tolerance for complementarity condition, double type, non-negative, default value is automatically set based on the code generation option default_tolerance_level

exit conditions

When any of the following conditions is satisfied, the solver will terminate iteration and return the corresponding exit reason (exit_reason) in output.

max_num_iter:

When the solving algorithm is 'pdipm', the maximum number of iterations, size_t type, default value is 100
When the solving algorithm is 'sqp', the maximum number of outer SQP iterations, size_t type, default value is 20

max_num_function_eval_ratio: Ratio of maximum function evaluations to maximum iterations, double type, greater than or equal to 1, default value is 2.0

max_num_function_eval_offset: Offset for maximum function evaluations, size_t type, default value is 20

Maximum function evaluations = max_num_iter * max_num_function_eval_ratio + max_num_function_eval_offset

tol_step: Tolerance for changes in optimization variables, double type, non-negative, default value is 1e-14

tol_obj_relative: Tolerance for relative change (relative to the previous iteration) of the objective function value, double type, non-negative, default value is 1e-14

tol_obj_relative_max_num_consecutive_iter: Maximum number of consecutive iterations where the relative change in objective function value is less than tol_obj_relative, size_t type, default value is 5

When the relative change of the objective function value is less than tol_obj_relative for tol_obj_relative_max_num_consecutive_iter consecutive iterations, the solver will terminate early

tol_obj_absolute: Tolerance for absolute change of the objective function value, double type, non-negative, default value is 1e-14

tol_obj_absolute_max_num_consecutive_iter: Maximum number of consecutive iterations where the absolute change in objective function value is less than tol_obj_absolute, size_t type, default value is 5

When the absolute change of the objective function value is less than tol_obj_absolute for tol_obj_absolute_max_num_consecutive_iter consecutive iterations, the solver will terminate early

tol_obj_require_feasibility: Whether to require solution feasibility when the objective function value change satisfies the tolerance over consecutive iterations, int type

0: No
1: Yes (default)

tol_max_ineq_dual: Tolerance for the maximum Lagrange multiplier of inequality constraints, double type, non-negative, default value is 1e12

tol_max_ineq_dual_max_num_consecutive_iter: Maximum number of consecutive iterations where the maximum inequality constraint Lagrange multiplier exceeds tol_max_ineq_dual, size_t type, default value is 5 when the solving algorithm is 'pdipm', and 3 when the solving algorithm is 'sqp'

initialization

ineq_dual_init_method: Initialization method for inequality constraint Lagrange multipliers, int type

0: Initialize all to 1 (default)
1: Initialize based on complementarity condition

eq_dual_init_method: Initialization method for equality constraint Lagrange multipliers, int type

0: Initialize all to 0 (default)
1: Initialize based on stationarity condition

barrier

When the solving algorithm is 'sqp', the following options are for the pdipm solver in the QP subproblem. When the solving algorithm is 'pdipm', the following options are for the main problem.

barrier_strategy: Barrier strategy, int type

0: Monotone strategy
1: LOQO adaptive strategy
2: Combined monotone and LOQO adaptive strategy
3: Mehrotra strategy

When the optimization problem is a linear SOCP, the default value of barrier_strategy is 3; otherwise, the default value is 1.

barrier_init: Initial value of the barrier parameter, double type, non-negative, default value is 1.0

barrier_target: Target value of the barrier parameter, double type, non-negative and not greater than mu_start, default value is automatically set based on the code generation option default_tolerance_level

mehrotra_correction: Whether to use correction step in the Mehrotra strategy, int type

When the optimization problem is a linear SOCP, the default value is 1; otherwise, the default value is 0

Other Options

bfgs_max_num_skipping: When hessian_approximation is set to 'bfgs', the maximum number of BFGS update skips. When this number is exceeded, the Hessian will be reinitialized. size_t type, default value is 2

pdipm Options

This section introduces options specific to the pdipm solving algorithm.

try_warm_start_barrier: Whether to attempt warm start solving from barrier_target (when hessian_approximation is set to 'bfgs', the Hessian will also be set to the Hessian value from the previous solve). If warm start succeeds, it will effectively reduce the number of iterations. Suitable for optimization problems that require consecutive solving and where barrier_target is not too small. int type

0: No (default)
1: Yes

If the warm start attempt fails, the barrier parameter will be set to barrier_init to start iteration, and dual variables, slack variables, and Hessian will all be reinitialized. In this case, there will be one more iteration compared to the setting where try_warm_start_barrier is 0.

line search

line_search_method: Line search strategy, int type, default value is automatically set based on problem type

0: No line search, i.e., full step is accepted at each iteration
1: Filter strategy

line_search_max_num_iter: Maximum number of line search iterations, size_t type, default value is 10

line_search_max_num_consecutive_fails: Maximum number of consecutive line search failures, size_t type, default value is 5

infeasibility_relaxation_weight: When line search is enabled and the maximum number of line search iterations is reached, OPTIMake will perform l1 relaxation on all equality hard constraints and inequality hard constraints (excluding variable hard bound constraints). This value is the relaxation weight, double type, non-negative, default value is 1e4

sqp Options

This section introduces options specific to the sqp solving algorithm.

qp_max_num_iter: Maximum number of iterations for QP subproblems, size_t type, default value is 30

Workspace Settings

Initial Guess

The initial values (initial guess) of optimization variables are set through the workspace.

Below is example code for setting the initial guess:

for (i = 0; i < VEHICLE_DIM_N; i++) {
    /* initial guess */
    workspace.primal.var[i][VEHICLE_VAR_X] = 2.0; /* x */
    workspace.primal.var[i][VEHICLE_VAR_Y] = 5.0; /* y */
    workspace.primal.var[i][VEHICLE_VAR_PHI] = 1.57; /* phi */
}

Additionally, the workspace contains the following extra information:

Dual variables of the solver. The initial values of dual variables are automatically set by the solver. Users can access dual variables via workspace.dual after solving
Hessian. Users can access the Lagrangian Hessian via workspace.hessian after solving. The Hessian for each stage is stored in column-major order, and only the lower triangle (including the diagonal) is stored

solve_status

solve_status is the solving status:

1: Solve succeeded: found a solution satisfying tol_eq, tol_ineq, tol_stat, and tol_comp
2: Solve exited, feasible solution found: found a solution satisfying tol_eq and tol_ineq, but tol_stat or tol_comp is not satisfied
3: Problem infeasible, i.e., the problem was solved successfully after l1 relaxation, but the solution is infeasible for the original problem (this status only occurs when line_search_method option is set to 1)
4: Solve exited, no feasible or optimal solution found
5: Not applicable
6: Not applicable
7: Not initialized before solving
8: Invalid solving problem
9: Invalid solving option
100: License check failed
101: Initial guess check failed (contains illegal inf/nan values)
200: Solver internal error

Among these, statuses 2 and 4 both indicate solver exit. The exit reason will be printed when print_level is set to 1 or above, or can be obtained through the output information below.

output

output contains the following information:

iter: Number of iterations
qp_iter_total: Total number of iterations across all SQP subproblems (only valid when the solving algorithm is sqp)
exit_reason: Exit reason code
- 1: Exit due to successful solve of the original problem or the l1-relaxed problem (solve_status is 1 or 3)
- 2: Maximum number of iterations reached
- 3: Maximum number of function evaluations reached
- 4: Maximum number of consecutive line search failures reached
- 5: Relative or absolute change of objective function value is less than the corresponding tolerance for several consecutive iterations
- 6: Change in optimization variables is less than tol_step
- 7: Numerical issues (e.g., inf/nan) occurred during iteration
obj: Objective function value
solve_time: Solve time (total time including function evaluations), in seconds (valid when enable_timing is True in code generation, otherwise 0)
function_eval_time: Function evaluation time, in seconds (valid when enable_timing is True in code generation, otherwise 0)
res_eq: Equality constraint residual
res_ineq: Inequality constraint residual
res_stat: Stationarity condition residual
res_comp: Complementarity condition residual
primal: Primal variables, storing optimization variables, constraint softening slack variables, etc.
max_ineq_dual_info: The 8 largest inequality constraint Lagrange multipliers

Primal Variables

The components of the primal variables are described as follows:

The $j$ -th optimization variable at the $i$ -th stage can be accessed via output.primal.var[i][j]. Only variables within the valid number of stages are effective, i.e., stage index ranges from 0 to valid_dim_N - 1
output.primal.p_f and output.primal.n_f are the slack variables $p$ and $n$ introduced by softening the transition equality constraint $f$ . The same applies to other equality constraints
output.primal.p_g is the slack variable $p$ introduced by softening the inequality constraint $g$ . The same applies to other inequality constraints

max_ineq_dual_info

max_ineq_dual_info stores the 8 largest inequality constraint Lagrange multipliers after the last iteration, to facilitate analysis of infeasibility caused by constraint conflicts.

Below is a description of its components:

type: Constraint type
- 'l': Variable lower bound constraint
- 'u': Variable upper bound constraint
- 'g': Inequality constraint $g$
- 'c': Second order cone constraint
- 'n': This slot is not used
stage: Stage index of the constraint, starting from 0
index: Index of the constraint within its type at that stage (type is 'l' or 'u', the index is the variable index), starting from 0
value: Lagrange multiplier value of the constraint

info

When there are fewer than 8 inequality constraint Lagrange multipliers, the type of the remaining slots is set to 'n' (unused)
The Lagrange multipliers of variable soft bound constraints are not recorded here, as their values do not affect feasibility analysis
When print_level is set to 3 or above and solve_status is not 1, the information of the 8 largest inequality constraint Lagrange multipliers will be printed after solving

Example

warning

When the problem dimensions are large, the local variables for prob, workspace, and output may occupy a large stack space, potentially causing stack overflow. This can be resolved by using dynamic memory allocation or increasing the stack size.

Below is a complete demo showing how to set problem, option, and initial guess (using direct C/C++ calls):

vehicle_demo.cpp
#include "vehicle_solver.h"
#include "vehicle_prob.h"
#include <stdio.h>

int main(void)
{
    size_t i = 0;
    size_t j = 0;
    int status;
    Vehicle_Problem prob;
    Vehicle_Option option;
    Vehicle_WorkSpace ws;
    Vehicle_Output output;
    
    /* must be initialized before the very first solve */
    vehicle_init(&prob, &option, &ws);

    /* prob */
    prob.param[VEHICLE_PARAM_X0] = 0; /* x */
    prob.param[VEHICLE_PARAM_Y0] = 0; /* y */
    prob.param[VEHICLE_PARAM_PHI0] = 0; /* phi */
    prob.param[VEHICLE_PARAM_LENGTH] = 1.0; /* L */
    for (i = 0; i < VEHICLE_DIM_N; i++) {
        prob.param_stage[i][VEHICLE_PARAM_STAGE_XREF] = i;
        prob.param_stage[i][VEHICLE_PARAM_STAGE_YREF] = i;
    }

    /* option */
    option.print_level = 2;
    
    /* workspace, initial guess */
    for (i = 0; i < VEHICLE_DIM_N; i++) {
        ws.primal.var[i][VEHICLE_VAR_X] = i;
        ws.primal.var[i][VEHICLE_VAR_Y] = i;
    }

    status = vehicle_solve(&prob, &option, &ws, &output);

    for (i = 0; i < VEHICLE_DIM_N; i++) {
        for (j = 0; j < VEHICLE_DIM_VAR; j++) {
            printf("%f\t", output.primal.var[i][j]);
        }
        printf("\n");
    }
    printf("\n");

    return 0;
}

Problem Settings​

Parameter Settings​

Valid Number of Stages​

Option Settings​

General Options​

auto scaling​

regularization​

tolerance​

exit conditions​

initialization​

barrier​

Other Options​

pdipm Options​

line search​

sqp Options​

Workspace Settings​

Initial Guess​

solve_status​

output​

Primal Variables​

max_ineq_dual_info​

Example​

Problem Settings

Parameter Settings

Valid Number of Stages

Option Settings

General Options

auto scaling

regularization

tolerance

exit conditions

initialization

barrier

Other Options

pdipm Options

line search

sqp Options

Workspace Settings

Initial Guess

solve_status

output

Primal Variables

max_ineq_dual_info

Example