Modified Optimal configuration

I have a question about how to write the following model in CVX.
It is called “optimal configuration” or “graph realization” and It is the modified model
number (8) in the paper by Sun et al.
I do not really how to solve this model using CVX, especially the
constraints and how to write the vertices and edges?

The model is like:

\begin{array}{ll} \min & y\\ s.t. & \sum_i \| x_i \|^2 = 1 \\ & \| x_i - x_j \|^2 \leq y~~~ (ij \in E)\\ & \sum_i x_i = 0\\ & x_i \in \mathbb{R}^n, y \in \mathbb{R} \end{array}

where i’s are nodes of the graph and ij are edges.
Thanks for the comments in advance.

You don’t need to explicitly write out the vertices and edges per se. For each edge, there will be a d_i_j, which is the problem input data. Model (8) has a norm(xi-xj) <= d_i_j constraint for each edge.

Note that (8) is not a convex optimization problem, as it is a maximization of a convex objective. Therefore, if you wish to use CVX, you will need to solve a different formulation, such as the primal, model (3), whose dual is equivalent to model (8), and which is convex and expressible as a DCP.

As to your modified model, you are solving a different and non-equivalent optimization problem, whose merits and “purpose” vs. the optimization problem in the paper are, I believe, outside the scope of discussion for this board. Nevertheless, I believe you meant to minimize y, not maximize y as you have written.

@Mark L. Stone: thanks. I changed it little bit. How about this modified model? now we do not have any data for constraint and it is going to minimize the bound of distance between nodes.

thank a lot. You are right. it is a minimization for sure.

@Mark L. Stone: Thanks for the comments.
I have now difficulty with the second constraint and I have an DCP error. could you please let me know how it could be written in CVX?

I think you’re out of luck on the first constraint (non-convex). As to the 2nd constraint, use norm instead of norm^2 (you can “absorb” the sqrt in the y and still minimize y) or “if you must square”, use square_pos(norm())

thanks, what would you suggest for solving this model then? I mean shall I use another solver rather than CVX, like SeDumi or etc.?

If you really want to solve model(8), then solve model(3) via CVX. If your so-called modified model is what you really want to solve, then unless you have some good trick, choose from among http://www.neos-guide.org/content/nonlinear-programming-software for local solvers or (continued)

from http://www.neos-guide.org/content/global-optimization-software for global solvers. Perhaps someone else can give you more specific guidance or tricks (dualizing, user of integer variables, or whatever).

duplicate post

from http://www.neos-guide.org/content/global-optimization-software for global solvers. Perhaps someone else can give you more specific guidance or tricks (dualizing, user of integer variables, or whatever).