I am looking for some helps concerning 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} $$ where $C1$ and $C2$ are two given parameters. I'm asking if the above problem can be rewritten in the follwing form $$ \begin{equation} \begin{aligned} & \underset{X}{\text{max}} & & \frac{ X^T H X}{X}+A^TX\\ %\mathbf {1}_N & \text{subject to} & & 0 \leq X \leq C \\ \end{aligned} \end{equation} $$ If yes what would be the value of $H$,$A$ and $X$ and if not how can I optimize the first formulation by matlab knowing that the second formulation can be optimized in matlab by CVX package for convex optimization using its "quad_over_lin" function.
Thanks a lot

  • $\begingroup$ Welcome to SciComp.Exchange. Is the $X$ a vector? If it is, how can you divide by a vector in your reformulation? $\endgroup$
    – nicoguaro
    Commented Dec 14, 2015 at 21:17
  • 1
    $\begingroup$ Presumably the denominator should be $B^{T}X$ where $B$ is a constant vector (in this case it would be the vector of all ones.) $\endgroup$ Commented Dec 14, 2015 at 22:06
  • $\begingroup$ Yes, as noted by Mr. Brian Borchers, the denominator take the form of $ B^T X$ where $B $is a vector of ones and $X$ depends on $\alpha$ and $\beta$. Thanks $\endgroup$
    – alya
    Commented Dec 15, 2015 at 7:53

1 Answer 1


This question sounds a lot like a homework exercise, so I'll simply give a couple of hints.

  1. Break your objective into the sum of two of two terms, and then use the "epigraph trick" on each separately. So, you'd have

$\max s + t$

subject to

$s \leq -\mbox{quad_over_lin(...)}$

$t \leq -\mbox{quad_over_lin(...)}$

  1. Recognize that the two parts of your objective function are already almost in quad_over_lin form. How can you write

$\sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_{i} x_{i}^{T}x_{j} \alpha_{j}$


$\| X\alpha \|_{2}^{2}$?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.