PICOS中的Minimax优化 [英] Minimax optimization in PICOS
问题描述
我有一个通用的问题，关于如何使用Python中的PICOS包解决Min-Max类型的优化问题.在搜索 PICOS文档以及在网络上时，在这种情况下，我发现的信息很少. >
我可以想象下面形式的一个简单示例.
给定一个矩阵M，找到x * = argmin_x [max_y x ^ T M y]，其中x> 0，y> 0，sum(x)= 1和sum(y)= 1.
我尝试了几种方法，最直接的想法是在PICOS Problem类的目标函数中使用minimax，minmax关键字.事实证明，这些关键字都不有效，请参阅目标功能的包文档.此外，嵌套目标函数也被证明是无效的.
在我的最后一次幼稚尝试中，我有两个函数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本身不支持最小-最大问题，还是我编码问题的方式不正确?
请注意:我坚持使用PICOS的原因是，理想情况下，我想在解决最小-最大半确定程序(SDP)的背景下知道我的问题的答案.但是我认为一旦确定了如何使用PICOS做一个简单的最小-最大问题，添加半定约束并不难.
第一个答案是，PICOS本身不支持最小-最大问题.但是，只要内部最大化问题是凸优化问题，就可以将其重新构造为最小化问题(采用拉格朗日对偶)，因此您会遇到最小-最小问题.
您的特定问题是一个标准的零和游戏，可以将其重新表示为:(假设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)
在Picos中:
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
最好， 纪尧姆.
I have a generic question on how to solve optimization problems of the Min-Max type, using the PICOS package in Python. I found little information in this context while searching the PICOS documentation and on the web as well.
I can imagine a simple example of the below form.
Given a matrix M, find x* = argmin_x [ max_y x^T M y ], where x > 0, y > 0, sum(x) = 1 and sum(y) = 1.
I have tried a few methods, starting with the most straightforward idea of having minimax, minmax keywords in the objective function of PICOS Problem class. It turns out that none of these keywords are valid, see the package documentation for objective functions. Furthermore, having nested objective functions also turns out to be invalid.
In the last of my naive attempts, I have two functions, Max() and Min() which are both solving a linear optimization problem. The outer function, Min(), should minimize the inner function Max(). So, I have used Max() in the objective function of the outer optimization problem.
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)))
When I run the above code, it gives me the following error message.
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$
At this point, I am stuck and unable to fix this problem.
Is it just that PICOS does not natively support min-max problem or is my way of encoding the problem, incorrect?
Please note: The reason I am insisting on using PICOS is that ideally, I would like to know the answer to my question in the context of solving a min-max semidefinite program (SDP). But I think the addition of semidefinite constraints is not hard, once I can figure out how to do a simple min-max problem using PICOS.
The first answer is that min-max problems are not natively supported in PICOS. However, whenever the inner maximization problem is a convex optimization problem, you can reformulate it as a minimization problem (by taking the Lagrangian dual), and so you get a min-min problem.
Your particular problem is a standard zero-sum game, and can be reformulated as: (assuming M is of dimension 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)
In Picos:
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
If you also need the optimal y, then you can show that it corresponds to the optimal value of the constraint M'x <= t:
print 'the solution of the inner max-problem is y='
print P.constraints[0].dual
Best, Guillaume.
这篇关于PICOS中的Minimax优化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
