1

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

alya
  • 11
  • 1
  • Welcome to SciComp.Exchange. Is the $X$ a vector? If it is, how can you divide by a vector in your reformulation? – nicoguaro Dec 14 '15 at 21:17
  • 1
    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.) – Brian Borchers Dec 14 '15 at 22:06
  • 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 – alya Dec 15 '15 at 07:53

1 Answers1

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

as

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

Brian Borchers
  • 18,719
  • 1
  • 39
  • 70
  • Thanks Mr Brian for your answers. I have used your answer to a problem presented in http://scicomp.stackexchange.com/questions/20292/minimization-of-normalized-constrained-quadratic-function – alya Dec 15 '15 at 03:50