Htykuut

Now I have a convex function $f(x)$, $xin mathbb{R}^n$, consider the minimization problem: $min_x f(x)+lambda x^Ts$, where $s$ is a positive real vector and $lambda$ is a parameter, I am wondering for different values of $lambda$, when the above min problem reaches its minimization, how does $x^Ts$ changes? Is there any rules?

Given $lambda$ and $s$, you want to find $x in mathbb{R}^n$ to minimize
$$ f(x) + lambda x^Ts $$
Assume at least one minimizer exists for each value of $lambda$ that is considered.

If $lambda_1<lambda_2$ and $x_1$ minimizes for $lambda_1$, $x_2$ minimizes for $lambda_2$, then indeed:
$$x_1^Ts geq x_2^Ts$$
Intuitively, since we penalize the constraint function $x^Ts$ more with the larger $lambda_2$, we get a smaller constraint value $x_2^Ts$. This is easy to prove in 2-3 lines by just using the definition of "minimum," and convexity assumptions are not required. See related and/or more general statements here (Theorem III.2 page 14, Exercises IX-B.5, IX-B.6 page 41): http://ee.usc.edu/stochastic-nets/docs/network-optimization-notes.pdf

More generally if $mathcal{X}subseteq mathbb{R}^n$ is any set (possibly nonconvex and/or disconnected), $f:mathcal{X}rightarrowmathbb{R}$, $g:mathcal{X}rightarrowmathbb{R}$ are any functions (not necessarily convex or continuous) and we consider:
begin{align}
&mbox{Minimize:} quad f(x) + lambda g(x) \
&mbox{Subject to:} quad x in mathcal{X}
end{align}
Then the same holds: If $lambda_1<lambda_2$ and $x_1inmathcal{X}$ and $x_2 in mathcal{X}$ are respective minimizers (assuming minimizers exist), then $g(x_1)geq g(x_2)$. (The proof is the same 2-3 line argument.)

As described in the notes of the above link, this motivates a simple bisection procedure for optimization subject to one constraint, where we zero-in on a good solution (with an optimized $lambda$) exponentially fast (whether or not this bisection procedure always finds a solution, i.e. if there exists a $lambda$ that leads to an optimized $x$ that satisfies the desired constraint, depends on existence of "Hidden/Unhidden" Pareto optimal points, and convexity is then of use for this extended question.)