I’m using Optim.jl via Optimization.jl and hitting Initial guess is not an interior point. I get that I could/should change my initial condition, but I’d like a general solution that works in general whenever a solution exists (I’m exposing the functionality to not-so-technical users). It made me wonder why Optim.jl / Optimization.jl does not simply start by searching for an interior point, instead of complaining? In a complex non-convex problem this might be difficult, but a lot of optimization problems aren’t.
Is there any function I can call to easily find an interior point (any point that satisfies the constraints?)
I’m not completely sure, but I think they use an infeasible primal-dual method: they transform general inequality constraints into equality constraints by adding slacks s, and move the bounds on the primals x and slacks s into barrier terms.
Therefore an interior initial guess must satisfy strict bound constraints on the x (and s) variables (and strict bound constraints on the bound dual variables if they are provided). So that’s too difficult to obtain.
Edit: solvers like IPOPT automatically push the initial guess into the interior of the bound constraints.
Methods like the interior point Newton do require - even without fancy primal-dual - an interior point, since they “keep away from the boundary” in their steps. Or in other words: In the outside, their barrier part would evaluate to infinity.
There is not much you can do about this, besides switching to methods that do not require this.
In principle you could start with something like an Augmented Lagrangian and wait for it to be inside - which might not happen if your solution lies on the boundary.
(I guess, but probably is the truth): because this procedure alone admits of no efficient solution method, so they simply don’t implement. As you mentioned, the context is non-convex.
Gurobi can solve nonlinear nonconvex optimization (of course including help you find a feasible point), but the algorithm it uses is not guaranteed to be efficient either.
You could just minimize the constraint violation, e.g. if you have a constraint c(x) \le 0, you could minimize c(x), stopping as soon as you reach a point < 0. If you have multiple constraints c_k(x) \le 0 you could minimize the epigraph formulation (which is a way to transform the “minimax” optimization of the biggest constraint violation into a differentiable NLP):
\begin{array}{c}
\displaystyle{\min_{t\in \mathbb{R}, x} t} \\
\text{s.t. } t \ge c_k(x) \end{array} \Longleftrightarrow \min_x \left[ \max_k c_k(x) \right]
(This can easily be initialized to a feasible starting point t_0 = \max_k c_k(x_0).)
(The CCSA/MMA algorithms in NLopt.jl do something of this flavor IIRC.)
Of course, this is not guaranteed to find a feasible point, but that’s true in general of non-convex optimization: finding a point in the feasible set might be arbitrarily hard. This is the fundamental reason why algorithms like to assume that you start with a feasible point — they can only guarantee convergence to a local optimum if they start at a feasible point.
3 Likes