Dtjytyk

What Happens when Passenger Refuses to Fly Boeing 737 Max?

Makefile strange variable substitution

Latex does not go to next line

Do f-stop and exposure time perfectly cancel?

What wound would be of little consequence to a biped but terrible for a quadruped?

Could you please stop shuffling the deck and play already?

How to secure an aircraft at a transient parking space?

Virginia employer terminated employee and wants signing bonus returned

Why does the negative sign arise in this thermodynamic relation?

What problems would a superhuman have whose skin is constantly hot?

Was Luke Skywalker the leader of the Rebel forces on Hoth?

Why was Goose renamed from Chewie for the Captain Marvel film?

Are babies of evil humanoid species inherently evil?

How are showroom/display vehicles prepared?

Difference on montgomery curve equation between EFD and RFC7748

Does this video of collapsing warehouse shelves show a real incident?

Database Backup for data and log files

Reversed Sudoku

Why doesn't this Google Translate ad use the word "Translation" instead of "Translate"?

In the quantum hamiltonian, why does kinetic energy turn into an operator while potential doesn't?

Counting all the hearts

Definition of Statistic

How did Alan Turing break the enigma code using the hint given by the lady in the bar?

Does a warlock using the Darkness/Devil's Sight combo still have advantage on ranged attacks against a target outside the Darkness?

Minimization of norm distance using SDPs, cone programming, etc.

Minimization of Frobenius norm and Schur complementDual of a semidefinite programSemidefinite programming formulation for a simple minimizationRedefining an SDP problemMinimization of Frobenius norm and Schur complementHow to solve this minimization problem involving the nuclear norm?Transforming a nearest matrix optimization problem to a standard formSpectral norm minimizationProjection onto the Set of Circulant Matricesprimal and dual semi-definite programs - problemThe Exponential Cone and Semi-definite programming

0

$begingroup$

Building on top of this question Minimization of Frobenius norm using SDPs, I would like to know for what class of norms ($ Vert cdot Vert $ in the following) can we represent the following problem using semidefinite programming (SDP), or cone programming, or some standard optimization problem:

$$
begin{align*}
& text{min. } Vert A - X Vert \
& text{s.t. }X in mathcal{S}
end{align*}
$$

where $A$ is a (symmetric) matrix and $mathcal{S}$ is some convex set, for which the membership condition can be represented say using SDP constraints.

In particular, I am interested in the following cases:

1. The case where the problem can be represented using SDPs.


2. The norm is the Schatten p-norm.


3. The norm is an Operator norm.

Finally, any reference for dealing with this class of problems would be much appreciated.

matrices convex-analysis convex-optimization semidefinite-programming matrix-norms

share|cite|improve this question

edited 2 days ago

Rodrigo de Azevedo

13k41960

asked 2 days ago

NoelNoel

827

$endgroup$

add a comment | 

0

$begingroup$

Building on top of this question Minimization of Frobenius norm using SDPs, I would like to know for what class of norms ($ Vert cdot Vert $ in the following) can we represent the following problem using semidefinite programming (SDP), or cone programming, or some standard optimization problem:

$$
begin{align*}
& text{min. } Vert A - X Vert \
& text{s.t. }X in mathcal{S}
end{align*}
$$

where $A$ is a (symmetric) matrix and $mathcal{S}$ is some convex set, for which the membership condition can be represented say using SDP constraints.

In particular, I am interested in the following cases:

1. The case where the problem can be represented using SDPs.


2. The norm is the Schatten p-norm.


3. The norm is an Operator norm.

Finally, any reference for dealing with this class of problems would be much appreciated.

matrices convex-analysis convex-optimization semidefinite-programming matrix-norms

share|cite|improve this question

edited 2 days ago

Rodrigo de Azevedo

13k41960

asked 2 days ago

NoelNoel

827

$endgroup$

add a comment | 

$begingroup$

Building on top of this question Minimization of Frobenius norm using SDPs, I would like to know for what class of norms ($ Vert cdot Vert $ in the following) can we represent the following problem using semidefinite programming (SDP), or cone programming, or some standard optimization problem:

$$
begin{align*}
& text{min. } Vert A - X Vert \
& text{s.t. }X in mathcal{S}
end{align*}
$$

where $A$ is a (symmetric) matrix and $mathcal{S}$ is some convex set, for which the membership condition can be represented say using SDP constraints.

In particular, I am interested in the following cases:

1. The case where the problem can be represented using SDPs.


2. The norm is the Schatten p-norm.


3. The norm is an Operator norm.

Finally, any reference for dealing with this class of problems would be much appreciated.

matrices convex-analysis convex-optimization semidefinite-programming matrix-norms

share|cite|improve this question

edited 2 days ago

Rodrigo de Azevedo

13k41960

asked 2 days ago

NoelNoel

827

$endgroup$

share|cite|improve this question

edited 2 days ago

Rodrigo de Azevedo

13k41960

asked 2 days ago

NoelNoel

827

share|cite|improve this question

edited 2 days ago

Rodrigo de Azevedo

13k41960

asked 2 days ago

NoelNoel

827

edited 2 days ago

Rodrigo de Azevedo

13k41960

edited 2 days ago

Rodrigo de Azevedo

13k41960

asked 2 days ago

NoelNoel

827

asked 2 days ago

NoelNoel

827

1 Answer
1

active

oldest

votes

2

$begingroup$

A lazy answer would be to simply list the help on norm which lists cases that are supported out of the box in the modelling language YALMIP (which would write these using LP/SOCP/SDP formulations)

 For matrices...

   norm(X)       models the largest singular value of X, max(svd(X)).

   norm(X,2)     is the same as norm(X).

   norm(X,1)     models the 1-norm of X, the largest column sum, max(sum(abs(X))).

   norm(X,inf)   models the infinity norm of X, the largest row sum, max(sum(abs(X'))).

   norm(X,'inf') same as above

   norm(X,'fro') models the Frobenius norm, sqrt(sum(diag(X'*X))).

   norm(X,'nuc') models the Nuclear norm, sum of singular values.

   norm(X,'*')   same as above

   norm(X,'tv')  models the (isotropic) total variation semi-norm 

 For vectors...

   norm(V) = norm(V,2) = standard Euclidean norm.

   norm(V,inf) = max(abs(V)).

   norm(V,1) = sum(abs(V))

In addition to that, you have that $(sum |x_i|^p)^{1/p}$ is conic representable for $pgeq 0$ (second-order cone, or more conveniently but perhaps slightly more esoteric using the power cone) thus covering arbitrary Schatten p-norms on matrices, as long as you can get that operator to act on a vector which upper bounds a sorted vector of the eigenvalues of $X^TX$ (which you also can through intricate modelling...)

Everything is available in (but hidden well...)

Nesterov, Yurii; Arkadii, Nemirovskii (1995). Interior-Point
Polynomial Algorithms in Convex Programming. Society for Industrial
and Applied Mathematics. ISBN 0898715156.

share|cite|improve this answer

answered 2 days ago

Johan LöfbergJohan Löfberg

5,3401811

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  One trivial detail—the vector $p$ norms are SOCP-representable only for rational $p$. You'll need that power code for the fully generic case. And I personally don't know about the representability of induced matrix $p$-norms (other than $1$, $2$, and $infty$).
  $endgroup$
  – Michael Grant
  2 days ago
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Johan I don't understand what you mean by: 'In addition to that, you have that... (which you also can through intricate modelling...)'. Could you elaborate/ give a simple example?
  $endgroup$
  – Noel
  yesterday
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  What I mean is that you through SDP modelling can represent the function $f(v)$ where $v$ are the eigenvalues of a symmetrix matrix and $f$ is any permutation invariant conic representable function.
  $endgroup$
  – Johan Löfberg
  yesterday
  

  
  
  
  

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


}
});

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%2f3140803%2fminimization-of-norm-distance-using-sdps-cone-programming-etc%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

2

$begingroup$

A lazy answer would be to simply list the help on norm which lists cases that are supported out of the box in the modelling language YALMIP (which would write these using LP/SOCP/SDP formulations)

 For matrices...

   norm(X)       models the largest singular value of X, max(svd(X)).

   norm(X,2)     is the same as norm(X).

   norm(X,1)     models the 1-norm of X, the largest column sum, max(sum(abs(X))).

   norm(X,inf)   models the infinity norm of X, the largest row sum, max(sum(abs(X'))).

   norm(X,'inf') same as above

   norm(X,'fro') models the Frobenius norm, sqrt(sum(diag(X'*X))).

   norm(X,'nuc') models the Nuclear norm, sum of singular values.

   norm(X,'*')   same as above

   norm(X,'tv')  models the (isotropic) total variation semi-norm 

 For vectors...

   norm(V) = norm(V,2) = standard Euclidean norm.

   norm(V,inf) = max(abs(V)).

   norm(V,1) = sum(abs(V))

In addition to that, you have that $(sum |x_i|^p)^{1/p}$ is conic representable for $pgeq 0$ (second-order cone, or more conveniently but perhaps slightly more esoteric using the power cone) thus covering arbitrary Schatten p-norms on matrices, as long as you can get that operator to act on a vector which upper bounds a sorted vector of the eigenvalues of $X^TX$ (which you also can through intricate modelling...)

Everything is available in (but hidden well...)

Nesterov, Yurii; Arkadii, Nemirovskii (1995). Interior-Point
Polynomial Algorithms in Convex Programming. Society for Industrial
and Applied Mathematics. ISBN 0898715156.

share|cite|improve this answer

answered 2 days ago

Johan LöfbergJohan Löfberg

5,3401811

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  One trivial detail—the vector $p$ norms are SOCP-representable only for rational $p$. You'll need that power code for the fully generic case. And I personally don't know about the representability of induced matrix $p$-norms (other than $1$, $2$, and $infty$).
  $endgroup$
  – Michael Grant
  2 days ago
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Johan I don't understand what you mean by: 'In addition to that, you have that... (which you also can through intricate modelling...)'. Could you elaborate/ give a simple example?
  $endgroup$
  – Noel
  yesterday
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  What I mean is that you through SDP modelling can represent the function $f(v)$ where $v$ are the eigenvalues of a symmetrix matrix and $f$ is any permutation invariant conic representable function.
  $endgroup$
  – Johan Löfberg
  yesterday
  

  
  
  
  

add a comment | 

2

$begingroup$

A lazy answer would be to simply list the help on norm which lists cases that are supported out of the box in the modelling language YALMIP (which would write these using LP/SOCP/SDP formulations)

 For matrices...

   norm(X)       models the largest singular value of X, max(svd(X)).

   norm(X,2)     is the same as norm(X).

   norm(X,1)     models the 1-norm of X, the largest column sum, max(sum(abs(X))).

   norm(X,inf)   models the infinity norm of X, the largest row sum, max(sum(abs(X'))).

   norm(X,'inf') same as above

   norm(X,'fro') models the Frobenius norm, sqrt(sum(diag(X'*X))).

   norm(X,'nuc') models the Nuclear norm, sum of singular values.

   norm(X,'*')   same as above

   norm(X,'tv')  models the (isotropic) total variation semi-norm 

 For vectors...

   norm(V) = norm(V,2) = standard Euclidean norm.

   norm(V,inf) = max(abs(V)).

   norm(V,1) = sum(abs(V))

In addition to that, you have that $(sum |x_i|^p)^{1/p}$ is conic representable for $pgeq 0$ (second-order cone, or more conveniently but perhaps slightly more esoteric using the power cone) thus covering arbitrary Schatten p-norms on matrices, as long as you can get that operator to act on a vector which upper bounds a sorted vector of the eigenvalues of $X^TX$ (which you also can through intricate modelling...)

Everything is available in (but hidden well...)

Nesterov, Yurii; Arkadii, Nemirovskii (1995). Interior-Point
Polynomial Algorithms in Convex Programming. Society for Industrial
and Applied Mathematics. ISBN 0898715156.

share|cite|improve this answer

answered 2 days ago

Johan LöfbergJohan Löfberg

5,3401811

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  One trivial detail—the vector $p$ norms are SOCP-representable only for rational $p$. You'll need that power code for the fully generic case. And I personally don't know about the representability of induced matrix $p$-norms (other than $1$, $2$, and $infty$).
  $endgroup$
  – Michael Grant
  2 days ago
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Johan I don't understand what you mean by: 'In addition to that, you have that... (which you also can through intricate modelling...)'. Could you elaborate/ give a simple example?
  $endgroup$
  – Noel
  yesterday
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  What I mean is that you through SDP modelling can represent the function $f(v)$ where $v$ are the eigenvalues of a symmetrix matrix and $f$ is any permutation invariant conic representable function.
  $endgroup$
  – Johan Löfberg
  yesterday
  

  
  
  
  

add a comment | 

$begingroup$

A lazy answer would be to simply list the help on norm which lists cases that are supported out of the box in the modelling language YALMIP (which would write these using LP/SOCP/SDP formulations)

 For matrices...

   norm(X)       models the largest singular value of X, max(svd(X)).

   norm(X,2)     is the same as norm(X).

   norm(X,1)     models the 1-norm of X, the largest column sum, max(sum(abs(X))).

   norm(X,inf)   models the infinity norm of X, the largest row sum, max(sum(abs(X'))).

   norm(X,'inf') same as above

   norm(X,'fro') models the Frobenius norm, sqrt(sum(diag(X'*X))).

   norm(X,'nuc') models the Nuclear norm, sum of singular values.

   norm(X,'*')   same as above

   norm(X,'tv')  models the (isotropic) total variation semi-norm 

 For vectors...

   norm(V) = norm(V,2) = standard Euclidean norm.

   norm(V,inf) = max(abs(V)).

   norm(V,1) = sum(abs(V))

In addition to that, you have that $(sum |x_i|^p)^{1/p}$ is conic representable for $pgeq 0$ (second-order cone, or more conveniently but perhaps slightly more esoteric using the power cone) thus covering arbitrary Schatten p-norms on matrices, as long as you can get that operator to act on a vector which upper bounds a sorted vector of the eigenvalues of $X^TX$ (which you also can through intricate modelling...)

Everything is available in (but hidden well...)

Nesterov, Yurii; Arkadii, Nemirovskii (1995). Interior-Point
Polynomial Algorithms in Convex Programming. Society for Industrial
and Applied Mathematics. ISBN 0898715156.

share|cite|improve this answer

answered 2 days ago

Johan LöfbergJohan Löfberg

5,3401811

$endgroup$

 For matrices...

   norm(X)       models the largest singular value of X, max(svd(X)).

   norm(X,2)     is the same as norm(X).

   norm(X,1)     models the 1-norm of X, the largest column sum, max(sum(abs(X))).

   norm(X,inf)   models the infinity norm of X, the largest row sum, max(sum(abs(X'))).

   norm(X,'inf') same as above

   norm(X,'fro') models the Frobenius norm, sqrt(sum(diag(X'*X))).

   norm(X,'nuc') models the Nuclear norm, sum of singular values.

   norm(X,'*')   same as above

   norm(X,'tv')  models the (isotropic) total variation semi-norm 

 For vectors...

   norm(V) = norm(V,2) = standard Euclidean norm.

   norm(V,inf) = max(abs(V)).

   norm(V,1) = sum(abs(V))

share|cite|improve this answer

answered 2 days ago

Johan LöfbergJohan Löfberg

5,3401811

answered 2 days ago

Johan LöfbergJohan Löfberg

5,3401811

answered 2 days ago

Johan LöfbergJohan Löfberg

5,3401811