Suppose I have a problem of the form m i n <mrow class="MJX-TeXAtom-ORD">

brendijadq

brendijadq

Answered question

2022-05-28

Suppose I have a problem of the form
m i n x ϵ , y 0 f ( x ) + g ( y ) x + y
subject to some (convex) inequality constraints and some affine equality constraints, and where f and g are known to be convex, and ϵ > 0 is some known constant. We can also assume that the feasible set is compact (in addition to being convex).

The main challenge here is when f ( x ) + g ( y ) x + y is not convex (otherwise it is just a convex problem), and also we don't have an easy escape like f and g are log convex, for example.

In my specific situation, I also know that f , g are of the form
f ( x ) = 0 x h f ( u )   d u   ,
and
g ( x ) = 0 x h g ( u )   d u   ,
for some (known) nondecreasing and integrable (but not necessarily continuous) functions h f : [ 0 , B f ] R and h g : [ 0 , B g ] R for some real numbers 0 < B f , B g < .

Are there any easy ways to tackle this sort of problem? I am hoping to find ways that would be computationally not much more difficult than convex optimization, but I am not sure if this is possible... it seems like even the simpler problem of minimizing f ( x ) / x is (surprisingly) difficult...

Answer & Explanation

a2g1g9x

a2g1g9x

Beginner2022-05-29Added 12 answers

You can solve it by bisection, i.e. use bisection to find smallest possible t such that f ( x ) + g ( x ) t ( x + y ). For fixed t this is a convex set, and you would thus use your convex programming machinery if available for your particular functions.

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Multivariable calculus

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?