Consider the minimization problem $$\min_{x \in \Delta_n} f(x)$$ where $f$ is $C^1$ function over the unit simplex $\Delta_n$. Prove that $x^*\in\Delta_n$ is a stationary point of the problem iff there exists $\mu\in\mathbb{R}$ such that $$\frac{\partial f}{\partial x_i}(x^*)=\left\{\begin{array}{rcl} = \mu&x_i^*>0 \\ \geq\mu&x_i^*=0 \end{array}\right.$$

I know the solution for the stationary points of $\mathbb{R}_{+}^{n}$ and for

$$C = \{ x : \sum_{i=1}^{n}x_i = 1 \}$$

and I need to solve this without KKT.
I've tried taking $y\in\Delta_n$ which defined by $y_k=\left\{\begin{array}{rcl} x_k^*&k\notin\{i,j\}\\ x_j^*&k=i\\ x_i^*&k=j\\ \end{array}\right.$
And then looking at the definition of stationary point for $x^*$ and y :
$\nabla f(x^*)(y-x^*)=\sum_{k=1}^{n}\frac{\partial f}{\partial x_k}(x^*)(y_k-x_k^*)=\frac{\partial f}{\partial x_i}(x_j-x_i)+\frac{\partial f}{\partial x_j}(x_i-x_j)=(x_j-x_i)(\frac{\partial f}{\partial x_i}-\frac{\partial f}{\partial x_j})\geq0$ and I tried from this condition to get the desired result but got stuck here.

Definition of Stationarity Let $f$ be $C^1$ function over a closed and convex set $C$ . then $x^*$ is called a stationary point of (P) if $\nabla f(x^*)(x-x^*)\geq0$ for any $x\in C$


1 Answer 1


Let $e^{(k)}$ denote the vector with $k$-th component 1 and all other components 0. Assume first that $x^*$ is a stationary point. Pick two indices $i\neq j$ for which $x_i^*$ and $x_j^*$ are both positive. Then for small positive $\delta$, $x=x^* + \delta e^{(i)} - \delta e^{(j)}$ and $x^-=x^* - \delta e^{(i)} + \delta e^{(j)}$ are in the simplex. Use the definition of stationarity to show that $\frac{\partial f}{\partial x_{i}}\left(x^{*}\right)=\frac{\partial f}{\partial x_{j}}\left(x^{*}\right)$. Next, assume that $x^*_i \gt 0$ and $x^*_j = 0$, in which case only $x^-$ is in the simplex. Use the definition of stationarity to show that $\frac{\partial f}{\partial x_{i}}\left(x^{*}\right) \le \frac{\partial f}{\partial x_{j}}\left(x^{*}\right)$.

Now assume that the gradient condition is satisfied, and use similar logic to show that the stationarity condition is met.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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