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
    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