下文我们将讲述小编对线性规划的理解以及展示两个算例，和使用 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文件。
/*引入头文件*//* 检查返回码的宏 */intmain(void) { /* 变量 */charstr[1024] = { "\0" }; MdoMdl*model=NULL; MdoResultcode=MDO_OKAY; MdoStatusstatus=MDO_UNKNOWN; constintrow1_idx[] = { 0, 1, 2, 3 }; constdoublerow1_val[] = { 1.0, 1.0, 2.0, 3.0 }; constintrow2_idx[] = { 0, 2, 3 }; constdoublerow2_val[] = { 1.0, -1.0, 6.0 }; constintqo_col1[] = { 0, 1, 1, 2, 3 }; constintqo_col2[] = { 0, 0, 1, 2, 3 }; constdoubleqo_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/Cmake-fMakefileall./MdoQoEx1
然后运行MdoQoEx1.c 文件后，得到求解的结果如下所示，/**/号里面是我添加的注释。
Modelsummary. /*模型摘要*/-Num. variables : 4-Num. constraints : 2-Num. nonzeros : 7-Boundrange : [1.0e+00,1.0e+01] -Objectiverange : [1.0e+00,1.0e+00] -Quad. obj. range : [5.0e-01,1.0e+00] -Matrixrange : [1.0e+00,6.0e+00] Presolverstarted. Presolverterminated. Time : 0.000sInteriorpointmethodstarted. /*内点法*/IterPrimObjDualObjPrimFeaDualFeaGapFeaMuTime0+5.21966603e+01-5.98089411e+017.3e-011.3e+002.1e+001.5e+010.00s1+6.67007650e+00-3.65314339e+001.8e-023.2e-022.8e+001.7e+000.00s2+1.36507017e+00+2.11936527e-024.6e-048.1e-041.3e+002.2e-010.00s3+5.85640966e-01+3.97564854e-012.6e-053.7e-031.9e-013.1e-020.00s4+4.53810895e-01+4.38464927e-016.4e-079.3e-051.5e-022.6e-030.00s5+4.40393096e-01+4.39961443e-011.6e-082.3e-064.3e-047.2e-050.00s6+4.40009842e-01+4.39999040e-014.0e-105.9e-081.1e-051.8e-060.00s7+4.40000247e-01+4.39999976e-011.0e-111.5e-092.7e-074.5e-080.00s8+4.40000006e-01+4.39999999e-012.5e-133.7e-116.8e-091.1e-090.01sTerminated. -Method : Interiorpointmethod. -Primalobjective : 4.3999999423925E-01-Dualobjective : 4.3999999955250E-01-Num. threads : 2-Num. iterations : 8-Solverdetails : Solverterminatedwithaprimal/dualoptimalstatus. Interiorpointmethodterminated. Time : 0.005sOptimizersummary. /*求解器最终选择的优化方法以及求解消耗的时间*/-Optimizerused : Interiorpointmethod/*内点法*/-Optimizerstatus : OPTIMAL-Totaltime : 0.006sSolutionsummary. Primalsolution-Objective : 4.3999999424e-01/*目标函数最优解*/
联系我们
钉钉群号：32451444
邮箱地址：solver.damo@list.alibaba-inc.com
