4
$\begingroup$

I want to solve $$\min_x f(x)\qquad \textrm{s.t.}\qquad g_i(x) \geq 0\ \ \textrm{or}\ \ h_i(x) \geq 0$$ for $i=1,\ldots,m$.

Clearly if the inequality constraints split the feasible set into $2^m$ disconnected components, there is no hope for an efficient numerical solution. But in my case I know there is only one feasible connected component (consider for example a single pair of constraints, $g(x,y) = x$ and $h(x,y) = y$).

Is there some trick for converting these constraints to the standard conjunction of inequality constraints supported by black-box (nonlinear, nonconvex) optimization software? One can try for instance replacing the constraints with $k_i = \max(g_i,h_i)$ but since $k_i$'s gradient is not continuous I have little hope that this idea is effective in practice.

EDIT: Another idea (thanks to a quick discussion with Bernard Mourrain) is to introduce slack variables $y_i$ and solve $$\min_{x,y} f(x)\quad \textrm{s.t.}\quad [g_i(x)-y_i][h_i(x)-y_i]=0,\ y_i \geq 0$$ which now has only conjunctions of constraints, albeit for increased number of constraints and variables. Is this approach viable?

$\endgroup$
3
$\begingroup$

Is there some trick for converting these constraints to the standard conjunction of inequality constraints supported by black-box (nonlinear, nonconvex) optimization software?

You could introduce binary variables for each logical statement. For instance, you add a binary variable $z_{i}$ for each $i = 1, \ldots, m$, and have $\min_{x, z}f(x)$ such that $g_{i}(x)z_{i} + h_{i}(x)(1-z_{i}) \geq 0$, where $z_{i} = 1$ if the $g_{i}$ constraint is satisfied, and $z_{i} = 0$ if the $h_{i}$ constraint is satisfied. The resulting problem will be mixed-integer, so you would need to use an MINLP solver.

One can try for instance replacing the constraints with $k_{i}=\max(g_{i},h_i)$ but since $k_i$'s gradient is not continuous I have little hope that this idea is effective in practice.

I agree. I am not an expert in nonsmooth methods, but it seems as though there are more MILP and MINLP solvers available than nonsmooth optimization solvers. If you elect to use a nonsmooth formulation, Overton has some papers that describe how BFGS methods appear to work fairly well in practice, and he provides a line-search criterion for an appropriate step size. However, the problems he and his coauthors solve tend to be no more than 2000ish variables; the number is impressive for nonsmooth problems, but I am aware of larger problem instances in real applications.

$\endgroup$

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.