PICOS中的Minimax优化

我有一个关于如何使用Python中的PICOS包来解决Min-Max类型的优化问题的通用问题。在搜索PICOS documentation和网络时，我在这方面发现的信息很少。PICOS中的Minimax优化

我可以想象一个简单的例子，下面的表格。

给定一个矩阵M，求x * = argmin_x [MAX_Y的x^TM Y]，其中x> 0，Y> 0，和（X）= 1，和（Y）= 1

我已经尝试了几种方法，从PICOS Problem类的目标函数中具有minimax,minmax关键字的最直接的想法开始。事实证明，这些关键字都不是有效的，请参阅包documentation for objective functions。而且，嵌套的目标函数也是无效的。在我最后的天真尝试中，我有两个函数Max（）和Min（），它们都解决了线性优化问题。外部函数Min（）应该使内部函数Max（）最小化。所以，我在外部优化问题的目标函数中使用了Max（）。

import numpy as np 
import picos as pic 
import cvxopt as cvx 

def MinMax(mat): 
    ## Perform a simple min-max SDP formulated as: 
    ## Given a matrix M, find x* = argmin_x [ max_y x^T M y ], where x > 0, y > 0, sum(x) = sum(y) = 1. 

    prob = pic.Problem() 

    ## Constant parameters 
    M = pic.new_param('M', cvx.matrix(mat)) 
    v1 = pic.new_param('v1', cvx.matrix(np.ones((mat.shape[0], 1)))) 

    ## Variables 
    x = prob.add_variable('x', (mat.shape[0], 1), 'nonnegative') 

    ## Setting the objective function 
    prob.set_objective('min', Max(x, M)) 

    ## Constraints 
    prob.add_constraint(x > 0) 
    prob.add_constraint((v1 | x) == 1) 

    ## Print the problem 
    print("The optimization problem is formulated as follows.") 
    print prob 

    ## Solve the problem 
    prob.solve(verbose = 0) 

    objVal = prob.obj_value() 
    solution = np.array(x.value) 

    return (objVal, solution) 

def Max(xVar, M): 
    ## Given a vector l, find y* such that l y* = max_y l y, where y > 0, sum(y) = 1. 

    prob = pic.Problem() 

    # Variables 
    y = prob.add_variable('y', (M.size[1], 1), 'nonnegative') 
    v2 = pic.new_param('v1', cvx.matrix(np.ones((M.size[1], 1)))) 

    # Setting the objective function 
    prob.set_objective('max', ((xVar.H * M) * y)) 

    # Constraints 
    prob.add_constraint(y > 0) 
    prob.add_constraint((v2 | y) == 1) 

    # Solve the problem 
    prob.solve(verbose = 0) 

    sol = prob.obj_value() 

    return sol 


def print2Darray(arr): 
    # print a 2D array in a readable (matrix like) format on the standard output 
    for ridx in range(arr.shape[0]): 
     for cidx in range(arr.shape[1]): 
      print("%.2e \t" % arr[ridx,cidx]), 

     print("") 

    print("========") 

    return None 


if __name__ == '__main__': 
    ## Testing the Simple min-max SDP 
    mat = np.random.rand(4,4) 
    print("## Given a matrix M, find x* = argmin_x [ max_y x^T M y ], where x > 0, y > 0, sum(x) = sum(y) = 1.") 
    print("M = ") 
    print2Darray(mat) 
    (optval, solution) = MinMax(mat) 
    print("Optimal value of the function is %.2e and it is attained by x = %s and that of y = %.2e." % (optval, np.array_str(solution)))

当我运行上面的代码时，它给了我下面的错误信息。

10:stackoverflow pavithran$ python minmaxSDP.py 
## Given a matrix M, find x* = argmin_x [ max_y x^T M y ], where x > 0, y > 0, sum(x) = sum(y) = 1. 
M = 
1.46e-01 9.23e-01 6.50e-01 7.30e-01  
6.13e-01 6.80e-01 8.35e-01 4.32e-02  
5.19e-01 5.99e-01 1.45e-01 6.91e-01  
6.68e-01 8.46e-01 3.67e-01 3.43e-01  
======== 
Traceback (most recent call last): 
    File "minmaxSDP.py", line 80, in <module> 
    (optval, solution) = MinMax(mat) 
    File "minmaxSDP.py", line 19, in MinMax 
    prob.set_objective('min', Max(x, M)) 
    File "minmaxSDP.py", line 54, in Max 
    prob.solve(verbose = 0) 
    File "/Library/Python/2.7/site-packages/picos/problem.py", line 4135, in solve 
    self.solver_selection() 
    File "/Library/Python/2.7/site-packages/picos/problem.py", line 6102, in solver_selection 
    raise NotAppropriateSolverError('no solver available for problem of type {0}'.format(tp)) 
picos.tools.NotAppropriateSolverError: no solver available for problem of type MIQP 
10:stackoverflow pavithran$

在这一点上，我卡住了，无法解决这个问题。

难道只是PICOS本身不支持min-max问题或者是我对编码问题的方式不正确吗？

请注意：我坚持使用PICOS的原因是，理想情况下，我想知道在解决最小最大半定规划（SDP）时我的问题的答案。但是我认为一旦我能够弄清楚如何使用PICOS来做一个简单的最小 - 最大化问题，那么添加半定义约束并不难。

来源

2016-02-27 Pavithran Iyer

第一个答案是在PICOS中本机不支持min-max问题。然而，无论何时内部最大化问题是凸优化问题，您都可以将其重新表述为最小化问题（通过采用拉格朗日对偶问题），因此您会遇到最小问题。

你的具体问题是一个标准的零和游戏，并且可以再次阐述为：（假设M是尺寸n x m的）：

min_x max_{i=1...m} [M^T x]_i = min_x,t t s.t. [M^T x]_i <= t (for i=1...m)

在皮科斯德：

import picos as pic 
import cvxopt as cvx 

n=3 
m=4 
M = cvx.normal(n,m) #generate a random matrix 

P = pic.Problem() 
x = P.add_variable('x',n,lower=0) 
t = P.add_variable('t',1) 
P.add_constraint(M.T*x <= t) 
P.add_constraint((1|x) == 1) 
P.minimize(t) 
print 'the solution is x=' 
print x

如果您还需要最优y，那么你可以证明它对应于约束的最优值M'x <= t：

print 'the solution of the inner max-problem is y=' 
print P.constraints[0].dual

最好，纪尧姆。

来源

2016-07-04 14:48:07 guigux

PICOS中的Minimax优化

回答

相关问题