# Gradient of a sum of indicators

EDITED w.r.t. whuber's comment: Say I have a function $\mathbb R^n \rightarrow \mathbb R$:

$$f(w_1,\ldots,w_n) = \frac{n^-\sum_{i\in I^-}w_ix_i}{n^+\sum_{i\in I^+}w_ix_i}$$

with fixed $x_i\in\mathbb R$ (data), $I^-$ the set of indexes with negative $w_ix_i$ and $n^-$ the number of negative $w_ix_i$ ($I^+$ and $n^+$ respectively constitute to positive values). The goal is to minimize this sum over weights $w = (w_1,\ldots,w_n), w\in\mathbb R^+$ possibly with constraints $w^L$ and $w^U$. The reason to include $n^-$ is to penalize not only large values of $w_ix_i$ but also the number of negative values.

My question is how can I compute function gradient at a given point: $\partial f/\partial w_i|_{w=w^0}$.

The difficulty here is with $n^-$ (which can be written as a sum of indicators $\sum_i 1\{w_ix_i < 0\}$). Is there any way of obtaining partial derivatives $\partial n^-/\partial w_i|_{w=w^0}$? If not how can I construct a function so that not only negative values are penalized but also the number of negative values?

• What is a "sum operand" and how is it related to the weights $w_i$ and the data $x_i$? Why not make $w_i$ arbitrarily large and negative when $x_i$ is positive and equal to zero otherwise? That would make $f$ arbitrarily large and negative. Surely, then, you must have in mind some constraints on the $w_i$: what are they? The partial derivatives do not exist at various points because $f$ is not differentiable everywhere. What, then are you trying to find a workaround for--the fact that $f$ is not differentiable? – whuber Jul 22 '15 at 19:01
• So the $x_i$ can be negative? I don't know what your real "objective" is. You should formulate a fairly smooth (differentiable) objective function which penalizes or prevents what you don't want. You could force negative $x_i$ values to have zero $w_i$ by use of an indicator constraint, which would introduce extra binary variables into your problem, and perhaps have a Mixed Integer Linear (?) Program, for which there is good free off the shelf software. You can get more guidance if you tell us at a more fundamental level what you're trying to accomplish with the optimization. – Mark L. Stone Jul 22 '15 at 20:37
• You need to decide what your constraints are on $w_i$. For instance lower and upper bounds, and maybe a constraint that they sum to 1. Those constraints are easy to incorporate in your optimization problem formulation. Then use an apropriate constrained optimization solver to solve it, Forget this gradient descent nonsense so popular on this board. – Mark L. Stone Jul 22 '15 at 20:41
• Yes $x_i$ can be negative. The fundamental problem is to construct a portfolio of different assets where $x_i$ are returns on asset $i$, usually $w^L = 0$ and $w^U$ a vector of positive values. Weights need not sum up to 1. What do you mean by "this gradient descent nonsense so popular on this board"? – danas.zuokas Jul 23 '15 at 6:36