首页>软件资讯>常见问题

常见问题

Gurobi求解器中非线性约束的对偶值的获取:QCP、QCQP、SOCP | 以及求解器最优性理论证明

发布时间:2024-05-08 16:46:11人气:867

一、Gurobi中非线性约束的对偶值的获取

Gurobi中非线性约束的对偶值是可以成功获取的,但是在求解模型之前,需要将参数QCPDual设置为1.Gurobi 参考手册——QCPi

注意:如果打开参数QCPDual的话,求解器一般会来求解KKT 方程组来获得QCP的对偶变量。


下面是一个具体的例子。


from gurobipy import * 


# Create a new model

m = Model("QCQP")


# Create variables

x = m.addVar(lb = 0, vtype=GRB.CONTINUOUS , name="x")

y = m.addVar(lb = 0, vtype=GRB.CONTINUOUS , name="y")


# Set objective

m.setObjective (1/2 * x * x + y * y - x * y - 2 * x - 6 * y, GRB.MINIMIZE)


m.setParam('QCPDual', 1)


# Add constraints

m.addConstr(-x + 2 * y <= 2, "c0")

m.addConstr(x * x + 1/2 * y <= 2, "c1")

m.addConstr (2 * x + y <= 3, "c2")


 # Write model to file

m.write("QCQP.lp")


# Solve the model

m.optimize ()


for con in m.getConstrs():

    print(con.ConstrName, '----', con.Pi)


for con in m.getQConstrs():

    print(con.QCName, '----', con.QCPi) 


求解日志如下


Changed value of parameter QCPDual to 1

   Prev: 0  Min: 0  Max: 1  Default: 0

Gurobi Optimizer version 9.0.1 build v9.0.1rc0 (win64)

Optimize a model with 2 rows, 2 columns and 4 nonzeros

Model fingerprint: 0xb070fdc1

Model has 3 quadratic objective terms

Model has 1 quadratic constraint

Coefficient statistics:

  Matrix range     [1e+00, 2e+00]

  QMatrix range    [1e+00, 1e+00]

  QLMatrix range   [5e-01, 5e-01]

  Objective range  [2e+00, 6e+00]

  QObjective range [1e+00, 2e+00]

  Bounds range     [0e+00, 0e+00]

  RHS range        [2e+00, 3e+00]

  QRHS range       [2e+00, 2e+00]

Presolve time: 0.01s

Presolved: 8 rows, 8 columns, 16 nonzeros

Presolved model has 2 second-order cone constraints

Ordering time: 0.00s


Barrier statistics:

 AA' NZ     : 2.100e+01

 Factor NZ  : 3.600e+01

 Factor Ops : 2.040e+02 (less than 1 second per iteration)

 Threads    : 1


                  Objective                Residual

Iter       Primal          Dual         Primal    Dual     Compl     Time

   0  -1.49326539e+01 -4.35523979e+00  1.76e+00 3.70e+00  4.65e+00     0s

   1  -6.12239820e+00 -1.12395144e+01  1.94e-06 1.22e-01  5.19e-01     0s

   2  -8.53301014e+00 -8.99477729e+00  1.54e-07 1.02e-03  4.24e-02     0s

   3  -8.82682363e+00 -8.85269793e+00  3.11e-13 5.50e-06  2.35e-03     0s

   4  -8.83955816e+00 -8.84007974e+00  1.03e-13 4.22e-09  4.74e-05     0s

   5  -8.83999672e+00 -8.84000230e+00  3.74e-12 5.43e-11  5.08e-07     0s


Barrier solved model in 5 iterations and 0.02 seconds

Optimal objective -8.83999672e+00


Solving KKT system to obtain QCP duals...



c0 ---- -1.0799994965216462

c2 ---- -1.8399999978917783

c1 ---- -1.1253017667406413e-10

可以看到,日志中说


Solving KKT system to obtain QCP duals...

可见确实是通过求解KKT方程组获得的dual。


二、求解器结果最优性具体理论证明

之前有人在【运小筹读者2群】里问:cplex、gurobi和COPT求解器求解出来的一定是最优解吗?有理论证明什么的吗?


我给除了下面的回答,我觉得对大家会有用,因此稍加整理分享一下。


首先,对于MIP,给足求解时间,设置MIPGap的容差为0,最后得到的一定是最优解。


cplex、gurobi和COPT等求解器使用的是通用的branch and cut算法框架,该框架是精确算法框架。


一个最小化的MIP问题,其松弛问题,即线性松弛是其下界,任意一个可行解是上界。下界和上界的相对差距,就是间隙,optimality gap,简称gap,也就是求解日志最后一列。


求解MIP的分支切割算法,是将精确算法割平面算法融入到另一个精确算法:分支定界框架中。


分支定界本质上是一种分而治之的隐枚举,通过隐枚举,更新全局最优上界和全局最优下界,整个过程都可以保证最优性,通过搜索,最后达到全局最优。


割平面法用来割去小数最优解,并且收紧可行域,加速求解,逼近凸包。


最终整个框架的最优性,通过gap得到证明。gap就是当前解距离最优解的 最大可能的 相对差距。gap等于0,说明当前解一定是全局最优解。


具体理论证明,分为这么几个大的部分:以min问题为例

一个LP,如果可行,我们是可以通过单纯形法,或者内点法求解到最优解的,最优性通过检验数等相关内容可以得到证明。具体证明见单纯形法相关内容。

一个MIP的线性松弛是一个LP,这个LP的最优解,是MIP一个下界,这个MIP的最优解不可能比这个小。

任意一个整数可行解,一定是MIP的一个上界。MIP的最优解一定小于等于这个可行解。

分支定界算法,通过隐枚举,更新全局上界和下界,一定可以保证最后得到最优解。具体证明见分支定界的全局上界和下界的证明。

割平面法,不会割去任何整数可行解。因此割平面法的使用,不会影响最优性,只是加速作用。

以上5个部分各自的证明,可以详细去看,我只是说了结论。以上5个部分,是cplex,gurobi等求解器求解MIP的算法框架branch and cut的主要内容,这每一个内容都有非常完善的理论证明以及最优性保障,综合起来,这个算法框架就是精确算法框架。如果模型有可行解,并且给足足够的求解时间,求解器100%可以保证得到最终的最优解。




上一条:Gurobi求解器中文官网

下一条:Gurobi并行计算的设置和操作