3
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\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.