版本：v0.6.0

求解接口

该章节介绍OPTIMake的求解接口. 求解接口接收problem, option, workspace作为输入, 返回solve_status与output. 下面为求解接口solve的伪代码:

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

注意

在第一次求解时, 需要调用初始化函数将problem, option以及workspace初始化. 在连续求解时, 也只需要在第一次求解前进行初始化. 该初始化函数会完成以下工作:

将problem中的参数 (包括stage-independent与stage-dependent parameter) 设置为-0.0
将problem中用户定义的数据初始化, 如插值表
将problem中的有效stage数设置为最大stage数N
将workspace中的primal变量的initial guess设置为-0.0; 并且将其他求解器需要清零的部分清零
将option设置为默认值

可通过参数与initial guess是否为-0.0, 判断参数或initial guess是否已被用户显式地设置

problem设置

通过problem结构体, 可以设置以下内容:

在模型中定义的stage-independent parameter与stage-dependent parameter (详见建模接口 > parameter定义), 分别通过param与param_stage设置
有效的stage数目, 通过valid_dim_N设置

parameter设置

下面为设置parameter的示例代码:

/* 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;
}

信息

VEHICLE_PARAM_MASS, VEHICLE_PARAM_LENGTH等enum变量会在代码生成时自动生成在prob.h的头文件中. 同时, 各优化变量index的enum值及各种维度信息也会被包含在该头文件中. 使用时需要包含该头文件 (比如vehicle模型需要包含vehicle_prob.h).

有效的stage数目

下面为设置有效stage数目的示例代码:

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

信息

终点等式约束 $f_e$ 或终点处额外的objective $l_e$ 作用在最后一个有效stage而非最大stage上
当优化问题具有等式约束 $f_e$ 或等式约束 $f$ 时, 需要保证有效stage数目大于等于2
有效stage数目必须小于等于最大stage数目N

option设置

求解器参数, 可分为通用option与求解算法相关option.

通用option

print_level: 打印信息的等级, int类型

0: 不打印
1: 打印错误信息与最终求解状态（默认值）
2: 在1的基础上, 打印迭代过程
3: 在2的基础上, 打印更多求解信息

max_num_iter: 最大迭代次数, size_t类型, 默认值为100

max_num_function_eval_ratio: 最大函数计算次数与最大迭代次数的比值, double类型, 大于等于1, 默认值为2.0

max_num_function_eval_offset: 最大函数计算次数的偏移量, size_t类型, 默认值为20

最大的函数计算次数 = max_num_iter * max_num_function_eval_ratio + max_num_function_eval_offset

max_stepsize: 最大迭代步长, double类型, 0~1, 默认值根据问题类型自动设置

auto scaling

obj_scaling_method: objective的scaling方法, int类型, 默认值根据问题类型自动设置

0: 无scaling
1: 用户指定scaling factor, 其值通过option中的obj_scaling_factor输入
2: 自动根据Hessian值进行scaling

obj_scaling_factor: objective的scaling factor, double类型, 非负, 仅当obj_scaling_method设置为1时有效, 默认值为1.0

regularization

reg_hessian: Hessian的regularization, double类型, 非负, 默认值根据问题类型自动设置

reg_eq: 等式约束拉格朗日乘子的regularization, double类型, 非负, 默认值根据问题类型自动设置

reg_ineq: 不等式约束拉格朗日乘子的regularization, double类型, 非负, 默认值根据问题类型自动设置

line search

line_search_method: 线搜索策略, int类型, 默认值根据问题类型自动设置

0: 无线搜索, 即每次迭代都全步长接收
1: filter策略

line_search_max_num_iter: 最大线搜索次数, size_t类型, 默认值为10

line_search_max_num_consecutive_fails: 最大连续线搜索失败次数, size_t类型, 默认值为5

infeasibility_relaxation_weight: 在线搜索打开且达到最大线搜索次数时, OPTIMake会将所有的等式硬约束与不等式硬约束 (不包含variable的hard bound约束)进行l1松弛, 该值为松弛的权重, double类型, 非负, 默认值为1e4

tolerance

tol_eq: 等式约束的tolerance, double类型, 非负, 默认值为根据代码生成选项default_tolerance_level自动设置

tol_ineq: 不等式约束的tolerance, double类型, 非负, 默认值为根据代码生成选项default_tolerance_level自动设置

tol_stat: stationarity condition的tolerance, double类型, 非负, 默认值为根据代码生成选项default_tolerance_level自动设置

tol_comp: complementarity condition的tolerance, double类型, 非负, 默认值为根据代码生成选项default_tolerance_level自动设置

tol_step: 优化变量的变化的tolerance, double类型, 非负, 默认值为1e-14

tol_obj_relative: 目标函数值的相对变化 (相对上一次迭代)的tolerance, double类型, 非负, 默认值为1e-14

tol_obj_relative_max_num_consecutive_iter: 目标函数值相对变化小于tol_obj_relative的最大连续迭代次数, size_t类型, 默认值为5

当目标函数值的相对变化在连续tol_obj_relative_max_num_consecutive_iter次迭代中均小于tol_obj_relative时, 求解器将提前终止迭代

tol_obj_absolute: 目标函数值的绝对变化的tolerance, double类型, 非负, 默认值为1e-14

tol_obj_absolute_max_num_consecutive_iter: 目标函数值绝对变化小于tol_obj_absolute的最大连续迭代次数, size_t类型, 默认值为5

当目标函数值的绝对变化在连续tol_obj_absolute_max_num_consecutive_iter次迭代中均小于tol_obj_absolute时, 求解器将提前终止迭代

tol_obj_require_feasibility: 在目标函数值变化满足tolerance的连续迭代结束时, 是否要求解的可行性, int类型

0: 否
1: 是 (默认)

initialization

ineq_dual_init_method: 不等式约束拉格朗日乘子的初始化方法, int类型

0: 全部初始化为1 (默认)
1: 根据complementarity condition初始化

eq_dual_init_method: 等式约束拉格朗日乘子的初始化方法, int类型

0: 全部初始化为0 (默认)
1: 根据stationarity condition初始化

其他option

bfgs_max_num_skipping: bfgs更新的最大skip次数, 当大于该次数时, Hessian会被初始化. size_t类型, 默认值为2

pdipm option

barrier

barrier_strategy: barrier策略, int类型

0: monotone策略
1: loqo adaptive策略 (默认)
2: 结合monotone策略与loqo adaptive策略

barrier_init: barrier parameter的初始值, double类型, 非负, 默认值为1.0

barrier_target: barrier parameter的最终值, double类型, 非负且不大于mu_start, 默认值根据代码生成选项default_tolerance_level自动设置

try_warm_start_barrier: 是否尝试从barrier_target开始warm start求解 (当hessian_approximation设置为'bfgs'时, Hessian也会被设置为上一次求解的Hessian值), 如果warm start成功, 将有效降低迭代次数, 适合需要连续求解且barrier_target不至于过小的优化问题. int类型

0: 否 (默认)
1: 是

如果warm start尝试失败, barrier parameter会被设置为 barrier_init 开始迭代, 且对偶变量, slack变量, Hessian均会被初始化. 此时相对于try_warm_start_barrier为0的设置会多一次迭代.

workspace设置

initial guess

优化变量的初始值 (initial guess)通过workspace设定.

下面为设置初始解的示例代码:

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 */
}

同时, workspace中也包含了以下额外信息:

求解器的对偶变量, 对偶变量的初始值会被求解器自动设置. 用户可以在求解结束后通过workspace.dual访问对偶变量
Hessian, 用户可以在求解结束后通过workspace.hessian访问Lagrangian的Hessian. 每个stage的Hessian按照列优先存储, 且只存储下三角 (包含对角线)

solve_status

solve_status为求解状态:

1: 求解成功: 找到tol_eq、tol_ineq、tol_stat、tol_comp均满足的解
2: 求解退出，找到可行解: 找到满足tol_eq与tol_ineq, 但tol_stat或tol_comp不满足的解
3: 问题不可行, 即问题进行l1松弛后求解成功, 但该解对原问题不可行 (需要将line_search_method求解选项设置为1才会出现该状态)
4: 求解退出, 未找到可行解或者最优解
5: 不涉及
6: 不涉及
7: 求解前未初始化
8: 求解问题无效
9: 求解option无效
100: license检查失败
101: 初始解检查失败 (包含inf/nan非法值)
200: 求解器内部错误

其中, 状态2与4均表示求解器退出，退出的原因会在print_level设置为1及以上时打印, 或者可通过下面的output中的信息进行获取.

output

output中包含了以下信息:

iter: 迭代次数
exit_reason: 求解退出原因的代码
- 1: 原问题或者进行l1松弛后的问题求解成功 (solve_status为1或3)导致的退出
- 2: 达到最大迭代次数
- 3: 达到最大函数计算次数
- 4: 达到最大连续线搜索失败次数
- 5: 目标函数值的相对或绝对变化在连续若干次迭代中均小于对应的tolerance
- 6: 优化变量的变化小于tol_step
- 7: 迭代过程中出现数值问题 (如inf/nan)
obj: 目标函数值
solve_time: 求解时间 (包含函数计算在内的所有时间), 单位为秒 (代码生成中enable_timing 为True时有效, 否则为0)
function_eval_time: 函数计算时间, 单位为秒 (代码生成中enable_timing 为True时有效, 否则为0)
res_eq: 等式约束的残差
res_ineq: 不等式约束的残差
res_stat: stationarity condition的残差
res_comp: complementarity condition的残差
primal: primal变量, 存储了优化变量, 约束软化的slack变量等
max_ineq_dual_info: 最大的8个不等式约束拉格朗日乘子

primal变量

primal变量中各部分的说明如下:

第 $i$ 个stage的第 $j$ 个优化变量可通过output.primal.var[i][j]获取, 只有有效stage数目内的变量才有效, 即stage的index从0到valid_dim_N - 1
output.primal.p_f与output.primal.n_f为转移等式约束 $f$ 软化引入的slack变量 $p$ 与 $n$ , 其他等式约束同理
output.primal.p_g为不等式约束 $g$ 软化引入的slack变量 $p$ , 其他不等式约束同理

max_ineq_dual_info

max_ineq_dual_info存储了最后一次迭代后最大的8个不等式约束拉格朗日乘子, 以便分析约束冲突导致的不可行性.

下面为其各部分的说明:

type: 约束类型
- 'l': 变量的lower bound约束
- 'u': 变量的upper bound约束
- 'g': 不等式约束 $g$
- 'c': second order cone约束
- 'n': 该slot未被使用
stage: 约束所在的stage index, 从0开始
index: 约束在该stage中所属类型约束的index (type为'l'和'u'时index为变量的index), 从0开始
value: 该约束的拉格朗日乘子值

信息

当不等式约束的拉格朗日乘子数量少于8时, 多余的slot的type被设置为'n' (未使用)
这里没有记录变量的soft bound约束的拉格朗日乘子, 因为其值不会影响问题的可行性分析
当print_level设置为3及以上，并且solve_status为非1时，求解结束后会打印出最大的8个不等式约束拉格朗日乘子的信息

示例

注意

当问题的维度较大时, prob, workspace, output的局部变量会占用较大的栈空间, 可能会导致栈溢出. 可以通过动态内存分配或增加栈的大小解决该问题.

以下为一个介绍了如何设置problem, option, initial guess的完整的demo (使用C/C++直接调用):

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设置​

parameter设置​

有效的stage数目​

option设置​

通用option​

auto scaling​

regularization​

line search​

tolerance​

initialization​

其他option​

pdipm option​

barrier​

workspace设置​

initial guess​

solve_status​

output​

primal变量​

max_ineq_dual_info​

示例​