Minimum of a minimum in CVX


#1

Hi,

Sorry if this is a basic question. I’m new to CVX and my problem is as follows - I have tried to create a minimum working example:

Variable \rho is a matrix
Minimize Tr(\rho A) + \inf_{\sigma \in X} D(\rho, \sigma).

Here D is the trace distance between \rho and \sigma for \sigma \in X, where X is a convex set. Hence the objective function is indeed convex. The first part can be expressed using norm_nuc. How do I express \inf_{\sigma \in X} D(\rho, \sigma)? Can CVX do this type of minimum of a minimum optimization?


#3

Perhaps my notation is confusing or there is an error in terminology so let me clarify the problem first. I have some convex set X embedded inside a larger set A. So X \subset A. I have elements \rho \in A. The function D(\rho, \sigma) = ||\rho - \sigma|| finds \sigma \in X such that the distance (any valid metric) from \rho to \sigma is minimized.

It is the shortest line from \rho to X.

Proof that this is convex:
Consider \rho_1, \rho_2 \in A and let \sigma_1, \sigma_2 \in X be the respective closest points.
For any \lambda\rho_1 + (1-\lambda)\rho_2, we want to show that there exists \sigma_3\in X such that ||\lambda\rho_1 + (1-\lambda)\rho_2 - \sigma_3|| \leq \lambda ||\rho_1 - \sigma_1|| + (1-\lambda)||\rho_2 - \sigma_2||

Let \sigma_3 = \lambda \sigma_1 + (1-\lambda)\sigma_2. Since X is convex, \sigma_3\in X. Then we have,
||\lambda\rho_1 + (1-\lambda)\rho_2 - \sigma_3|| = ||\lambda(\rho_1 - \sigma_1) + (1-\lambda)(\rho_2 - \sigma_2)|| \leq \lambda ||\rho_1 - \sigma_1|| + (1-\lambda)||\rho_2 - \sigma_2||.

The last line uses a triangle inequality.


(Mark L. Stone) #4

http://cvxr.com/cvx/doc/advanced.html#new-functions-via-partially-specified-problems


#5

Sorry, I tried to understand how this was done but couldn’t quite follow. Would you be able to add a few words, specific to my problem?

In the meantime, I discovered a CVX approved way of writing \sigma \in X as a constraint. Then I simply take variables \rho and \sigma, write the objective function as it is an impose the constraint \sigma \in X. However, the runtimes are very slow. Is my way of doing it equivalent (in terms of computational time) to the partially specified problems method?


(Mark L. Stone) #6

Follow the Huber example in that section. You need to write a function,D_function. Then call that function from your top level CVX program.

Show us your program with the “CVX approved way of writing \sigma \in X as a constraint”. Then perhaps someone, not necessarily me, will comment on it.