Converting a first norm into a linear program
$begingroup$
I want to convert the following problem into a linear program.
$$ min_{x in mathbb{R}^n} qquad lvertlvert Ax - b rvertrvert_1$$
Here $A in mathbb{R}^{mtimes n}$, $x in mathbb{R}^n$ and $b in mathbb{R}^m$
This was my train of thought so far:
By definition, the first norm is,
$$ lvert lvert yrvert rvert_1 = lvert y_1rvert + lvert y_2 rvert + ...+ lvert y_nrvert$$
Now I know that an absolute value can be represented by replacing the variable with two non-negative variables. But I know it only for a single variable:
$$ lvert x rvert = x^+ - x^- $$
I have no idea how to do this when the expression is in the format $lvert a_i^Tx - b_irvert$ where $a_i^T$ is a row of the matrix $A$. (Yes I am dumb, I know it).
The best I could think of is adding a constraint $y = Ax -b$ and using $y$ as my variable:
begin{align}
min_{y_i^+, y_i^- in mathbb{R}} quad & y_1^+ + y_1^- + y_2^+ + y_2^- + y_3^+ + y_3^-+ dots + y_m^+ + y_m^-\
s.t. quad & a_1^Tx - b_1 = y_1^+ - y_1^- \
& a_2^Tx - b_2 = y_2^+ - y_2^- \
& a_3^Tx - b_3 = y_3^+ - y_3^- \
vdots
& a_m^Tx - b_m = y_m^+ - y_m^-
end{align}
This is all I can think. Is this the right way to go? Is there anything missing? Or is this entirely wrong? Any help would be appreciated.
norm linear-programming
asked Dec 3 '18 at 20:16
PPGoodManPPGoodMan
657
$endgroup$
add a comment |
$begingroup$
I want to convert the following problem into a linear program.
$$ min_{x in mathbb{R}^n} qquad lvertlvert Ax - b rvertrvert_1$$
Here $A in mathbb{R}^{mtimes n}$, $x in mathbb{R}^n$ and $b in mathbb{R}^m$
This was my train of thought so far:
By definition, the first norm is,
$$ lvert lvert yrvert rvert_1 = lvert y_1rvert + lvert y_2 rvert + ...+ lvert y_nrvert$$
Now I know that an absolute value can be represented by replacing the variable with two non-negative variables. But I know it only for a single variable:
$$ lvert x rvert = x^+ - x^- $$
I have no idea how to do this when the expression is in the format $lvert a_i^Tx - b_irvert$ where $a_i^T$ is a row of the matrix $A$. (Yes I am dumb, I know it).
The best I could think of is adding a constraint $y = Ax -b$ and using $y$ as my variable:
begin{align}
min_{y_i^+, y_i^- in mathbb{R}} quad & y_1^+ + y_1^- + y_2^+ + y_2^- + y_3^+ + y_3^-+ dots + y_m^+ + y_m^-\
s.t. quad & a_1^Tx - b_1 = y_1^+ - y_1^- \
& a_2^Tx - b_2 = y_2^+ - y_2^- \
& a_3^Tx - b_3 = y_3^+ - y_3^- \
vdots
& a_m^Tx - b_m = y_m^+ - y_m^-
end{align}
This is all I can think. Is this the right way to go? Is there anything missing? Or is this entirely wrong? Any help would be appreciated.
norm linear-programming
asked Dec 3 '18 at 20:16
PPGoodManPPGoodMan
657
$endgroup$
add a comment |
$begingroup$
I want to convert the following problem into a linear program.
$$ min_{x in mathbb{R}^n} qquad lvertlvert Ax - b rvertrvert_1$$
Here $A in mathbb{R}^{mtimes n}$, $x in mathbb{R}^n$ and $b in mathbb{R}^m$
This was my train of thought so far:
By definition, the first norm is,
$$ lvert lvert yrvert rvert_1 = lvert y_1rvert + lvert y_2 rvert + ...+ lvert y_nrvert$$
Now I know that an absolute value can be represented by replacing the variable with two non-negative variables. But I know it only for a single variable:
$$ lvert x rvert = x^+ - x^- $$
I have no idea how to do this when the expression is in the format $lvert a_i^Tx - b_irvert$ where $a_i^T$ is a row of the matrix $A$. (Yes I am dumb, I know it).
The best I could think of is adding a constraint $y = Ax -b$ and using $y$ as my variable:
begin{align}
min_{y_i^+, y_i^- in mathbb{R}} quad & y_1^+ + y_1^- + y_2^+ + y_2^- + y_3^+ + y_3^-+ dots + y_m^+ + y_m^-\
s.t. quad & a_1^Tx - b_1 = y_1^+ - y_1^- \
& a_2^Tx - b_2 = y_2^+ - y_2^- \
& a_3^Tx - b_3 = y_3^+ - y_3^- \
vdots
& a_m^Tx - b_m = y_m^+ - y_m^-
end{align}
This is all I can think. Is this the right way to go? Is there anything missing? Or is this entirely wrong? Any help would be appreciated.
norm linear-programming
asked Dec 3 '18 at 20:16
PPGoodManPPGoodMan
657
$endgroup$
I want to convert the following problem into a linear program.
$$ min_{x in mathbb{R}^n} qquad lvertlvert Ax - b rvertrvert_1$$
Here $A in mathbb{R}^{mtimes n}$, $x in mathbb{R}^n$ and $b in mathbb{R}^m$
This was my train of thought so far:
By definition, the first norm is,
$$ lvert lvert yrvert rvert_1 = lvert y_1rvert + lvert y_2 rvert + ...+ lvert y_nrvert$$
Now I know that an absolute value can be represented by replacing the variable with two non-negative variables. But I know it only for a single variable:
$$ lvert x rvert = x^+ - x^- $$
I have no idea how to do this when the expression is in the format $lvert a_i^Tx - b_irvert$ where $a_i^T$ is a row of the matrix $A$. (Yes I am dumb, I know it).
The best I could think of is adding a constraint $y = Ax -b$ and using $y$ as my variable:
begin{align}
min_{y_i^+, y_i^- in mathbb{R}} quad & y_1^+ + y_1^- + y_2^+ + y_2^- + y_3^+ + y_3^-+ dots + y_m^+ + y_m^-\
s.t. quad & a_1^Tx - b_1 = y_1^+ - y_1^- \
& a_2^Tx - b_2 = y_2^+ - y_2^- \
& a_3^Tx - b_3 = y_3^+ - y_3^- \
vdots
& a_m^Tx - b_m = y_m^+ - y_m^-
end{align}
This is all I can think. Is this the right way to go? Is there anything missing? Or is this entirely wrong? Any help would be appreciated.
norm linear-programming
norm linear-programming
asked Dec 3 '18 at 20:16
PPGoodManPPGoodMan
657
asked Dec 3 '18 at 20:16
PPGoodManPPGoodMan
657
asked Dec 3 '18 at 20:16
PPGoodManPPGoodMan
657
asked Dec 3 '18 at 20:16
PPGoodManPPGoodMan
657
asked Dec 3 '18 at 20:16
PPGoodManPPGoodMan
657
657
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Seems fine. Don't forget to include the nonnegative constraints for your $y_i^+$ and $y_i^-$.
Alternatively
$$min sum_{i=m}^n z_i$$
$$z_i ge a_i^Tx-b_i$$
$$z_i ge -(a_i^Tx-b_i)$$
$forall i in {1, ldots, m}$.
answered Dec 4 '18 at 8:07
Siong Thye GohSiong Thye Goh
101k1466117
$endgroup$
$begingroup$
Thank you very much!
$endgroup$
– PPGoodMan
Dec 4 '18 at 14:28
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',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3024600%2fconverting-a-first-norm-into-a-linear-program%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Seems fine. Don't forget to include the nonnegative constraints for your $y_i^+$ and $y_i^-$.
Alternatively
$$min sum_{i=m}^n z_i$$
$$z_i ge a_i^Tx-b_i$$
$$z_i ge -(a_i^Tx-b_i)$$
$forall i in {1, ldots, m}$.
answered Dec 4 '18 at 8:07
Siong Thye GohSiong Thye Goh
101k1466117
$endgroup$
$begingroup$
Thank you very much!
$endgroup$
– PPGoodMan
Dec 4 '18 at 14:28
add a comment |
$begingroup$
Seems fine. Don't forget to include the nonnegative constraints for your $y_i^+$ and $y_i^-$.
Alternatively
$$min sum_{i=m}^n z_i$$
$$z_i ge a_i^Tx-b_i$$
$$z_i ge -(a_i^Tx-b_i)$$
$forall i in {1, ldots, m}$.
answered Dec 4 '18 at 8:07
Siong Thye GohSiong Thye Goh
101k1466117
$endgroup$
$begingroup$
Thank you very much!
$endgroup$
– PPGoodMan
Dec 4 '18 at 14:28
add a comment |
$begingroup$
Seems fine. Don't forget to include the nonnegative constraints for your $y_i^+$ and $y_i^-$.
Alternatively
$$min sum_{i=m}^n z_i$$
$$z_i ge a_i^Tx-b_i$$
$$z_i ge -(a_i^Tx-b_i)$$
$forall i in {1, ldots, m}$.
answered Dec 4 '18 at 8:07
Siong Thye GohSiong Thye Goh
101k1466117
$endgroup$
Seems fine. Don't forget to include the nonnegative constraints for your $y_i^+$ and $y_i^-$.
Alternatively
$$min sum_{i=m}^n z_i$$
$$z_i ge a_i^Tx-b_i$$
$$z_i ge -(a_i^Tx-b_i)$$
$forall i in {1, ldots, m}$.
answered Dec 4 '18 at 8:07
Siong Thye GohSiong Thye Goh
101k1466117
edited Dec 4 '18 at 8:13
answered Dec 4 '18 at 8:07
Siong Thye GohSiong Thye Goh
101k1466117
answered Dec 4 '18 at 8:07
Siong Thye GohSiong Thye Goh
101k1466117
answered Dec 4 '18 at 8:07
Siong Thye GohSiong Thye Goh
101k1466117
101k1466117
$begingroup$
Thank you very much!
$endgroup$
– PPGoodMan
Dec 4 '18 at 14:28
add a comment |
$begingroup$
Thank you very much!
$endgroup$
– PPGoodMan
Dec 4 '18 at 14:28
$begingroup$
Thank you very much!
$endgroup$
– PPGoodMan
Dec 4 '18 at 14:28
$begingroup$
Thank you very much!
$endgroup$
– PPGoodMan
Dec 4 '18 at 14:28
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3024600%2fconverting-a-first-norm-into-a-linear-program%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
