0
$\begingroup$

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

1 Answers 1

1

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.

  • 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.2012-08-24