Hello, I am trying to solve a constrained nonlinear optimization problem, in which the objective function uses the max operator. Given a constant k, I want to maximize a function f with respect to the functions g(.) and h(.,.):
m(k,c,s) is a function of the three variables, say: m(k,c,s)=kcs; g(c) is a pdf where c is a discrete random variable. h(c,r) is a conditional pdf: h(c,r) = p(cr) where r,s are discrete random variables. C is some positive integer. k is a fixed real number in [0,1]. If it weren't for the maximum operator inside the objective function, I would be able to solve the problem using the KKT conditions. But with the maximum operator showing that way, I am not able to differentiate the objective function. Are there tricks or techniques I could use to overcome this problem? Thanks. asked 21 Sep '12, 19:32 aboo0ood
showing 5 of 6
show 1 more comments

This problem can be formulated as a 01 mixed integer nonlinear programming problem. First, note that the function g can be represented by a vector indexed by r and the function h can be represented by a matrix of variables, indexed by c and r. Introduce additional variables t(r,s) where t(r,s) is the maximum over c of g(r)h(c,r)m(k,s,c). Then the problem is max sum_r sum_s t(r,s) The hard part of formulating this problem is dealing with the inner maximization. Introduce additional 01 variables y(r,s,c), where sum_c y(r,s,c) = 1 Then add constraints t(r,s) >= g(r)h(c,r)m(k,s,c) for all r,s,c and t(r,s) <= (1y(r,s,c))M+y(r,s,c)g(r)h(c,r)m(k,s,c) for all r,s,c where M is a very large constant (picked to be larger than any possible value of g(r)h(c,r)m(k,s,c). These constraints force t(r,s) to be equal to the maximum over c of g(r)h(c,r)m(k,s,c). The resulting MINLP can be solved by branch and bound for reasonably small values of $C$. Unfortunately, the number of binary variables grows as C^3, so this will be impractical for anything other than small values of C. answered 25 Sep '12, 09:15 Brian Borchers Thanks! I wonder if the reformulation can be solved using an optimization software without specifying the constant k, i.e. I want to obtain results as a function of k.
(29 Sep '12, 21:10)
aboo0ood
Your objective (with m(k,c,s)=kcs) is linear in k, so you can just factor it out of the objective function.
(29 Sep '12, 22:27)
Brian Borchers
That is true for the objective function above, but what if m(k,c,s) is more complicated such that the constant cannot be factored out? Do optimization software have the capability of solving such problems for a general k without specifying its value? Are there software which can provide answers as functions of the constant, rather than a point (in case of specifying k).
(01 Oct '12, 18:00)
aboo0ood
1
For that more general objective, you'll have to reoptimize for each new value of k. There's nothing useful that can be said about the optimal value of a nonparametric MINLP like that.
(02 Oct '12, 15:51)
Brian Borchers

Your problem statement is somewhat unclear.
Could you be more specific about the set of values that $c$ takes on when you refer to for all $c$? Similarly for $r$ and $s$? Are these finite sets in each case? If they are finite, how big are they? Are they countably infinite sets? Intervals on $R$?
You also haven't been clear about what you're optimizing over and what's fixed. Is it the case that $m(k,c,s)$ is fixed and you're trying maximize over all possible functions $g$ and $h$ that satisfy the constraints?
The discrete random variables r,c and s take values belonging to the finite set {1,2,...,C}, where C is some positive integer.
Yes, I want to maximize over all possible functions g(.) and h(.,.) while m(k,c,s) is fixed. k is a fixed real number in the interval [0,1].
Roughly how big is $C$? Is it small (e.g. less than 10), or very large (e.g. in the thousands or even bigger?)
I would rather solve the problem without specifying C. It could be as small as 2 or arbitrarily finitely large. However, if a solution is only possible for small C that does not involve enumerating all possible outcomes of the maximum operator, I would want to hear it.
Your problem can be formulated as a 01 mixed integer nonlinear programming problem, but it's likely to be difficult to solve this in practice unless C is quite small. The problem is inherently nonconvex and nonsmooth, so you shouldn't expect to be able to do much better than that. I'll try to write this up later today.
Thanks, I will be waiting for your reply.