0
$\begingroup$

the problem i have is like following: $x'Qx + f'x \rightarrow \min_x$ subject to $Ax \le 0$. $Q \ge 0$, so there's nothing wrong there, usual QP with a linear constraint. Is there a way to relax the constraint by introducting a cost of violating it?

Just to be more clear: ideally, I'd like to be able to solve something like $x'Qx + f'x + \lambda max(Ax, 0) \rightarrow \min_x$, where $max(Ax, 0)$ is component-wise maximum of Ax and 0.

1 Answers 1

1

Look for penalty methods, or barrier methods.

Also, you may want to try something like

$x'Qx+f'x+ \mu || \max(Ax,0) ||^2$

which is differentiable. So you could solve it as an unconstrained optimization. You need some other methods for determining $\mu$ or a series of $(\mu_k)$.

  • 0
    I believe you meant convex, not differentiable (it's not differentiable on the hyperplane Ax=0). But you're absolutely right, it is convex and even more, this problem could be transformed to quadratic by a simple trick, so thanks that really helped!2011-04-05
  • 0
    I think, it is differentiable. In the most simplest case, consider $0.5 (\max(x,0))^2$, whose derivative is $x$ if $x\geq 0$; $0$ otherwise. So it is differentiable at $x=0$.2011-04-05
  • 0
    yes, you're absolutely right, it is differentiable for 2-norm! Actually, now I think my question was stupid from the very beginning, because introducting a new variable $t$, such that $t >= 0$ and $t \ge Ax$ with a objective function of $x'Qx+f'x+\lambda t \rightarrow \min$ directly solves the problem2011-05-19