2
$\begingroup$

$$\min_{x\geq 0}\sum_{i=1}^n (a_i-x b_i)^2 [a_i-x b_i\leq 0],\quad a_i,b_i\in\mathbb R,n\in\mathbb N$$

where $[p]$ is an Iverson bracket.

The objective function seemed easy (convex).

1.Is there any the concrete name for this kind of optimization or specific method to solve?

2.Any reference material?

3.To find the solution, is there suitable package in R?

  • 1
    Well, it's a constrained optimization (programming) problem... the piecewise nature of your function would certainly trip up most of the routines, since they assume nice behavior of the derivatives...2011-07-24
  • 0
    Unless the rest of you guys have better ideas, you might want to check out any of the stochastic methods (e.g. "differential evolution" or "simulated annealing"); they take a fair bit of computational effort, but at least they don't assume that the objective function has neat derivatives...2011-07-24
  • 0
    Thanks for your kindness.I haven't thought so looking-easy problem is difficult. Maybe I should quit. But I will go to browse materials as you mentioned to try.2011-07-24
  • 0
    The derivative of your function is piecewise linear, with corners at $x_j = \frac{a_j}{b_j}$. At each such corner, the slope of $f'(x)$ increases by $2b_i^2$. A few application of the cumsum function plus a linear interpolation should allow you to find the answer.2011-07-24

1 Answers 1

2

For a convex function $F$ of one variable you can always find the minimum by simple bisection: if you know that the minimum is attained on $[a,b]$ (in your case $a=0$ and the initial $b$ can be found going to the right geometrically until the current value is greater than the previous one), then you can split $[a,b]$ into 4 equal parts by the points $a

If $F(a)

if $F(x)

if $F(y)

if $F(z)

switch to $[z,b]$.

This approach is somewhat crude but quick and once you are close enough to the minimum, you can find it exactly because you will know which brackets are involved.

  • 0
    Your method is general and simple, thanks. Indeed, I get a upper bound of the parameter. **How about many variables, for instance both x and b are four dimensional vectors which I have thought? **2011-07-24
  • 0
    I would just do some version of the gradient descent then (fortunately, to compute the gradient here is not any harder than to compute the function). Let me know if you need more details.2011-07-24
  • 0
    How to compute the gradient? Is there way to get the derivative vector of each coordinate. Please tell me the details, I really appreciate it and curious about it.2011-07-25