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

  • 1
    I don't think you can solve the constrained problem directly using coordinate descent. For example, consider $\min \{ x^2+y^2 | x+y \geq 1 \}$. If you are at the feasible (but not optimal) point $(\frac{1}{4}, \frac{3}{4})$, then you cannot obtain a descent along the coordinates.2012-07-09
  • 0
    Finding gradient is not required. I searched more and found the following paper: C.-J. Hsieh, K.-W. Chang, C.-J. Lin, S. S. Keerthi, and S. Sundararajan, “A dual coordinate descent method for large-scale linear SVM,” in ICML’08. What they do is to fix all but one variable and solve QP for the fixed variable which is certainly simple.2012-07-09
  • 0
    I understand the idea. But if you take the problem I described above, the point I mentioned is optimal in each coordinate if you take just one coordinate at a time. That is, the QP in either variable is already solved, but is non-optimal for the original problem (which is minimized at $(\frac{1}{2},\frac{1}{2})$, of course).2012-07-09
  • 0
    The constraints in the paper are 'box' constraints, not a general constraint like $Ax \leq c$. Box constraints (ie, of the form $x_i \in [\underline{x}_i, \overline{x}_i]$) *are* amenable to coordinate-wise solution.2012-07-09
  • 0
    You are right! I experienced that problem with Coordinate Descent in another problem.2012-07-27
  • 0
    If we consider $min\{x^2+y^2\mid x+y\leq 1 , x\geq 0 , y\geq 0\}$, can we use the Coordinate Descent to get the answer $(0,0)$ from any starting point in the interior of feasible region?2012-10-19
  • 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