# Convex Optimization, Non-negativity constraints, Interior-Point or Projected Gradient?

Assume I have the following convex optimization problem, with a convex objective function on conventional non-negativity constraints.

\begin{align} \min_{x \geq 0} \sum_{i=1}^{I} a_{i}x_{i} - f(\bf{x}), \end{align}

where $$\bf{x}$$ is a vector of dimension I, $$f(\bf{x})$$ is a concave function, and the dimension of $$I$$ is very large. The solution is sparse, meaning that in the optimal vector there is a large amount of zeros. This comes from the fact that for some entries $$i$$

\begin{align} a_{i} > f_{i}(\bf{x}^{*}) \end{align}

where $$f_{i}(\bf{x})$$ corresponds to $$\partial f(\bf{x}^{*})/x_{i}$$. Since the function is convex, I know that the KKT conditions are necessary and sufficient for global optimality, all local optima are also global, and the set of solutions is convex.

However, I have questions about how to solve for the optimum numerically,

1. If I use a Projected Gradient Method, I have seen on the internet that the projection step of the algorithm is just

$$x^{k+1} = \max\left\{0,x^{k}-\alpha_{k}(a-\nabla f(x^{k}))\right\}$$

However, I have not found a proof or a paper that shows this. Can someone provide a proof or reference?

1. The other option is to use Interior-Point methods. However, what confuses me in this case is that when one uses barrier methods, how does it work if the solution is not interior, but in the boundary for some entries?
• In particular, why in these problems the fact that we have inequality constraints does not make it combinatorial? Oct 23, 2022 at 21:35
• Your objective has $-f(\mathbf{x})$ (no index on $f$), but then you wrote "for some entries $i$, $a_{i} > f_{i}(\mathbf{x}^{*})$". Is there a unique $f$, or are there multiple $f_{i}$s? Oct 23, 2022 at 22:30
• Sorry. @mtanneau I meant $f_i(\bf{x})$ to be the partial derivative with respect to the $i-th$ variable. I edited the text to reflect this. Oct 24, 2022 at 0:39
• @mtanneau I edited the post to clarify the language further. Oct 24, 2022 at 12:37