How can I convexify the max min constraint?

(Dipak Narayanan) #1

I have an objective function given by

\underset{a_{c,i}}{\max}\hspace{1mm}\underset{i,i=1,\cdots,M}{\min}\hspace{1mm}\frac{s_i(a_{c,i})}{d_i}

c=1,2,\cdots,N, i=1,2,\cdots,M

s_i=\sum_{c=1}^Na_{c,i}f_{c,i} with 0\le a_{c,i}\le1

where, f_{c,i}\ge0 (are known)

What can we say about the convexity of this objective function

d_i's are >0 and s_i(a_{c,i})>0

Are \max \min optimization objective nonlinear/nonconvex?

If so, how can I linearize/convexify it?

          maximize(min(s./d))

does the job I want. But, however, I am more into the cnvexity issue.

(Mark L. Stone) #2

CVX wouldn’t accept it if weren’t a convex problem.

s_i is an affine function of a_{c,i}, and so is s_i/d. The min of that is concave, so maximizing that min is convex.