Optimization of sum of two quadratic over linear function

Uncategorized
Mar 18, 2016
M
#1

I’m computer science student. Iam looking for some helps concerning the resolution of an optimization problem.
I have an optimization problem defined on two sets \mathcal{X}=\{x_i\}_{i=1}^n and \mathcal{Y}=\{y_j\}_{j=1}^m and described as follows

\begin{equation} \begin{aligned} & \underset{\alpha, \beta}{\text{max}} & & \sum_{i=1}^n \alpha_i x_i^T x_i-\frac{\sum_{i=1}^n \sum_{j=1}^n \alpha_i x_i^Tx_j \alpha_j}{\sum_{i=1}^n \alpha_i}+\sum_{k=1}^m \beta_k y_k^T y_k-\frac{\sum_{k=1}^m \sum_{l=1}^m \beta_k y_k^Ty_l \beta_l}{\sum_{j=1}^m \beta_j }\\ & \text{subject to} & & 0 \leq \alpha \leq C1 \\ & & & 0 \leq \beta \leq C2 \\ \end{aligned} \end{equation}

Please help me how can I resolve it using CVX.

Thanks a lot.

E
#2

Is \sum_i \sum_j \alpha_i x_i^T x_j \alpha_j concave i.e. is it concave in \alpha. If that is not the case I doubt cvx can help you.

1 reply
M
#3
Replying to #2

I believe they are concave, since they are kernel matrices, and this is maximization, so it should be OK.

M
#4

I think what you have to do here is assemble the matrices X and Y from those inner products, so that X_{ij}=x_i^Tx_j and Y_{ij}=y_{ij}, etc. Once you do that, I think the objective becomes

diag(X)'*alpha - quad_over_lin(sqrtm(X)*alpha,sum(alpha)) - diag(Y)'*beta - quad_over_lin(sqrtm(Y)*beta,sum(beta)