Timeline for Prove the optimal solution to maximizing nuclear norm with constraints is attained at corner points of feasible region
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 23, 2023 at 4:13 | comment | added | Rylan Schaeffer | @MarkL.Stone and Iosif , can I ask you two to please take a look at my question over here? math.stackexchange.com/questions/4757229/… I discovered this question while hunting for an answer to my own and I'm hopeful one of you two might know how to answer my question | |
| Jul 11, 2020 at 1:24 | comment | added | Jack | @MarkL.Stone Strict convexity can be used to prove my conclusion. However, my conclusion is possible to be true for convex functions which are not strictly convex. | |
| Jul 10, 2020 at 20:41 | comment | added | Mark L. Stone | You mean it's convex, not strictly convex? Well, you're the one claiming there can't be a non-extreme global optimum. Neither @Iosif Pinelis nor I have made such a claim. | |
| Jul 10, 2020 at 20:17 | comment | added | Iosif Pinelis | @MarkL.Stone : The difficulty is that the nuclear norm, given by the formula $\|X\|_*:=\text{trace}\sqrt{X^TX}$, is not strictly convex. | |
| Jul 10, 2020 at 19:06 | comment | added | Mark L. Stone | I think you should be able to differentiate the nuclear norm with respect to the matrix elements, using $\|X\|_* = \sqrt{trace(X^TX)}$ | |
| Jul 10, 2020 at 17:11 | comment | added | Jack | @MarkL.Stone I plotted the objective values in the case of two dimensions. I found what I want to prove is true. And I believe it's also true for higher dimensions. I think the main difficulty is from the unusual definition of nuclear norm of a matrix. The definition seems disconnected from the original elements of the matrix because of the operation of SVD. So I can't find the proper tool to study the behavior of nuclear norm with respect to the change of elements of the matrix. | |
| Jul 10, 2020 at 16:43 | comment | added | Mark L. Stone | Yes, the result quoted by @Iosif Pinelis is a well-known result that if there is a global optimum of a concave programming problem (i.e., minimizing a concave function (or, equivalently, maximizing a convex function) subject to convex constraints) with compact (convex) constraints, there is a global optimum at an extreme of the constraints. That does not rule out that there could be additional global optima located elsewhere..Why do you think that situation could be avoided for your problem? | |
| Jul 10, 2020 at 16:14 | comment | added | Jack | @MarkL.Stone My question is to prove that the optimal solution is only attained at the extreme point of $S$ and can't be other points. That is to say, being an extreme point is a necessary condition for an optimal solution. I gave a counterexample based on losif Pinelis's answer. For example, $F(X)=1$ is a convex function, but the optimal solution is attained at any feasible solution. Thus, it's not enough to only depend on the convexity of nuclear norm. | |
| Jul 10, 2020 at 16:05 | comment | added | Mark L. Stone | @Jack Why is Iosif Pinelis' answer not correct? | |
| Jul 7, 2020 at 18:58 | comment | added | Jack | I'm sorry but there is ambiguity in my question. I mean the optimal solution in only attained at extreme points. I have updated the question accordingly. For example, $F(X)=1$ is a convex function, but the optimal solution is attained at any feasible solution. | |
| Jul 7, 2020 at 18:38 | history | edited | Iosif Pinelis | CC BY-SA 4.0 |
edited body
|
| Jul 7, 2020 at 18:30 | history | answered | Iosif Pinelis | CC BY-SA 4.0 |