Fdtxjr

Are cabin dividers used to "hide" the flex of the airplane?

What does 'script /dev/null' do?

What does "enim et" mean?

How would photo IDs work for shapeshifters?

If a centaur druid Wild Shapes into a Giant Elk, do their Charge features stack?

Why did the Germans forbid the possession of pet pigeons in Rostov-on-Don in 1941?

Is it legal to have the "// (c) 2019 John Smith" header in all files when there are hundreds of contributors?

Where else does the Shulchan Aruch quote an authority by name?

Need help identifying/translating a plaque in Tangier, Morocco

Finding files for which a command fails

Is Social Media Science Fiction?

Is domain driven design an anti-SQL pattern?

Are white and non-white police officers equally likely to kill black suspects?

Is "plugging out" electronic devices an American expression?

How did the USSR manage to innovate in an environment characterized by government censorship and high bureaucracy?

Why do UK politicians seemingly ignore opinion polls on Brexit?

How is it possible for user's password to be changed after storage was encrypted? (on OS X, Android)

What is the meaning of "of trouble" in the following sentence?

What is GPS' 19 year rollover and does it present a cybersecurity issue?

"My colleague's body is amazing"

I see my dog run

What happens when a metallic dragon and a chromatic dragon mate?

COUNT(*) or MAX(id) - which is faster?

Symmetry in quantum mechanics

“Convert” quadratic constraint to quadratic objective

Linear programming with one quadratic equality constraintHow to linearize a quadratic objective function with linear constraints?Minimizing quadratic objective function on the unit $ell_1$ sphereLasso with non-linear objectiveLinear objective function with quadratic constraintsIs it possible to delete a constraint after replacing it in another constraint?Optimization problem with quadratic objective and a bilinear constraintOptimization of linear objective with non-convex quadratic constraintMinimizing quadratic objective subject to a quadratic equality constraintRank-dependent constraints in linear programming

1

$begingroup$

I have a large sparse quadratic optimization problem with a single quadratic constraint:

$$beginarrayll textmaximize & c'x\ textsubject to & l leq Ax leq u\ & x'Qx + b'x leq u_qendarray$$

where

• $x = (x_1, x_2, dots, x_n)'$.




• $A$ is a $k times n$ matrix of linear constraint coefficients.




• $l$ and $u$ are $k times 1$ vectors of lower and upper bounds, respectively.




• $Q$ is a $n times n$ positive definite matrix.




• $b$ is a $n times 1$ vector.




• $u_q$ is a scalar.

The solver I am using can handle quadratic objective function but only linear constraints. I was wondering if there is a way to reformulate the problem as:

$$beginarrayll textminimize & hat c'x + x'hat Qx\ textsubject to & hat l leq hat Ax leq hat u\endarray$$

optimization convex-analysis convex-optimization constraints qclp

share|cite|improve this question

edited Mar 25 at 9:58

user10203644

asked Mar 22 at 14:43

user10203644user10203644

83

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  If you actually have the inequality constraint with $l_q$, I do not believe so. But if you do not, then it might be possible.
  $endgroup$
  – Alex Shtof
  Mar 22 at 17:20
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Since $Q$ is positive definite, try to convert $x'Qx + b'x$ to something like $(x-c)' M (x - c)$. Then make $y := x - c$ and work with $y$.
  $endgroup$
  – Rodrigo de Azevedo
  Mar 23 at 5:05
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  This is a non-convex problem because the constraint $ l_q leq x'Qx + b'x $ is not convex. I think it should be reformulatable as a Mixed-Integer QP (MIQP).
  $endgroup$
  – Mark L. Stone
  Mar 23 at 19:37
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Apologies, there is no $l_q$ bound actually. Edited the problem setup now.
  $endgroup$
  – user10203644
  Mar 25 at 9:51
  

  
  
  
  

add a comment | 

1

$begingroup$

I have a large sparse quadratic optimization problem with a single quadratic constraint:

$$beginarrayll textmaximize & c'x\ textsubject to & l leq Ax leq u\ & x'Qx + b'x leq u_qendarray$$

where

• $x = (x_1, x_2, dots, x_n)'$.




• $A$ is a $k times n$ matrix of linear constraint coefficients.




• $l$ and $u$ are $k times 1$ vectors of lower and upper bounds, respectively.




• $Q$ is a $n times n$ positive definite matrix.




• $b$ is a $n times 1$ vector.




• $u_q$ is a scalar.

The solver I am using can handle quadratic objective function but only linear constraints. I was wondering if there is a way to reformulate the problem as:

$$beginarrayll textminimize & hat c'x + x'hat Qx\ textsubject to & hat l leq hat Ax leq hat u\endarray$$

optimization convex-analysis convex-optimization constraints qclp

share|cite|improve this question

edited Mar 25 at 9:58

user10203644

asked Mar 22 at 14:43

user10203644user10203644

83

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  If you actually have the inequality constraint with $l_q$, I do not believe so. But if you do not, then it might be possible.
  $endgroup$
  – Alex Shtof
  Mar 22 at 17:20
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Since $Q$ is positive definite, try to convert $x'Qx + b'x$ to something like $(x-c)' M (x - c)$. Then make $y := x - c$ and work with $y$.
  $endgroup$
  – Rodrigo de Azevedo
  Mar 23 at 5:05
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  This is a non-convex problem because the constraint $ l_q leq x'Qx + b'x $ is not convex. I think it should be reformulatable as a Mixed-Integer QP (MIQP).
  $endgroup$
  – Mark L. Stone
  Mar 23 at 19:37
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Apologies, there is no $l_q$ bound actually. Edited the problem setup now.
  $endgroup$
  – user10203644
  Mar 25 at 9:51
  

  
  
  
  

add a comment | 

$begingroup$

I have a large sparse quadratic optimization problem with a single quadratic constraint:

$$beginarrayll textmaximize & c'x\ textsubject to & l leq Ax leq u\ & x'Qx + b'x leq u_qendarray$$

where

• $x = (x_1, x_2, dots, x_n)'$.




• $A$ is a $k times n$ matrix of linear constraint coefficients.




• $l$ and $u$ are $k times 1$ vectors of lower and upper bounds, respectively.




• $Q$ is a $n times n$ positive definite matrix.




• $b$ is a $n times 1$ vector.




• $u_q$ is a scalar.

The solver I am using can handle quadratic objective function but only linear constraints. I was wondering if there is a way to reformulate the problem as:

$$beginarrayll textminimize & hat c'x + x'hat Qx\ textsubject to & hat l leq hat Ax leq hat u\endarray$$

optimization convex-analysis convex-optimization constraints qclp

share|cite|improve this question

edited Mar 25 at 9:58

user10203644

asked Mar 22 at 14:43

user10203644user10203644

83

$endgroup$

share|cite|improve this question

edited Mar 25 at 9:58

user10203644

asked Mar 22 at 14:43

user10203644user10203644

83

share|cite|improve this question

edited Mar 25 at 9:58

user10203644

asked Mar 22 at 14:43

user10203644user10203644

83

asked Mar 22 at 14:43

user10203644user10203644

83

asked Mar 22 at 14:43

user10203644user10203644

83