R中受线性等式和不等式约束的二次目标函数最大化

Question

我试图找到如何在R中最大化具有等式和不等式约束的二次函数：

最大化x’*H*x
根据以下条件：

问题的简化版本可以是

最大化x^2 y^2，根据x y=1和x，y

由于这是一个最大化问题，我无法使用solve。quadprog包中的QP功能。

我也尝试过使用constrOptim。但请注意，有一个等式约束，constrOptim需要对可行区域的内部进行初始猜测。因此，constrOptim不能用于等式约束。

我也尝试在阿拉巴马州的软件包中使用auglag。但我似乎没有找到最大化问题的正确答案。

如果问题是最小化问题，那么简单问题的答案是x=0.5，y=0.5。auglag和solve。QP给我这个答案。

但是我正在寻找最大化问题的解决方案。几何的答案是（x=1和y=0）OR（x=0和y=1）。




Answer 1

如果可用软件可以处理非凸目标，则可以解决此问题。两点：

1. 要绕过非线性等式约束的问题，可以执行以下操作

Answer 2

这不是一个完整的答案，但可能会向您展示一些替代的算法方法。

这个问题似乎没有covex，这使得它很难解决（并且限制了可用的好软件的数量）。

正如Christoph在评论中提到的，一般非线性优化是一种可能的方法。当然，我们失去了关于全局最优解决方案的保证。在内部使用优秀的开源软件ipopt将是一次很好的尝试。

你可以考虑一下凸凹规划（它可以全局解决一些简单的问题），它有一个非常有效的启发式方法，叫做凸凹过程（Yuille，Alan L.，and Anand Rangarajan，“凸凹过程”神经计算15.4（2003）：915-936 ），它应该比更一般的非线性方法工作得更好。

我不确定是否有一种在R中做到这一点的好方法（无需手动操作），但在Python中有非常现代的开源研究库dccp（基于cvxpy）。

from cvxpy import *
import dccp
from dccp.problem import is_dccp

x = Variable(1)
y = Variable(1)
constraints = [x >= 0, y >= 0, x+y == 1]
objective = Maximize(square(x) + square(y))
problem = Problem(objective, constraints)

print("problem is DCP:", problem.is_dcp())
print("problem is DCCP:", is_dccp(problem))

problem.solve(method='dccp')

print('solution (x,y): ', x.value, y.value)

('problem is DCP:', False)
('problem is DCCP:', True)
iteration= 1 cost value =  -2.22820497851 tau =  0.005
iteration= 2 cost value =  0.999999997451 tau =  0.006
iteration= 3 cost value =  0.999999997451 tau =  0.0072
('solution (x,y): ', 0.99999999872569856, 1.2743612156911721e-09)

根据问题的大小（小），您也可以尝试全局非线性解算器，如couenne。

from pyomo.environ import *

model = ConcreteModel()

model.x = Var()
model.y = Var()

model.xpos = Constraint(expr = model.x >= 0)
model.ypos = Constraint(expr = model.y >= 0)
model.eq = Constraint(expr = model.x + model.y == 1)
model.obj = Objective(expr = model.x**2 + model.y**2, sense=maximize)

model.preprocess()

solver = 'couenne'
solver_io = 'nl'
stream_solver = True     # True prints solver output to screen
keepfiles =     True    # True prints intermediate file names (.nl,.sol,...)
opt = SolverFactory(solver,solver_io=solver_io)
results = opt.solve(model, keepfiles=keepfiles, tee=stream_solver)

print("Print values for all variables")
for v in model.component_data_objects(Var):
  print str(v), v.value

Couenne 0.5.6 -- an Open-Source solver for Mixed Integer Nonlinear Optimization
Mailing list: [e-mail]
Instructions: http://www.coin-or.org/Couenne

Couenne: new cutoff value -1.0000000000e+00 (0.004 seconds)
NLP0012I 
              Num      Status      Obj             It       time                 Location
NLP0014I             1         OPT -0.5        6 0.004
Loaded instance "/tmp/tmpLwTNz1.pyomo.nl"
Constraints:            3
Variables:              2 (0 integer)
Auxiliaries:            3 (0 integer)

Coin0506I Presolve 11 (-1) rows, 4 (-1) columns and 23 (-2) elements
Clp0006I 0  Obj -0.9998 Primal inf 4.124795 (5) Dual inf 0.999999 (1)
Clp0006I 4  Obj -1
Clp0000I Optimal - objective value -1
Clp0032I Optimal objective -1 - 4 iterations time 0.002, Presolve 0.00
Clp0000I Optimal - objective value -1
NLP Heuristic: NLP0014I             2         OPT -1        5 0
no solution.
Clp0000I Optimal - objective value -1
Optimality Based BT: 0 improved bounds
Probing: 0 improved bounds
NLP Heuristic: no solution.
Cbc0013I At root node, 0 cuts changed objective from -1 to -1 in 1 passes
Cbc0014I Cut generator 0 (Couenne convexifier cuts) - 0 row cuts average 0.0 elements, 2 column cuts (2 active)
Cbc0004I Integer solution of -1 found after 0 iterations and 0 nodes (0.00 seconds)
Cbc0001I Search completed - best objective -1, took 0 iterations and 0 nodes (0.01 seconds)
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost

couenne: Optimal

    "Finished"

Linearization cuts added at root node:         12
Linearization cuts added in total:             12  (separation time: 0s)
Total solve time:                           0.008s (0.008s in branch-and-bound)
Lower bound:                                   -1
Upper bound:                                   -1  (gap: 0.00%)
Branch-and-bound nodes:                         0
Print values for all variables
x 0.0
y 1.0