2
$\begingroup$

Consider the following problem \begin{equation} \begin{aligned} \min_{x,y} \quad & f(x,y), \\ \textrm{s.t.} \quad & \exp(x) + \exp(y) = 1 \end{aligned} \tag{1} \end{equation} where $f : (-\infty,0) \times (-\infty,0) \to \mathbb [0,\infty)$ is convex and monotone increasing in $x$ and $y$ (in the sense that, if $x_1 \leq x_2$ and $y_1 \leq y_2$, then $f(x_1,y_1) \leq f(x_2,y_2)$). Also, note that the left-hand side of the constraint is non-linear, convex, and strictly monotone increasing in $x$ and $y$ (in the sense that, if $x_1 < x_2$ and $y_1 < y_2$, then $\exp(x_1) + \exp(y_1) < \exp(x_2) + \exp(y_2)$).

The problem in $(1)$ is almost convex. The challenge here is that the constraint defines a non-linear curve in $\mathbb R^2$. My initial attempt at making this problem convex was to relax this constraint into $\exp(x) + \exp(y) \leq 1$ and then show that this relaxation is tight (that is, solving $(1)$ with the constraint $\exp(x) + \exp(y) \leq 1$ yields the same solution as solving $(1)$ with the constraint $\exp(x) + \exp(y) = 1$).

However, this approach does not work here, since, in order to decrease $f$, we would need to decrease $x$ and $y$ (because $f$ is monotone increasing in $x$ and $y$), but this would in-turn decrease $\exp(x) + \exp(y)$ since it is strictly monotone increasing. This means that, starting at the point $(x_0,y_0)$ that is inside the convex feasible set defined by the constraint $\exp(x) + \exp(y) \leq 1$, $\exp(x) + \exp(y) = 1$ would not be satisfied no matter how much $x$ and $y$ are decreased in order to decrease $f$.

Ideally, there should be some invertible function $g : (0,\infty) \to \mathbb R$ that I can apply to both sides of the equality constraint such that the constraint becomes $g(\exp(x) + \exp(y)) = g(1)$ and so that $g(\exp(x) + \exp(y))$ is convex and strictly monotone decreasing in $(x,y)$ on the left-hand side and $g(1) = 1$ on the right-hand side. This would mean that the new constraint is $g(\exp(x) + \exp(y)) = 1$ and so I can apply the relaxation as before to get $g(\exp(x) + \exp(y)) \leq 1$. In this case, the relaxation should be tight, since the left-hand side of the inequality increases as $(x,y)$ is decreased, which also decreases the objective $f$. However, I'm not sure of the following:

  1. Which function $g$ to choose that fits this case (I've thought about $g(x) = \frac{1}{x}$, but this didn't work).
  2. Whether there is a better approach than mine to relax the constraint in $(1)$ so that $(1)$ becomes a convex optimization problem.
$\endgroup$
1
  • $\begingroup$ Just use a local or global non-convex solver, unless you don't care about how good the solution is, in which case you can do anything. $\endgroup$ Nov 25, 2023 at 1:14

2 Answers 2

2
$\begingroup$

Let $g(x)=f(x, \log(1 - \exp(x))).$ Try plotting that to see if it is unimodal and, if so, whether the min is attained in the interior or only approached (infimum) as $x\rightarrow -\infty$ or as $x\rightarrow 0$. If it is unimodal with an interior minimum, you have a one-dimensional problem, which can be solved by bisection search or golden section search, or maybe by gradient descent if $f$ is smooth.

$\endgroup$
3
  • $\begingroup$ If I understand correctly, you are suggesting that I rewrite the equality constraint $\exp(x) + \exp(y) = 1$ as $y = \log(1-\exp(x))$ and then substitute this value of $y$ into my objective function $f(x,y) = f(x,\log(1-\exp(x)))$ to get an unconstrained 1D optimization problem. Is this right? $\endgroup$
    – mhdadk
    Nov 25, 2023 at 13:58
  • $\begingroup$ It's not exactly unconstrained -- you still have the domain restriction $-\infty < x < 0$ -- but yes, that is what I am suggesting. $\endgroup$
    – prubin
    Nov 25, 2023 at 16:38
  • $\begingroup$ You are correct. I plotted $f(x,\log(1-\exp(x)))$ and it is indeed unimodal. Thank you for the helpful advice. $\endgroup$
    – mhdadk
    Nov 26, 2023 at 18:27
0
$\begingroup$

In addition to @prubin's answer, another approach, which may be useful when $x$ and $y$ are high-dimensional, is to solve the problem in $(1)$ as a difference-of-convex (DC) program. This approach is described in the paper

Lipp, T., Boyd, S. Variations and extension of the convex–concave procedure. Optim Eng 17, 263–287 (2016).

The main idea is to re-write the equality constraint $\exp(x) + \exp(y) = 1$ as the following two inequality constraints: \begin{align} \left[\exp\left(x\right) + \exp\left(y\right)\right] - 1 &\leq 0 \\ 1 - \left[\exp\left(x\right) + \exp\left(y\right)\right] &\leq 0 \end{align} The left-hand side of both inequality constraints is a difference of convex functions. In addition, since the objective function is convex, then $(1)$ qualifies as a DC program. There is also a Python package that can be used to solve DC programs.

$\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.