Convert Quadratic to Conic Constraint

Clash Royale CLAN TAG#URR8PPP

up vote
0
down vote

favorite

Per Wikipedia, a quadratic constraint of the below form

$$x^TA^TAx+b^Tx+cleq0tag1$$

can be written as the following equivalent conic formulation

$$left |[(1+b^Tx+c)/2,~Ax ]right |_2leq(1-b^Tx-c)/2tag2$$

I tried my hand at proving the above, and seem to be getting a different expression. Starting with equation (1)-

$$||Ax||_2^2+b^Tx+cleq0implies||Ax||_2^2+(1+b^Tx+c)/2leq(1-b^Tx-c)/2$$

This seems to be going nowhere. I could try completing a square, but would end up with a square root on the affine $x$ expression. Then I tried to manipulate equation (2)-

$$||Ax||_2^2+(1+b^Tx+c)/2^2+x^TA^T(1+b^Tx+c)leq(1-b^Tx-c)/2^2$$

$$Leftrightarrow||Ax||_2^2+(b^Tx+c)(I+x^TA^T)+x^TA^Tleq0$$

This doesn't look like a condition that should hold in general. Am I missing something here?

optimization convex-optimization constraints qcqp socp

share|cite|improve this question

asked Jul 26 at 7:39

Amrit Prasad

727

add a comment | 

up vote
0
down vote

favorite

Per Wikipedia, a quadratic constraint of the below form

$$x^TA^TAx+b^Tx+cleq0tag1$$

can be written as the following equivalent conic formulation

$$left |[(1+b^Tx+c)/2,~Ax ]right |_2leq(1-b^Tx-c)/2tag2$$

I tried my hand at proving the above, and seem to be getting a different expression. Starting with equation (1)-

$$||Ax||_2^2+b^Tx+cleq0implies||Ax||_2^2+(1+b^Tx+c)/2leq(1-b^Tx-c)/2$$

This seems to be going nowhere. I could try completing a square, but would end up with a square root on the affine $x$ expression. Then I tried to manipulate equation (2)-

$$||Ax||_2^2+(1+b^Tx+c)/2^2+x^TA^T(1+b^Tx+c)leq(1-b^Tx-c)/2^2$$

$$Leftrightarrow||Ax||_2^2+(b^Tx+c)(I+x^TA^T)+x^TA^Tleq0$$

This doesn't look like a condition that should hold in general. Am I missing something here?

optimization convex-optimization constraints qcqp socp

share|cite|improve this question

asked Jul 26 at 7:39

Amrit Prasad

727

add a comment | 

up vote
0
down vote

favorite

up vote
0
down vote

favorite

Per Wikipedia, a quadratic constraint of the below form

$$x^TA^TAx+b^Tx+cleq0tag1$$

can be written as the following equivalent conic formulation

$$left |[(1+b^Tx+c)/2,~Ax ]right |_2leq(1-b^Tx-c)/2tag2$$

I tried my hand at proving the above, and seem to be getting a different expression. Starting with equation (1)-

$$||Ax||_2^2+b^Tx+cleq0implies||Ax||_2^2+(1+b^Tx+c)/2leq(1-b^Tx-c)/2$$

This seems to be going nowhere. I could try completing a square, but would end up with a square root on the affine $x$ expression. Then I tried to manipulate equation (2)-

$$||Ax||_2^2+(1+b^Tx+c)/2^2+x^TA^T(1+b^Tx+c)leq(1-b^Tx-c)/2^2$$

$$Leftrightarrow||Ax||_2^2+(b^Tx+c)(I+x^TA^T)+x^TA^Tleq0$$

This doesn't look like a condition that should hold in general. Am I missing something here?

optimization convex-optimization constraints qcqp socp

share|cite|improve this question

asked Jul 26 at 7:39

Amrit Prasad

727

Per Wikipedia, a quadratic constraint of the below form

$$x^TA^TAx+b^Tx+cleq0tag1$$

can be written as the following equivalent conic formulation

$$left |[(1+b^Tx+c)/2,~Ax ]right |_2leq(1-b^Tx-c)/2tag2$$

I tried my hand at proving the above, and seem to be getting a different expression. Starting with equation (1)-

$$||Ax||_2^2+b^Tx+cleq0implies||Ax||_2^2+(1+b^Tx+c)/2leq(1-b^Tx-c)/2$$

This seems to be going nowhere. I could try completing a square, but would end up with a square root on the affine $x$ expression. Then I tried to manipulate equation (2)-

$$||Ax||_2^2+(1+b^Tx+c)/2^2+x^TA^T(1+b^Tx+c)leq(1-b^Tx-c)/2^2$$

$$Leftrightarrow||Ax||_2^2+(b^Tx+c)(I+x^TA^T)+x^TA^Tleq0$$

This doesn't look like a condition that should hold in general. Am I missing something here?

optimization convex-optimization constraints qcqp socp

share|cite|improve this question

asked Jul 26 at 7:39

Amrit Prasad

727

share|cite|improve this question

share|cite|improve this question

asked Jul 26 at 7:39

Amrit Prasad

727

asked Jul 26 at 7:39

Amrit Prasad

727

asked Jul 26 at 7:39

Amrit Prasad

727

727

add a comment | 

add a comment | 

1 Answer
1

active

oldest

votes

up vote
2
down vote



accepted

You have an extra term in your expansion of the left-hand side of the square of (2). A simple dimension check will tell you that the last term doesn’t belong—the other two terms are scalars, but the third is a row vector. $[(1+b^Tx+c)/2,(Ax)^T]^T$ is just $Ax$ with an extra scalar component prepended to it. The correct expansion of the square of its norm is $|Ax|_2^2+(1+b^Tx+c)^2/4$. Expand both terms and pull out the quadratic constraint to get $x^TA^TAx+b^Tx+c+dots$. The elided terms factor nicely into something relevant.

share|cite|improve this answer

answered Jul 26 at 9:10

amd

25.8k2943

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2863170%2fconvert-quadratic-to-conic-constraint%23new-answer', 'question_page');

);

Post as a guest

Name Email

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
2
down vote



accepted

You have an extra term in your expansion of the left-hand side of the square of (2). A simple dimension check will tell you that the last term doesn’t belong—the other two terms are scalars, but the third is a row vector. $[(1+b^Tx+c)/2,(Ax)^T]^T$ is just $Ax$ with an extra scalar component prepended to it. The correct expansion of the square of its norm is $|Ax|_2^2+(1+b^Tx+c)^2/4$. Expand both terms and pull out the quadratic constraint to get $x^TA^TAx+b^Tx+c+dots$. The elided terms factor nicely into something relevant.

share|cite|improve this answer

answered Jul 26 at 9:10

amd

25.8k2943

add a comment | 

up vote
2
down vote



accepted

You have an extra term in your expansion of the left-hand side of the square of (2). A simple dimension check will tell you that the last term doesn’t belong—the other two terms are scalars, but the third is a row vector. $[(1+b^Tx+c)/2,(Ax)^T]^T$ is just $Ax$ with an extra scalar component prepended to it. The correct expansion of the square of its norm is $|Ax|_2^2+(1+b^Tx+c)^2/4$. Expand both terms and pull out the quadratic constraint to get $x^TA^TAx+b^Tx+c+dots$. The elided terms factor nicely into something relevant.

share|cite|improve this answer

answered Jul 26 at 9:10

amd

25.8k2943

add a comment | 

up vote
2
down vote



accepted

up vote
2
down vote



accepted

You have an extra term in your expansion of the left-hand side of the square of (2). A simple dimension check will tell you that the last term doesn’t belong—the other two terms are scalars, but the third is a row vector. $[(1+b^Tx+c)/2,(Ax)^T]^T$ is just $Ax$ with an extra scalar component prepended to it. The correct expansion of the square of its norm is $|Ax|_2^2+(1+b^Tx+c)^2/4$. Expand both terms and pull out the quadratic constraint to get $x^TA^TAx+b^Tx+c+dots$. The elided terms factor nicely into something relevant.

share|cite|improve this answer

answered Jul 26 at 9:10

amd

25.8k2943

You have an extra term in your expansion of the left-hand side of the square of (2). A simple dimension check will tell you that the last term doesn’t belong—the other two terms are scalars, but the third is a row vector. $[(1+b^Tx+c)/2,(Ax)^T]^T$ is just $Ax$ with an extra scalar component prepended to it. The correct expansion of the square of its norm is $|Ax|_2^2+(1+b^Tx+c)^2/4$. Expand both terms and pull out the quadratic constraint to get $x^TA^TAx+b^Tx+c+dots$. The elided terms factor nicely into something relevant.

share|cite|improve this answer

answered Jul 26 at 9:10

amd

25.8k2943

share|cite|improve this answer

share|cite|improve this answer

answered Jul 26 at 9:10

amd

25.8k2943

answered Jul 26 at 9:10

amd

25.8k2943

answered Jul 26 at 9:10

amd

25.8k2943

25.8k2943

add a comment | 

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2863170%2fconvert-quadratic-to-conic-constraint%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email