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(.,.):

maximize: f({g(.),h(.,.)}) = sum_r sum__s max_c {g(r)h(c,r) m(k,c,s)}

subject to:

0<=g(c) for all c in {1,2,...,C}

0<=h(c,r) for all c,r in {1,2,...,C}

sum_c g(c) =1

sum_r h(r,c) = 1 for all r in {1,2,...,C}

m(k,c,s) is a function of the three variables, say:


g(c) is a pdf where c is a discrete random variable.

h(c,r) is a conditional pdf:

h(c,r) = p(c|r) 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?


asked 21 Sep '12, 19:32

aboo0ood's gravatar image

accept rate: 0%

edited 22 Sep '12, 16:19

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?

(22 Sep '12, 15:20) Brian Borchers

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].

(22 Sep '12, 16:14) aboo0ood

Roughly how big is $C$? Is it small (e.g. less than 10), or very large (e.g. in the thousands or even bigger?)

(22 Sep '12, 22:24) Brian Borchers

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.

(23 Sep '12, 06:12) aboo0ood

Your problem can be formulated as a 0-1 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 non-convex and non-smooth, so you shouldn't expect to be able to do much better than that. I'll try to write this up later today.

(23 Sep '12, 12:37) Brian Borchers

Thanks, I will be waiting for your reply.

(24 Sep '12, 16:20) aboo0ood
showing 5 of 6 show 1 more comments

This problem can be formulated as a 0-1 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 0-1 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


t(r,s) <= (1-y(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%20Borchers's gravatar image

Brian Borchers
accept rate: 21%

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

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 answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 21 Sep '12, 19:32

Seen: 4,120 times

Last updated: 02 Oct '12, 15:51

OR-Exchange! Your site for questions, answers, and announcements about operations research.