Efficient ways of minimizing a complicated objective "function"?

Question

My problem at hand neither has any special structure that gives me closed-form solutions nor can be written by a single expression. Yet, it is still an objective "function," as I can compute a value (via a chain of operations) if you give me an input.

To briefly give you a sense what the objective function looks like: given independent variable $x$ I can formulate an eigenproblem, which I can solve deterministically. With the solution to the eigenproblem, I then can compute deterministically the "goodness" of $x$. That is,

$$f(x)=g(\text{sol}(\text{an eigenproblem formulated with } x)).$$

Maybe not that bad?

Is heuristic optimization (such as genetic algorithm and simulated annealing) my only resort? I generally hate this kind of "brutal algorithms."

P.S.: I am not sure what is the name of this kind of objective functions. It is definitely nonconvex and nondifferentiable, but I feel these two adjectives are not enough to describe this class of functions. I would appreciate it if someone could suggest a better name.

Maybe you could describe a rough-cut version of your objective function? Speaking arbitrarily might have downsides when discussing specifics. — Xoque55, Jun 30 '16 at 11:18
Maybe google for the keyword "black box optimization." I could help you more if you even had some uncertainty in the equations defining the constraints. — Peter Franek, Jun 30 '16 at 11:19
One problem is that without any exploitable information about the objective function $f(x)$, it's hard to propose any useful solution. In fact, the two properties you've identified (non-convex and non-differentiable) are almost the exact opposite of "exploitable". In a worst-case scenario, $f(x)$ behaves like a random function (e.g.: a cryptographic hash function) so that there is almost literally nothing you can do beyond exhaustively searching the input space. — mhum, Jul 09 '16 at 01:06
I would like to add to the above: Even exhaustive search would not ensure optimality without additional assumptions. And your problem does seem to have a "special structure": It is "an Eigenproblem". Post details about this, then maybe one can do something about it. Stated as is nothing can be said. — g g, Jul 10 '16 at 06:47

score 1 · Answer 1 · answered Jul 04 '16 at 19:29

How to find the minimum (or maximum) of a very complicated real-valued function $F(x)$ at the interval $A < x < B$ , that's the question (I think).
First select two points $(1)$ and $(2)$ at this interval in such a way that $\,x_1 = A + L_1 (B-A)\,$ and $\,x_2 = A + L_2 (B-A)\,$ , with $\,0 < L_1 , L_2 < 1$ .
If $\,F(x_1) < F(x_2)\,$ then next search must be between $(A)$ and $(2)$
If $\,F(x_1) > F(x_2)\,$ then next search must be between $(1)$ and $(B)$
It is demanded that none of the points $(1,2)$ is to be preferred. $$ x_2 = B + L_1 (A-B) = A + (1-L_1) (B-A) = A + L_2 (B-A)\\ \Longrightarrow \quad L_2 = 1-L_1$$ Also, in order to save work, points must be reusable. Arrange for iteration $k$ in such a way that (two possibilities): $$A(k+1) = A(k) \quad , \quad B(k+1) = x_2(k) \quad , \quad x_2(k+1) = x_1(k) \\ A(k+1) = x_1(k) \quad , \quad B(k+1) = B(k) \quad , \quad x_1(k+1) = x_2(k)$$ Take the first of these equations (the other gives same result): $$ x_2(k+1) = x_1(k)\\ A(k+1) + L_2.[B(k+1) - A(k+1)] = A(k) + L_1.[B(k) - A(k)]\\ A(k) + L_2.[x_2(k) - A(k)] = A(k) + L_1.[B(k) - A(k)]\\ L_2.[A(k) + L_2.[B(k) - A(k)] - A(k)] = L_1.[B(k) - A(k)]\\ L_2.L_2.[B(k) - A(k)] = L_1.[B(k) - A(k)] \\ \Longrightarrow \quad L_2.L_2 = L_1$$ With $L_2 = 1-L_1$ and $L_1 < 1$ giving: $$(1-L_1)^2 = L_1 \quad \Longrightarrow \quad L_1^2 - 3.L_1 + 1 = 0\\ \Longrightarrow \quad L_1 = (3 - \sqrt{5})/2 \quad \Longrightarrow \quad L_2 = (\sqrt{5} - 1)/2$$ Hence the name: Golden Rule Search. Convergence behaviour is determined by: $$B(k+1) - A(k+1) = x_2(k) - A(k) = A(k) + L_2 [B(k) - A(k)] - A(k)$$ Hence: $B(k+1) - A(k+1) = L_2.[B(k) - A(k)] = 0.618$ times smaller. The biggest of the two roots determines convergence behavior.
Here is the algorithm (in Delphi Pascal) that implements the above theory. The function returns the position $x$ of the minimum with an error $\pm \epsilon/2$ .

function Dal(A,B,eps : double; welke : funktie) : double;
{
  (A,B) = interval to start with
  eps = acceptable interval error
  welke = your difficult function
}
var 
  een, twee, ga, gb, weg, eerste, tweede : double;
begin
{ The two Fibonacci numbers }
  een  := (3 - sqrt(5))/2; { = 0.381966... }
  twee := (sqrt(5) - 1)/2; { = 0.618034... }

  weg := B-A;
  ga := A + een*weg; gb := A + twee*weg;
  eerste := welke(ga); tweede := welke(gb);

  while weg > eps do
  begin
    if eerste < tweede then
    begin
      B := gb; gb := ga;
      tweede := eerste;
      weg := B-A;
      ga := A + een*weg;
      eerste := welke(ga);
      Writeln(B);
    end else begin
      A := ga; ga := gb;
      eerste := tweede;
      weg := B-A;
      gb := A + twee*weg;
      tweede := welke(gb);
      Writeln(A);
    end;
    Readln;
  end;
  Dal := (A + B)/2;
end;

Disclaimer. My eyes are not good. Please pinpoint to any typos in the above, if necessary.

Efficient ways of minimizing a complicated objective "function"?

1 Answers1