Global infimum of strictly convex quadratic functions with bounded perturbations (Q604811): Difference between revisions

The aim of this paper is to minimize over some convex subset of \({\mathbb R}^n\) a function \(\tilde{f}\) obtained by perturbing a strictly convex quadratic function \(f(x)=x^TAx+b^Tx\) by a function \(p\) bounded by some positive number \(s\). The convexity of \(f\) is not completely lost by adding a bounded perturbation, since some trace remains in form of rough convexity of \(\tilde f.\) In Section 2 the notion of outer \(\gamma\)-convexity is introduced: \(\tilde f:D\to {\mathbb R}\) is said to be outer \(\gamma\)-convex (strictly) w.r.t. roughness degree \(\gamma>0\) if for all \(x_0,x_1\in D\) satisfying \(\|x_0-x_1\|>\gamma\) there is a closed subset \(\Lambda\subset [0,1]\) containing \(\{0,1\}\) such that \[ [x_0,x_1]\subset \{(1-\lambda)x_0+\lambda x_1|\lambda\in\Lambda\}+\overline{B}(0,\gamma/2) \] and \[ \forall \lambda\in\Lambda:\tilde{f}((1-\lambda)x_0+\lambda x_1)\leq (<) (1-\lambda)\tilde{f}(x_0)+\lambda \tilde{f}(x_1). \] Moreover, the notion of convexity modulus of \(f\) is recalled: \[ h_1(\gamma):=\inf_{x_0,x_1\in{\mathbb R}^n,\|x_0-x_1\|=\gamma}\left({1\over 2}(f(x_0)+f(x_1))-f\left({1\over 2}(x_0+x_1)\right)\right), \] where \(\gamma\in {\mathbb R}_+.\) For the function \(f\) previously defined, \(h_1(\gamma)={1\over 4}\lambda_{\min}\gamma^2, \) where \(\lambda_{\min}\) is the smallest eigenvalue of \(A.\) The (strict) outer \(\gamma\)-convexity of \(\tilde{f}\) for every \(\gamma (>) \geq \gamma^*=2(2s/\lambda_{\min})^{1/2}\) is proved using the convexity modulus \(h_1\) of \(f\). In Section 3 the sets of global infimizers and global minimizers of outer \(\gamma\)-convex functions are studied. In particular, the authors prove that a \(\gamma^*\)-local minimal solution of \(\tilde f\) is its global minimal solution, and the diameter of the set of global infimizers of \(\tilde{f}\) is less than or equal to \(\gamma^*\). In addition, they show that \(\gamma^*/2\) is a sharp upper bound of the distance between a global infimizer of \(\tilde{f}\) and the unique global minimizer of \(f\) (if any). Section 4 is devoted to the study of roughly generalized support properties; moreover, the authors prove two optimality conditions for the optimization problem with objective \(\tilde{f}\) over a set \(D\) obtained by intersecting a finite number of hyperplanes.