How to optimize objective function that contains the “k-largest” operator? I want to solve the following optimization problem:
$$\min_{x,y} f(x*A+y*B)$$
$$s.t  ~~~ \{x,y\} \geq 0$$
$$~~~~~~~ x+y=1$$
in which, $A,B$ are square matrices and $x,y$ are scalars.
The function $f(A)=\sum s_i$, and $s_i$ means sum of $k$ largest entries in the $i$th row of $A$.
For example if 
$A=\begin{bmatrix}
1 & 2 & 3\\
5 & 1 & 7\\
3 & 4 & 2
\end{bmatrix}
$, then $f(A)$ for $k=2$ would be $(2+3)+(5+7)+(4+3)=24$
If i could calculate the derivatives of $f$ respect to $(x,y)$ then the problem would be solved easily.
Also i know that one way to deal with "$max(a)$" in an objective is to add a stack variable $t$ to the objective and adding $a \leq t$ to the constraints. But i couldn't find the above problem that straightforward.
In order to compare the optimality of the solution, I solve the above problem using the Matlab general solver, but i need to know how can i optimize it myself.
 A: The sum of the $k$ largest elements in a vector is a convex function and is linear programming representable if you use the operator in a convex setting (which you do as you minimize a sum of those operators)
The epigraph representation (with $s$ representing the value) of the sum of the $k$ largest elements of a vector $x$ can be constructed by first introducing an auxiliary variable $z$ of same dimension as $x$, and an additional scalar $q$ and the linear constraints
$$     s\geq kq+\sum z,~z \geq 0, ~z-x+q \geq  0$$
In your case, you simply want to apply this to every column of your matrix and sum up the epigraph variables $s_i$.
Here is an example in the optimization language YALMIP which overloads this operator (disclaimer, MATLAB Toolbox developed by me)
A = randn(3);
B = randn(3);
sdpvar x y
C = x*A + y*B;
Objective = sumk(C(:,1),2)+sumk(C(:,2),2)+sumk(C(:,3),2);
Constraints = [x >= 0, y >= 0, x + y == 1];
optimize(Constraints,Objective)

A: Very good question. I will give you a reformulation, of a more general problem, which you could solve on the computer. 
Consider the problem 
$$\min g(x)=f(x_1A_1+ x_2A_2+\ldots + x_n A_n),$$ 
$$s.t\; x_j\geq 0,\;\sum_{j=1}^n x_j=1.$$ Here $A_l=(a_{ij}^l)\in \Bbb R^{m\times m}$ for $l=1,\ldots,n,$ and $f(A)$ is the summ of the $k$ greatest terms in each row of $A$. In order to simplify notation, for $i,j\in \{1,\ldots,m \},$ define the vector $$c_{ij}=(a_{ij}^1,\ldots,a_{ij}^n )^T.$$ With this notation, we have that the $(i,j)$ entry of the matrix $A(x)=x_1A_1+ x_2A_2+\ldots + x_n A_n$ is just $c_{ij}^Tx.$ Now, a reformulation of the problem is 
$$\min \sum_{i=1}^m s_i,$$
$$s.t \; x\geq 0,\;\sum_{j=1}^n x_j=1,$$
$$\sum_{t=1}^k c_{ij_t}^Tx\leq s_i, \;\forall \;i\in \{1,\ldots, m\},\;(j_1,\ldots,j_k)\subseteq \{1,\ldots,m\}. $$ 
As you see, there are approximately $m \times C_k^m$ constraints in the reformulation, which makes the problem hard to solve. But hey, it is a difficult problem!! Hope this helps
