Piecewise linear and global optimization

Question

I am new to OR, and apologies if my mathematical notation is not clear. I have tried my best to keep it concise and given an explanation with numerical data. I would like to understand:

1. Can this model be formulated as convex, such as piecewise linear or quadratic, or SOCP? I will be interested to know both for the case when the variables $x_i$ are binary and also if they are non-binary.
2. Can we use a global solver, such as Octeract or Baron to solve this problem of large size (n=10,000 and T=1200)? I have seen a number of posts on this website that some global solvers can reformulate the model that can be solved efficiently, but it would be good to know whether it will work for this case.

$\max\ q_1+q_2 $

$\text{Subject to}$

$\qquad \sum_{i=1}^{n} p_{i} x_{i} = \sum_{t=0}^{T} \frac{F_{t}}{(1+q_{1})^{t}} \qquad \qquad \qquad(1)$

$\qquad \sum_{i=1}^{n} p_{i} x_{i} = \sum_{t=0}^{T}\sum_{i=1}^{n} \frac{b_{i}^{t} x_{i}}{\left ( 1+q_{2} \right )^{t}} \qquad \qquad(2)$

$\qquad \sum_{i=1}^{n} p_{i} x_{i} = \beta \sum_{t=0}^{T} \frac{F_{t}}{(1+q_{1}+q_{2})^{t}} \qquad \qquad(3)$

where

$x_i\in \{0,1\} \qquad \text{are optimization variables}$

$q_1 \geq\ 0, \qquad q_2 \geq\ 0 \qquad \text{are variables}$

$i\ =\ {1,2,3,...n}$

$t\ =\ {0,1,2,...T}$

$\beta \quad \text{is a constant}$

$F\ =\ {c_1,c_2,c_3,...c_T} \quad \text{(coefficients)}$

$p_i\ =\ {p_1,p_2,p_3,...p_n} \quad \text{(coefficients)}$

$b_i\ =\ {b_i^0,b_i^1,b_i^2,...b_i^T} \quad \text{(coefficients)}$

I have illustrated this using numerical data in the attached image (in case if the maths above is written incorrectly)

Answer 1

As far as I can see there is no exact convex reformulation for this, unless someone else can think of a nice trick. Constraint 1 can actually be convexified for certain ranges of $q_i$ as these functions are partially convex, e.g. $1/(1+x)^3$ is:

The fractions in constraint 3 are also convex past certain hyperplanes. However, you would have to restrict your feasible region quite significantly to impose that, which means missing out on solutions.

Constraint 2 unfortunately can not be convexified because of the multiplication by $x_i$.

As you mentioned, a deterministic global optimisation solver such as Octeract Engine, Baron, ANTIGONE, or Couenne, will solve this problem automatically. The solver will not make the problem convex, but will instead generate a convex relaxation that can be solved rigorously (because it's convex). This value provides a rigorous lower bound on your problem (assuming minimisation), and the solver will the iteratively generate and solves such relaxations using branch-and-bound until it proves global optimality.

If you want to try this out, Couenne and our own Octeract Engine are free to use for any purpose.

As a final note, keep in mind that equality constraints with convex functional forms do not generally make the problem convex. Intuitively, assuming we're minimising subject to e.g., $x^2=1$, this constraint is equivalent to:

$x^2 \le 1$, and

$ x^2\ge1 \implies-x^2 \le-1 $.

The first constraint defines a convex feasible region, but the second constraint defines a concave one. The intersection of the two gives us the equality feasible region.

Some solvers can handle this out-of-the-box (e.g., Octeract Engine), but certain solvers (especially if they are convex-only) only support convex inequality constraints, so make sure to check what your solver is designed to handle.

As a final-final note on semantics, since you are maximising, a convex optimisation problem is either (i) the maximisation of a concave objective, or (ii) the minimisation of a convex objective, over a convex set. Convex problems are can be minimized to global optimality in a single local solve, and concave problems can be maximized to global optimality in a single local solve. Since your objective is linear this doesn't affect your problem, but keep it in mind as you experiment with reformulations.

Answer 2

I might be missing something here (and by "might be" I mean "probably am"), but at least for the case of $x_i \in [0,1]$ you might be able to get solutions via "brute force". I'm assuming that all the parameters ($F,p,b,\beta$) are positive.

Suppose we slap a somewhat arbitrary upper bound $M$ on $q_1$, and then do a bisection search (or any other one-dimensional line search) on $q_1$. Since (1)-(3) all have the same LHS, the RHS of (1) equals the RHS of (3), and for fixed $q_1$ the RHS of (3) looks like a strictly decreasing function of $q_2$. So given a value of $q_1$, either we can use the fact that the RHS of (3) equals the known RHS of (1) to solve for $q_2$, or else we find there is no solution (so the value of $q_1$ is infeasible).

Assuming we find a value for $q_2$, we solve for $x$ satisfying (1) and (2). Given $q_1$ and $q_2$, these are now linear equations in $x$, and if the system is underdetermined (likely) that's fine. We don't care which feasible solution we find; we just need to confirm that there is a solution that respects the bounds on $x$. One way to do this would be solve a linear program. If the LP is infeasible, again that means our choice of $q_1$ is infeasible. If it's feasible, we have a new feasible solution with a known objective value, and now we go back to the line search of $q_1$ and use the new objective value to decide where to look next.