8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Could you be a bit more specific about what you are looking for? Do you want to find p1 and p2 such that k and t attain (as closely as possible) their maximal values? I assume you have a function that, given p1 and p2, returns the value of k and t, but no information on the derivatives of k and t with respect to p1 and p2? $\endgroup$ – Christian Clason Sep 19 '12 at 10:51
  • $\begingroup$ @ChristianClason yes, you understand it correctly. I cannot get the derivatives, and in general there is no analitics available. $\endgroup$ – user1639 Sep 19 '12 at 11:01
  • $\begingroup$ And do you know whether the maximum of k and t will be attained at the same point (which you are trying to find), or are you looking for a trade-off? $\endgroup$ – Christian Clason Sep 19 '12 at 11:04
  • $\begingroup$ @ChristianClason I assume (and sure) that the maximum values are not at the same point. I am looking for a trade-off. But cannot say in which manner - probably I can compare the products or the sums of the values... $\endgroup$ – user1639 Sep 19 '12 at 11:05
12
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you for the great answer! It is really helpful although the subject is rather complicated for me. Sorry, my reputation is too low, cannot vote up for your answer. $\endgroup$ – user1639 Sep 19 '12 at 12:24
  • $\begingroup$ @AlexPi Don't worry, I'm happy the answer is of some help. And the subject is indeed complicated (otherwise mathematicians would be out of a job :)). If you have access to Matlab's Optimization Toolbox, you could try feeding your $F$ into fminunc (which uses a method similar to the above) to see what happens. $\endgroup$ – Christian Clason Sep 19 '12 at 12:37
  • 2
    $\begingroup$ @AlexPi: don't take $eps$ too small, or you'll run into problems of numerical stability. $\endgroup$ – Arnold Neumaier Sep 19 '12 at 16:20
  • $\begingroup$ @ArnoldNeumaier: Good point. I have added some remarks on this issue. $\endgroup$ – Christian Clason Sep 19 '12 at 16:56
  • $\begingroup$ Your recipes are adequate for the gradient but not for the hessian! $\endgroup$ – Arnold Neumaier Sep 19 '12 at 17:06
2
$\begingroup$

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

$\endgroup$

Your Answer

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