Simultaneous maximization of two functions without available derivatives

Question

I have two variables k and t as functions of two other variables p1 and p2. I also know their maximum values. I do not have any analytic expression for this. I want to find the values of k and t which are the closest to their maximum values.

Is there a way to optimise the k = f1(p1, p2) and t = f2(p1, p2)?

I can try to check the product k0 * t0 or the product of the squares k0^2 * t0^2 or some other relation of the two.

Is this efficient and which way to go?

Thank you.

Answer 1

There are two issues here:

1. Your optimization problem has two competing objectives: maximizing $k=f_1(p_1,p_2)$ and maximizing $t = f_2(p_1,p_2)$. This is known as multi-objective (or multi-criteria) optimization, and such problems have an infinite number of solutions, each based on a specific choice of the relative weight of the objectives (i.e., is it more important for $f_1$ to be close to the maximal value than for $f_2$?). If both have the same importance for you, then you can simply minimize the function $$ F(p_1,p_2) = (f_1(p_1,p_2)-K)^2 + (f_2(p_1,p_2)-T)^2, $$ where $K$ and $T$ are the known maximal values of $k$ and $t$, respectively. Otherwise you would add a corresponding weight before each term. (If the maximal values were not known, you'd instead minimize $-f_1^2-f_2^2$.)

2. To find a minimizer of $F$, you can only use function values of $F$ at a given point $(p_1,p_2)$. This is known as derivative-free optimization; see, e.g., Introduction to Derivative-Free Optimization by Conn, Scheinberg and Vicente or chapter 9 in Numerical Optimization. The most of these use approximate derivatives based on finite differences or derivatives of interpolating functions. Since $F$ is a function of only two variables, building finite difference approximations of the full Hessian is not too expensive (or unstable). The idea is the following: given a point $p^k=(p_1^k,p_2^k)$, you construct a local quadratic model $$ m_k(p^k + d) = F(p^k) + (g^k)^T d + \frac{1}{2} d^TH^kd, $$ compute its minimizer $d^k$ and set $p^{k+1} = p^k+d^k$. Here, for a small (but not too small, see below) $\epsilon>0$, $$ g^k = (g_1,g_2)^T,\quad g_i = \frac{F(p^k+\epsilon e_i)-F(p^k-\epsilon e_i)}{2\epsilon} $$ with $e_1 = (1,0)^T$ and $e_2 = (0,1)^T$, is the approximate gradient and $$ H^k = \begin{pmatrix}h_{11}&h_{12}\\h_{21}&h_{22}\end{pmatrix}, \quad h_{ij} = \frac{F(p^k+\epsilon e_i + \epsilon e_j) - F(p^k + \epsilon e_i) - F(p^k+\epsilon e_j) + F(p^k)}{\epsilon^2} $$ is a Taylor approximation of the Hessian. This requires evaluating $F$ at 5 additional points in every iteration.

   An important issue in any finite difference approximation is the choice of $\epsilon$: If it is too large, you have a poor approximation of the derivative; if it is too small, you run into the danger of cancellation and hence numerical instability. A good rule of thumb is to take $\epsilon = {u}^{1/3}$, where $u$ is the unit roundoff (about $10^{-16}$ for double precision).

   In practice, you would want to combine this with a trust-region strategy, where you would require $d^k$ to inside a ball whose radius you adapt during the iteration (see the books mentioned above).

   A comparison of algorithms and implementations for derivative-free optimization can be found on this webpage, which accompanies the paper "Derivative-free optimization: A review of algorithms and comparison of software implementations" by Luis Miguel Rios and Nikolaos V. Sahinidis

Answer 2

With multi-objective optimization, there are many ways you can combine/compare the objective variables in your analysis. The problem is that there isn't a "right" way to do it. It depends entirely on what the problem actually is and what the variables represent. Your best bet is likely to maximize something like $k+a*t$ where $a$ is an arbitrary positive value. Once you have an answer, see if you like the resultant $k$ and $t$, and modify $a$ as necessary until you find a solution you are happy with.

As for the actual optimization, not having an analytical expression for the functions isn't the end of the world, but not having any information is going to make it rough. If you can assume some level of smoothness/continuity, even if it is only piece-wise, you can use a root finding algorithm on a derivative approximation to find local maxima (there are many more sophisticated methods than this, but I am unfamiliar with them. Other people here could likely point you in the right direction). If you can establish convexity, you could extend it to global optimality.

True black box multi-objective optimization isn't exactly an easy problem, but a few assumptions and an iterative process with a objective reduction should get you an answer that is acceptable (assuming one exists).