# Nonconvex qcqp dual

I’m interested in solving the dual of a nonconvex qcqp, similar to that described in section 2.2 of this paper: http://www.stanford.edu/class/ee392o/relaxations.pdf

This involves concatenating an LMI with affine expressions, which I don’t understand how to code in cvx.

The problem is in this form:

max gamma + sum(lambda_ir_i) + r_0
subject to:
[P_0 + sum(lamda_i
P_i), [q_0 + sum(lamda_iq_i)]/2;
[q_0 + sum(lamda_i
q_i)]^T/2 -gamma] == semidefinite % Please forgive the indefinite notation

lamda_i >= 0

How do I code the LMI semidefinite constraint in CVX?

I’m going to take a stab at answering your question. It’s not entirely clear what you want to solve, but it seems like \lambda is your variable, and you want to solve something like

\begin{array}{ll} \mbox{maximize} & \gamma + \sum_{i=1}^n \lambda_i r_i \\ \mbox{subject to} & P_0 + \sum_{i=1}^n (\lambda_i P_i) \in \mathcal{S}^n_+ \end{array}

I can’t actually parse the rest of your problem (if you update it, or ask a follow-on, I might be able to give you some more help).

Anyway, it turns out that you can write your CVX code like the math (assuming your P matrices are stored in a cell array):

cvx_begin
variable lambda(n)
maximize gamma + lambda'*r
subject to
constr = P{0} % this *has* to be a single equals (an assignment)
for i = 1:n
constr = constr + P{i}*lambda(i)
end
constr == semidefinite(n) % this *has* to be a double equals (a set constraint)
cvx_end


Hope that gives you some idea about how to do this! Feel free to ask for clarification.

Update: Now that I see your problem, I can write the CVX code for you.

cvx_begin
variables lambda(m) gamma
maximize ( gamma + lambda'*r + r0 )
% this will form the upper left part of the matrix
% (it's important that these are single equals)
X11 = P0;
for i = 1:m,
X11 = X11 + lambda(i)*P(:,:,i);
end

% this will form the upper right
X12 = q0;
for i = 1:m,
X12 = X12 + lambda(i)*q(:,i);
end
X12 = (1/2)*X12;

% lower left is the same as upper right

% finally, the constraints
[X11 X12; X12 -gamma] == semidefinite( % you have to figure out the dimensions )
lambda >= 0
cvx_end


To get a better understanding of why we use the assignment “=” instead of the equality “==”, you might want to read up on expressions in CVX (section 3.8 of the user guide).

Here’s the best of the Latex I could learn in 15 min:

$$\underset{x}{\text{maximize}};\gamma + \displaystyle\sum\limits_{i=1}^m \lambda_ir_i+r_0$$
$$\text{subject to:};\left( \begin{array}{ccc} P_0+\displaystyle\sum\limits_{i=1}^m \lambda_iP_i & (q_0+\displaystyle\sum\limits_{i=1}^m \lambda_iq_i)/2 \ (q_0+\displaystyle\sum\limits_{i=1}^m \lambda_iq_i)^T/2 & -\gamma \ \end{array} \right)\succeq 0$$
$$-\lambda\leq0$$

The variables are the scalar gamma and vector lambda.

The P_i's are known matrices that are not necessarily PSD and the q_i's and r_i's are known vectors.

I basically don’t know how to code/setup the semidefinite constraint in CVX.