0
$\begingroup$

The nuclear norm (trace norm) of a matrix $X \in \Bbb R^{m \times n}$ is defined as

$$\|X\|_* := \sum_{i=1}^{\min(m,n)} \sigma_i(X)$$

where $\sigma_i(X)$ are the singular values of $X$.

The optimization problem I met is as follows, $$ \max_X \|X\|_* $$ where $X\in \Bbb R^{m\times n}$ needs meet the constraints: $X_{ij}\ge 0$ and $\sum_{j=0}^n X_{ij}=1$. That is to say, each row of $X$ is a probability distribution.

Question: I want to prove that the optimal solution $X^*$ is only attained at corner points of the feasible region, i.e., the row of $X^*$ is from the set $\{e_1,...,e_n\}$, where $e_i$ is a standard orthogonal basis vector of the space of $\Bbb R^n$.

What I have done is constructing a new optimization problem $F(X_k)$ as follows, and prove $F(X_k)$ is strictly convex. Then the problem can be solved by proof by contradiction. However, I can't prove it. I also posted a question on Mathematics StackExchange, but there hasn't been an answer until now.

$$\max_{X_k}F(X_k)=\|X\|_*$$

where $X_k$ is the $k$-th row of $X$, and the constraints for $X$ are the same as abovementioned.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The nuclear norm $\|\cdot\|_*$ is a norm and hence a convex function. On the other hand, the set $$S:=\{X\in\mathbb R^{m\times n}\colon X_{ij}\ge0\text{ and }\sum_{j=1}^n X_{ij}=1\ \forall i,j\}$$ is convex and compact. So, the maximum of the nuclear norm $\|\cdot\|_*$ on the set $S$ is attained at an extreme point of $S$, which is clearly a matrix $X\in S$ such that one entry of each row of $X$ is $1$ and the other entries are $0$. (You have to allow the non-strict inequalities $X_{ij}\ge0$ for the maximum to be attained.)

Improve this answer
$\endgroup$
10
  • $\begingroup$ 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. $\endgroup$
    – Jack
    Commented Jul 7, 2020 at 18:58
  • $\begingroup$ @Jack Why is Iosif Pinelis' answer not correct? $\endgroup$
    – Mark L. Stone
    Commented Jul 10, 2020 at 16:05
  • $\begingroup$ @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. $\endgroup$
    – Jack
    Commented Jul 10, 2020 at 16:14
  • $\begingroup$ 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? $\endgroup$
    – Mark L. Stone
    Commented Jul 10, 2020 at 16:43
  • $\begingroup$ @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. $\endgroup$
    – Jack
    Commented Jul 10, 2020 at 17:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .