On saddle points in nonconvex semi-infinite programming

DOI10.1007/S10898-011-9753-7MaRDI QIDQ1928307zbMATH OpenOpenAlexFDO

Authors Ralf Werner, Francisco Guerra Vazquez, Jan-Joachim Rückmann

Publication date 3 January 2013

Published in Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10898-011-9753-7

(partial) \(p\)-power formulation duality extended Mangasarian Fromovitz constraint qualification (EMFCQ)extended strong second-order sufficient condition (ESSOSC)Lagrangian function linear independent constraint qualification local convexification local saddle point primal dual method reduction approach semi-infinite programming (SIP)strong second-order sufficient condition (SSOSC)

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Semi-infinite programming (90C34) Optimality conditions and duality in mathematical programming (90C46)

Review text

The Lagrangian of a nonconvex SIP (\(\min f(x) \) s.t. \(G(x,y)\geq 0\) for all \(y\in Y\), \(Y\) compact) w.r.t. the reduction approach is -- roughly spoken -- convexified by using the \(p\)-th power method of \textit{D. Li} and \textit{X. L. Sun} [J. Optimization Theory Appl. 104, No. 1, 109--120 (2000; Zbl 0960.90070)]. The main assumptions are the EMFCQ and the ESSOSC at the local solution \(\bar x\) of the SIP, and the SSOSC for each solution \(y\) of the lower level problem (LL(x): \(\min G(x,y)\) s.t. \(y\in Y\)). \(Y\) is given by a finite number of equality and inequality constraints with over all valid LICQ. The functions \(f\) and \(G\) have the not much restricted structure \(G(x,y):=g(x,y)-b(y)\), where \(g(x,y)\geq 0\), \(b(y)>0\) and \(f(x)\geq 0\) for each \(y\in Y\) and \(x\) in some neighborhood \(U(\bar x)\). Now the main steps of the tricky construction of the local saddle point property for the SIP: Each solution \(y^{B_j}\) of LL(x) with valid SSOSC defines a smooth function \(x\rightarrow y^{B_j}(x)\) over the reduced KKT-conditions with active inequalities (index set \(B_j\) arbitrary between the one of SSOSC and of KKT) as equalities by using the implicit function theorem. The corresponding Lagrangian \(L_p^B(x,\mu):=f(x)^p+\sum_{j=1}^s \mu_j(b(y^{B_j}(x))^p-g(x,y^{B_j}(x))^p) \) has a positively definite Hessian w.r.t. \(x\) at \(\bar x\) and hence is then convex in \(x\) in some neighborhood \(U(\bar x)\) for all KKT-multipliers \(\mu_j\) and for all sufficiently large \(p>0\) which yields a intermediate local saddle point statement for all possible \(L_p^B\). Now the existence theorem of \textit{M. Kojima} [in: Analysis and computation of fixed points, Proc. Symp., Univ. Wis. 1979, 93--138 (1980; Zbl 0478.90062)] for parametric behavior of local solutions of LL(x) and the resulting reduction approach of SIP with finite \(C^{1,1}\) constraints \(G(x,y^j(x))\geq 0\), \(j=1,\dots,s\), is used. Since by this theorem for each \(x\in U(\bar x)\) there is a corresponding \(B_j\) with \(y^j(x)=y^{B_j}(x)\), the local saddle point statement can be pointwisely extended to the \(p\)-th power Lagrangian \(L_p(x,\mu):=f(x)^p+\sum_{j=1}^s \mu_j(b(y^j(x))^p-g(x,y^j(x))^p)\) of the SIP. A similar local saddle point theorem, where the power of the objective is one, is given without proof. Examples of nonconvex SIP illustrate that the level sets of the \(p\)-th power Lagrangian are convex in both cases for \(p=3.1\) in a small neighborhood of a local solution. This methods give opportunities to apply primal dual methods for a broader class of nonconvex SIP.

Recommendations

Cites work

Cited in

(14)

This page was built for publication: On saddle points in nonconvex semi-infinite programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1928307)