Return to Question

Preliminary: 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.

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.

Preliminary: 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, $$ F(X) = \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^*$ to $F(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.

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

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

Preliminary: 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.

Preliminary: 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, $$ F(X) = \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 to $F(X)$ is only attained at corner points of the feasible region, i.e., from the set $\{e_1,...,e_n\}$, where $e_i$ is a standard orthogonal basis vector of the space of $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.

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

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

Preliminary: 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, $$ F(X) = \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^*$ to $F(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.

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

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