1
$\begingroup$

I have a problem, for predefined $x_0,z\in\mathbb{R}$, which looks like $$\min_{\alpha,x} \sum_{i=1}^n \alpha_i f_i(x_i,z) $$ subject to \begin{align} \sum_{i=1}^n \alpha_i &= 1 \\ \sum_{i=1}^n \alpha_i x_i &= x_0 \\ 0 \le \alpha_i, x_i &\le 1, \quad\forall i=1,\dotsc,n. \end{align} We don't know much useful about the $f$ functions, other than that they are continuous and bounded below. They are certainly nonlinear and nonconvex. They are defined by a large set of input data which are fixed for the problem. This problem is solved for local minima, and we have heuristics for finding a supposed global minimum (by sampling the space pseudo-randomly).

There is always one $f_k$ which as $z$ increases takes a lower value than all other $f_i$. So for sufficiently large $z$ the solution is always $a_k=1$, $x_k=x_0$, and all other $\alpha_i=0$, with other $x_i$ values irrelevant. We always know what $k$ is for a given set of input data defining the $f_i$.

What I want to do now is find that critical minimum value of $z$ above which $\alpha_k=1$. The problem would look like $$\min_z z$$ subect to \begin{align} f_k(x_0,z) &\le \min_{\alpha,x} \sum_{i=1}^n \alpha_i f_i(x_i,z) \\ \sum_{i=1}^n \alpha_i &= 1 \\ \sum_{i=1}^n \alpha_i x_i &= x_0 \\ 0 \le \alpha_i, x_i &\le 1, \quad\forall i=1,\dotsc,n. \end{align}

My question is

What is this kind of problem called?

I am trying to do a literature search and not having much success. "Optimization constrained optimization problem", or "problem with optimization constraint," might be my intuitive guess at a name.

In addition to a searchable name for the type of problem this is, if you have pointers to literature on methods of solution, or descriptions of those methods, that's even better.

$\endgroup$
4
  • $\begingroup$ In the last two problems, are $x_i,\alpha_i$'s constants or variables? $\endgroup$ May 9, 2014 at 15:32
  • $\begingroup$ They are variables in the "constraint problem". $\endgroup$ May 9, 2014 at 15:39
  • $\begingroup$ There is something funny about your setup: for a fixed $z$ and $x_0$ you are just looking for the bottom point of a convex polygon with vertices in $n$ fixed sets $S_j=\{(x,f_j(x,z)):x\in[0,1]\}$ on the vertical line $x=x_0$. However, it is pretty obvious from the geometric considerations that the bottom point is always a linear combination of just two vertices. Of course, the way you pose the problem is formally correct as is, but it looks somewhat strange to me that you don't mention this possibly quite useful fact. $\endgroup$
    – fedja
    May 9, 2014 at 20:07
  • $\begingroup$ @fedja, absolutely correct, in the 1-D case. In general we expand to $N$ arbitrary dimensions so have the convex combination of $N$ functions. As $z$ changes the $N$ involved functions change. All this seems a detail -- more important to me is a way to categorize the problem so I can find literature on the subject. $\endgroup$ May 10, 2014 at 0:59

1 Answer 1

0
$\begingroup$

Have a look at bilevel programming. In general such a problem cannot be readily solved, despite it being quite wide spread. Your best options are reformulating it as one NLP problem, or making your own branch and bound assuming you have some integers. At least those are the two options I'm aware of, but I would love to hear more suggestions, as I have similar problems.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .