Stack Overflow
Stack Overflow

Questions tagged [non-convex]

non-convex is a sub-set of optimisation problems domain, where a utility / penalty function does not meet a condition of convexity

In optimization, the problems for which an assumption of convex function holds over convex sets, simplifies the optimization search process in some sense, right by using the underlying convex-property, which causes the search to become, in it's way, "easier" than the general case.

problem domains do not enjoy such "ease" - for example, having both local and global minima, having inflections and similar "un-easy" properties, that may confuse or trap convex-solvers on domains.

67 questions
9
votes
5 answers

Standard mesh for Concave Hexagons with two Mouths?

I am planning a visualization of flows though Concave Bisymmetric hexagons with two mouths. Example where the length of the side d1 equals the other length of the side d2: which naming I discussed initially here about Irregular hexagons. There is…
Léo Léopold Hertz 준영
  • 134,464
  • 179
  • 445
  • 697
9
votes
1 answer

how to order vertices in a non-convex polygon (how to find one of many solutions)

I have the same problem as here: how to order vertices in a simple, non-convex polygon but there is no solutions I can use. I have coordinates of points and need to find some polygon. Does not matter that there is more solutions for one list of…
1daemon1
  • 1,001
  • 3
  • 11
  • 29
8
votes
1 answer

find the maximum convex area

My question is very similar to Plow's Question; but with this difference: How can I find the maximum convex area that can fit inside a non-convex region? For an example, consider this non-convex region: Any ideas or solution would be appreciated,…
Zakhar
  • 313
  • 1
  • 4
  • 12
7
votes
2 answers

Detect corner coordinates of a non-convex polygon in clockwise order MATLAB

I have some images which includes both convex as well as non-convex polygons. Each image contains exactly one polygon. I need to detect the corner coordinates and need to sort them in clock-wise or counter-clockwise order. For convex polygons, I use…
Santhan Salai
  • 3,888
  • 19
  • 29
6
votes
2 answers

How to find out whether a triangle mesh is concave or not?

Given a three dimensional triangle mesh, how can I find out whether it is convex or concave? Is there an algorithm to check that? If so it would be useful to define a tolerance range to ignore small concavities. Image Source:…
danijar
  • 32,406
  • 45
  • 166
  • 297
5
votes
1 answer

Sweep Line Polygon triangulation: How to find edge left to current vertex?

I'm currently writing an y-monotone sweep line algorithm to triangulate non-convex polygons. The first step to achieve this is to make the polygon y-monotone. Pseudocode of MakeMonotone from the book "Computation Geometry by Mark de Berg"…
skeeks
  • 359
  • 2
  • 8
4
votes
0 answers

Python package for implementing branch-and-bound technique for solving a non-convex non-linear integer multi-objective optimization problem?

Here, X1 and X2 take integer values. I want to use branch-and-bound technique to solve this problem. What are the python tools available to solve this problem?
vp_050
  • 583
  • 2
  • 4
  • 16
4
votes
1 answer

Non-convex optimization with linear constraints

I'm trying to solve an optimization question similar to the toy example described below. As noted in the comment, my current implementation with scipy is too slow and doesn't seem to converge. How do I get a decent solution? You can use scipy,…
nalzok
  • 14,965
  • 21
  • 72
  • 139
4
votes
1 answer

How to apply bounds on a variable when performing optimisation in Pytorch?

I am trying to use Pytorch for non-convex optimisation, trying to maximise my objective (so minimise in SGD). I would like to bound my dependent variable x > 0, and also have the sum of my x values be less than 1000. I think I have the penalty…
Capeboom
  • 425
  • 1
  • 5
  • 13
4
votes
1 answer

MATLAB: Calculate volume of concave polyhedron from set of scattered 3D points

I have 20 to 30 randomly generated 3D points as vertices from which a polyhedron is defined. I have tried using DelaunayTri(points) to enumerate the facets and use the determinant of the cross product to calculate and sum the tetrahedral volumes,…
Slaiyer
  • 444
  • 8
  • 22
4
votes
1 answer

Non-convex polygon - preprocess to use convex hull algorithm

I used the convexHull algorithm to find the contour for some... irregular shape. It is not good enough though... Quite possibly because I can't guarantee that the shape I have is convex... I have a set of rectangles, and I would like to be able to…
Thalia
  • 13,637
  • 22
  • 96
  • 190
3
votes
1 answer

Gurobi or CPLEX? Quadratic indefinite objective - quadratic positive-semidefinite constraints

I want to minimize a quadratic objective function subject to a set of linear and quadratic constraints. The quadratic objective function is indefinite (non-convex). The quadratic constraints are positive-semidefinite (convex). The variables are…
user436994
  • 601
  • 5
  • 15
3
votes
1 answer

Finding a common interior point to two polygons

Suppose I have overlapping polygons. Neither is necessarily convex. What's an efficient algorithm to find a point interior to both of them and not on either's boundary? Assuming that they overlap, and our polygons are defined by their sets of…
Charles Taylor
  • 686
  • 6
  • 23
2
votes
1 answer

How to define "executable" solver path with pyomo multistart

I am having a non-linear minimization problem apparently with non-convexity. I use the Pyomo framework for an energy system operation optimization model, where a once configured optimization model needs to be evaluated in sequential hours (I create…
Kristof
  • 31
  • 3
2
votes
1 answer

Exterior penalty function method

I am trying to implement an exterior penalty function method for minimizing the below problem. min f(x)=100*(x(2)-x(1)^2)^2+(1-x(1))^2 s.t, x(1)+2x(2)<=1 2x(1)+x(2)=1 First of all, I have found the minimum using fmincon, which the answer is x:…
Anis.kvh
  • 21
  • 2
1
2 3 4 5