1
$\begingroup$

Essentially I am trying to develop an algorithm to minimize a function over a convex set that I don't know explicitly. However, I have a starting point "deepest in the set" (i.e. with largest norm distance to the boundaries), and a way to check if the feasibility criterion, $g(x) \le 0$, is met: I can call the function and check.

Here is a picture of my set, which is convex. Unfortunately I only obtain it numerically, hence not describing by functions. The red part is where my constraint is true, and X is my starting point, right in the "middle":

enter image description here

So I start my algorithm at x = X, a feasible starting point. Assuming the rest of my problem is convex, my plan is to take Newton steps from X and use a backtracking line search to determine step size while checking that I'm still feasible with respect to $g(x) \le 0$.

Is it the case that when I can no longer take a step size $t > \epsilon$ because I won't be feasible (i.e. $g(x) \le 0$ but $g(x + tv) \gt 0$ for all $t > \epsilon$), that I'll be at a point on the boundary, and thus optimal?

Extending on that, is this a valid iteration approach in general if your iterative algorithm can start at a point "deepest" in the convex set?

$\endgroup$
2
$\begingroup$

No, it is not the case, I am afraid. It is still possible, indeed likely, that you will hit the boundary at a suboptimal spot with a method like this. If that happens, you will have to find a way to traverse around the boundary until you reach the optimal solution, and that is by no means going to be straightforward in your case.

In the case of an interior-point method, where the feasible region is associated with, say, a barrier function, care is taken to make sure that the iterates do not reach the feasible region too quickly. The closer the iterate gets to the boundary, the more poorly condition the resulting search direction calculations, making it more difficult to increase the accuracy of the solution.

I think that in order to pull this off, you're going to need to find a way to get a little more information out of your function $g(x)$ besides just its sign. You say you know for sure that your feasible set is convex---how? Surely there is something buried in your proof of convexity you can exploit.

For instance, suppose that when you arrive at the boundary, you can compute a tangent hyperplane to that point on the boundary. A subgradient of $g(x)$ will actually give you this. If you can do that, then you could build an analytic center cutting plane method to solve your problem. Google is your friend on this one, but here is a PDF from UCLA with some slides that provide a rough description of the method.

You might be able to get away with an approximate subgradient, something numerically computed from points near the boundary, but I'm not sure.

$\endgroup$
  • $\begingroup$ Thank you for the response. I have more than just the sign of $g(x)$, I know that it is monotonically decreasing from my center point X to its boundary - in every direction. Could this help? $\endgroup$ – JDS Mar 4 '15 at 20:56
  • $\begingroup$ I'd say you still need tangent hyperplanes, somehow. Or more specifically: given any point $x$ outside the feasible set, you need a separating hyperplane between $x$ and the feasible set. $\endgroup$ – Michael Grant Mar 4 '15 at 21:33
  • 1
    $\begingroup$ Actually, how about trying a barrier or penalty method? Sure, you may not have derivatives, but you could numerically differentiate. $\endgroup$ – Michael Grant Mar 4 '15 at 21:34

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.