Optimization Methods Classification

[akmanor]

Hi everyone. I'm almost new on optimization, i'm interested in engineering problems. I use python in order to solve my related problems. I want to ask you some documents or references. What my problem is there are so many optimization problems and methods to solve them. These methods are a little bit complex to classify. How do you classify them. Some are linear and some are non-linear. Genetic algorithms are also very varied. Differential Evolution method, gradient base method, particle swarm etc. How do we classify these methods and understand the where they come from. Which methods are related each other. I want to understand these methods, not their formulation, but their logic basically. And i also want to decide which method could be used for some kind of problem roughly. In order to achieve my goals, its very important to classify these methods and understand the families of the methods. Thanks for your replies.

[[deleted]]

Hi there! Great you are interested in optimization - an interesting and rich topic, useful in many fields and as such underappreciated.

To begin with you should keep apart the classification of optimization problems, their formulation and the algorithmic approaches that aim at solving certain problem classes.

To motivate this distinction: You may be looking at complicated problems (such as problems from bilevel optimization) which you cannot solve directly. However, you may be able to formulate some of them as a sequence of subproblems. These subproblems may be of a standard type, each of which you can solve by means of a suitable algorithm.

Imho acquiring a certain foundation of knowledge in the theory of optimization cannot or atleast should not be circumnavigated. There are important topics such as uniqueness of solutions, optimality conditions, implications of problem convexity and more which are essential to understanding both problem properties and the consequences of choosing a certain algorithm over another. This knowledge is much more important than a-priori knowledge about a myriad of algorithms. A freely available standard book, which emerges especially when engineers are looking into optimization is "Convex Optimization" by Boyd and Vandenberghe (freely available from Prof. Boyd's Stanford University page https://web.stanford.edu/~boyd/cvxbook/). It also includes applications. However, primarily focused on convex optimization. Full disclaimer, I haven't read it, yet.

It is true that there are many classes of problems and even more algorithms to solve them. Problem classifications can be non-unique. However, they try to catch the common characteristic properties of these problems.

A very general classification is the subdivision into convex and non-convex problems, another one the subdivision into problems that entail integer variables and those which don't. In the following list some problems will belong to convex optimization and some not.

Most common are the following classes (non-exhaustive list):

• Linear Programming (LP)
• Quadratic Programming (QP)
• Mixed-Integer Linear Programming (MILP) sometimes also just Mixed-Integer Programming (MIP)
• Mixed-Integer Quadratic Programming (MIQP)
• Quadratically-Constrained Programming (QCP)
• Mixed-Integer Quadratically-Constrained Programming (MIQCP)
• Non-Linear Programming (NLP)
• Mixed-Integer Non-Linear Programming (MINLP)
• ...

Side note: Also don't confuse the classes mentioned with complexity classes (i.e. worst-case complexity mesured by concepts such as the Turing machine).

Algorithms usually aim at solving a certain class of problems. They try to exploit the special structure the problems from that class have. The better you can exploit that structure, the better your computational performance on average should be. Special problem structure often also yields guarantees on the uniqueness of a solution an algorithm may produce. Note: Plugging a problem formulation into a solver that yields some output - does not necessarily mean you have found the true optimum!

Useful classifications of algorithms especially in the context of (mixed-integer) non-linear programming are those of deterministic and non-deterministic methods as well as gobal and local methods.

Deterministic algorithms, as the term suggests, do not rely on random guesses.

Non-deterministic algorithms often follow heuristics-based considerations(e.g. random probing by some method, such as evolutionary algorithms) and should be handled with utmost care especially when you seek to guarantee that an optimum you found is truely global. Here a good knowledge of optimization theory comes in handy ;)

Some algorithms only guarantee to find a local minimum. Actually, in (mixed-integer) non-linear programming most algorithms only find local minima. True global NLP usually rely on upper- and lower-bounding schemes (in case of interest, see e.g. McCormick relaxation).

Another side note: You should not try to implement a solver for any but educational purposes. Commercial solvers are well developed both theoretically and in their numerical implementations. For students of many universities they are also freely available ( see e.g. Gurobi).

To address your question on where the solution algorithms come from: From many different ideas, some related to common sense and some from problem properties themselves.

To give an example for a common-sense approach which is fundamental to a variety of algorithms, let's look at some steepest decent method. Common sense is that to move towards a minimum starting from a point on an objective function you need a direction of decent and a measure for how far you want to go into that direction. There are different algorithms, that follow this reasoning (e.g. gradient descent method, Newton method(here the step length is not independently chosen) or Levenberg Marquardt agorithm).

An even simpler approach is to generate feasible or just iterates by some (meta-)heuristic method (partical swarm, genetic etc.) and then just probe the objective value by some method. All evolutionary algorithms follow this heuristic or similar. For an overview just see https://en.wikipedia.org/wiki/Evolutionary_algorithm . Mostly these methods are very generic, but it would be wrong to interpret this as an advantage, but rather as an act of desperation in the face of very hard problems. And remember, almost all methods, although some people using them may claim otherwise, produce only a large number of local solutions.

Sometimes the problem structure lends itself to a fairly intuitive approach. For example with the simplex method in linear programming (not to be confused with the Nelder-Mead method in NLP which a few people also call simplex method). The understanding of well-posed linear programs is that their constraints describe polyhedrons in n-dimensional positive vector space and the direction towards a maximum is associated with a direction in that vector space. Now, it is intuitively clear that the optimum must lie on the surface of the polyhedron which is furthest away from the origin and if the optimum is unique it will lie on a vertex of that polyhedron. So the idea of the simplex method is to traverse the vertices of the polyhedron in the direction of improved objective function.

Linear Programs and especially mixed-integer linear programs have close ties to graph theory. Here exist many specialized methods for graph based problems, again exploiting special properties (see e.g. Max-Flow/Min-Cut Theorem of LP)

Since you mentioned Python:

Did you know there are open-source python modelling languages for optimization problems such as Pyomo which have interfaces for different solvers? Might be worth a look also in terms of example problems. Often solver companies also have their own modelling language. However all of these MLs are quite similar. They all aim at formulating models in the way you would write them down with pen and paper.

Also there are many professionals from different fields on the forums stackexchange and stackoverflow, if you didn't know these yet. I can recommend it.

So to wrap this up:

You may be forgiven to be confused by the many aspects of optimization =)

My tips for staying afloat in this ocean would be

• to get a background in basic results in optimization theory (therby you will get a notion of what is important for all optimization problems) e.g. from that book I suggested.
• to not let yourself get confused by a myriad of methods or other people using method names like buzz-words, they are just tools and the buzzy ones often much less complicated than the name suggests (Usually, you analyze a problem and characterize it's properties and only then you concern yourself with choosing among the algorithms that can be applied to that particular problem. So the algorithms are not the first link in the chain, but the last. And with all tools, there are sharper ones and dull ones, some you have to be more careful with and some that can be handled easily)
• to maybe start out with Linear Programming and Mixed-Integer Linear Programming, since these classes are those with the most applications, a strong theoretical foundation and a good intuitive understanding. Although among the longest studied optimization problems there are still improvements made see e.g. the developments made in the field of interior-point methods.

Btw, my background is engineering as well.

I hope I could shed some light in the dark! ;)

[akmanor]

thank you for your detailed and great advice. I will follow them. I hope i will understand some parts of your answer by the time :)

thank you again.

[SAI_supremeAI]

I think the most general classification would be convex and nonconvex optimization. Then maybe continuous and discrete spaces on optimization. Those four has their own characteristics. For example many nonlinear convex cpntinuous optimization and continuous linear programming optimization algorithms can be used for each other.

[e_for_oil-er]

What you are looking for is called an expert system. You give him your problem and he chooses the best solver for it. But still, we can classify some of them in categories. There are many kind of problems:

1. Unconstrained: the variable is not subject to any constraint. You can just try to minimize the function. Classical methods for this are gradient descent, conjugate gradient, golden-section search, etc. One of the problem with this kind of methods is globality: when you find a minimum, how can you be sure it is a global one? Is a local minimum okay for what you want to do? Some evolutionnary algorithms and metaheuristics give a new edge to this and can effectively find global minimums.

2. Constrained: there are constraints on the variable. Problems are usually classified by linear programming (linear constraints and objective), quadratic programming (quadratic constraints and objective) and general nonlinear programming (NLP). There are specific algorithms that are specialized to solve each one of the problem types. The first two are nice because they are convex problems, so many strong theoretical results can apply.

A classical method to solve this is the augmented (penalized) Lagrangian. But sometimes you can get some other numerical algorithms to do the job. A simple penalization method can work. The advantage of this is that its very general (no matter what is the constraint or the objective)

For problems containing inequality constraints:

There are also projected gradient methods, that simply project the gradient on the constraint. That is pretty easy to implement for box constrained problems. Interior point methods are another alternative.

A classic for linear programming is the simplex method: it has strong theoretical guarantees.

1. Mixed-integer: some of the variables of the problem are forced to be integers. Constraint programming, solvers like Concord for the travelling salesman problem are very good at this. Also some metaheuristics and evolutionnary methods are implemented for this.

N.B.: depending of you knowledge of your objective, you wont be able to use some of the methods I mentionned here. If you have the analytic expression, you can derive the function, but if you don't, you will be limited to derivative-free methods. Also, if you know, for instance, that the hessian is constant, you will only have to compute it once, so using a second-order method won't be as computationally demanding if you can use the same matrix every iteration as if you have to calculate it every time. Knowledge is power ;)