4
$\begingroup$

I am working on a research project with an optimization problem of the form

$$\begin{array}{ll} \text{minimize} & c^T x\\ \text{subject to} & A x + b = 0\\ & x_i \le x_j x_k\\ & x \in \mathbb R_+^n\end{array}$$

where $x_i$, $x_j$ and $x_k$ are different elements of the vector $x$. My questions are the following:

  • Can I reformulate this problem in some way to make it convex?

  • If not, what would be the most efficient way (algorithm or method) to find a global optimum?

I am mostly curious about this because when I solve the problem with powerful NLP solvers (e.g. CONOPT, MINOS) I always get the same general result (independent of initial guesses and problem parameters). Therefore my guess is that there are not many "bumps" on the way for GRG based solvers, but I haven't been able to express that in any meaningful (mathematical) form.

Now I have established that this is not a convex problem in this form. I have also tried, unsuccessfully, to show this is a quasiconvex problem, which would have been the case if the inequality constraint was of the form $\alpha \le x_j x_k$ where $\alpha$ is some scalar (see similar problem in Boyd example 3.31). On this website I found some clever tricks that transform similar constraints by taking the square root on both sides (geometric mean is concave on $R^n_+$). This would transform the inequality constraint for my problem to $g(x)=\sqrt{x_i} - \sqrt{x_j x_k} \le 0$. Now $g(x)$ is a mixture of a concave and convex function and that is as close as I have been able to get.

The bottom line is that I haven't been able to transform this into a convex or quasiconvex problem, and as a last resort I am posting the problem here in hope of some satisfying answer...

$\endgroup$
  • 1
    $\begingroup$ Have you considered using logarithms (instead of square roots): $\ln x_i \leq \ln x_j + \ln x_k$ ? $\endgroup$ – Jean Marie Nov 30 '17 at 9:44
  • 3
    $\begingroup$ Short answer: No. $\endgroup$ – Johan Löfberg Nov 30 '17 at 14:01
  • $\begingroup$ @JeanMarie Thank you for the comment. I had actually considered the logarithms as well. The thing is that once you move them to the other side of the inequality the left hand side is again a combination of concave and convex functions, i.e. $g(x) = \ln x_i - \ln x_j - \ln x_k \le 0$. It was perhaps not clear in the question, but I believe I need to reformulate the inequality into the form $g(x) \le 0$ where $g(x)$ is a convex function. $\endgroup$ – Egill Juliusson Nov 30 '17 at 21:14
  • $\begingroup$ @JohanLöfberg Thank you for your comment. I believe you :-) Is there any chance that you have an answer to my second question, i.e. what would be the most efficient way (algorithm or method) to find a global optimum? Alternatively I would be interested in learning something about to quantify how hard it is to find a unique solution (how nonlinear or non-convex the problem is). $\endgroup$ – Egill Juliusson Nov 30 '17 at 21:19
  • 2
    $\begingroup$ There is no "most efficient" way. You will have to test local nonlinear solvers, semidefinite programming based relaxations for global solutions, standard deterministic global solvers, randomized global solvers, MILP based picewise affine approximations etc, and see what works best in your particular case, and what kind of solution quality you are fine with. It all depends on the structure of the problem such as sparsity and number of variables etc. $\endgroup$ – Johan Löfberg Dec 1 '17 at 7:32
1
$\begingroup$

If you only have a single constraint of the form $x_i \leq x_j x_k$, you could use some of the transformations mentioned (either by you, or in the comments) and reformulate the problem as a convex program with a single reverse convex constraint. A tailored global optimization algorithm for this class of problems has been investigated here.

Edit: The above method works theoretically even for multiple reverse convex constraints. It also occurred to me that you could use so-called reduced-space branch-and-bound methods for global optimization that exploit the structure of your problem (since the number of variables participating in a nonconvex fashion in your formulation are relatively small and/or most of your constraints are simple equality constraints), see the works of Epperly and Pistikopoulos, Dur and Horst, and Stuber et al.

$\endgroup$
  • $\begingroup$ Thank you for your comment and pointing out those references. I am afraid I do not quite understand the first suggestion. You point out that I could formulate the problematic constraint as a reverse convex constraint, i.e. $g(x) \leq 0$, but I cannot figure out how to do that. All the reformulations I have found give me a function $g(x)$ that is a combination of convex and concave functions (i.e. $g(x)$ neither convex nor concave). Am I missing something obvious? $\endgroup$ – Egill Juliusson Dec 21 '17 at 10:06
  • 1
    $\begingroup$ You reformulate your constraint as $z - \sqrt{x_j x_k} \leq 0$, $z = \sqrt{x_i}$, which can in turn be reformulated as $z - \sqrt{x_j x_k} \leq 0$, $0 \leq \sqrt{x_i} - z$, $0 \geq \sqrt{x_i} - z$. Only one of the above three constraints is reverse convex constraint. $\endgroup$ – madnessweasley Dec 21 '17 at 12:20
  • $\begingroup$ I understand - clever. Thank you. $\endgroup$ – Egill Juliusson Dec 22 '17 at 20:01

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.