Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$$\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?

share|improve this question
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... –  J. M. Jul 24 '11 at 12:52
    
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... –  J. M. Jul 24 '11 at 12:58
    
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. –  jerryren Jul 24 '11 at 13:01
    
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. –  Hans Engler Jul 24 '11 at 13:29

1 Answer 1

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<x<y<z<b$ and look at the values at those points to choose a smaller interval.

If $F(a)<F(x)$, switch to $[a,x]$, else

if $F(x)<F(y)$, switch to $[a,y]$, else

if $F(y)<F(z)$, switch to $[x,z]$, else

if $F(z)<F(b)$, switch to $[y,b]$, else

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.

share|improve this answer
    
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? ** –  jerryren Jul 24 '11 at 14:42
    
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. –  fedja Jul 24 '11 at 21:34
    
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. –  jerryren Jul 25 '11 at 4:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.