Nonconvex qcqp dual

1

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_iP_i), [q_0 + sum(lamda_iq_i)]/2;
[q_0 + sum(lamda_iq_i)]^T/2 -gamma] == semidefinite % Please forgive the indefinite notation

lamda_i >= 0

How do I code the LMI semidefinite constraint in CVX?

2

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

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).

3

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.