3
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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)
$\endgroup$
  • $\begingroup$ Very nice!! (+1) This is way more efficient than my solution. Thanks! I learned something new. $\endgroup$ – John D Sep 15 '17 at 6:41
  • $\begingroup$ Thank you for this nice solution. I tried the epigraph representation and it works, but i couldn't figure out why, and also couldn't get the logic behind those additional constraints involving the auxiliary variables $z,q$? $\endgroup$ – Babak Sep 16 '17 at 19:31
  • $\begingroup$ If i try $sumk(C(:,1),2) - sumk(C(:,2),2)$ it fails! Also i tried it with the epigraph representation. Is it because the "-" makes it a non-convex problem?! $\endgroup$ – Babak Jul 24 '18 at 0:40
  • $\begingroup$ sumk is convex, hence -sumk is concave and thus the difference is not convex. $\endgroup$ – Johan Löfberg Jul 24 '18 at 7:13
  • 1
    $\begingroup$ No, impossible. You can formulate it as a MILP though $\endgroup$ – Johan Löfberg Jul 25 '18 at 14:00
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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