Is it possible to reformulate this optimization problem as a geometric program?

Question

Is it possible to reformulate the following optimization problem as a geometric program?

$$ \begin{array}{ll} \underset {x, y, z} {\text{minimize}} & \dfrac{x}{{2x + 3y}} + \dfrac{y}{{y + z}} + \dfrac{z}{{z + x}} =: P (x,y,z) \\ \text{subject to} & x, y, z \in \left[ {1,4} \right] \\ & x \ge y \\ & x \ge z \end{array} $$

Although this is a problem from a university entrance exam and has been solved here, I was wondering if there is some convex reformulation of this problem.

Answer 1

Here's maybe not what you were expecting, but it's certainly a way to solve this problem using a computer. We'll be doing this in sage using the qepcad interface, which lets us solve equations over $\mathbb{R}$ using quantifier elimination. For more specifics about this method, you might be interested in an old blog post of mine where I talk at length about solving problems like this using this machinery.

So, the first thing to do is to figure out what the solution "should" be. We can do this by trying a hundred thousand random points

x,y,z = var('x,y,z')
P = x / (2*x + 3*y) + y / (y+z) + z / (x+z)

# choose 100000 random points x,y,z
N = 100000

print("generating points")
pts = []
for blah in range(N):
    z = uniform(1,4)
    y = uniform(1,4)
    x = uniform(max(y,z),4)
    pts += [(x,y,z)]

# get the best choice of (x,y,z)
print("computing min")
lowest = pts[0]
for (x,y,z) in pts:
    if P.subs(x=x,y=y,z=z) <= P.subs(x=lowest[0], y=lowest[1], z=lowest[2]):
        lowest = (x,y,z)

l = P.subs(x=lowest[0],y=lowest[1],z=lowest[2])
print("min: ", l, "at", lowest)

The exact output will depend on what random numbers you get, but I got roughly $(3.99, 1.00, 1.99)$. Since we know this came from some kind of competition problem, it's a good guess that the solution should be an integer, so the actual solution is probably $(4,1,2)$.

With that in mind, let's use qepcad to verify that this is correct! We see $P(4,1,2) = 34/33$, so the dream is to prove $P(x,y,z) \geq 34/33$ on our domain of interest, and ideally to check that we get equality only at $(4,1,2)$ (or maybe at finitely many other points as well).

Quantifier elimination only works for polynomial queries. But thankfully we can easily turn the inequality $P \geq 34/33$ into a polynomial inequality by clearing denominators on the left hand side. Doing this gives the following query

qf = qepcad_formula
x,y,z = var('x,y,z')
P = x * (y+z) * (z+x) + y * (2*x + 3*y) * (z+x) + z * (2*x + 3*y) * (y+z)  >=  34/33 * (2*x + 3*y) * (y+z) * (x+z)
P = qf.atomic(P.expand())
qepcad(P, assume=[x>=1, 4>=x, y>=1, 4>=y, z>=1, 4>=z, x>=y, x>=z])

Sage outputs TRUE incredibly quickly, which tells us that $P \geq 34/33 = P(4,1,2)$ on our domain! So $(4,1,2)$ really is a minimum. But it's natural to ask if there are any other minima, and it's easy to get sage to tell us the answer is "no". If we modify our query to ask for equality, we can get sage to tell us all the solutions to $P = 34/33$!

qf = qepcad_formula
x,y,z = var('x,y,z')
P = x * (y+z) * (z+x) + y * (2*x + 3*y) * (z+x) + z * (2*x + 3*y) * (y+z)  ==  34/33 * (2*x + 3*y) * (y+z) * (x+z)
P = qf.atomic(P.expand())
qepcad(P, assume=[x>=1, 4>=x, y>=1, 4>=y, z>=1, 4>=z, x>=y, x>=z], solution='all-points')

Here, sage outputs [{'x': 4, 'y': 1, 'z': 2}], so we know we've found the only solution. (As a cute exercise, you can actually copy/paste this code into the cells on the page I linked earlier to see for yourself how quickly it runs!)

---

I hope this helps ^_^

Answer 2

Basically you have to convert the objective into posynomials. Since the affine functions are linear so you can try this transformation
Obj $= x\delta_{1}^{-1}+y\delta_{2}^{-1}+z\delta_{3}^{-1} $
st
$0 \le \delta_{i} \le 20\quad \forall i $
$2x +3y = \delta_1 $
$ y+z =\delta_2$
$ x+z = \delta_3$