Python语言如何使用MindOpt建模并求解二次规划问题

简介: MindOpt是一款高效的优化算法软件包,求解算法实现了线性规划(LP)、混合整数线性规划(MILP)、二次规划(QP),可以支持命令行、c、c++、java和python调用。接下来我们将发布一系列文章,讲述各个语言如何使用 MindOpt 来求解数学规划问题。

本篇文章是系列文章的第三篇,下文小编首先分享个人对二次规划定义的理解,然后举一个例题,最后使用 MindOpt Python 语言的 API 来建模以及求解 二次规划问题示例 中的问题以及展示求解的结果。


MindOpt Python、C、C++语言求解LP、MILP、QP问题系列


安装

用户可以点这里下载安装MindOpt优化求解器,免费的。找不到安装步骤点这里

(官网https://opt.aliyun.com有更多信息等着您哟!)


二次规划定义

在前文线性规划问题示例中,讲述到线性规划在我个人认为是在线性的目标和约束中,找出一个最优解。而本文的二次规划,是非线性规划中的一类。具体地说,是一个线性约束的、二次规划问题,就是优化(最小化或最大化)二次函数目标的问题。


关于优化的类别,有很多,比如MindOpt的案例广场的标签里面提到的问题标签,就列出了常见的数学规划的类型。其中关于变量、约束、目标这建模三要素,进行罗列:

  • 关于变量:取值有连续的,有整数的,还有更特殊的二进制(0或1)的,
  • 关于约束和目标:一般用变量的函数变换来表达,其中约束再增加它函数的取值范围。
  • 当函数是变量的线性关系时,比如x的1次方相加,我们称呼为线性约束、线性的目标。(如果变量也是连续的,这个就是线性规划问题啦。)
  • 当函数是变量的是二次关系的时候,比如函数中有 x的2次方项。我们称呼为二次约束,或二次目标。
  • 函数还会有凸函数和非凸函数,数学里面都代表不同的特性,大家可以再多去查阅材料。

image.png


本文主要讲 凸二次规划,Convex Quadratic Programming。

数学形式下的二次规划问题:

image.png

公式参考自MindOpt文档:https://solver.damo.alibaba.com/doc/html/model/qp/quadratic%20problem.html


案例

讲一个简单的例子,使用二次规划方法优化汽车轨迹,自动化驾驶车辆行驶在道路比较狭窄的路径上,还有其他障碍物阻碍的情况下,如果需要快速通过的话,我们需要暂时借用相邻车道通过,这个情况需要考虑自身车辆的情况、交通规则、保障远离障碍物距离的信息,然后找出一条通道。那么这个例子的解决办法是先考虑自身车辆的位置和周围障碍物,精确处理前一步可用车道,得到路径的边界,然后对路径边界进行优化(比如把车辆和障碍物之间的距离最大化,以允许车辆安全通过间隙)。


image.png


再比如,二次规划在机器人中应用,解决机械臂控制的问题。对于机器人来说,常常具备冗余关节,并且存在关节角度、角速度等限制条件,非常适合用二次规划方法来进行优化求解

image.png


数学算例

接下来我们举一个简单的数学算例,和如何用MindOpt优化求解器进行求解。

二次规划问题示例:

image.png


Python+MindOpt代码实现

核心的用的几个APIs是:

model=MdoModel()
model.set_int_attr(MDO_INT_ATTR.MIN_SENSE, 1)
model.set_quadratic_elements([ x[0], x[1], x[1], x[2], x[3] ], [ x[0], x[0], x[1], x[2], x[3] ], [  1.0,  0.5,  1.0,  1.0,  1.0 ]
model.solve_prob()
model.display_results()

下面是完整的例子,假设它命名为test_QP.py

# 引入python包frommindoptpyimport*if__name__=="__main__":
MDO_INFINITY=MdoModel.get_infinity()
# Step 1. 创建模型并更改参数。model=MdoModel()
try:
# Step 2.  输入模型# 改为最小化问题。# 通过 mindoptpy.MdoModel.set_int_attr() 将目标函数设置为 最小化model.set_int_attr(MDO_INT_ATTR.MIN_SENSE, 1)
# 添加变量。# 调用 mindoptpy.MdoModel.add_var() 来添加四个优化变量,# 定义其下界、上界、名称和类型x= []
x.append(model.add_var(0.0,         10.0, 1.0, None, "x0", False))
x.append(model.add_var(0.0, MDO_INFINITY, 1.0, None, "x1", False))
x.append(model.add_var(0.0, MDO_INFINITY, 1.0, None, "x2", False))
x.append(model.add_var(0.0, MDO_INFINITY, 1.0, None, "x3", False))
# 添加约束。# 注意这里的非零元素是按行顺序输入的。model.add_cons(1.0, MDO_INFINITY, 1.0*x[0] +1.0*x[1] +2.0*x[2] +3.0*x[3], "c0")
model.add_cons(1.0,          1.0, 1.0*x[0]              -1.0*x[2] +6.0*x[3], "c1")
# 添加二次目标矩阵 Q。##  注意。#  1. 目标函数定义为c^Tx + 1/2 x^TQx,其中Q以坐标格式存储。#  2. Q 将在内部缩放 1/2。#  3. 为了保证Q的对称性,用户只需要输入下三角部分。## Q = [ 1.0  0.5  0    0   ]#     [ 0.5  1.0  0    0   ]#     [ 0.0  0.0  1.0  0   ]#     [ 0    0    0    1.0 ]# 调用 mindoptpy.MdoModel.set_quadratic_elements() 来设置目标的二次项系数 model.set_quadratic_elements([ x[0], x[1], x[1], x[2], x[3] ], [ x[0], x[0], x[1], x[2], x[3] ], [  1.0,  0.5,  1.0,  1.0,  1.0 ])
# Step 3. 解决问题并填充结果。# 调用 mindoptpy.MdoModel.solve_prob() 求解优化问题,# 并用 mindoptpy.MdoModel.display_results() 来查看优化结果model.solve_prob()
model.display_results()
# 调用 mindoptpy.MdoModel.get_status() 来检查求解器的优化状态,# 并通过 mindoptpy.MdoModel.get_real_attr() 和 # mindoptpy.MdoVar.get_real_attr() 来获取目标值和最优解。status_code, status_msg=model.get_status()
ifstatus_msg=="OPTIMAL":
print("Optimizer terminated with an OPTIMAL status (code {0}).".format(status_code))
print("Primal objective : {0}".format(round(model.get_real_attr(MDO_REAL_ATTR.PRIMAL_OBJ_VAL), 2)))
forcurr_xinx:
print(" - x[{0}]          : {1}".format(curr_x.get_index(), round(curr_x.get_real_attr(MDO_REAL_ATTR.PRIMAL_SOLN), 2)))
else:
print("Optimizer terminated with a(n) {0} status (code {1}).".format(status_msg, status_code))
exceptMdoErrorase:
print("Received Mindopt exception.")
print(" - Code          : {}".format(e.code))
print(" - Reason        : {}".format(e.message))
exceptExceptionase:
print("Received exception.")
print(" - Reason        : {}".format(e))
finally:
# Step 4. 释放模型。model.free_mdl()

MindOpt求解的结果

运行代码,比如在命令行中执行python test_QP.py,得到的结果如下所示。(#号后面是小编的注解)

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] #obj范围-Matrixrange       : [1.0e+00,6.0e+00] #矩阵范围Presolverstarted.
Presolverterminated. Time : 0.000sInteriorpointmethodstarted.
IterPrimObjDualObjPrimFeaDualFeaGapFeaMuTime0+5.21950421e+01-5.93593455e+011.3e+008.0e-012.1e+001.5e+010.01s1+5.75093325e+00-3.28624247e+003.2e-022.0e-022.8e+001.5e+000.01s2+1.19681205e+00+1.03397025e-048.1e-043.7e-031.2e+002.0e-010.01s3+6.52164783e-01+3.52420863e-011.7e-043.7e-033.0e-014.9e-020.01s4+4.65540318e-01+4.35143347e-014.2e-069.3e-053.0e-025.1e-030.01s5+4.40907312e-01+4.39861230e-011.0e-072.3e-061.0e-031.7e-040.01s6+4.40022716e-01+4.39996554e-012.6e-095.8e-082.6e-054.4e-060.01s7+4.40000569e-01+4.39999914e-016.5e-111.5e-096.6e-071.1e-070.01s8+4.40000014e-01+4.39999998e-011.6e-123.7e-111.6e-082.7e-090.01s9+4.40000000e-01+4.40000000e-014.1e-149.1e-134.1e-106.9e-110.01sTerminated.
-Method             : Interiorpointmethod. #内点法-Primalobjective   : 4.3999999966807E-01-Dualobjective     : 4.3999999996074E-01-Num. threads       : 1-Num. iterations    : 9-Solverdetails     : Solverterminatedwithaprimal/dualoptimalstatus.
Interiorpointmethodterminated. Time : 0.010sOptimizerterminatedwithanOPTIMALstatus (code1).
Primalobjective : 0.44-x[0]          : 0.0-x[1]          : 0.0-x[2]          : 0.2# 决策变量的最佳取值-x[3]          : 0.2Optimizersummary.
-Optimizerused     : Interiorpointmethod-Optimizerstatus   : OPTIMAL-Totaltime         : 0.010sSolutionsummary.       Primalsolution#目标函数最优解-Objective          : 4.3999999967e-01

联系我们

钉钉群号:32451444

邮箱地址:solver.damo@list.alibaba-inc.com

更多更新通知:https://solver.damo.alibaba.com

相关文章
|
2月前
|
机器学习/深度学习 算法 数据可视化
【BetterBench博士】2024年中国研究生数学建模竞赛 C题:数据驱动下磁性元件的磁芯损耗建模 问题分析、数学模型、python 代码
2024年中国研究生数学建模竞赛C题聚焦磁性元件磁芯损耗建模。题目背景介绍了电能变换技术的发展与应用,强调磁性元件在功率变换器中的重要性。磁芯损耗受多种因素影响,现有模型难以精确预测。题目要求通过数据分析建立高精度磁芯损耗模型。具体任务包括励磁波形分类、修正斯坦麦茨方程、分析影响因素、构建预测模型及优化设计条件。涉及数据预处理、特征提取、机器学习及优化算法等技术。适合电气、材料、计算机等多个专业学生参与。
1662 17
【BetterBench博士】2024年中国研究生数学建模竞赛 C题:数据驱动下磁性元件的磁芯损耗建模 问题分析、数学模型、python 代码
|
2月前
|
机器学习/深度学习 数据采集 算法
【BetterBench博士】2024华为杯C题:数据驱动下磁性元件的磁芯损耗建模 Python代码实现
本文介绍了2024年中国研究生数学建模竞赛C题的详细分析,涵盖数据预处理、特征提取、模型训练及评估等多个方面。通过对磁通密度数据的处理,提取关键特征并应用多种分类算法进行波形分类。此外,还探讨了斯坦麦茨方程及其温度修正模型的应用,分析了温度、励磁波形和磁芯材料对磁芯损耗的影响,并提出了优化磁芯损耗与传输磁能的方法。最后,提供了B站视频教程链接,供进一步学习参考。
153 6
【BetterBench博士】2024华为杯C题:数据驱动下磁性元件的磁芯损耗建模 Python代码实现
|
1月前
|
开发者 Python
Python类和子类的小示例:建模农场
Python类和子类的小示例:建模农场
|
1月前
|
算法 安全 Go
Python与Go语言中的哈希算法实现及对比分析
Python与Go语言中的哈希算法实现及对比分析
40 0
|
3月前
|
JSON 数据格式 Python
python中有哪些常用语言成分?
Python作为一种广泛使用的编程语言,其语言成分丰富多样,涵盖了多个方面。
60 9
|
3月前
|
数据建模 大数据 数据库
【2023年4月美赛加赛】Y题:Understanding Used Sailboat Prices 建模思路、建模方案、数据来源、相关资料、Python代码
本文提供了2023年MCM问题Y的解题思路、建模方案、数据来源、相关资料以及Python代码,旨在建立数学模型解释二手帆船的挂牌价格,并分析地区对价格的影响,以及在香港(SAR)市场上的应用。
42 1
【2023年4月美赛加赛】Y题:Understanding Used Sailboat Prices 建模思路、建模方案、数据来源、相关资料、Python代码
|
3月前
|
机器学习/深度学习 人工智能 文字识别
轻松识别文字,这款Python OCR库支持超过80种语言
轻松识别文字,这款Python OCR库支持超过80种语言
|
3月前
|
机器学习/深度学习 搜索推荐 数据可视化
【2023年第十一届泰迪杯数据挖掘挑战赛】C题:泰迪内推平台招聘与求职双向推荐系统构建 建模及python代码详解 问题二
本文介绍了2023年第十一届泰迪杯数据挖掘挑战赛C题的解决方案,重点讲解了如何构建招聘与求职双向推荐系统的建模过程和Python代码实现,并对招聘信息和求职者信息进行了详细分析和画像构建。
77 1
|
3月前
|
机器学习/深度学习 数据可视化 数据挖掘
为啥我敢说Python是数据分析界的扛把子语言?
为啥我敢说Python是数据分析界的扛把子语言?
|
3月前
|
Rust JavaScript Java
简单对比Java、Python、Go、Rust等常见语言计算斐波拉契数的性能
简单对比Java、Python、Go、Rust等常见语言计算斐波拉契数的性能