The constrained optimization problem that I am struggling with is the following: \begin{equation} \begin{aligned} &\underset{x\in[0,1],y\in[0,1]}{\max}~F(x,y)\triangleq xA(x,y)+yB(x,y)\\ &\mbox{s.t. }~A(x,y)\leq K,~B(x,y)\leq K, \end{aligned} \end{equation} where $K>0$ and \begin{align*} &A(x,y)=\begin{cases} \displaystyle 1-x-(1-\alpha)c_0/2,~&\mbox{if }x-y<-c_0\\ \displaystyle \alpha(1-x)+\frac{1-\alpha}{c_0}(y-x)[1-(x+y)/2],~&\mbox{if }-c_0\leq x-y<0\\ \displaystyle\alpha[1-(x-y)/c_0](1-x),~&\mbox{if }0\leq x-y\leq c_0\\ \displaystyle 0,~&\mbox{if }x-y>c_0 \end{cases}\\ &B(x,y)=\begin{cases} \displaystyle 0,~&\mbox{if }x-y<-c_0\\ \displaystyle (1-\alpha)[1-(y-x)/c_0](1-y),~&\mbox{if }-c_0\leq x-y<0\\ \displaystyle(1-\alpha)(1-y)+\frac{\alpha}{c_0}(x-y)[1-(x+y)/2],~&\mbox{if }0\leq x-y\leq c_0\\ \displaystyle 1-y-\alpha c_0/2,~&\mbox{if }x-y>c_0 \end{cases}, \end{align*} where $c_0\in(0,1),~\alpha\in(0,1)$.

I numerically find that the optimal solution to the unconstrained optimization problem is $(x,y)=(0.5,0.5)$ and the 3D surface of $F(x,y)$ is the following

enter image description here

My current strategy is: for each region of $(x,y)$, I try to solve the optimization problem that is parameterized by $K$ and hope that once I solve all the 4 big cases, then I choose the maximum out of these four cases. But I quickly found that within each big case, there are many small cases. Also, the 2nd case was not easy to solve. I wonder if there is a better way to attach this problem. It seems that when $K\geq 1/2\max\{\alpha, (1-\alpha)\}$, then the constraints are inactive, and hence the optimal solution is $(0.5,0.5)$. But I don't know what happens when $K<\max\{\alpha, (1-\alpha)\}$, in which case, I guess one of the constraints should be binding.

  • 1
    $\begingroup$ I edited the tags for accuracy. In particular, constraint-programming actually refers to a certain class of combinatorial/logical problems, and not simply optimization problems with constraints. And this is definitely not a convex problem. $\endgroup$ – Michael Grant Apr 5 '18 at 1:22
  • $\begingroup$ @MichaelGrant Thanks! But I think the objective function $F(x,y)$ is concave, isn't it? The feasible region I guess it is not convex though... $\endgroup$ – KevinKim Apr 5 '18 at 1:25
  • $\begingroup$ Your graph certainly suggests it is not concave; visually, it seems to have saddle points. In some regions it is the sum of bilinear functions, which is neither convex nor concave. $\endgroup$ – Michael Grant Apr 5 '18 at 1:26

Your Answer

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

Browse other questions tagged or ask your own question.