Usbrth

Can the DM override racial traits?

Create an outline of font

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

Still taught to reverse oxidation half cells in electrochemistry?

Can withdrawing asylum be illegal?

Didn't get enough time to take a Coding Test - what to do now?

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

What are these Gizmos at Izaña Atmospheric Research Center in Spain?

Converting from Markdown-with-biblatex-commands to LaTeX

Why can't devices on different VLANs, but on the same subnet, communicate?

How to pronounce 1ターン?

How to delete random line from file using Unix command?

University's motivation for having tenure-track positions

Did the UK government pay "millions and millions of dollars" to try to snag Julian Assange?

Sort list of array linked objects by keys and values

How to test the equality of two Pearson correlation coefficients computed from the same sample?

Why does the Event Horizon Telescope (EHT) not include telescopes from Africa, Asia or Australia?

How are presidential pardons supposed to be used?

Is every episode of "Where are my Pants?" identical?

Hopping to infinity along a string of digits

Change bounding box of math glyphs in LuaTeX

Is a pteranodon too powerful as a beast companion for a beast master?

Scientific Reports - Significant Figures

how can a perfect fourth interval be considered either consonant or dissonant?

How are these two optimization problems equivalent?

0

$begingroup$

I'm trying to show that the two problems are equivalent

Let $Bbb A = A_1, dots, A_n$ where $A_i in Bbb R^m times n$ and $bin mathbbR^m$

Then

$$min_xin mathbbR^n max_i=1, dots, k |A_ix - b|$$

is equivalent to

$$min_xin mathbbR^n space sup mid A in textconv(A_1, dots,
A_n)$$

Where $textconv$ is the convex hull.

I know that two problems are equivalent when from the solution from one you can find the solution of the other, but I'm having trouble seeing how to show this.

Anyone have any ideas?

convex-optimization

share|cite|improve this question

edited Apr 8 at 12:13

Nathanael Skrepek

1,7601615

asked Apr 8 at 11:59

Oliver GOliver G

1,2621634

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I am not sure in which variable you want to minimize. In $x$, in $b$ or in $(x,b)$?
  $endgroup$
  – Nathanael Skrepek
  Apr 8 at 12:04
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  The variable is $x$, I have edited the question for clarity.
  $endgroup$
  – Oliver G
  Apr 8 at 12:06
  

  
  
  
  

add a comment | 

0

$begingroup$

I'm trying to show that the two problems are equivalent

Let $Bbb A = A_1, dots, A_n$ where $A_i in Bbb R^m times n$ and $bin mathbbR^m$

Then

$$min_xin mathbbR^n max_i=1, dots, k |A_ix - b|$$

is equivalent to

$$min_xin mathbbR^n space sup mid A in textconv(A_1, dots,
A_n)$$

Where $textconv$ is the convex hull.

I know that two problems are equivalent when from the solution from one you can find the solution of the other, but I'm having trouble seeing how to show this.

Anyone have any ideas?

convex-optimization

share|cite|improve this question

edited Apr 8 at 12:13

Nathanael Skrepek

1,7601615

asked Apr 8 at 11:59

Oliver GOliver G

1,2621634

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I am not sure in which variable you want to minimize. In $x$, in $b$ or in $(x,b)$?
  $endgroup$
  – Nathanael Skrepek
  Apr 8 at 12:04
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  The variable is $x$, I have edited the question for clarity.
  $endgroup$
  – Oliver G
  Apr 8 at 12:06
  

  
  
  
  

add a comment | 

$begingroup$

I'm trying to show that the two problems are equivalent

Let $Bbb A = A_1, dots, A_n$ where $A_i in Bbb R^m times n$ and $bin mathbbR^m$

Then

$$min_xin mathbbR^n max_i=1, dots, k |A_ix - b|$$

is equivalent to

$$min_xin mathbbR^n space sup mid A in textconv(A_1, dots,
A_n)$$

Where $textconv$ is the convex hull.

I know that two problems are equivalent when from the solution from one you can find the solution of the other, but I'm having trouble seeing how to show this.

Anyone have any ideas?

convex-optimization

share|cite|improve this question

edited Apr 8 at 12:13

Nathanael Skrepek

1,7601615

asked Apr 8 at 11:59

Oliver GOliver G

1,2621634

$endgroup$

share|cite|improve this question

edited Apr 8 at 12:13

Nathanael Skrepek

1,7601615

asked Apr 8 at 11:59

Oliver GOliver G

1,2621634

share|cite|improve this question

edited Apr 8 at 12:13

Nathanael Skrepek

1,7601615

asked Apr 8 at 11:59

Oliver GOliver G

1,2621634

edited Apr 8 at 12:13

Nathanael Skrepek

1,7601615

edited Apr 8 at 12:13

Nathanael Skrepek

1,7601615

asked Apr 8 at 11:59

Oliver GOliver G

1,2621634

asked Apr 8 at 11:59

Oliver GOliver G

1,2621634

1 Answer
1

active

oldest

votes

1

$begingroup$

Note that every element in $Ainoperatornameconv(A_1,dots,A_k)$ can be written as $A = sum_i=1^n lambda_i A_i$, where $lambda_iin [0,1]$ and $sum_i=1 lambda_i = 1$. In particular we also have $b = sum_i=1 lambda_i b$. Consequently we obtain the following inequality
beginalign
|Ax - b| &= Big|sum_i=1^n lambda_i A_i x -sum_i=1^n lambda_i bBig|
=Big|sum_i=1^n lambda_i(A_ix-b)Big| leq sum_i=1^n lambda_i|A_i x-b|\
&leq sum_i=1^n lambda_i max_i=1,dots,k|A_i x-b| = max_i=1,dots,k|A_i x-b|
endalign
for arbitrary $xin mathbbR^n$ and $bin mathbbR^m$.
One immediate consequence is
$$
sup_Ainoperatornameconv(A_1,dots,A_k) |Ax - b| leq max_i=1,dots,k|A_i x-b|.
$$
On the other hand since every $A_i in operatornameconv(A_1,dots,A_k)$ we also have
$$
sup_Ainoperatornameconv(A_1,dots,A_k) |Ax - b| geq max_i=1,dots,k|A_i x-b|.
$$
Hence, we have equality. Clearly this won't change if we minimize over $xin mathbbR^n$.

So this has nothing to do with the minimization problem. In fact this is the key essence of the simplex algorithm.

share|cite|improve this answer

answered Apr 8 at 14:57

Nathanael SkrepekNathanael Skrepek

1,7601615

$endgroup$

add a comment | 

Your Answer

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
);



);

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

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3179536%2fhow-are-these-two-optimization-problems-equivalent%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

1

$begingroup$

Note that every element in $Ainoperatornameconv(A_1,dots,A_k)$ can be written as $A = sum_i=1^n lambda_i A_i$, where $lambda_iin [0,1]$ and $sum_i=1 lambda_i = 1$. In particular we also have $b = sum_i=1 lambda_i b$. Consequently we obtain the following inequality
beginalign
|Ax - b| &= Big|sum_i=1^n lambda_i A_i x -sum_i=1^n lambda_i bBig|
=Big|sum_i=1^n lambda_i(A_ix-b)Big| leq sum_i=1^n lambda_i|A_i x-b|\
&leq sum_i=1^n lambda_i max_i=1,dots,k|A_i x-b| = max_i=1,dots,k|A_i x-b|
endalign
for arbitrary $xin mathbbR^n$ and $bin mathbbR^m$.
One immediate consequence is
$$
sup_Ainoperatornameconv(A_1,dots,A_k) |Ax - b| leq max_i=1,dots,k|A_i x-b|.
$$
On the other hand since every $A_i in operatornameconv(A_1,dots,A_k)$ we also have
$$
sup_Ainoperatornameconv(A_1,dots,A_k) |Ax - b| geq max_i=1,dots,k|A_i x-b|.
$$
Hence, we have equality. Clearly this won't change if we minimize over $xin mathbbR^n$.

So this has nothing to do with the minimization problem. In fact this is the key essence of the simplex algorithm.

share|cite|improve this answer

answered Apr 8 at 14:57

Nathanael SkrepekNathanael Skrepek

1,7601615

$endgroup$

add a comment | 

1

$begingroup$

Note that every element in $Ainoperatornameconv(A_1,dots,A_k)$ can be written as $A = sum_i=1^n lambda_i A_i$, where $lambda_iin [0,1]$ and $sum_i=1 lambda_i = 1$. In particular we also have $b = sum_i=1 lambda_i b$. Consequently we obtain the following inequality
beginalign
|Ax - b| &= Big|sum_i=1^n lambda_i A_i x -sum_i=1^n lambda_i bBig|
=Big|sum_i=1^n lambda_i(A_ix-b)Big| leq sum_i=1^n lambda_i|A_i x-b|\
&leq sum_i=1^n lambda_i max_i=1,dots,k|A_i x-b| = max_i=1,dots,k|A_i x-b|
endalign
for arbitrary $xin mathbbR^n$ and $bin mathbbR^m$.
One immediate consequence is
$$
sup_Ainoperatornameconv(A_1,dots,A_k) |Ax - b| leq max_i=1,dots,k|A_i x-b|.
$$
On the other hand since every $A_i in operatornameconv(A_1,dots,A_k)$ we also have
$$
sup_Ainoperatornameconv(A_1,dots,A_k) |Ax - b| geq max_i=1,dots,k|A_i x-b|.
$$
Hence, we have equality. Clearly this won't change if we minimize over $xin mathbbR^n$.

So this has nothing to do with the minimization problem. In fact this is the key essence of the simplex algorithm.

share|cite|improve this answer

answered Apr 8 at 14:57

Nathanael SkrepekNathanael Skrepek

1,7601615

$endgroup$

add a comment | 

$begingroup$

Note that every element in $Ainoperatornameconv(A_1,dots,A_k)$ can be written as $A = sum_i=1^n lambda_i A_i$, where $lambda_iin [0,1]$ and $sum_i=1 lambda_i = 1$. In particular we also have $b = sum_i=1 lambda_i b$. Consequently we obtain the following inequality
beginalign
|Ax - b| &= Big|sum_i=1^n lambda_i A_i x -sum_i=1^n lambda_i bBig|
=Big|sum_i=1^n lambda_i(A_ix-b)Big| leq sum_i=1^n lambda_i|A_i x-b|\
&leq sum_i=1^n lambda_i max_i=1,dots,k|A_i x-b| = max_i=1,dots,k|A_i x-b|
endalign
for arbitrary $xin mathbbR^n$ and $bin mathbbR^m$.
One immediate consequence is
$$
sup_Ainoperatornameconv(A_1,dots,A_k) |Ax - b| leq max_i=1,dots,k|A_i x-b|.
$$
On the other hand since every $A_i in operatornameconv(A_1,dots,A_k)$ we also have
$$
sup_Ainoperatornameconv(A_1,dots,A_k) |Ax - b| geq max_i=1,dots,k|A_i x-b|.
$$
Hence, we have equality. Clearly this won't change if we minimize over $xin mathbbR^n$.

So this has nothing to do with the minimization problem. In fact this is the key essence of the simplex algorithm.

share|cite|improve this answer

answered Apr 8 at 14:57

Nathanael SkrepekNathanael Skrepek

1,7601615

$endgroup$

share|cite|improve this answer

answered Apr 8 at 14:57

Nathanael SkrepekNathanael Skrepek

1,7601615

answered Apr 8 at 14:57

Nathanael SkrepekNathanael Skrepek

1,7601615

answered Apr 8 at 14:57

Nathanael SkrepekNathanael Skrepek

1,7601615