1
$\begingroup$

I have an algorithm (in R) that maximizes a convex function on a compact convex set in every iteration. Based on the maximum principle, I know that the maximima are only attained on the boundary. But my current implementation searches in the whole space which is not necessary and time-consumer. To increase the time efficiency, I would like to narrow the search space, but I couldn't find any algorithm that only searchs on the boundary. Any help is appreciated.

Edit: The dimension can very from 2 to 6. For case 2 the compact set is a rectangle [a, b]*[c, d] and the boundary is the perimeter of the rectangle. The function is nonlinear.

P.S. I have the R code, but if I publish it here then my question would be transfered to Stack Overflow, which I don't think is a right place for my problem. I am looking for an algorithm or optimization method only the boundary.

$\endgroup$
  • $\begingroup$ You could of course only optimize over the points on the boundary. The questions I would have in that case all relate to how simple it is to describe this set of points that make up the boundary -- in particular, how many dimensions you have, and how you describe the compact set over which you optimize (i.e., how are the inequality constraints defined)? $\endgroup$ – Wolfgang Bangerth Dec 27 '14 at 23:27
  • $\begingroup$ @WolfgangBangerth, I edited my question based on your comment. I am not sure if this extra information (maxima on the boundary) can be called as a CONSTRAINT because without this extra information the optimization algorithm automatically find the maxima, but with some unecessary searches inside the region. The purpose is to boost the optimization algorithm, not to pose a constraint or penalty and slow it down. $\endgroup$ – Ehsan Dec 28 '14 at 0:34
  • 1
    $\begingroup$ What is the optimization problem? Why use PSO instead of an active set method? $\endgroup$ – Geoff Oxberry Dec 28 '14 at 1:48
  • $\begingroup$ @GeoffOxberry PSO is not necessary. You can also use local optimizer. I added the function, however I think it makes the question look more complicated nad specific. My question is simple: How we can implement the result of maximum principle in our numerical algorithm? $\endgroup$ – Ehsan Dec 28 '14 at 11:31
  • 1
    $\begingroup$ Isn't it that the maxima lie on the extreme points of the set? If you are really dealing with low dimensions up to 6 and the domains are rectangles you could enumerate... $\endgroup$ – Dirk Dec 28 '14 at 18:06
2
$\begingroup$

Check Rockafellars "Convex Analysis" Theorem 32.2: If a convex function is defined on a set which is the convex hull of a set of points than the function attains its maximum at one of the points. If I got your problem right, you just need to check your function on the corners. This seems doable for the dimensions you indicated.

$\endgroup$
  • $\begingroup$ Do you know if it has generalization for invex function? $\endgroup$ – Ehsan Dec 28 '14 at 23:09
  • $\begingroup$ For invex functions there is no such statement (as far as I remember invex functions are characterized by having only global minima). $\endgroup$ – Dirk Dec 29 '14 at 11:17
  • $\begingroup$ Ben Israel and Mond (1985), Theorem 1: "f is invex if and only if every stationary point is a global minimum". Then, can I conclude that the maxima of a continuous invex function on a compact space only attain on the edge (not necessarily on the corners)? $\endgroup$ – Ehsan Dec 29 '14 at 17:30
  • $\begingroup$ It smells like you have another question you would like to ask here on the site... $\endgroup$ – Dirk Dec 29 '14 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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