Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
How can I reformat the problem below to follow DCP rules?
DCP rules are Disciplined Convex Programming Rules that allow convex programs to be solved. DCP
Is there a way to reformat the problem below so that I can solve it with any solver?
I'm trying to maximize (or minimize) $x\cdot\min x$ where $x$ is an array.
import cvxpy as cp
x = cp.Variable(10)
objective = cp.Maximize(cp.sum(x*cp.min(x)))
constraints = [x >=0, x<=10]
prob = cp.Problem(objective, constraints)
result = prob.solve()
See https://dcp.stanford.edu/ for an explanation of Disciplined Convex Programming (DCP)
As for your problem. First consider the case in which the dimension of x is 1. Then the objective is x^2, which is convex, and therefore maximizing it is a non-convex problem, which therefore can not be modeled by DCP. That objective could be minimized however if entered as x^2.
When the dimension of x is greater than 1, sum(x)*min(x) is neither convex nor concave, so neither minimizing nor maximizing it is a convex optimization problem. Therefore, this can not be handled by Disciplined Convex Programming. (DCP).
The one remaining question is whether this problem can be handled by MIDCP - Mixed-Integer DCP. The answer is yes, presuming an ungainly approximation is used. First of all, replace min(x) with the scalar continuous variable y, and add a number of binaries equal to the dimension of x, and Big M constraints, per the last portion of section 2.2 of FICO MIP formulations and linearizations Quick reference. That results in an objective of sum(x)*y, which can not be handled by DCP. The only way to handle that in MIDCP is to use approximate binary-encoded expansions of both sum(x) and y, which turns sum(x)*y into a sum of products of binary variables, each of which can be linearized as shown in section 2.8 of that linked reference. The resulting objective function is linear, as are all constraints (other than binary "constraint"), and therefore this objective can be either maximized or minimized in accordance with MIDCP. That is a horrible mess, which can be implemented in CVXPY and CVX, but I recommend you don't try, except for educational purposes.
