下文我们将讲述小编对线性规划的理解以及展示两个算例，和使用 MindOpt C 语言的 API 来建模以及求解 二次规划示例 中的问题。
(二次规划定义、算数例题都是与前文python语言的二次规划问题是一致的，已经阅读了前文可以忽略，直接点击目录进阶算例阅读建模优化代码。)
MindOpt Python、C、C++语言求解LP、MILP、QP问题系列
- Python: 线性规划LP问题、混合整数线性规划MILP问题、二次规划QP问题
- C : 线性规划LP问题、混合整数线性规划MILP问题、二次规划QP问题(本篇)
- C++ : 线性规划LP问题、混合整数线性规划MILP问题、二次规划QP问题
下载安装
用户可以点这里下载安装MindOpt优化求解器，免费的。找不到安装步骤点这里。
(官网https://opt.aliyun.com有更多信息等着您哟!)
二次规划
在前文线性规划问题示例中，讲述到线性规划在我个人认为是在线性的目标和约束中，找出一个最优解。而本文的二次规划，是非线性规划中的一类。具体地说，是一个线性约束的、二次规划问题，就是优化（最小化或最大化）二次函数目标的问题。
关于优化的类别，有很多，比如MindOpt的案例广场的标签里面提到的问题标签，就列出了常见的数学规划的类型。其中关于变量、约束、目标这建模三要素，进行罗列：
- 关于变量：取值有连续的，有整数的，还有更特殊的二进制（0或1）的，
- 关于约束和目标：一般用变量的函数变换来表达，其中约束再增加它函数的取值范围。
- 当函数是变量的线性关系时，比如x的1次方相加，我们称呼为线性约束、线性的目标。（如果变量也是连续的，这个就是线性规划问题啦。）
- 当函数是变量的是二次关系的时候，比如函数中有 x的2次方项。我们称呼为二次约束，或二次目标。
- 函数还会有凸函数和非凸函数，数学里面都代表不同的特性，大家可以再多去查阅材料。
本文主要讲 凸二次规划，Convex Quadratic Programming。
数学形式下的二次规划问题：
公式参考自MindOpt文档：https://solver.damo.alibaba.com/doc/html/model/qp/quadratic%20problem.html
案例
讲一个简单的例子，使用二次规划方法优化汽车轨迹，自动化驾驶车辆行驶在道路比较狭窄的路径上，还有其他障碍物阻碍的情况下，如果需要快速通过的话，我们需要暂时借用相邻车道通过，这个情况需要考虑自身车辆的情况、交通规则、保障远离障碍物距离的信息，然后找出一条通道。那么这个例子的解决办法是先考虑自身车辆的位置和周围障碍物，精确处理前一步可用车道，得到路径的边界，然后对路径边界进行优化(比如把车辆和障碍物之间的距离最大化，以允许车辆安全通过间隙)。
再比如，二次规划在机器人中应用，解决机械臂控制的问题。对于机器人来说，常常具备冗余关节，并且存在关节角度、角速度等限制条件，非常适合用二次规划方法来进行优化求解。
数学算例
接下来我们举一个简单的数学算例，和如何用MindOpt优化求解器进行求解。
二次规划问题示例：
C语言+MindOpt代码实现
核心使用的几个APIs是：
MDO_CHECK_CALL(Mdo_createMdl(&model)) MDO_CHECK_CALL(Mdo_setIntAttr(model, MDO_INT_ATTR_MIN_SENSE, MDO_YES)) MDO_CHECK_CALL(Mdo_addRow(model, 1.0, MDO_INFINITY, 4, row1_idx, row1_val, "c0")); MDO_CHECK_CALL(Mdo_addRow(model, 1.0, 1.0, 3, row2_idx, row2_val, "c1")); MDO_CHECK_CALL(Mdo_solveProb(model)); Mdo_displayResults(model);
#关于更多API的详细使用方式，请参考 C 接口函数
下面是完整的例子，可复制存为MdoQoEx1.c文件。
/*引入头文件*/ /* 检查返回码的宏 */ int main(void) { /* 变量 */ char str[1024] = { "\0" }; MdoMdl * model = NULL; MdoResult code = MDO_OKAY; MdoStatus status = MDO_UNKNOWN; const int row1_idx[] = { 0, 1, 2, 3 }; const double row1_val[] = { 1.0, 1.0, 2.0, 3.0 }; const int row2_idx[] = { 0, 2, 3 }; const double row2_val[] = { 1.0, -1.0, 6.0 }; const int qo_col1[] = { 0, 1, 1, 2, 3 }; const int qo_col2[] = { 0, 0, 1, 2, 3 }; const double qo_values[] = { 1.0, 0.5, 1.0, 1.0, 1.0 }; /*------------------------------------------------------------------*/ /* Step 1. 创建模型并更改参数。 */ /*------------------------------------------------------------------*/ /* 创建一个空模型。 */ MDO_CHECK_CALL(Mdo_createMdl(&model)); /*------------------------------------------------------------------*/ /* Step 2. 输入模型。 */ /*------------------------------------------------------------------*/ /* 改成最小化问题。 */ /*通过 Mdo_setIntAttr() 将目标函数设置为 最小化 */ MDO_CHECK_CALL(Mdo_setIntAttr(model, MDO_INT_ATTR_MIN_SENSE, MDO_YES)); /* 添加变量。 */ /*调用 Mdo_addCol() 来添加四个优化变量，定义其下界、上界、名称和类型*/ MDO_CHECK_CALL(Mdo_addCol(model, 0.0, 10.0, 1.0, 0, NULL, NULL, "x0", MDO_YES)); MDO_CHECK_CALL(Mdo_addCol(model, 0.0, MDO_INFINITY, 1.0, 0, NULL, NULL, "x1", MDO_YES)); MDO_CHECK_CALL(Mdo_addCol(model, 0.0, MDO_INFINITY, 1.0, 0, NULL, NULL, "x2", MDO_YES)); MDO_CHECK_CALL(Mdo_addCol(model, 0.0, MDO_INFINITY, 1.0, 0, NULL, NULL, "x3", MDO_NO)); /* 添加约束。 * 请注意，这里的非零元素是按行顺序输入的。 *调用 Mdo_addRow() 来输入约束 */ MDO_CHECK_CALL(Mdo_addRow(model, 1.0, MDO_INFINITY, 4, row1_idx, row1_val, "c0")); MDO_CHECK_CALL(Mdo_addRow(model, 1.0, 1.0, 3, row2_idx, row2_val, "c1")); /* 添加二次目标项。*/ MDO_CHECK_CALL(Mdo_setQuadraticElements(模型, 5, qo_col1, qo_col2, qo_values)); /*------------------------------------------------------------------*/ /* Step 3. 解决问题并填充结果。 */ /*------------------------------------------------------------------*/ /* 调用 Mdo_solveProb() 求解优化问题，并通过 Mdo_displayResults() 查看优化结果 */ MDO_CHECK_CALL(Mdo_solveProb(model)); Mdo_displayResults(model); /*------------------------------------------------------------------*/ /* Step 4. 释放模型。 */ /*------------------------------------------------------------------*/ /* 调用 Mdo_freeMdl() 来释放内存 */ Mdo_freeMdl(&model); return (int)code; }
MindOpt求解的结果
如何编译及运行MdoQoEx1.c文件
#运行方式与前文线性规划一致，只需要修改文件就好；把MdoQoEx1.c换成MdoQoEx1.c
windows系统本例是在Visual Studio上运行，版本为2019
/*linux和mac系统直接在命令行输入*/ cd <MDOHOME>/<VERSION>/examples/C make -f Makefile all ./MdoQoEx1
然后运行MdoQoEx1.c 文件后，得到求解的结果如下所示，/**/号里面是我添加的注释。
Model summary. /*模型摘要*/ - Num. variables : 4 - Num. constraints : 2 - Num. nonzeros : 7 - Bound range : [1.0e+00,1.0e+01] - Objective range : [1.0e+00,1.0e+00] - Quad. obj. range : [5.0e-01,1.0e+00] - Matrix range : [1.0e+00,6.0e+00] Presolver started. Presolver terminated. Time : 0.000s Interior point method started. /*内点法*/ Iter PrimObj DualObj PrimFea DualFea GapFea Mu Time 0 +5.21966603e+01 -5.98089411e+01 7.3e-01 1.3e+00 2.1e+00 1.5e+01 0.00s 1 +6.67007650e+00 -3.65314339e+00 1.8e-02 3.2e-02 2.8e+00 1.7e+00 0.00s 2 +1.36507017e+00 +2.11936527e-02 4.6e-04 8.1e-04 1.3e+00 2.2e-01 0.00s 3 +5.85640966e-01 +3.97564854e-01 2.6e-05 3.7e-03 1.9e-01 3.1e-02 0.00s 4 +4.53810895e-01 +4.38464927e-01 6.4e-07 9.3e-05 1.5e-02 2.6e-03 0.00s 5 +4.40393096e-01 +4.39961443e-01 1.6e-08 2.3e-06 4.3e-04 7.2e-05 0.00s 6 +4.40009842e-01 +4.39999040e-01 4.0e-10 5.9e-08 1.1e-05 1.8e-06 0.00s 7 +4.40000247e-01 +4.39999976e-01 1.0e-11 1.5e-09 2.7e-07 4.5e-08 0.00s 8 +4.40000006e-01 +4.39999999e-01 2.5e-13 3.7e-11 6.8e-09 1.1e-09 0.01s Terminated. - Method : Interior point method. - Primal objective : 4.3999999423925E-01 - Dual objective : 4.3999999955250E-01 - Num. threads : 2 - Num. iterations : 8 - Solver details : Solver terminated with a primal/dual optimal status. Interior point method terminated. Time : 0.005s Optimizer summary. /*求解器最终选择的优化方法以及求解消耗的时间*/ - Optimizer used : Interior point method /*内点法*/ - Optimizer status : OPTIMAL - Total time : 0.006s Solution summary. Primal solution - Objective : 4.3999999424e-01 /*目标函数最优解*/
联系我们
钉钉：damodi
邮箱地址：solver.damo@list.alibaba-inc.com
