Usbrth

Need a suitable toxic chemical for a murder plot in my novel

New Order #5: where Fibonacci and Beatty meet at Wythoff

How can players take actions together that are impossible otherwise?

Who can trigger ship-wide alerts in Star Trek?

Complexity of many constant time steps with occasional logarithmic steps

90's book, teen horror

Can smartphones with the same camera sensor have different image quality?

How to rotate it perfectly?

What would be Julian Assange's expected punishment, on the current English criminal law?

How to set letter above or below the symbol?

3 doors, three guards, one stone

How to say that you spent the night with someone, you were only sleeping and nothing else?

Windows 10: How to Lock (not sleep) laptop on lid close?

What LEGO pieces have "real-world" functionality?

Why is there no army of Iron-Mans in the MCU?

When is phishing education going too far?

Can I throw a longsword at someone?

Cauchy Sequence Characterized only By Directly Neighbouring Sequence Members

What do I do if technical issues prevent me from filing my return on time?

Statistical model of ligand substitution

What was the last x86 CPU that did not have the x87 floating-point unit built in?

Did the new image of black hole confirm the general theory of relativity?

Is above average number of years spent on PhD considered a red flag in future academia or industry positions?

How to politely respond to generic emails requesting a PhD/job in my lab? Without wasting too much time

Simplification of a Quadratically constrained, Quadratic objective (to apply Semidefinite relaxation)

2

$begingroup$

I came up with the following optimization problem:

$$argmax_G_i quad G_1^TI^TIG_1 + ...+G_N^TI^TIG_N$$
subject to:
$$|G_i|_2^2=1 quad forall i$$
$$|G_i-G_o_i|_2^2leq c quad forall i$$
$$|G_i^TG_j|leqepsilon quad forall i,j,ineq j quad$$
$$sum_j=1^n G_i(j)=0 quad forall i,j,ineq j quad$$
where $G_i in R^n$.

Is there any way to somehow factor out $I^TI$ and convert it to semidefinite programming problem? how could I use semidefinite Relaxation for this problem?

I tried to use semidefinite relaxation, but the second and third constraints are hard to deal with for me:

Let:
$$C=I^TI, X_i=G_iG_i^T$$

Now we can rewrite the problem as:
$$argmax_X_i quad sum_i=1^N tr(CX_i) $$
subject to:
$$tr(X_i)=1 quad forall i$$
$$X_isucceq 0 quad forall i$$
$$Rank(X_i)=1 quad forall i$$
$$|G_i-G_o_i|_2^2leq c quad forall i$$
$$|G_i^TG_j|leqepsilon quad forall i,j,ineq j quad$$
$$sum_j=1^n G_i(j)=0 quad forall i,j,ineq j quad$$

But I don't know how to rewrite last two constraints based on $X_i$.
Update: Let $[G_i;1]^T$ as the new variable for the problem, the second constraint could be homogenized. But still the third and forth constraints, I don't know how to write them based on new variable.

optimization quadratic-programming non-convex-optimization semidefinite-programming relaxations

share|cite|improve this question

edited Apr 11 at 21:48

Panda

asked Apr 8 at 20:18

PandaPanda

3791619

$endgroup$

This question has an open bounty worth +50
reputation from Panda ending ending at 2019-04-18 21:42:51Z">in 4 days.

This question has not received enough attention.

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  What exactly is $I$?
  $endgroup$
  – Rodrigo de Azevedo
  Apr 9 at 8:00
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  Your problem is the nonconvex quadratic equality constraint and the final nonconvex bilinear constraint, not the objective which is a convex quadratic
  $endgroup$
  – Johan Löfberg
  Apr 9 at 10:27
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @RodrigodeAzevedo $I$ is a $m*n$ matrix, so $I^TI$ has the dimension $n*n$
  $endgroup$
  – Panda
  Apr 9 at 13:37
  
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  Draw the feasible set for the constraint $x^2 = 1$ where $x$ is a scalar...
  $endgroup$
  – Johan Löfberg
  Apr 9 at 14:15
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  and no, these are intrinsically nonconvex sets
  $endgroup$
  – Johan Löfberg
  Apr 9 at 14:16
  
  

  
  
  
  

 | 
show 3 more comments

2

$begingroup$

I came up with the following optimization problem:

$$argmax_G_i quad G_1^TI^TIG_1 + ...+G_N^TI^TIG_N$$
subject to:
$$|G_i|_2^2=1 quad forall i$$
$$|G_i-G_o_i|_2^2leq c quad forall i$$
$$|G_i^TG_j|leqepsilon quad forall i,j,ineq j quad$$
$$sum_j=1^n G_i(j)=0 quad forall i,j,ineq j quad$$
where $G_i in R^n$.

Is there any way to somehow factor out $I^TI$ and convert it to semidefinite programming problem? how could I use semidefinite Relaxation for this problem?

I tried to use semidefinite relaxation, but the second and third constraints are hard to deal with for me:

Let:
$$C=I^TI, X_i=G_iG_i^T$$

Now we can rewrite the problem as:
$$argmax_X_i quad sum_i=1^N tr(CX_i) $$
subject to:
$$tr(X_i)=1 quad forall i$$
$$X_isucceq 0 quad forall i$$
$$Rank(X_i)=1 quad forall i$$
$$|G_i-G_o_i|_2^2leq c quad forall i$$
$$|G_i^TG_j|leqepsilon quad forall i,j,ineq j quad$$
$$sum_j=1^n G_i(j)=0 quad forall i,j,ineq j quad$$

But I don't know how to rewrite last two constraints based on $X_i$.
Update: Let $[G_i;1]^T$ as the new variable for the problem, the second constraint could be homogenized. But still the third and forth constraints, I don't know how to write them based on new variable.

optimization quadratic-programming non-convex-optimization semidefinite-programming relaxations

share|cite|improve this question

edited Apr 11 at 21:48

Panda

asked Apr 8 at 20:18

PandaPanda

3791619

$endgroup$

This question has an open bounty worth +50
reputation from Panda ending ending at 2019-04-18 21:42:51Z">in 4 days.

This question has not received enough attention.

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  What exactly is $I$?
  $endgroup$
  – Rodrigo de Azevedo
  Apr 9 at 8:00
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  Your problem is the nonconvex quadratic equality constraint and the final nonconvex bilinear constraint, not the objective which is a convex quadratic
  $endgroup$
  – Johan Löfberg
  Apr 9 at 10:27
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @RodrigodeAzevedo $I$ is a $m*n$ matrix, so $I^TI$ has the dimension $n*n$
  $endgroup$
  – Panda
  Apr 9 at 13:37
  
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  Draw the feasible set for the constraint $x^2 = 1$ where $x$ is a scalar...
  $endgroup$
  – Johan Löfberg
  Apr 9 at 14:15
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  and no, these are intrinsically nonconvex sets
  $endgroup$
  – Johan Löfberg
  Apr 9 at 14:16
  
  

  
  
  
  

 | 
show 3 more comments

$begingroup$

I came up with the following optimization problem:

$$argmax_G_i quad G_1^TI^TIG_1 + ...+G_N^TI^TIG_N$$
subject to:
$$|G_i|_2^2=1 quad forall i$$
$$|G_i-G_o_i|_2^2leq c quad forall i$$
$$|G_i^TG_j|leqepsilon quad forall i,j,ineq j quad$$
$$sum_j=1^n G_i(j)=0 quad forall i,j,ineq j quad$$
where $G_i in R^n$.

Is there any way to somehow factor out $I^TI$ and convert it to semidefinite programming problem? how could I use semidefinite Relaxation for this problem?

I tried to use semidefinite relaxation, but the second and third constraints are hard to deal with for me:

Let:
$$C=I^TI, X_i=G_iG_i^T$$

Now we can rewrite the problem as:
$$argmax_X_i quad sum_i=1^N tr(CX_i) $$
subject to:
$$tr(X_i)=1 quad forall i$$
$$X_isucceq 0 quad forall i$$
$$Rank(X_i)=1 quad forall i$$
$$|G_i-G_o_i|_2^2leq c quad forall i$$
$$|G_i^TG_j|leqepsilon quad forall i,j,ineq j quad$$
$$sum_j=1^n G_i(j)=0 quad forall i,j,ineq j quad$$

But I don't know how to rewrite last two constraints based on $X_i$.
Update: Let $[G_i;1]^T$ as the new variable for the problem, the second constraint could be homogenized. But still the third and forth constraints, I don't know how to write them based on new variable.

optimization quadratic-programming non-convex-optimization semidefinite-programming relaxations

share|cite|improve this question

edited Apr 11 at 21:48

Panda

asked Apr 8 at 20:18

PandaPanda

3791619

$endgroup$

share|cite|improve this question

edited Apr 11 at 21:48

Panda

asked Apr 8 at 20:18

PandaPanda

3791619

share|cite|improve this question

edited Apr 11 at 21:48

Panda

asked Apr 8 at 20:18

PandaPanda

3791619

asked Apr 8 at 20:18

PandaPanda

3791619

asked Apr 8 at 20:18

PandaPanda

3791619