Минимаксная оптимизация в PICOS

У меня есть общий вопрос о том, как решить проблемы оптимизации типа Min-Max, используя пакет PICOS в Python. Я нашел мало информации в этом контексте при поиске в документации PICOS, а также в Интернете.

Я могу представить себе простой пример формы ниже.

Для матрицы M найдите x * = argmin_x [max_y x ^ T M y], где x> 0, y> 0, sum (x) = 1 и sum (y) = 1.

Я попробовал несколько методов, начиная с самой простой идеи наличия ключевых слов minimax, minmax в целевой функции класса PICOS Problem. Оказывается, ни одно из этих ключевых слов не является действительным, см. Документацию пакета для целевых функций. Более того, наличие вложенных целевых функций также оказывается недопустимым.

В последней из моих наивных попыток у меня есть две функции, 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, заключается в том, что в идеале я хотел бы знать ответ на свой вопрос в контексте решения полуопределенной программы min-max (SDP). Но я думаю, что добавление полуопределенных ограничений несложно, как только я смогу понять, как решить простую задачу min-max с помощью PICOS.


python optimization minmax cvxopt picos-api
person Pavithran Iyer    schedule 27.02.2016    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Первый ответ заключается в том, что задачи min-max изначально не поддерживаются в PICOS. Однако всякий раз, когда проблема внутренней максимизации является проблемой выпуклой оптимизации, вы можете переформулировать ее как задачу минимизации (взяв двойственный лагранжиан), и таким образом вы получите задачу min-min.

Ваша конкретная проблема - это стандартная игра с нулевой суммой, и ее можно переформулировать следующим образом: (при условии, что 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

Лучше, Гийом.

person guigux    schedule 04.07.2016