How to optimize objective function that contains the “k-largest” operator?

Question

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.

Answer 1

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)

Answer 2

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