1
$\begingroup$

Apologies for my basic question, but I am kinda new to optimization methods, and I am bumping into the optimization problem below:

$\min_{x} (c_1 \cdot u_1 + c_2 \cdot u_2)\\ \mbox{subject to:}\\ u_1 \geq f(x) \\ u_2 \geq g(x) \\ u_1, u_2 \geq 0 $

In general, I would like to minimize the cost function with decision variable $x$. However, $x$ does not exist in my objective function but instead is hidden in two constraints. $f(x), g(x)$ are two functions of $x$, which can be any functions. In the simplest case, it can be just a linear function such as $w^Tx$; however, it can be altered to any more complicated function.

My questions are:

  1. Is this a linear or non-linear problem? I think it is a non-linear problem but I am not so sure.

  2. Do you know any solver that I can use to solve this problem and which methods to use? Would be nice if I can directly use it with Python.

Any suggestion/hint would be highly appreciated. Thank you in advance.

$\endgroup$
  • 4
    $\begingroup$ The problem is to minimize with respect to $x, u_1$, and $u_2$. if $f(x)$ and $g(x)$ are both linear, this is a Linear Programming problem, otherwise it is a Nonlinear Programming problem. As to what optimizer to use, that depends on the form and properties of $f(x) $ and $g(x)$, such as continuity, differentiability, availability of derivatives, convexity, special form such as (convex) quadratic (or second order cone), etc.. $\endgroup$ – Mark L. Stone Apr 27 at 17:15
  • $\begingroup$ @MarkL.Stone: Thank you very much! I would like first try it with the simpliest form, in which both of them are linear, such as in the form of $w^Tx + a$ and $w^Tx + b$ respectively. In this case do you have any suggestion? A separate answer would be nice as suggested by the moderator, I guess. $\endgroup$ – blurryface Apr 27 at 18:11
  • $\begingroup$ @MarkL.Stone I think your ANSWER is complete and useful. $\endgroup$ – Oguz Toragay Apr 27 at 18:12
  • 1
    $\begingroup$ Related: or.stackexchange.com/questions/2605/… $\endgroup$ – LarrySnyder610 Apr 27 at 19:38
7
$\begingroup$

The problem is to minimize with respect to $x, u_1$, and $u_2$ (i.e., those are the decision, a.k.a. optimization, variables).

If $f(x)$ and $g(x)$ are both linear, this is a Linear Programming (LP) problem; otherwise it is a Nonlinear Programming (NLP) problem.

If this is a Linear Programming problem, then use an LP solver. There are many optimization modeling systems, tools, and solvers available under Python, essentially all of which should be able to handle LPs, and which can be found by searching this site.

If this is a Nonlinear Programming problem, you will need an NLP solver.

As to what NLP solver to use, that depends on the form and properties of $f(x)$ and $g(x)$, such as continuity, differentiability, availability of derivatives, convexity, special form such as (convex) quadratic (QCQP), or second order cone (SOCP)), etc. There are many optimization modeling systems, tools, and solvers available under Python, many of which can handle either somewhat general NLPs, or perhaps special cases, such as QCQP and SOCP. Solvers specialized for special cases may perform better and be easier to use for those cases. If you use a fairly general optimization tool, you may be able to handle variations on $f(x)$ and $g(x)$ of the type which change the problem class.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you, it is very useful. I will look into those solvers. $\endgroup$ – blurryface Apr 28 at 7:01
1
$\begingroup$

The answer by Mark L. Stone is to the point. In addition to it, I would suggest you read about metaheuristics, especially Genetic Algorithms. Some useful links for it:

[1] Goldberg, D. E. (2006). Genetic algorithms. Pearson Education India.

[2] Bäck, T., Fogel, D. B., & Michalewicz, Z. (1997). Handbook of evolutionary computation. CRC Press.

[3] https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3

[4] https://towardsdatascience.com/introduction-to-optimization-with-genetic-algorithm-2f5001d9964b

The GAs are population-based randomized search heuristics, inspired by the theory of genetics and natural selection, whose search is not strictly dependent on the nature (linear/non-linear) of the optimization problem. One thing I have experienced about GAs is that the GA-search can be as powerful/efficient as you could design it by customizing operators using the problem's domain knowledge.

For its code in python, you could refer to the GA-code uploaded by Prof. K. Deb:

[1] https://pymoo.org/

[2] Blank, J., & Deb, K. (2020). pymoo: Multi-objective Optimization in Python. arXiv preprint arXiv:2002.04504.

Examples of customized operators in GA are:

[1] enhanced initialization, i.e., to generate at least one feasible solution in the initial population instead of all randomized ones,

[2] retaining poor/infeasible solutions to maintain diversity in the population,

[3] enhanced crossover/mutation operators,

[4] infeasibility repair operators, etc.

Some useful articles for such customizations are (though the problem formulations might be different, you will get some idea about it):

[1] J. E. Beasley, P. C. Chu, A genetic algorithm for the set covering problem, European journal of operational research 94 (2) (1996) 392–404.

[2] Deb, K., & Myburgh, C. (2016, July). Breaking the billion-variable barrier in real-world optimization using a customized evolutionary algorithm. In Proceedings of the Genetic and Evolutionary Computation Conference 2016 (pp. 653-660).

[3] D. Aggarwal, D. K. Saxena, T. Bäck, M. Emmerich, Real-World Airline Crew Pairing Optimization: Customized Genetic Algorithm versus Column Generation Method, arXiv:2003.03792 [cs.NE] (Unpublished).

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thank you very much for suggestion! I will look into those. $\endgroup$ – blurryface Apr 28 at 7:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.