Interior-point methods for nonconvex nonlinear programming: cubic regularization

In this paper, we present a primal-dual interior-point method for solving nonlinear programming problems. It employs a Levenberg-Marquardt (LM) perturbation to the Karush-Kuhn-Tucker (KKT) matrix to handle indefinite Hessians and a line search to obtain sufficient descent at each iteration. We show that the LM perturbation is equivalent to replacing the Newton step by a cubic regularization step with an appropriately chosen regularization parameter. This equivalence allows us to use the favorable theoretical results of Griewank (The modification of Newton’s method for unconstrained optimization by bounding cubic terms, 1981), Nesterov and Polyak (Math. Program., Ser. A 108:177–205, 2006), Cartis et al. (Math. Program., Ser. A 127:245–295, 2011; Math. Program., Ser. A 130:295–319, 2011), but its application at every iteration of the algorithm, as proposed by these papers, is computationally expensive. We propose a hybrid method: use a Newton direction with a line search on iterations with positive definite Hessians and a cubic step, found using a sufficiently large LM perturbation to guarantee a steplength of 1, otherwise. Numerical results are provided on a large library of problems to illustrate the robustness and efficiency of the proposed approach on both unconstrained and constrained problems.     

On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets

In the paper we prove that any nonconvex quadratic problem over some set ${K\subset \mathbb {R}^n}$ with additional linear and binary constraints can be rewritten as a linear problem over the cone, dual to the cone of K-semidefinite matrices. We show that when K is defined by one quadratic constraint or by one concave quadratic constraint and one linear inequality, then the resulting K-semidefinite problem is actually a semidefinite programming problem. This generalizes results obtained by Sturm and Zhang (Math Oper Res 28:246–267, 2003). Our result also generalizes the well-known completely positive representation result from Burer (Math Program 120:479–495, 2009), which is actually a special instance of our result with ${K=\mathbb{R}^n_{+}}$ .     

Tangential extremal principles for finite and infinite systems of sets II: applications to semi-infinite and multiobjective optimization

This paper contains selected applications of the new tangential extremal principles and related results developed in Mordukhovich and Phan (Math Program 2011) to calculus rules for infinite intersections of sets and optimality conditions for problems of semi-infinite programming and multiobjective optimization with countable constraints.     

General two-function topological minimax theorems

Using the level set method of Joó (Acta Math Hung 54(1–2):163–172, 1989), a general two-function topological minimax theorem are proved. The theorem improves and generalizes the known results shown by Cheng and Lin (Acta Math Hung 73(1–2):65–69, 1996), Lin and Cheng (Acta Math Hung 100(3):177–186, 2003), and Frenk and Kassay (Math Program Ser A 105(1):145–155, 2006).     

The triangle closure is a polyhedron

Recently, cutting planes derived from maximal lattice-free convex sets have been studied intensively by the integer programming community. An important question in this research area has been to decide whether the closures associated with certain families of lattice-free sets are polyhedra. For a long time, the only result known was the celebrated theorem of Cook, Kannan and Schrijver who showed that the split closure is a polyhedron. Although some fairly general results were obtained by Andersen et al. (Math Oper Res 35(1):233–256, 2010) and Averkov (Discret Optimiz 9(4):209–215, 2012), some basic questions have remained unresolved. For example, maximal lattice-free triangles are the natural family to study beyond the family of splits and it has been a standing open problem to decide whether the triangle closure is a polyhedron. In this paper, we show that when the number of integer variables $m=2$ the triangle closure is indeed a polyhedron and its number of facets can be bounded by a polynomial in the size of the input data. The techniques of this proof are also used to give a refinement of necessary conditions for valid inequalities being facet-defining due to Cornuéjols and Margot (Math Program 120:429–456, 2009) and obtain polynomial complexity results about the mixed integer hull.     

On the Gauss–Newton method

We provide a new semilocal convergence analysis of the Gauss–Newton method (GNM) for solving nonlinear equation in the Euclidean space. Using a combination of center-Lipschitz, Lipschitz conditions, and our new idea of recurrent functions, we provide under the same or weaker hypotheses than before (Ben-Israel, J. Math. Anal. Appl. 15:243–252, 1966; Chen and Nashed, Numer. Math. 66:235–257, 1993; Deuflhard and Heindl, SIAM J. Numer. Anal. 16:1–10, 1979; Guo, J. Comput. Math. 25:231–242, 2007; Häußler, Numer. Math. 48:119–125, 1986; Hu et al., J. Comput. Appl. Math. 219:110–122, 2008; Kantorovich and Akilov, Functional Analysis in Normed Spaces, Pergamon, Oxford, 1982), a finer convergence analysis. The results can be extended in case outer or generalized inverses are used. Numerical examples are also provided to show that our results apply, where others fail (Ben-Israel, J. Math. Anal. Appl. 15:243–252, 1966; Chen and Nashed, Numer. Math. 66:235–257, 1993; Deuflhard and Heindl, SIAM J. Numer. Anal. 16:1–10, 1979; Guo, J. Comput. Math. 25:231–242, 2007; Häußler, Numer. Math. 48:119–125, 1986; Hu et al., J. Comput. Appl. Math. 219:110–122, 2008; Kantorovich and Akilov, Functional Analysis in Normed Spaces, Pergamon, Oxford, 1982).     

A computational study of a solver system for processing two-stage stochastic LPs with enhanced Benders decomposition

We report a computational study of two-stage SP models on a large set of benchmark problems and consider the following methods: (i) Solution of the deterministic equivalent problem by the simplex method and an interior point method, (ii) Benders decomposition (L-shaped method with aggregated cuts), (iii) Regularised decomposition of Ruszczy??ski (Math Program 35:309?C333, 1986), (iv) Benders decomposition with regularization of the expected recourse by the level method (Lemaréchal et al. in Math Program 69:111?C147, 1995), (v) Trust region (regularisation) method of Linderoth and Wright (Comput Optim Appl 24:207?C250, 2003). In this study the three regularisation methods have been introduced within the computational structure of Benders decomposition. Thus second-stage infeasibility is controlled in the traditional manner, by imposing feasibility cuts. This approach allows extensions of the regularisation to feasibility issues, as in Fábián and Sz?ke (Comput Manag Sci 4:313?C353, 2007). We report computational results for a wide range of benchmark problems from the POSTS and SLPTESTSET collections and a collection of difficult test problems compiled by us. Finally the scale-up properties and the performance profiles of the methods are presented.     

Some constraint qualifications for quasiconvex vector-valued systems

In this paper, we consider minimization problems with a quasiconvex vector-valued inequality constraint. We propose two constraint qualifications, the closed cone constraint qualification for vector-valued quasiconvex programming (the VQ-CCCQ) and the basic constraint qualification for vector-valued quasiconvex programming (the VQ-BCQ). Based on previous results by Benoist et al. (Proc Am Math Soc 13:1109–1113, 2002), and Suzuki and Kuroiwa (J Optim Theory Appl 149:554–563, 2011), and (Nonlinear Anal 74:1279–1285, 2011), we show that the VQ-CCCQ (resp. the VQ-BCQ) is the weakest constraint qualification for Lagrangian-type strong (resp. min–max) duality. As consequences of the main results, we study semi-definite quasiconvex programming problems in our scheme, and we observe the weakest constraint qualifications for Lagrangian-type strong and min–max dualities. Finally, we summarize the characterizations of the weakest constraint qualifications for convex and quasiconvex programming.     

Optimal Transport, Convection, Magnetic Relaxation and Generalized Boussinesq Equations

We establish a connection between optimal transport theory (see Villani in Topics in optimal transportation. Graduate studies in mathematics, vol. 58, AMS, Providence, 2003, for instance) and classical convection theory for geophysical flows (Pedlosky, in Geophysical fluid dynamics, Springer, New York, 1979). Our starting point is the model designed few years ago by Angenent, Haker, and Tannenbaum (SIAM J. Math. Anal. 35:61–97, 2003) to solve some optimal transport problems. This model can be seen as a generalization of the Darcy–Boussinesq equations, which is a degenerate version of the Navier–Stokes–Boussinesq (NSB) equations. In a unified framework, we relate different variants of the NSB equations (in particular what we call the generalized hydrostatic-Boussinesq equations) to various models involving optimal transport (and the related Monge–Ampère equation, Brenier in Commun. Pure Appl. Math. 64:375–417, 1991; Caffarelli in Commun. Pure Appl. Math. 45:1141–1151, 1992). This includes the 2D semi-geostrophic equations (Hoskins in Annual review of fluid mechanics, vol. 14, pp. 131–151, Palo Alto, 1982; Cullen et al. in SIAM J. Appl. Math. 51:20–31, 1991, Arch. Ration. Mech. Anal. 185:341–363, 2007; Benamou and Brenier in SIAM J. Appl. Math. 58:1450–1461, 1998; Loeper in SIAM J. Math. Anal. 38:795–823, 2006) and some fully nonlinear versions of the so-called high-field limit of the Vlasov–Poisson system (Nieto et al. in Arch. Ration. Mech. Anal. 158:29–59, 2001) and of the Keller–Segel for Chemotaxis (Keller and Segel in J. Theor. Biol. 30:225–234, 1971; Jäger and Luckhaus in Trans. Am. Math. Soc. 329:819–824, 1992; Chalub et al. in Mon. Math. 142:123–141, 2004). Mathematically speaking, we establish some existence theorems for local smooth, global smooth or global weak solutions of the different models. We also justify that the inertia terms can be rigorously neglected under appropriate scaling assumptions in the generalized Navier–Stokes–Boussinesq equations. Finally, we show how a “stringy” generalization of the AHT model can be related to the magnetic relaxation model studied by Arnold and Moffatt to obtain stationary solutions of the Euler equations with prescribed topology (see Arnold and Khesin in Topological methods in hydrodynamics. Applied mathematical sciences, vol. 125, Springer, Berlin, 1998; Moffatt in J. Fluid Mech. 159:359–378, 1985, Topological aspects of the dynamics of fluids and plasmas. NATO adv. sci. inst. ser. E, appl. sci., vol. 218, Kluwer, Dordrecht, 1992; Schonbek in Theory of the Navier–Stokes equations, Ser. adv. math. appl. sci., vol. 47, pp. 179–184, World Sci., Singapore, 1998; Vladimirov et al. in J. Fluid Mech. 390:127–150, 1999; Nishiyama in Bull. Inst. Math. Acad. Sin. (N.S.) 2:139–154, 2007).     

Graver basis and proximity techniques for block-structured separable convex integer minimization problems

We consider $N$ -fold $4$ -block decomposable integer programs, which simultaneously generalize $N$ -fold integer programs and two-stage stochastic integer programs with $N$ scenarios. In previous work (Hemmecke et al. in Integer programming and combinatorial optimization. Springer, Berlin, 2010), it was proved that for fixed blocks but variable  $N$ , these integer programs are polynomial-time solvable for any linear objective. We extend this result to the minimization of separable convex objective functions. Our algorithm combines Graver basis techniques with a proximity result (Hochbaum and Shanthikumar in J. ACM 37:843–862,1990), which allows us to use convex continuous optimization as a subroutine.     

The convergence of a modified smoothing-type algorithm for the symmetric cone complementarity problem

The symmetric cone complementarity problem (denoted by SCCP) is a broad class of optimization problems, which contains the semidefinite complementarity problem, the second-order cone complementarity problem, and the nonlinear complementarity problem. In this paper we first extend the smoothing function proposed by Huang et al. (Sci. China 44:1107–1114, 2001) for the nonlinear complementarity problem to the context of symmetric cones and show that it is coercive under suitable assumptions. Based on this smoothing function, a smoothing-type algorithm, which is a modified version of the Qi-Sun-Zhou method (Qi et al. in Math. Program. 87:1–35, 2000), is proposed for solving the SCCP. By using the theory of Euclidean Jordan algebras, we prove that the proposed algorithm is globally and locally quadratically convergent under suitable assumptions. Preliminary numerical results for some second-order cone complementarity problems are reported which indicate that the proposed algorithm is effective.     

General convergence conditions of Newton’s method for m-Fréchet differentiable operators

We present a local as well as a semilocal convergence analysis for Newton’s method for approximating a locally unique solution of a nonlinear equation in a Banach space setting. Our hypotheses involve m-Fréchet-differentiable operators and general Lipschitz-type hypotheses, where m≥2 is a positive integer. The new convergence analysis unifies earlier results; it is more flexible and provides a finer convergence analysis than in earlier studies such as Argyros in J. Comput. Appl. Math. 131:149–159, 2001, Argyros and Hilout in J. Appl. Math. Comput. 29:391–400, 2009, Argyros and Hilout in J. Complex. 28:364–387, 2012, Argyros et al. Numerical Methods for Equations and Its Applications, CRC Press/Taylor & Francis, New York, 2012, Gutiérrez in J. Comput. Appl. Math. 79:131–145, 1997, Ren and Argyros in Appl. Math. Comput. 217:612–621, 2010, Traub and Wozniakowski in J. Assoc. Comput. Mech. 26:250–258, 1979. Numerical examples are presented further validating the theoretical results.     

An iterative algorithm for common fixed points for nonexpansive semigroups and strictly pseudo-contractive mappings with optimization problems

In this paper, we introduce an iterative algorithm for finding a common element of the set of solutions of a system of mixed equilibrium problems, the set of solutions of a variational inclusion problems for inverse strongly monotone mappings, the set of common fixed points for nonexpansive semigroups and the set of common fixed points for an infinite family of strictly pseudo-contractive mappings in Hilbert spaces. Furthermore, we prove a strong convergence theorem of the iterative sequence generated by the proposed iterative algorithm under some suitable conditions which solves some optimization problems. Our results extend and improve the recent results of Chang et al. (Appl Math Comput 216:51–60, 2010), Hao (Appl Math Comput 217(7):3000–3010, 2010), Jaiboon and Kumam (Nonlinear Anal 73:1180–1202, 2010) and many others.     

Counterexamples to a triality theorem for quadratic-exponential minimization problems

The main goal of this note is to give a counterexample to the Triality Theorem in Gao and Ruan (Math Methods Oper Res 67:479–491, 2008). This is done first by considering a more general optimization problem with the aim to encompass several examples from Gao and Ruan (Math Methods Oper Res 67:479–491, 2008) and other papers by Gao and his collaborators (see f.i. Gao Duality principles in nonconvex systems. Theory, methods and applications. Kluwer, Dordrecht, 2000; Gao and Sherali Advances in applied mathematics and global optimization. Springer, Berlin, 2009). We perform a thorough analysis of the general optimization problem in terms of local extrema while presenting several counterexamples.     

The strong convergence of a three-step algorithm for the split feasibility problem

Based on the very recent work by Dang and Gao (Invers Probl 27:1–9, 2011) and Wang and Xu (J Inequal Appl, doi:10.1155/2010/102085, 2010), and inspired by Yao (Appl Math Comput 186:1551–1558, 2007), Noor (J Math Anal Appl 251:217–229, 2000), and Xu (Invers Probl 22:2021–2034, 2006), we suggest a three-step KM-CQ-like method for solving the split common fixed-point problems in Hilbert spaces. Our results improve and develop previously discussed feasibility problem and related algorithms.     

Sample approximation technique for mixed-integer stochastic programming problems with expected value constraints

This paper deals with the theory of sample approximation techniques applied to stochastic programming problems with expected value constraints. We extend the results of Branda (Optimization 61(8):949–968, 2012c) and Wang and Ahmed (Oper Res Lett 36:515–519, 2008) on the rates of convergence to the problems with a mixed-integer bounded set of feasible solutions and several expected value constraints. Moreover, we enable non-iid sampling and consider Hölder-calmness of the constraints. We derive estimates on the sample size necessary to get a feasible solution or a lower bound on the optimal value of the original problem using the sample approximation. We present an application of the estimates to an investment problem with the Conditional Value at Risk constraints, integer allocations and transaction costs.     

Directional Lipschitzness of Minimal Time Functions in Hausdorff Topological Vector Spaces

In a general Hausdorff topological vector space E, we associate to a given nonempty closed set S???E and a bounded closed set Ω???E, the minimal time function T _S,Ω defined by $T_{S,\Omega}(x):= \inf \{ t> 0: S\cap (x+t\Omega)\not = \emptyset\}$ . The study of this function has been the subject of various recent works (see Bounkhel (2012, submitted, 2013, accepted); Colombo and Wolenski (J Global Optim 28:269–282, 2004, J Convex Anal 11:335–361, 2004); He and Ng (J Math Anal Appl 321:896–910, 2006); Jiang and He (J Math Anal Appl 358:410–418, 2009); Mordukhovich and Nam (J Global Optim 46(4):615–633, 2010) and the references therein). The main objective of this work is in this vein. We characterize, for a given Ω, the class of all closed sets S in E for which T _S,Ω is directionally Lipschitz in the sense of Rockafellar (Proc Lond Math Soc 39:331–355, 1979). Those sets S are called Ω-epi-Lipschitz. This class of sets covers three important classes of sets: epi-Lipschitz sets introduced in Rockafellar (Proc Lond Math Soc 39:331–355, 1979), compactly epi-Lipschitz sets introduced in Borwein and Strojwas (Part I: Theory, Canad J Math No. 2:431–452, 1986), and K-directional Lipschitz sets introduced recently in Correa et al. (SIAM J Optim 20(4):1766–1785, 2010). Various characterizations of this class have been established. In particular, we characterize the Ω-epi-Lipschitz sets by the nonemptiness of a new tangent cone, called Ω-hypertangent cone. As for epi-Lipschitz sets in Rockafellar (Canad J Math 39:257–280, 1980) we characterize the new class of Ω-epi-Lipschitz sets with the help of other cones. The spacial case of closed convex sets is also studied. Our main results extend various existing results proved in Borwein et al. (J Convex Anal 7:375–393, 2000), Correa et al. (SIAM J Optim 20(4):1766–1785, 2010) from Banach spaces and normed spaces to Hausdorff topological vector spaces.     

On Ulm’s method for Fréchet differentiable operators

We provide new sufficient convergence conditions for the semilocal convergence of Ulm’s method (Izv. Akad. Nauk Est. SSR 16:403–411, 1967) in order to approximate a locally unique solution of an equation in a Banach space setting. We show that in some cases, our hypotheses hold true but the corresponding ones (Burmeister in Z. Angew. Math. Mech. 52:101–110, 1972; Kornstaedt in Aequ. Math. 13:21–45, 1975; Petzeltova in Comment. Math. Univ. Carol. 21:719–725, 1980; Potra and Ptǎk in Cas. Pest. Mat. 108:333–341, 1983; Ulm in Izv. Akad. Nauk Est. SSR 16:403–411, 1967) do not. We also show that under the same hypotheses and computational cost as (Burmeister in Z. Angew. Math. Mech. 52:101–110, 1972; Kornstaedt in Aequ. Math. 13:21–45, 1975; Petzeltova in Comment. Math. Univ. Carol. 21:719–725, 1980; Potra and Ptǎk in Cas. Pest. Mat. 108:333–341, 1983; Ulm in Izv. Akad. Nauk Est. SSR 16:403–411, 1967) finer error sequences can be obtained. Numerical examples are also provided further validating the results.     

Non-Decaying Solutions to the Navier Stokes Equations in Exterior Domains

We establish a new theorem of existence (and uniqueness) of solutions to the Navier-Stokes initial boundary value problem in exterior domains. No requirement is made on the convergence at infinity of the kinetic field and of the pressure field. These solutions are called non-decaying solutions. The first results on this topic dates back about 40 years ago see the references (Galdi and Rionero in Ann. Mat. Pures Appl. 108:361–366, 1976, Arch. Ration. Mech. Anal. 62:295–301, 1976, Arch. Ration. Mech. Anal. 69:37–52, 1979, Pac. J. Math. 104:77–83, 1980; Knightly in SIAM J. Math. Anal. 3:506–511, 1972). In the articles Galdi and Rionero (Ann. Mat. Pures Appl. 108:361–366, 1976, Arch. Ration. Mech. Anal. 62:295–301, 1976, Arch. Ration. Mech. Anal. 69:37–52, 1979, Pac. J. Math. 104:77–83, 1980) it was introduced the so called weight function method to study the uniqueness of solutions. More recently, the problem has been considered again by several authors (see Galdi et al. in J. Math. Fluid Mech. 14:633–652, 2012, Quad. Mat. 4:27–68, 1999, Nonlinear Anal. 47:4151–4156, 2001; Kato in Arch. Ration. Mech. Anal. 169:159–175, 2003; Kukavica and Vicol in J. Dyn. Differ. Equ. 20:719–732, 2008; Maremonti in Mat. Ves. 61:81–91, 2009, Appl. Anal. 90:125–139, 2011).     

An improved local convergence analysis for a two-step Steffensen-type method

We study a class of Steffensen-type algorithm for solving nonsmooth variational inclusions in Banach spaces. We provide a local convergence analysis under ω-conditioned divided difference, and the Aubin continuity property. This work on the one hand extends the results on local convergence of Steffensen’s method related to the resolution of nonlinear equations (see Amat and Busquier in Comput. Math. Appl. 49:13–22, 2005; J. Math. Anal. Appl. 324:1084–1092, 2006; Argyros in Southwest J. Pure Appl. Math. 1:23–29, 1997; Nonlinear Anal. 62:179–194, 2005; J. Math. Anal. Appl. 322:146–157, 2006; Rev. Colomb. Math. 40:65–73, 2006; Computational Theory of Iterative Methods, 2007). On the other hand our approach improves the ratio of convergence and enlarges the convergence ball under weaker hypotheses than one given in Hilout (Commun. Appl. Nonlinear Anal. 14:27–34, 2007).