Does anyone know if this is convex?

Watch
Toasticide
Badges: 17
Rep:
?
#1
Report Thread starter 1 month ago
#1
Hi,
I recently made a post on convexity but I have another similar issue.
According to the wikipedia page on Euclidian distance, your standard d^2=(x2-x1)^2+(y2-y1)^2 is convex. I am willing to believe that. Also on wikipedia, it is stated that Euclidian norm's are convex (This I proved to myself by hand for the 2 dimensional case which was important at the time). Does that mean d=sqrt((x2-x1)^2+(y2-y1)^2) is convex? I thought the answer would obviously be yes but I am very skeptical at the transformation as I have had a lot of shenanigans recently involving this topic!

I started to prove this to myself by hand but the problem involves determinant of a 4x4 involving d as described above in every element, and it's too big for symbolab. If you have a free entire week perhaps try it yourself haha. But if you can tell me if d is convex or not that would be much appreciated, even better if you can point to a source that explicity proves convexity for the root function as opposed to the squared one
0
reply
DFranklin
Badges: 18
Rep:
?
#2
Report 1 month ago
#2
Yes. See for example https://math.stackexchange.com/quest...vectors-convex

Edit: to clarify, that's "yes, it is convex", rather than the canonical unhelpful mathmo reply "yes, someone does know if it's convex"...
Last edited by DFranklin; 1 month ago
0
reply
Toasticide
Badges: 17
Rep:
?
#3
Report Thread starter 1 month ago
#3
(Original post by DFranklin)
Yes. See for example https://math.stackexchange.com/quest...vectors-convex

Edit: to clarify, that's "yes, it is convex", rather than the canonical unhelpful mathmo reply "yes, someone does know if it's convex"...
oh my god that is brilliant thank you so much!!!! unfortunately my linear algebra isn't quite the level to think of this stuff easily so i'm stuck with the classic det(A-I(lambda))=0 to analyse eigenvalues and going from there. Shame I gave the thumbs up think to you on my last post cause i cant now.... you're a lifesaver though
0
reply
DFranklin
Badges: 18
Rep:
?
#4
Report 1 month ago
#4
(Original post by Toasticide)
oh my god that is brilliant thank you so much!!!! unfortunately my linear algebra isn't quite the level to think of this stuff easily so i'm stuck with the classic det(A-I(lambda))=0 to analyse eigenvalues and going from there. Shame I gave the thumbs up think to you on my last post cause i cant now.... you're a lifesaver though
As I said in the previous post, in this case I think you're better off proving convexity directly. I'm not clear whether your problem domain means that's always going to be the case, but I think you should definitely consider direct methods if you're dealing with "distance-like" functions before jumping to finding eigenvalues.
0
reply
Toasticide
Badges: 17
Rep:
?
#5
Report Thread starter 1 month ago
#5
(Original post by DFranklin)
As I said in the previous post, in this case I think you're better off proving convexity directly. I'm not clear whether your problem domain means that's always going to be the case, but I think you should definitely consider direct methods if you're dealing with "distance-like" functions before jumping to finding eigenvalues.
Damn I would rather not as I have little clue how I would use a direct method but that's looking like it'll have to be the case as the more I think about it, using stackexchange as a reference isnt perhaps the best thing to do. Regardless though, brilliant to know from there that I'm not wasting my time! (well i say I can't, more I don't feel confident in my ability, you stated the formula and my lecturer has notes on it vaguely)
Last edited by Toasticide; 1 month ago
0
reply
DFranklin
Badges: 18
Rep:
?
#6
Report 1 month ago
#6
(Original post by Toasticide)
Damn I would rather not as I have little clue how I would use a direct method but that's looking like it'll have to be the case as the more I think about it, using stackexchange as a reference isnt perhaps the best thing to do. Regardless though, brilliant to know from there that I'm not wasting my time! (well i say I can't, more I don't feel confident in my ability, you stated the formula and my lecturer has notes on it vaguely)
To be honest, I'm a little concerned with your answers here.

It doesn't sound like you actually "know" what convexity is; the fundamental definition doesn't require that f is differentiable, and makes no reference to the Hessian, or eigenvalues / determinants.

The fundamental definition is that f is convex if f((1-\lambda){\bf a} + \lambda {\bf b}) \leq (1-\lambda)f({\bf a}) + \lambda f({\bf b}), for all a, b and all \lambda \in [0,1]. To think of this geometrically, if you consider the value of f as defining a surface, then the line between f(a) and f(b) never goes below the surface.

For your particular problem, it's pretty obvious (to me) that looking at the Hessian is the wrong approach, not only because the algebra is going to be daunting, but because it relies on your function being twice differentiable, and \sqrt{(x_2-x_1)^2+(y_2-y1)^2} is not even once differentiable when x_1 = x_2 and y_1=y_2.

It just feels like you've been taught a particular box of tricks for dealing with smooth, twice differentiable functions, but the actual problem you're trying to solve is very different. Which seems odd when it sounds like this problem is a substantial element of your study.

If you feel able to post more details about the problem you're trying to solve (and why/how you ended up trying to solve this particular problem) I feel it would be helpful.

I'd also suggest you have a look at https://en.wikipedia.org/wiki/Convex_function - read the whole thing, or as much of it as you can understand (feel free to skip the Strongly Convex Functions section!). There's a lot there that's relevant to problems like the one you've described.
1
reply
Toasticide
Badges: 17
Rep:
?
#7
Report Thread starter 1 month ago
#7
(Original post by DFranklin)
To be honest, I'm a little concerned with your answers here.

It doesn't sound like you actually "know" what convexity is; the fundamental definition doesn't require that f is differentiable, and makes no reference to the Hessian, or eigenvalues / determinants.

The fundamental definition is that f is convex if f((1-\lambda){\bf a} + \lambda {\bf b}) \leq (1-\lambda)f({\bf a}) + \lambda f({\bf b}), for all a, b and all \lambda \in [0,1]. To think of this geometrically, if you consider the value of f as defining a surface, then the line between f(a) and f(b) never goes below the surface.

For your particular problem, it's pretty obvious (to me) that looking at the Hessian is the wrong approach, not only because the algebra is going to be daunting, but because it relies on your function being twice differentiable, and \sqrt{(x_2-x_1)^2+(y_2-y1)^2} is not even once differentiable when x_1 = x_2 and y_1=y_2.

It just feels like you've been taught a particular box of tricks for dealing with smooth, twice differentiable functions, but the actual problem you're trying to solve is very different. Which seems odd when it sounds like this problem is a substantial element of your study.

If you feel able to post more details about the problem you're trying to solve (and why/how you ended up trying to solve this particular problem) I feel it would be helpful.

I'd also suggest you have a look at https://en.wikipedia.org/wiki/Convex_function - read the whole thing, or as much of it as you can understand (feel free to skip the Strongly Convex Functions section!). There's a lot there that's relevant to problems like the one you've described.
(warning a rather big reply)
yeah you're pretty much right about what my lecturer taught me with the box of tricks. My question is my coursework, so of course I don't expect people to answer it for me but I will briefly say here what it is and my procedure in case you're curious!:

You have a rectangular plot of ocean (2000km x 1000km) and you must place 10 ships, each with tracking devices of radius r. the tracking devices must not exceed the plot and must not detect each other. What is the maximum size covered by the devices?

Objective function i thought would be max 10pi*r^2 but as a minimisation problem which is required for descent algorithms that becomes non convex, but maximising r instead should be fine considering the modelling I chose.
I am modelling each boat position as two variables, its x and y coordinate effectively. (forewarning this is probably a bad idea!)
There are the obvious constraints that each x+r<2000, y+r<1000, x-r>0, y-r>0
However the interfering constraint is where it goes downhill. taking say ships 1 and 2 I wanted the following:
(x2-x1)^2+(y2-y1)^2>2r^2; distance greater than twice the radius, but this is distance squared so you square both sides. Unfortunately re-arranging that into the proper form creates a -r^2 term. Alas, we use the pure distance (root of the left hand side) and we can retain the 2r which is convex.
I should say now I can define new variables as the horizontal distance and vertical distance between each pair. But this adds so many constraints and I will likely lose marks for unneccessary formulation, hence the sacrifice of expanding the constraint dimension to reduce total constraints.
All fine until the question asks for me to discuss convexity. What you said about the lack of twice differentiability is also very likely why the solver methods arent working! (that's another story though and the AMPL world seems to be very lonely haha)

Again, this is my coursework so I dont want people telling me the answer, however since its a modelling problem there is far from one answer and this is literally my first formulation and I immaturely often try to work as far as i can through my first try and adapting it rather than thinking afresh. I think the time has come for me to think outside the box!

Thank you so much for the explanation and source material to look at though, will definitely read through that as whatever formulation I come up with I know it's not gonna be likely to be easy to do. Sorry for the long ass reply also

edit- just wanted to say I know the definition in terms of the meaning with the curve always being below the linear line and the equation of it but damn if i can avoid doing that stuff i will as while i can recall it, I cant apply it. Also just wanted to say while this is my coursework, I'm only asking here basically to see if my current formulation i'm totally wasting my time on or not, wouldn't dream of asking someone to do it for me (besides I genuinely enjoy this despite the frustration from time to time)
Last edited by Toasticide; 1 month ago
0
reply
DFranklin
Badges: 18
Rep:
?
#8
Report 1 month ago
#8
My feeling is that this is the wrong approach, or at any rate it is going to be a lot of work trying to get a good solution this way. It seems to be you are going to have lots of "local minima" which aren't necessarily close to the ideal solution.

Are you trying to get an "exact" solution (correct to at least 6 sig fig, say) or just do the best you can?

And are there constraints on how you're supposed to solve it, or does "anything go"? Personally, I'd aim for an approximate solution by some variant of simulated annealing - possibly with a "physical simulation" phase where you model the 10 positions being "pushed" away from each other by a force that grows rapidly as you near the current "best radius". But that's as much because it would be reasonably easy to code/experiment with as anything else.

Have you been given any hints on what kind of problem this is? Because I know the "key phrase" to Google, I've been able to find a website with best known solutions for various N. Of note is a comment that in the case of a 1x0.6 rectangle, the best known result for N=7 was improved in 2013. So it's unlikely any general method (i.e. one not using specific analysis relating to the geometry) can be expected to give exact answers for N=10.
0
reply
Toasticide
Badges: 17
Rep:
?
#9
Report Thread starter 1 month ago
#9
(Original post by DFranklin)
My feeling is that this is the wrong approach, or at any rate it is going to be a lot of work trying to get a good solution this way. It seems to be you are going to have lots of "local minima" which aren't necessarily close to the ideal solution.

Are you trying to get an "exact" solution (correct to at least 6 sig fig, say) or just do the best you can?

And are there constraints on how you're supposed to solve it, or does "anything go"? Personally, I'd aim for an approximate solution by some variant of simulated annealing - possibly with a "physical simulation" phase where you model the 10 positions being "pushed" away from each other by a force that grows rapidly as you near the current "best radius". But that's as much because it would be reasonably easy to code/experiment with as anything else.

Have you been given any hints on what kind of problem this is? Because I know the "key phrase" to Google, I've been able to find a website with best known solutions for various N. Of note is a comment that in the case of a 1x0.6 rectangle, the best known result for N=7 was improved in 2013. So it's unlikely any general method (i.e. one not using specific analysis relating to the geometry) can be expected to give exact answers for N=10.
Yeah I have just given up with the last method I think. I may be able to get it to work if i was particularly adept in AMPL but unfortunately it was introduced last week alongside the coursework being set. One week only of lectures too on it so the intended "style" of solution i'm definitely veering away from.
Some general advice was to try different starting points and discuss the effect so i sense its do the best I can. Regardless, the code loves setting vertical/horizontal distances to 0 no matter what basic things i try, resulting in a radius of 0.
Unfortunately because of my basic knowledge I can't program detailed methods, and the most sophisticated stuff is array manipulation. Should be enough but ill admit now im not good at it.
Oh wow that is very interesting to hear! If you don't mind, don't tell me the phrase to google. It sounds like this question was intended to be an especially tricky one from what you said there, as opposed to an obnoxious one so I want to try and find it myself. (Plus I really need to practice my searching skills, I am horrific at it. What my friends find in 5 minutes it can take me days)

But thank you very much for that, that has helped me more than I can imagine!
1
reply
DFranklin
Badges: 18
Rep:
?
#10
Report 1 month ago
#10
(Original post by Toasticide)
Yeah I have just given up with the last method I think. I may be able to get it to work if i was particularly adept in AMPL but unfortunately it was introduced last week alongside the coursework being set. One week only of lectures too on it so the intended "style" of solution i'm definitely veering away from.
Some general advice was to try different starting points and discuss the effect so i sense its do the best I can. Regardless, the code loves setting vertical/horizontal distances to 0 no matter what basic things i try, resulting in a radius of 0.
Reading a bit of literature, it's obvious that this is actually a hard problem. There are lots of things that make it hard for solvers, and the objective functions tend to behave badly.

If you denote R_i for the maximal radius of ship i, one thing you might want to experiment with is making a smooth objective function, that doesn't try to maximize the minimum value of R_i, but instead tries to minimize the sum of some function of R_i. e.g. \sum R_i^\alpha) where alpha < 0. The motivation for this is as \alpha \to -\infty, this sum becomes more and more dominated by the minimum R_i.

Oh wow that is very interesting to hear! If you don't mind, don't tell me the phrase to google. It sounds like this question was intended to be an especially tricky one from what you said there, as opposed to an obnoxious one so I want to try and find it myself. (Plus I really need to practice my searching skills, I am horrific at it. What my friends find in 5 minutes it can take me days)

But thank you very much for that, that has helped me more than I can imagine!
FWIW, I did a bit of experimenting this morning with a (not very good) simulated annealing solution and got within 1% of the "best known" solution (and even more pleasingly, when I plotted the solution, it looked very like the best known one). Considering I never got formally taught how to do annealing properly, and I just hacked this together, I suspect it's possible to do a fair bit better than this.

You might also want to try a few manual solutions to give you a baseline. There's an obvious strategy (that probably feels like "this is too simple to be any good") that actually comes fairly close to the optimal solution and will give you a target.
0
reply
DFranklin
Badges: 18
Rep:
?
#11
Report 1 month ago
#11
Update: couple of tweaks and I got to 0.1% of the "best known" solution.
0
reply
Toasticide
Badges: 17
Rep:
?
#12
Report Thread starter 1 month ago
#12
Huh. Well, to quote my specification, something I didn't make clear was that generally all radii are the same across all ships. However the last bullet point is:
"After the main analysis, provide an AMPL formulation for the case where radii aren't equal. You do not need to apply a solver."

My first thought when reading it was huh, considering it's all about iterations/descent algorithms, how can adding that one specification suddenly stop solvers from working effectively? Well, you explained why that is!

Fortunately I don't have lectures today so I can try and change my mindset a bit in terms of modelling this problem, and as you said, do a bit of reading. That's very interesting to hear about the "broader" problem though, having learnt about heuristics last semester I actually understand what simulated annealing is and how these approaches can likely be used on these problems. Good, because I can predict I wouldnt be able to understand the literature very well otherwise
0
reply
DFranklin
Badges: 18
Rep:
?
#13
Report 1 month ago
#13
FWIW, a bit of tweaking in my lunch break and I got to about 0.0001% of the best known result. (I'm doing trial and error tweaking of a couple of "convergence" parameters that affect how it decides to go from coarse to fine adjustments as time goes on).

I'd say another key question here is how much "intervention" you're supposed to do. Once you have a decent solution, there are things you can see are "almost certainly true" about the optimal solution (e.g. that there's some kind of symmetry, or certain ships are always right on the radar boundary), which would let you reduce the number of search parameters and make it much easier to get convergence to a good solution. But whether that's allowed I have no idea.
0
reply
Toasticide
Badges: 17
Rep:
?
#14
Report Thread starter 1 month ago
#14
Thank you for the advice there about patterns in what the optimal solution would be. One of the bullet points I have to address is differing the number of ships and I did quickly think about what an optimal solution would look like in terms of symmetry and geometry.

Annoyingly, while I wanted to set initial values for the algorithms to be these thoughts, I will first need to do more research on AMPL. The notes provided explain how to initially assign a set of values all to be the same value. So I can set all x coordinates to be say 500, but that really doesn't help in terms of interference constraints! In terms of what's allowed, I think anything goes really. The coursework for this and my previous module on Linear programming have differed quite drastically from the key notes. Lecturer told me we're marked on basically efficient constraints and logical thinking.
(If you're curious, that assignment was that you are at a mine and there is an inverted shaped grid of blocks and you have to choose what blocks are optimal to mine with opencast mining where a block mined must have the blocks above it mined, combined with the costs associated for each block. Needless to say binary variables were a must and a lot of modelling and less knowledge on the simplex method. Was fascinating formulating it though I must say with a big sense of accomplishment when it worked. Shame I had to use Xpress for that and AMPL here...)
0
reply
Toasticide
Badges: 17
Rep:
?
#15
Report Thread starter 1 month ago
#15
Just a tiny update if you're curious. Packing problems sounds like the right direction (spent a while looking through covering problems, close but not quite). Interestingly this first paper looking deeply into it emphasises how the formulation is often non-convex. May have to ask my lecturer in private if there's a *chance* the formulation is non-convex, encouraging the point talking about the convexity of the problem. Considering the linear programming course made us formulate a binary problem which definitely needed a solver not simplex, I heavily suspect this is the case.

And here I was thinking that simply meant taking a reasonable sized matrix and finding eigenvalues!
0
reply
DFranklin
Badges: 18
Rep:
?
#16
Report 1 month ago
#16
(Original post by Toasticide)
Just a tiny update if you're curious. Packing problems sounds like the right direction (spent a while looking through covering problems, close but not quite). Interestingly this first paper looking deeply into it emphasises how the formulation is often non-convex. May have to ask my lecturer in private if there's a *chance* the formulation is non-convex, encouraging the point talking about the convexity of the problem. Considering the linear programming course made us formulate a binary problem which definitely needed a solver not simplex, I heavily suspect this is the case.

And here I was thinking that simply meant taking a reasonable sized matrix and finding eigenvalues!
I think any reasonable way you amalgamate individual distance functions into a function that covers the entire problem set (as opposed to a single interaction between two ships) is going to end up with something non-convex; at the same time I believe the function you originally posted is convex. I wouldn't be totally shocked if it isn't, because you're not using it in the way I was thinking, but I'm not sure it's relevant to the overall problem.

(Intuitively, it's fairly clear it's easy to optimize the distance between two ships with no other constraints, while the same problem with 10 ships can easily have local minima where "to do better" you need to completely disrupt your existing solution as opposed to simply making small incremental improvements).
0
reply
Toasticide
Badges: 17
Rep:
?
#17
Report Thread starter 1 month ago
#17
(Original post by DFranklin)
I think any reasonable way you amalgamate individual distance functions into a function that covers the entire problem set (as opposed to a single interaction between two ships) is going to end up with something non-convex; at the same time I believe the function you originally posted is convex. I wouldn't be totally shocked if it isn't, because you're not using it in the way I was thinking, but I'm not sure it's relevant to the overall problem.

(Intuitively, it's fairly clear it's easy to optimize the distance between two ships with no other constraints, while the same problem with 10 ships can easily have local minima where "to do better" you need to completely disrupt your existing solution as opposed to simply making small incremental improvements).
I absolutely agree especially with the big changes to the existing solution. I hope my lecturer allows non-convex formulations. Gives more to discuss in the associated section, plus opens up the possibility for functions to consider drastically! I say consider; there is a lot of things like how smooth the functions are that I need to bear in mind of course.
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

What factors affect your mental health the most right now?

Anxiousness about lockdown easing (166)
4.89%
Uncertainty around my education (498)
14.68%
Uncertainty around my future career prospects (379)
11.17%
Lack of purpose or motivation (473)
13.94%
Lack of support system (eg. teachers, counsellors, delays in care) (164)
4.83%
Impact of lockdown on physical health (208)
6.13%
Loneliness (288)
8.49%
Financial worries (122)
3.6%
Concern about myself or my loves ones getting/having been ill (137)
4.04%
Exposure to negative news/social media (155)
4.57%
Lack of real life entertainment (186)
5.48%
Lack of confidence in making big life decisions (302)
8.9%
Worry about missed opportunities during the pandemic (315)
9.28%

Watched Threads

View All
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise