Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 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)$.

share|improve this answer
    
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! –  user8994 Apr 5 '11 at 10:26
    
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$. –  FEQ Apr 5 '11 at 15:34
    
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 problem –  user8994 May 19 '11 at 11:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.