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優化

回答

相關問題