optimization of normalized 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)$$

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 describing the different mathematical steps for solving such problem in order to make the necessary implementation.

thanks.

In fact, $ b^t=\left[b_1,...,b_N\right] $ is a parameter vector. $B=\left[b_{ij}\right] $ is a symmetric matrix of parameters. $ \alpha 1_N $ denotes the product of the vectors of alpha by the vector of ones (with size $N$). i.e $ \alpha 1_N = \sum_{i=1}^{N} \alpha_i $. $C$ is a parameter. — MahopeRam, Jul 22 '15 at 12:46
$0 \leq \alpha \leq C $ mean that $ \forall i \in {1,...,N}, \quad 0 \leq \alpha_i \leq C $. — MahopeRam, Jul 25 '15 at 15:50

score 0 · Answer 1 · answered Jul 26 '15 at 11:41

This is rectangle constrained optimization problem. First solve the unconstrained problem, then check is the constraints are fullfield if not then solve the problem on each edge of the contrains ($\alpha_i = C$, $\alpha_i = 0$), and choose the minimum.

Solving the unconstrained problem: \begin{equation} f(\alpha)=\frac{\alpha^T B\alpha}{2\sum_{i=0}^{n}{\alpha_i}}+b^T\alpha \end{equation} This is looks very similar to quadratic problem, but it is some kind of rational function. Therefore I would just use an iterative method.

\begin{equation} \alpha_{n+1}=\alpha_n+\gamma d\alpha \end{equation}

You can use gradient-desent it is the most simple to perform but it is the most slow solution. I would suggest Newton's method, and find $d\alpha$ from:

\begin{equation} Hf(\alpha)d\alpha=\nabla f(\alpha) \end{equation}

I didn't check this but i think that in this case the hessian matrix will be positive definite, and allow you to find $d\alpha$ by using the cholesky decomposition.

optimization of normalized quadratic function

1 Answers1