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.

I am trying to solve the following minimization problem, perhaps by getting it into a LP form:

Let $u= [u_1, u_2, ...u_N]^T$ a column vector, and $v=[{1\over u_1}, {1 \over u_2}, ...{1 \over u_N}]^T$ a column vector of the reciprocals of elements in u. Let d be another column vector in $R^N$.

problem: find u that minimizes $d^Tv$ such that $1^Tu \le 1$ (i.e. $\sum u_i \le 1$)

share|improve this question

1 Answer 1

up vote 1 down vote accepted

I'll assume all components of $u$, $v$, and $d$ are strictly positive (otherwise you have other problems). In this case, the feasible set $\sum v_i^{-1} \le 1$ is convex in $v$, and the objective is linear, therefore the optimum is attained on the boundary $\sum v_i^{-1}=1$. Lagrange multipliers give you the optimality criteria $v_i^{-2}=\lambda d_i$ which you can plug into $\sum v_i^{-1} = 1$ to get the optimum.

share|improve this answer
    
I assume you mean $v_i^{-2}=d_i/\lambda$ ? Also, I don't see why $\sum v_i^{-1} \le 1$ is convex, but that the solution is on the boundary makes sense in the physical problem this math problem came from. Thx, this was very helpful. –  Guy Aug 24 '12 at 3:43
1  
@Guy: Yes, $v_i^{-2} = d_i/\lambda$ would be the usual way to write it, though it makes no difference to the solution. The functions $v_i^{-1}$ are convex as can be seen from their second derivatives; $\sum v_i^{-1}$ is a sum of convex functions and is therefore convex; $\sum v_i^{-1} \le 1$ is the sublevel set of a convex function, so it is a convex set. Although on second thought it doesn't really matter, because the objective is linear and so cannot have an optimum in the interior in the first place. –  Rahul Aug 24 '12 at 4:11

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.