Solving a (Non-)Linear Programming Problem

Question

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.

Answer 1

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.

Answer 2

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).