6
$\begingroup$

I have the following optimization problem:
\begin{align}\min&\quad x\\ \text{s.t.}&\quad x=\max_{i} \{x_{i}\}\\ &\quad x_{i}y_{i}=z_{i}\\ &\quad x_{i}, y_{i}, z_{i}\geqslant0 \end{align} with $i\in\{1,\ldots,n\}, n \in \mathbb{N}$ and some linear equality constraints involving $y_{i}$, $z_{i}$ and other variables.

Is it possible to reformulate this problem with usual conic constraints (linear constraints, quadratic cone, rotated quadratic cone, primal power cone or its dual, primal exponential or its dual, semidefinite) accepted in software like Mosek for example?

If not possible, how do I demonstrate it?

Improve this question
$\endgroup$
2
  • $\begingroup$ Let me just clarify that even if $n=1$, you present a quasiconvex (and generally nonconvex) optimization problem where standard reformulation techniques are bound to fail. The special case of $n=1$ can be cast as an LP though, via nonlinear variable substitution (a so called hidden convexity), but these results are very sporadic and I don't know any results for $n \geq 2$. $\endgroup$
    – Henrik Alsing Friberg
    Commented Dec 20, 2022 at 19:01
  • $\begingroup$ @Henrik Alsing Friberg See my answer with bisection solution per Vandenberghe. $\endgroup$
    – Mark L. Stone
    Commented Dec 20, 2022 at 19:07

1 Answer 1

Reset to default
5
$\begingroup$

Let $x_i = \frac{z_i}{y_i}$.

Then, presuming $x_i$ does not appear in any of the other constraints, this appears to be a Generalized linear-fractional programming problem per section 4.3.2 "Linear-fractional programming" of Boyd and Vandenberghe, "Convex Optimization".

It can be solved by bisection as discussed in Vandenberghe's notes for Lecture 8 of EE236A (Fall 2013-14) "Linear-fractional optimization" As stated there on p. 8-7 (edited by me to add some details for clarity),

In contrast to Linear Fractional Programming problem of p. 8–2, generalized Linear Fractional Programming problem is not reducible to a Linear Programming problem. It can be solved efficiently as a sequence of Linear Programming feasibility problems using the bisection algorithm on p. 8-9.

So, using the bisection algorithm, this could be solved by making a sequence of calls to Mosek, or any other LP solver.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.