CONTEXT: Suppose you have the nonlinear program $$ \begin{aligned} &\min f(x)\\ \text{subject to: }\quad & h_1(x) = 0 \\ &\quad\quad\vdots\\ &h_m(x) = 0 \end{aligned} $$ where $x\in\mathbb{R}^n$, $f,h_1,\dots,h_m:\mathbb{R}^n\to\mathbb{R}$. Degeneracy occurs when there are "nonregular/irregular" points $x$ which comply $h_i(x)=0, i=1,\dots,m$ and $$ \{\nabla h_1(x),\dots,\nabla h_m(x)\} $$ are linearly dependent. The problem is that typical Lagrange multiplier conditions apply only to points which are regular. So if the global optimum of the nonlinear program corresponds to a nonregular point, it may be hard to find: you have to come up with a tailor-made method to find nonregular points, which is hard in general.

In linear programming, with linear constraints, degeneracy can be detected directly (apparently there are well known results for this in the simplex literature). I've seen that in this case some people (e.g. here) use a different program constructed from the original, by perturbing a little bit the constraints, such to avoid degeneracy. Moreover, they can show formally that the perturbed program is non-degenerate.

Question I was wondering if this can be done in general: if you could perturb the constraints of the nonlinear program using small random noise in order to make sure that the global optimum is regular. If it can't be done in general, do you know other special cases? Take the following example in which I'm particularly interested:

Example: I'm particularly interested quadratic functions: $f(x)=x^TP_0x$ and constraints of the form $h_i(x)=x^TP_ix-1$ with $P_i$ distinct positive definite matrices (constraints define intersection of ellipses). Do you think that adding a disturbance $P_i\leftarrow P_i+\varepsilon_i$ with $\varepsilon_i$ a random matrix with components uniformly distributed in $[-\epsilon,\epsilon]$ could result in the global optimum to be regular (almost surely)?


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.