|
I am not sure what is the proper term for what I am looking for. Let's say I have an optimization problem with a quadratic objective and linear inequality constraints. Now lets say I partition my constraints into K non-overlapping groups. Question 1: I want to optimize the objective, such that at least one of the groups of constraints are satisfied. (this is easy to do by solving K optimization problems, one for each of the groups of constraints, and taking the minimum among these. But can it be done more efficiently in one take?) Question 2: I want to change the objective to include a term for the number of satisfied groups of constraints, so the optimization should balance between finding the minimum objective and satisfying as many as possible (but at least one) of the groups of constraints. This is easy to model if I could drop the "at least one group" requirement (by adding slack variables).
This is also easy to model if the slack variables are allowed to be binary, but that turns the problem into a mixed-integer programming, which is NP-hard. Is there a trick for achieving the same goal while remaining efficient? |
|
How about you add slack variables and then look at the pareto-optimal curve (i.e., the regularization path returned by LARS is a pareto-optimal curve; here you'd be looking at how the objective changes as alpha changes and how the constraints change as alpha changes) if this turns out to be easy? Maybe with an objective like f0(x) + alpha sum_i fi(x) where f0(x) is your original objective and fi(x) is something that grows/shrinks with the satisfaction of each constraint group you can get good results with warm restarts in the optimization problem and bisection to find the inflection points? Or maybe even LARS will do here, as LARS optimizes something very similar to this linear/quadratic thing? Thanks. I don't know what LARS is, and it is a really tough term to google for.. can you provide a link?
(Aug 23 '11 at 09:14)
yoavg
1
LARS is least angle regression http://en.wikipedia.org/wiki/Least-angle_regression , an algorithm for l1-regularized least squares that gives you the full regularization path (pareto-optimal curve) for "free".
(Aug 23 '11 at 09:24)
Alexandre Passos ♦
Thanks,I'll look into that!
(Aug 23 '11 at 09:44)
yoavg
@Alexandre: can you elaborate a bit more on this idea? There is a single parameter alpha that controlls all the group constrains? And you look at the regularization path of alpha? Where do the slack variables fit in? Thanks!
(Aug 24 '11 at 05:25)
Andreas Mueller
1
@Andreas: I have no idea if in this specific problem this will work, as there are some conditions. If you can rewrite each group of constraints as a single constraint (say, scaling and shifting them and then putting a limit on their maximum/minimum norm) so that you can tell when all are satisfied, write the problem like a lagrangian, something like min. f0(x) + alpha sum_c fc(x), where fc(x) is each of these functions that capture whether a whole group of constraints is satisfied or not. As you increase alpha you should see more groups being satisfied as the constraints become more important than the objective, so you can kind of squint and look at this as a regularization path. This assumes a lot about the problem structure, which is why it might not work.
(Aug 24 '11 at 07:25)
Alexandre Passos ♦
Thanks! I think I got it now. Maybe I'll give it a try :)
(Aug 24 '11 at 07:32)
Andreas Mueller
showing 5 of 6
show all
|
I feel that this has something in common with multiple instance learning, where there are some convex constrains and a hard max constraint. For 2): A common approach there is to alternate the assignment of constrains to be satisfied and the optimization with a fixed set of constrains. This is of course just an approximation procedure for the mixed integer programming problem.
I think multiple instance learning can be cast as a problem of the kind of question 2). There are some methods for that but most are not convex, so .I don't think you'll find an easy solution