Optimization Online


Generic properties for semialgebraic programs

Gue Myung LEE (gmlee***at***pknu.ac.kr)
Tien Son PHAM (sonpt***at***dlu.edu.vn)

Abstract: In this paper we study genericity for the following parameterized class of nonlinear programs: \begin{eqnarray*} \textrm{minimize } f_u(x) := f(x) - \langle u, x \rangle \quad \textrm{subject to } \quad x \in S, \end{eqnarray*} where $f \colon \mathbb{R}^n \rightarrow \mathbb{R}$ is a polynomial function and $S \subset \mathbb{R}^n$ is a closed semialgebraic set, which is not necessarily compact. Assume that the constraint set $S$ is regular. It is shown that there exists an open and dense semialgebraic set $\mathscr{U} \subset \mathbb{R}^n$ such that for any $\bar{u} \in \mathscr{U},$ if the corresponding function $f_{\bar{u}}$ is bounded from below on $S,$ then for all vectors $u \in \mathbb{R}^n,$ sufficiently close to $\bar{u},$ the problem $\min_{x \in S} f_u(x)$ has the following properties: the objective function $f_u$ is coercive on the constraint set $S,$ there is a unique optimal solution, lying on a unique active manifold, and for which the strong second-order sufficient conditions, the quadratic growth condition, and the global sharp minima hold. Further, the active manifold is constant, and the optimal solution and the optimal value function vary analytically under local perturbations of the objective function. As a consequence, for almost all polynomial optimization problems, we can find a natural sequence of computationally feasible semidefinite programs, whose solutions give rise to a sequence of points in $\mathbb{R}^n$ converging to the optimal solution of the original problem.

Keywords: Semialgebraic program, Sensitivity analysis, Genericity, Coercivity, Strong second-order sufficient conditions, Active constraints, Uniform quadratic growth, Uniform and global sharp minima

Category 1: Global Optimization

Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization )


Download: [PDF]

Entry Submitted: 06/09/2015
Entry Accepted: 06/12/2015
Entry Last Modified: 06/30/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society