8
$\begingroup$

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()
$\endgroup$
  • 1
    $\begingroup$ What are DCP rules? What have you tried and where is the problem arising? Maybe I'm just not knowledgable about the topic you're asking about but I can't tell exactly what you're asking. (See or.meta.stackexchange.com/a/111/38.) $\endgroup$ – LarrySnyder610 Jul 11 '19 at 23:56
  • 1
    $\begingroup$ @LarrySnyder61 . Not defending the way the question is written, but look up DCP on or.stackexchange.com/questions/865/… , (DCP is one I added) then google it. $\endgroup$ – Mark L. Stone Jul 12 '19 at 0:00
  • 1
    $\begingroup$ I just added MIDCP to "What are common abbreviations in Operations Research?" or.stackexchange.com/questions/865/… . MIDCP is a program which follows DCP rules, except that one or more optimization (decision) variables are declared to be binary or integer. I.e., an MIDCP program is a program whose continuous relaxation is DCP. $\endgroup$ – Mark L. Stone Jul 12 '19 at 0:47
  • 1
    $\begingroup$ For anyone thinking about using DCP (using CVX, CVXPY, CVXR), I recommend you read ask.cvxr.com/t/why-isnt-cvx-accepting-my-model-read-this-first/… . It can be very convenient and powerful when it applies, but it does not apply to all convex optimization problems, let alone to all optimization problems. $\endgroup$ – Mark L. Stone Jul 12 '19 at 0:51
8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ thank you!! I was hoping there would be an easier way, but I may just have to find a different way to reformulate my problem. I'll be sure to post once I find a way. $\endgroup$ – David Jul 12 '19 at 0:38

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.