Как создать ограничение неравенства для внутреннего произведения двух столбцов в CVXPY?

Question

Предположим, мое ограничение - произведение первого столбца, а третий столбец матричной переменной больше единицы. Как я могу реализовать в CVXPY? Пример:

w = Variable(4,3) 

В Matlab мое ограничение будет:

w(:,1)'*w(:,3)>1

Как я могу реализовать это в CVXPY? Или мы можем выполнить точечное произведение под CVXPY? numpy.dot не поддерживается CVXPY.

Answer 1

Если обе переменные положительны, то множество {x * y > 1} на самом деле выпуклый, в то время как функция x*y не является ни выпуклым, ни вогнутым. Это можно проверить, посмотрев на собственные значения матрицы вторых производных

(x*y)'' = 
[[0, 1],
 [1, 0]]

которые {-1, 1}, Матрица не является положительно определенной и не является отрицательно определенной.

Иногда вы можете преобразовать проблему так, чтобы она стала выпуклой. В этом случае это возможно, взяв логарифм обеих сторон:

log(x) + log(y) >= 0

это допустимое ограничение, так как и log(x), и log(y) являются вогнутыми функциями, а неравенство больше или равно. Это ограничение пройдет правила "дисциплинированного выпуклого программирования". Удачи.

Answer 2

Невозможно умножить две переменные, все ограничения должны быть линейными (в общем случае DCP).

CVXPY вызывает DCPError, если вы пытаетесь выполнить запрещенную операцию.

import cvxpy
x = cvxpy.Variable()
y = cvxpy.Variable()
constraints = [x*y > 1]

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "C:\Python27\lib\site-packages\cvxpy\expressions\expression.py", line 43, in cast_op
    return binary_op(self, other)
  File "C:\Python27\lib\site-packages\cvxpy\expressions\expression.py", line 226, in __mul__
    raise DCPError("Cannot multiply two non-constants.")
cvxpy.error.DCPError: Cannot multiply two non-constants.

Вы можете использовать переменную slack, чтобы избежать этого, если хотя бы одна переменная является целочисленной / логической. В противном случае вы можете использовать любой нелинейный решатель, например, IPOPT.

На этот же вопрос ответили здесь.

Answer 3

У вас есть строгое ограничение неравенства на северо-восточном элементе матрицы Грама Q := W.T * W, который является симметричным и положительным полуопределенным. Следовательно, работайте с матрицей Грама Q вместо этого, а затем ввести строгое ограничение неравенства Q[0,2] > 1,

Например, вот полуопределенная программа (SDP) с нулевой целью:

>>> from cvxpy import *
>>> Q = Semidef(3)
>>> objective = Minimize(0)
>>> constraints = [ Q[0,2] > 1 ]
>>> prob = Problem(objective,constraints)
>>> prob.solve()
0.0
>>> Q.value
matrix([[  2.33101529e+00,   2.57980002e-30,   1.76709537e+00],
        [  2.57980002e-30,   2.57740598e-15,  -2.00304682e-30],
        [  1.76709537e+00,  -2.00304682e-30,   2.33101529e+00]])

Обратите внимание, что северо-восточная запись 1.76709537e+00 > 1, Восстановить матрицу W из матрицы Грамма Qиспользуйте разложение Холецкого и добавьте ряд нулей, чтобы получить матрицу 4 x 3 следующим образом:

>>> import numpy as np
>>> L = np.linalg.cholesky(Q.value)
>>> W = (np.insert(L, 3, np.array([0,0,0]), axis=1)).T
>>> W
matrix([[  1.52676628e+00,   1.68971508e-30,   1.15741053e+00],
        [  0.00000000e+00,   5.07681591e-08,  -7.79768444e-23],
        [  0.00000000e+00,   0.00000000e+00,   9.95698832e-01],
        [  0.00000000e+00,   0.00000000e+00,   0.00000000e+00]])

Позвольте нам проверить:

>>> W.T * W - Q.value
matrix([[  0.00000000e+00,   0.00000000e+00,   0.00000000e+00],
        [  0.00000000e+00,   0.00000000e+00,   7.00649232e-46],
        [  0.00000000e+00,   7.00649232e-46,   0.00000000e+00]])