2
$\begingroup$

I'm trying to implement either one of these objective functions, but I'm having a hard time with the squared terms. I'm attaching both so you can take a look at the structure and see if you can give me any tips. Is there any way to implement either one of them?

1- Matrix notation:

enter image description here

$x$: decision variable

$1$: column of ones

$k$: squared matrix

2- Summation notation:

enter image description here

$x$: decision variable $m$: degree of the node i $rho$: parameter that takes into account the influence of the neighbors that surround node i $a$: terms of the adjacency matrix. Shows if nodes i and j are connected

Thank you in advance!

Improve this question
$\endgroup$
7
  • $\begingroup$ Hello and welcome to OR.SE. What are the $a_{il}$s and $m_i$s? $\endgroup$ – Oguz Toragay Jul 10 '20 at 19:18
  • 1
    $\begingroup$ Actually it would be good if you could explain all the notations... $\endgroup$ – Oguz Toragay Jul 10 '20 at 19:28
  • 1
    $\begingroup$ In what way are you having a hard time? Is the question how to code squared terms with either CPLEX or Gurobi (in which case you should specify what API you are using)? $\endgroup$ – prubin Jul 10 '20 at 20:26
  • 1
    $\begingroup$ @OguzToragay thank you for reaching out! I will edit the post with all the notations. $\endgroup$ – PoofyBridge Jul 12 '20 at 0:58
  • $\begingroup$ @prubin thanks for reaching out! yes, my problem is I don't know how to implement the second term of the objective function in the matrix notation since the term is squared. On the other hand, I tried implementing the second equation of the post, but I run into a memory error. I'm using Gurobi with Python. $\endgroup$ – PoofyBridge Jul 12 '20 at 1:05
4
$\begingroup$

It's relatively easy to write $(1^{T}Kx)^{2}$ in standard quadratic form.

Since $1^{T}Kx$ is a scalar,

$(1^{T}Kx)^{2}=(1^{T}Kx)(1^{T}Kx)^{T}=1^{T}Kxx^{T}K^{T}1$.

Using the cyclic property of the trace of a product of matrices,

$1^{T}Kxx^{T}K^{T}1=\mbox{tr}(1^{T}Kxx^{T}K^{T}1)=\mbox{tr}(x^{T}K^{T}11^{T}Kx)=x^{T}(K^{T}11^{T}K)x$.

Unfortunately, $K^{T}11^{T}K$ will be dense, so if $x$ is large you'll probably run out of storage.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.