0

I have devised some function that I wish to minimize. Overall the function is not convex, but it is so on the relevant constraint set of its arguments (which is also convex). My question is now whether the overall nonconvexity of the function may render the whole problem a nonconvex one, despite the fact that optimization takes place only in some convex domain where the function is also convex. My intuition say that this shouldn’t pose a problem, but I am lacking a strict argument, let alone a proof.

any help is appreciated…

Andreas Steimer
  • 128
  • I'd say it's a duplicate of this one: http://math.stackexchange.com/questions/2038759/why-is-it-necessary-to-have-convexity-outside-the-feasible-region – Michael Grant Mar 30 '17 at 21:33
  • Ah, no, it's not. In this case, there's an important distinction: your feasible region is nonconvex. In that case, you can find an initial feasible point without having to consider the nonconvexity of the objective at all. – Michael Grant Mar 30 '17 at 21:36

1 Answers1

1

If you define your function only on the convex set of relevant arguments, then it will be a convex function, regardless of possible extensions outside this set. Methods for minimizing convex functions on convex sets will then work as advertised.

A.G.
  • 2,781
  • 1
    In practice it may depend on whether one is handling constraints using a barrier method (where the iterates stay within the constraint set) or a penalty method (where they may venture outside temporarily). –  Mar 30 '17 at 11:55
  • Thanks for your comments A.G. and Rahul, I was also thinking about penalty methods posing a problem in this case. Luckily however I am using block coordinate descent for minimization, where the parameters are guaranteed to stay inside the constraint set. So referring back to A.G.'s answer this should be an ok method, right? – Andreas Steimer Mar 30 '17 at 14:17
  • @AndreasSteimer Right! – A.G. Mar 30 '17 at 18:30
  • 1
    Even if you use a barrier method, you have to find a feasible point first. If you can do that, you're fine, otherwise, you're back to the same nonconvex problem you had before. – Michael Grant Mar 30 '17 at 21:34
  • In my case (which for the sake of laziness I have not mathematically defined here, sorry for that) finding a feasible point is not a problem at all. In fact, the feasible region is super simple, it just consists of the cartesian product of the set of pos. definite matrices with the nonnegative reals. – Andreas Steimer Mar 31 '17 at 21:07