The bug is that such plateaus in the picture correspond to discontinuous "derivatives": at the kink there is not one unique "slope" of the function, but infinitely many - for a one-dimensional such function it would be represented by an interval of valid subgradients - which otherwise would have told you where you could direct yourself.

The typical salvation is to use any of the subgradients as a direction (with a negative sign, as a kind of steepest descent direction), with a step-length that follows the usual formula - that is, shorter and shorter as you go along the, according one of the typical - the easiest being length_k = 1/k, k=1, 2, 3, ... . To me it appears that it might be a continuous function after all, but the image is blurred. With more info I might be able to help some more.

Thank you very much professor Michael Patriksson for your attention and answer. I was looking for your answer!

I have borrowed these figures from the following paper:

https://link.springer.com/article/10.1007/s00158-018-1958-7

The authors proposed a way to approximate the objective with the Kriging method. However, it seems that they were not familiar with discontinuous programming and used a heuristic to solve the problem. “Capture 1” which is attached for your consideration illustrates the objective function interpolated by Kriging for size optimization of a six-bar truss. However, “Capture 2” which is also attached illustrates a square tube under crash loading which will have millions of discontinuity in the objective.

I have solved such problems many times with simultaneous analysis and design using a metaheuristic, but I hate a metaheuristic solver due to the problems it has. Can I perform a sub-gradient for such a difficult problem with many discontinuities?

I would be so thankful if you please add an answer for me.

You might be able to use a paper from our joint work with friends from University of Linköping and Chalmers:

E. Gustavsson, M. Patriksson, and A.-B. Stromberg, Primal convergence from

dual subgradient methods for convex optimization, Mathematical Programming, vol. 150, no. 2 (2015), pp. 365--390.

But since the problem appears to be non-convex you might not find an optimum nevertheless.

Dear professor Michael Patriksson

Thank you very much for your effective reply, helpful comment, and interesting reference. Sorry for bothering you many times in different discussions! This would be my final question.

The problem is exactly non-convex. If I approximate the problem with convex objectives in each iteration and use your method, can I claim to reach optimum (as attached)? A similar method is presented as a method of moving asymptotes for continuous optimization:

“Svanberg, K. (1987). The method of moving asymptotes—a new method for structural optimization. International journal for numerical methods in engineering, 24(2), 359-373."

I doubt it. At least I would not bet that any standard solver would be able to find a global optimum, but maybe a local one (which can, of course, be bad as heck). Your objective may not be Lipschitz continuous, which means that local solvers will probably not be able to find an optimum, but if you can download a global solver - which of course would NOT be a metaheuristic! - then you might be able to. Baron is one of the solvers that I have used, and you may find downloads of other global solvers as well. Just google "global optimisation solvers" and see what you find.

By the way Krister Svanberg was a colleague of mine, several years ago.

Thank you very much, professor! No one else could guide me as you did!

You also need to check as well if your function is continuous! Are you sure that it is? Otherwise you may be in a lot of trouble.

Dear prof. Michael Patriksson

The problem that I am involved in has a “stair type” objective. The attached figure illustrates a two-dimensional example of the objective “nodal position” vs. one design variable “Area”. When the dimensions of the problem increases (I am dealing with more than 7000 variables in topology optimization), the number of “jumps” or “stairs” will be highly increased, while they might have interactions! Even a surrogate model must be improved to detect the “jumps” to give an acceptable approximation. I have not yet seen such a problem in mechanical engineering been solved with mathematical optimization (I cannot find it!).

Can sub-gradient solve such a problem?

The figure is also borrowed from the aforementioned paper.

As these problems of yours have a discontinuous non-convex objective, subgradients will be giving information only within each single step of the stair - giving no hint of the behaviour of the function beyond that.

In the one-dimensional picture with the nodal positions above the local direction of descent/ascent is a global one, too (global monotonicity). But is this the case with the problems you want to solve?

Consider as a one-dimensional example f(x)=x/5 - rounddown(x). This one locally increases with increasing x, but the other steps in that direction yield lower objective values.

A subgradient method would be working well for minimizing a convex, continuous, but not everywhere differentiable function, something like f(x)=|x|. In the kink at x=0 there is a subdifferential, which is the interval [-1,1].

But for a step function at the break points there is no subgradient, the limit of difference quotients is infinite.

BARON's approach of domain decomposition might help for - but if there are too many discontinuities (at unknown locations) like in the cube example you mentioned, it might not work too well...

Dear Dr. Ralf Gollmer

Thank you very much for your reply.

The figures that I presented in this discussion are the low dimensional examples of the problem. I uploaded them to give a sense of what I am looking for. The objective is also interpolated by Kriging. However, the numbers of design variables of the real problem are about 5000-10000 design variables. So the large scale problems may have billions of such discontinuities, jumps, and non-smoothness.

For sure, the problem is non-convex and this makes everything worse!

Regarding the global optimization solvers, like BARON, I am agreeing with you that discontinuities of the objective and the unavailability of the gradient may cause problems for me. I would also prefer to have my code instead of available commercial optimization codes because I cannot control and improve them.

For such problems, engineers use methods like “Hybrid Cellular Automata”. But this is a heuristic and not a scientific solution and mathematical solver. In low dimensions, the global heuristics will work, but in large scales (more than 200 variables) they will also fail and would be inefficient and the designs would be very bad. Besides, the heuristics are not good solvers generally.

I am so worried that this problem may have no mathematical solution!!!

What do you think about the following method:

"Bagirov, A. M., Jin, L., Karmitsa, N., Al Nuaimat, A., & Sultanova, N. (2013). Subgradient method for nonconvex nonsmooth optimization. Journal of Optimization Theory and applications, 157(2), 416-435."

Parameter selection for fitting models is also extremely important. For example, in three parameter cases the form y = Ax^2 + Bx + C is useful for smooth behavior,

while, for discontinuous step behavior, the three parameters (A,B,C) can be used to model step behavior (A and B) for the two step levels, and C for the location of the discontinuity step. The implementation of this latter option was essential for the context of radar modeling ionospheric behavior in the day-night transition of earth's atmosphere. This was a real puzzle in the early 1940's; the smooth parabolic option simply did not work.

It may be useful to make a distinction between 'global' optimisation (where one is given an explicit, non-convex objective function) and 'black-box' optimisation (where the function is not given explicitly). The methods for them are very different.

Dear professor Adam N. Letchford

Thank you very much for your attention to my question. As you mentioned this was a black-box optimization which is approximated by the Kriging model. Now, we have a surrogate model same as what we have in explicit objectives.

My problem is that how to solve this large scale non-convex non-smooth nonlinear programming problem. I was thinking about the sub-gradient methods, but some people mentioned that they mostly give global optima in convex objectives. Also, it was recommended to use global solvers in this problem, but some others mentioned that global solvers may not work well due to many discontinuities. Even the zero-order (inferior) methods like metaheuristics will also fail due to the scale of the problem and the high computational cost of objective evaluation.

I would be thankful if you please add your answer to me.

I guess it depends on the function that you are using. If it is a polynomial, there are some solution methods based on semidefinite programming, along with a dedicated optimiser, Gloptipoly. If it is factorable (e.g., a sum of Gaussians), then you can use a branch-and-reduce solver like BARON.

Dear Professor Adam N. Letchford

Thank you very much for your helpful reply.

However, the problem has so many discontinuities and non-smoothness (you can find them in some samples that I attached in this discussion in my previous replies) and I am not sure that BARON can work. In the discontinuous points, the problem is non-differentiable due to discontinuity (so it is called ill-posed problems) and solvers like BARON cannot guarantee to solve such problems as well.

Please also note that the optimal solution must be so close to those discontinuities!

It really depends on the nature of the function that you wish to minimise. There are specialised methods for, e.g., quadratic optimisation, polynomial optimisation, posynomial optimisation, quasi-convex optimisation, factorable programming, separable programming, fractional programming, mixed-integer nonlinear programming, and so on. You will need to give more details about the function before anyone can recommend a specific algorithm or software package.

Dear professor Adam N. Letchford

Yes, sir. it depends on the nature of the objective. Sorry for giving low information! I should ask a general question.

In one of such objectives, in the following paper:

https://link.springer.com/article/10.1007/s00158-018-1958-7

The author claimed as follows:

“Crashworthiness optimization problems are, though, ill posed as they include nonlinear, noncontinuous and noisy responses. This violates the Hadamard conditions for well-posed problems and therefore the applicability of gradient-based algorithms is limited.”

And somewhere else:

“Gradient-based algorithms, strictly seen, should not be used in combination with discontinuities in the design domain. Therefore…”

Therefore, they used metaheuristics. I wanted to know that is an inaccurate claim and there are mathematical solutions for such problems (am I right?).

Not all, but some discontinuous optimization problems can be solved using the equations of mathematical physics, for examples, Poisson's equations and heat conduction equations.

Dear Dr. Igor Prudnikov

Is there any specific condition for these discontinuous equations?

There are, but not burdensome. it's integrability

Dear Pooya Rostami, it sounds like you already have a reasonably effective method for identifying where the discontinuities lie. In other words, you can divide the domain of the variables into a collection of "regions", where the cost function is expected to be continuous within each region. In that case, you could just run any continuous optimisation method several times, once for each region.

If you don't know where the discontinuities lie, it is hard to say anything general. In that case, you could just use any heuristic, or run a local optimiser many times, from many different starting positions.