c++ - 无法为我的非凸 QP 获得对偶值

Question

如何让 CPLEX 求解二次规划中的对偶值？目前给我的错误是我的程序是混合整数，而实际上它不是。我想出了一个简单的例子如下:最大 z = x^2 + 2x + ys.t 0 <= x <= 10； 0 <= 是 <= 10

下面是我在 cplex c++ 中的代码:

IloEnv env;

IloNumVar x(env, 0, IloInfinity);
IloNumVar y(env, 0, IloInfinity);

IloExpr obj(env);
obj = x*x + 2*x + y;

IloModel model(env);
model.add(IloMaximize(env,obj));

IloRange r1(env, 0, x, 10);
IloRange r2(env, 0, y, 10);

model.add(r1);
model.add(r2);

IloCplex cplex(model);
cplex.setOut(env.getNullStream());
cplex.setWarning(env.getNullStream());
cplex.setParam(IloCplex::Param::SolutionTarget,IloCplex::SolutionOptimalGlobal);

try{
    cplex.solve();
    env.out() << "x: " << cplex.getValue(x) << endl;
    env.out() << "y: " << cplex.getValue(y) << endl;
    env.out() << "Dual r1: " << cplex.getDual(r1) << endl;
    env.out() << "Dual r2: " << cplex.getDual(r2) << endl;  

    } catch (IloException& e) {
    std::cerr << "IloException: " << e << endl;
} catch (std::exception& e) {
    std::cerr << "Standard exception: " << e.what() << endl;
} catch (...) {
    std::cerr << "Some other exception!" << endl;
}

虽然 cplex 能够求解最优解，但它无法生成对偶值。错误消息是“Cplex 错误 1017:不适用于混合整数程序。

Answer 1

您没有指定您使用的是哪个版本的 CPLEX。让我试试最新的 12.9。这是您的问题:

$ cat foo.lp
Maximize
 obj1: 2 x + y + [ 2 x ^2 ] / 2
Subject To
 c1: x <= 10
 c2: y <= 10
End

下面是将 OptimalityTarget 参数设置为 3 时的 CPLEX 日志，正如您所做的那样，以获得全局最优解:

$ cplex -c "read foo.lp" "set optimalitytarget 3" "optimize"

Welcome to IBM(R) ILOG(R) CPLEX(R) Interactive Optimizer 12.9.0.0
  with Simplex, Mixed Integer & Barrier Optimizers
5725-A06 5725-A29 5724-Y48 5724-Y49 5724-Y54 5724-Y55 5655-Y21
Copyright IBM Corp. 1988, 2019.  All Rights Reserved.

Type 'help' for a list of available commands.
Type 'help' followed by a command name for more
information on commands.

CPLEX> Problem 'foo.lp' read.
Read time = 0.00 sec. (0.00 ticks)
CPLEX> New value for type of solution CPLEX will attempt to compute: 3
CPLEX> CPXPARAM_OptimalityTarget                        3
Warning: global optimality target changes problem type to MIQP.
Found incumbent of value 0.000000 after 0.00 sec. (0.00 ticks)
Tried aggregator 1 time.
MIQP Presolve eliminated 2 rows and 2 columns.
All rows and columns eliminated.
Presolve time = 0.00 sec. (0.00 ticks)

Root node processing (before b&c):
  Real time             =    0.00 sec. (0.00 ticks)
Parallel b&c, 4 threads:
  Real time             =    0.00 sec. (0.00 ticks)
  Sync time (average)   =    0.00 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =    0.00 sec. (0.00 ticks)

Solution pool: 2 solutions saved.

MIP - Integer optimal solution:  Objective =  1.3000000000e+02
Solution time =    0.00 sec.  Iterations = 0  Nodes = 0
Deterministic time = 0.00 ticks  (2.00 ticks/sec)

CPLEX>

您会注意到以下警告(您看不到它，因为您禁用了警告流):

Warning: global optimality target changes problem type to MIQP.

为了将非凸 QP 求解为全局最优，CPLEX 必须将该问题视为混合整数 QP。对偶值不适用于混合整数问题。

要为您的解决方案获得对偶值，您可以将问题转化为固定的 MIQP:将问题放宽为 QP，并将变量边界固定为现有解决方案。然后求局部最优(否则问题又会变成MIQP)，重新求解。这是它在交互式中的样子:

$ cplex129 -c "read foo.lp" "set optimalitytarget 3" "optimize" \
              "change problem fixed_miqp" "set optimalitytarget 2" \
              "optimize" "display solution dual *"

[...]

CPLEX> MIQP problem relaxed to QP with fixed integer variables using
incumbent solution.
CPLEX> New value for type of solution CPLEX will attempt to compute: 2
CPLEX> CPXPARAM_OptimalityTarget                        2
Note: Q in objective is not positive semi-definite.
Tried aggregator 1 time.
QP Presolve eliminated 2 rows and 2 columns.
All rows and columns eliminated.
Presolve time = 0.00 sec. (0.00 ticks)
Barrier time = 0.00 sec. (0.00 ticks)

Total time on 4 threads = 0.00 sec. (0.00 ticks)

Barrier - Optimal:  Objective =  1.3000000000e+02
Solution time =    0.00 sec.  Iterations = 0
Deterministic time = 0.00 ticks  (0.68 ticks/sec)

CPLEX> Constraint Name             Dual Price
c1                           22.000000
c2                            1.000000
CPLEX>