minimization of normalized constrained quadratic function

Question

I'm a computer science student. Please I need a help in solving a constrained normalized quadratic function. I'm familiar with solving quadratic constrained optimization function with matlab by providing a symmetric matrix and a vector as inputs for quadprog matlab function. Now, I encountered an other form of quadratic function described as follows:

$$ \min_{0 \leq \alpha \leq C} \left( \frac{1}{2} \frac{\alpha^tB\alpha}{\alpha1_N}+ b^t\alpha \right)$$

where $ b^t=\left[b_1,...,b_N\right] $ is a parameter vector. $B=\left[b_ij\right] $ is a symmetric positive matrix of parameters. $ \alpha 1_N = \sum_{i=1}^{N} \alpha_i $. $0 \leq \alpha \leq C $ mean that $ \forall i \in {1,...,n}, 0 \leq \alpha_i \leq C $. I don't know how I can deal with such function. Can I rewrite the normalized quadratic function as a quadratic function? Is there any tutorial, any link describing the different mathematical steps for solving such problem in order to make the necessary implementation?

thanks.

Answer 1

A good starting point for this is Boyd and Vandenberghe's textbook, Convex Optimization. I'd strongly encourage you to get a copy (the authors have posted a free .pdf online, so it won't cost you anything, and the hardcover edition from Cambridge University Press is quite reasonably priced.)

Begin by Cholesky factoring your symmetric and positive definite matrix $B$ as

$B=R^{T}R$

Then write your problem as

$\min \frac{z^{T}z}{y} + b^{T}\alpha$

where

$z=R\alpha$

and

$y=2\alpha^{T}1_{N}$.

Introduce an auxilliary variable $t$, and write the problem as

$\min t + b^{T}\alpha$

subject to

$\frac{z^{T}z}{y} \leq t $

$z=R\alpha$

$y=2\alpha^{T}1_{N}$

$0 \leq \alpha \leq C$

At this point, you've got a linear objective function and a bunch of linear equality and inequality constraints in the variables $\alpha$, $z$, $y$, and $t$. Also, the constraints ensure that $y>0$ and $t \geq 0$.

The only difficult part is the hyperbolic constraint

$\frac{z^{T}z}{y} \leq t$.

Since $y>0$, this can be written as

$z^{T}z \leq ty$.

A clever trick from convex optimization (it's an exercise in the Boyd and Vandenberghe book) is that this hyperbolic constraint can be written as a second order cone constraint

$\left\| \left[ \begin{array}{c} 2z \\ y-t \\ \end{array} \right] \right\|_{2} \leq y+t $

At this point, you've got a standard second order cone programming problem that can be solved by a variety of solvers.

The CVX package for convex optimization in MATLAB can do this reformulation for you automatically using its "quad_over_lin" function.