7
$\begingroup$

My question is related to a previous one: Dedicated solver for convex problems

To minimize a convex function of the form $~f(x_i) = \left[ C + mx_i + \frac{s}{x_i+t} \right]^p $

with various parameters $~C$, $m$, $s$, $t~$ and $~p$, $~$where $~0 \le x_i \le 1~$ and $~p \ge 1$.

(By generating a graph of the function, I ensure that the function $f(x_i)$ is convex. $~$The constraints are all linear.)

Edit (5:30am GMT January 25): Apologies for not bringing this up earlier, since I assumed that it wouldn't make a difference. The variable actually is a vector $X =$ ($x_1$, $x_2$, $\cdots$, $x_n$).. The objective function is:

Minimise $~Z(X) = \sum_{i=1}^n Z_i = \sum_{i=1}^n f(x_i)$.

If each $f(x_i)$ is convex, then their sum $Z(X)$ is also convex.

My question is, which solvers are well-suited to minimize such a convex function (subject to linear constraints)?

Of all solvers at NEOS, only MINOS seems to come close, and even this is not perfect (sometimes returns errors for instances for which manually I'm able to obtain optimal feasible solutions).

$\endgroup$
6
  • 1
    $\begingroup$ Could you please clarify: (1) x is the only variable, all the other letters are parameters; (2) Is x a single number? If so, you can forget about the exponent, let g(x) = C + mx + s/(x+t), and solve directly the equation g'(x) = 0, i.e., x = -t +-sqrt(s/m). $\endgroup$
    – Stef
    Jan 24, 2023 at 14:26
  • 1
    $\begingroup$ If x is not a real number, but a vector, then I don't know what s/(x + t) means. But if x is a real number, then I don't know what you mean when you say "the constraints are linear", as linear constraints in one dimension are nothing more than just setting an interval. $\endgroup$
    – Stef
    Jan 24, 2023 at 14:35
  • $\begingroup$ To Stef -- good point! Let me be honest! There are several $x_i$ (that is, $~x_i$, $~$1 $\le i \le n$).. The objective function is actually (Minimise) $Z$ $= \sum_i Z_i$ $= \sum_i (~C + mx_i + s/(x_i + t) ~)^p $.. So I have linear constraints that connect different $x$'s, such as $x_i$ + $x_j$ $\le K_{i,j}$, etc.. If each $Z_i$ is convex, then the entire sum $Z$ is also convex. (I assume that the answers provided so far don't change with this extra info?) $\endgroup$ Jan 24, 2023 at 20:35
  • 1
    $\begingroup$ Ah, it makes a lot more sense then! I suggest editing your question to include what you just said in a comment. As for Henrik Friberg's answer below, the way I understand it, it looks like it assumed that the objective function was f(x) and x was a real number and one of the variables, but there might be other variables that were involved in the constraints without being involved in the objective function. Note that the answer emits a reserve: "Hence, if f(x) really is all there is to your objective function". $\endgroup$
    – Stef
    Jan 24, 2023 at 23:05
  • $\begingroup$ The answers of Oscar Dowson and Sutanu now don't make much sense in the new light that x is a vector and the objective function is a sum of functions of the x_i. $\endgroup$
    – Stef
    Jan 24, 2023 at 23:05

3 Answers 3

12
$\begingroup$

You are missing some details for the claimed convexity of $f(x)$. I will assume that you meant to say convex on the domain $C+mx+\frac{s}{x+t} \geq 0$ and $x+t \geq 0$. In this case the epigraph of $f(x)$ has conic normal form: $$ \begin{array}{ll} &f \geq \left(C+mx+\frac{s}{x+t}\right)^p\\\Leftrightarrow &f \geq \left(C+mx+y\right)^p,\quad y \geq \frac{s}{x+t},\\\Leftrightarrow &f \geq z^p,\quad z=C+mx+y,\quad y \geq \frac{s}{x+t},\\\Leftrightarrow &f \geq |z|^p,\quad z=C+mx+y \geq 0,\quad y (x+t) \geq s. \end{array} $$

where the last deduction adds in the missing convexity details. You can now input the representation in any Disciplined Convex Programming language using one power cone for $f \geq |z|^p$ (see, e.g, https://docs.mosek.com/modeling-cookbook/powo.html#powers), and one rotated quadratic cone for $y (x+t) \geq s$ (see, e.g., https://docs.mosek.com/modeling-cookbook/cqo.html#rotated-quadratic-cones). These two cones are so simple that their presence will hardly affect the interior-point algorithm from a complexity point of view.

As a last remark, note that minimizing $\left(C+mx+\frac{s}{x+t}\right)^p$ on $p\geq 1$ is equivalent to just minimizing $C+mx+\frac{s}{x+t}$. Hence, if $f(x)$ really is all there is to your objective function, you will get the same optimal solution by just minimizing $z$. This will allow you to get rid of the epigraph variable $f$ and the power cone that constrain it.

As to the question of which solver to use with Disciplined Convex Programming, I refer to this answer to your previous question: https://or.stackexchange.com/a/2727.

$\endgroup$
6
  • $\begingroup$ Thanks.. Yes, you're correct -- certainly we need $~\left(C + mx + \frac{s}{x+t} \right) \ge 0~$.. Just to make sure -- your $t$ (on the left side), is it the same as my $t$ (on the right side)? $~$Also, any reason why $~y \ge \frac{s}{x+t}$, and not $~y = \frac{s}{x+t}~$? $\endgroup$ Jan 24, 2023 at 4:08
  • 2
    $\begingroup$ @ShuxueJiaoshou (1) Yes that variable should not have been called $t$. I changed it so the function $f(x)$ is now represented by the epigraph variable $f$. (2) You want $y=\frac{s}{x+t}$ but that is nonconvex. Fortunately, the convex relaxtion $y \geq \frac{s}{x+t}$ is exact because $(C+mx+y)^p$ is nondecreasing in $y$ (see docs.mosek.com/modeling-cookbook/…). (3) Great achievement, the DCP rules are indeed powerful. I can highly recommend MOSEK. $\endgroup$ Jan 24, 2023 at 8:25
  • 1
    $\begingroup$ @HenrikAlsingFriberg, would you please, what's happened for parameter $t$ if we would replace it with the new variable $t'$? We should simply change the parameter to the variables!!? $\endgroup$
    – A.Omidi
    Jan 25, 2023 at 10:20
  • 1
    $\begingroup$ @A.Omidi: In my reformulation it doesn't matter if $t$ is a parameter or a variable as long as the convexity requirement, $x+t \geq 0$, is valid for the problem you are trying to solve. $\endgroup$ Jan 25, 2023 at 13:09
  • 1
    $\begingroup$ @HenrikAlsingFriberg, thanks for your explanation. 🙏 $\endgroup$
    – A.Omidi
    Jan 26, 2023 at 9:43
6
$\begingroup$

Use Ipopt and a modeling language. For example, JuMP: https://jump.dev/JuMP.jl/stable/tutorials/nonlinear/introduction/

julia> using JuMP, Ipopt

julia> model = Model(Ipopt.Optimizer)
A JuMP Model
Feasibility problem with:
Variables: 0
Model mode: AUTOMATIC
CachingOptimizer state: EMPTY_OPTIMIZER
Solver name: Ipopt

julia> set_silent(model)

julia> @variable(model, 0 <= x <= 1)
x

julia> C, m, s, t, p = 1, 1, 1, 0.1, 3
(1, 1, 1, 0.1, 3)

julia> @NLobjective(model, Min, (C + m * x + s / (x + t))^p)

julia> optimize!(model)

julia> value(x)
0.8999994186940709

julia> objective_value(model)
24.389000000008522

julia> (C + m * value(x) + s / (value(x) + t))^p
24.389000000008522
$\endgroup$
5
$\begingroup$

Best way is to apply log to the function as optimal solution to log of a function is the same for the function.
$ \log f = p[\log (C(x+t)+ mx(x+t)+s)-\log(x+t)]$
Then you have to get the actual solution by the exp of $\log$ base used (e, 2 or 10).

However log functions need to be transformed into auxillary variables. You can also use the exp with $p$ but these also have to expressed as additional variables using addition constraints. Here is the link to suggested piecewise solution by Gurobi. Gurobi provides constraints as model methods like addGenConstrLog() and addGenConstrExp(). These are available at Gurobi's reference guide. Solvers won't have a problem with 2nd degree $x^2$

$\endgroup$
5
  • 2
    $\begingroup$ Doesn't it require log(f(x)) to be convex on the domain for this to work? $\endgroup$ Jan 23, 2023 at 9:53
  • 2
    $\begingroup$ @HenrikAlsingFriberg: log preserves convexity $\endgroup$
    – Ben Voigt
    Jan 23, 2023 at 16:26
  • $\begingroup$ Thanks, but one worry is that taking $\log$ weakens the degree of convexity.. However as Henrik said in his answer, the exponent $p$ may be unnecessary for the minimisation. $\endgroup$ Jan 23, 2023 at 23:00
  • 1
    $\begingroup$ I don't think log weakens convexity, otherwise max loglikelihood wouldn't have used log to optimize in logistic/probit regression. Also not sure if $f(x)=x$ and $f(x)=x^2 $ will have same solution for $x=[-2,2]$ $\endgroup$ Jan 23, 2023 at 23:38
  • 2
    $\begingroup$ @Sutanu: You are able to use log-transformation of the likelihood objective because $\log(x)$ is strictly increasing (doesn't change optimal solution set), and you prefer to do it because log-likelihood is concave and likelihood alone isn't (you want concave objectives when maximizing, and convex objectives when minimizing). Please post a new question on this forum if you need more details as the comment section isn't suited for proper explanation. $\endgroup$ Jan 24, 2023 at 8:59

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.