4
$\begingroup$

Does anybody have any idea about how to solve the following problem with Coordinate Descent? \begin{align} \min &\quad \mathbf{x}^{\top}P\mathbf{x} + b^{\top}\mathbf{x}\\ \text{Subject to}& \quad A\mathbf{x} \leq c \end{align}

I don't want to use the Bump Function technique and need the Coordinate Descent to be able to solve it in high dimensions.

  • 0
    The OP didn't specify if the problem is convex, i.e., is the matrix $P$ positive (semi-)definite?2012-11-30

2 Answers 2

2

assuming $P$ to be positive semi-definite, your problem is simply a standard QP with linear constraints. Unless it shows some peculiarities in the linear constraints, the structure of $P$ or a huge dimension, I would just pick up any established QP solver (MOSEK, CPLEX, Gurobi...) or even just quadprog in MATLAB.

The papers you refer to deals to some specific situations:

  • Tseng et al. considers non-smooth functions and this is not your case.

  • Lin et al. is particularly focused on SVN application which are really huge problems. But in that case they solve the dual which a box-constrained QP which is somehow easier.

In general I would search for QP algorithms well before implement your own.

0

I think the following paper answers my question to a great extent:

Tseng, Paul, and Sangwoon Yun. "A coordinate gradient descent method for nonsmooth separable minimization." Mathematical Programming 117.1-2 (2009): 387-423.