We are given the following optimization problem: $$argmax_{x\in \mathbb{R}^n} f(x)$$such that $$g_i(x) \le \pi_i, \ i=1,\ldots, k$$ where $f$ is a real concave function, $g_i\colon \mathbb{R}^n\to \mathbb{R}$ are the functions defining the constraints of the optimization, and $\pi=(\pi_1,\ldots, \pi_k)$ is a vector in $\mathbb{R}^k$ defining the upper bounds of the constraints. We can assume all functions to be at least $C^2$. Let $x^*$ be an optimal solution for the problem above. Define $\Omega$ to be the set: $$\Omega=\left\{\eta\in\mathbb{R}^k \vert ||\eta-\pi||\le L \right\},\ L>0$$ I'm interested in finding the vector in $\Omega$ that yields the highest objective value. That is to say, we are free to vary the bounds of the constraints within a certain ball defined by the norm $||\cdot||$, in order to improve the quality of the solution $x^*$. In formulae, we want to find: $$\eta^* = argmax_{\eta\in\Omega}\left\{\max_x f(x)| g_i(x)\le \eta_i\right\}$$
Ideally, I'd like to do this through Lagrange multipliers, through an iterative fashion: one starts by computing Lagrange multipliers at $x^*$, then uses them to ''move'' the bounds by relaxing a bit the constraint indicated by the multiplier which is the biggest in norm. The move would clearly be an approximation of an infinitesimal increment, since unfortunately this algorithm should be actually implementable. Now compute the new Lagrange multipliers and repeat. This way we should be moving through the ball $\Omega$, and eventually converge to $\eta^*$. My questions are basically two:
- does my proposed solution make sense at all?
- is there a way to reach the solution in a non-iterative approach, or at least through a finite number of iterations?
Regarding the second question, what I'm afraid of is that by moving at each stage along the direction which is locally the most favourable, one risks to go along paths which are much longer than what one could do if they knew the globally optimal direction in advance.
Any help would be greatly appreciated.
Thanks!
I believe the simplest method would be to solve the following problem using your favorite method: $$ \begin{aligned} \max_{x, \eta} &\quad f(x)\\ \text{s.t.} &\quad g_i(x) \leq \eta_i \\ &\quad \| \eta - \pi \| \leq L \end{aligned} $$
If all $g_i$ are convex, the problem above is also convex.