1
$\begingroup$

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

$\endgroup$
  • $\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 Dec 14 '15 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$ – Brian Borchers Dec 14 '15 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 Dec 15 '15 at 7:53
1
$\begingroup$

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}$

as

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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