Feasible Method for Generalized Semi-Infinite Programming

In this paper, we analyze the outer approximation property of the algorithm for generalized semi-infinite programming from Stein and Still (SIAM J. Control Optim. 42:769–788, 2003). A simple bound on the regularization error is found and used to formulate a feasible numerical method for generalized semi-infinite programming with convex lower-level problems. That is, all iterates of the numerical method are feasible points of the original optimization problem. The new method has the same computational cost as the original algorithm from Stein and Still (SIAM J. Control Optim. 42:769–788, 2003). We also discuss the merits of this approach for the adaptive convexification algorithm, a feasible point method for standard semi-infinite programming from Floudas and Stein (SIAM J. Optim. 18:1187–1208, 2007).     

Weak and Strong Convergence Theorems for Maximal Monotone Operators in a Banach Space

In this paper, we introduce an iterative sequence for finding a solution of a maximal monotone operator in a uniformly convex Banach space. Then we first prove a strong convergence theorem, using the notion of generalized projection. Assuming that the duality mapping is weakly sequentially continuous, we next prove a weak convergence theorem, which extends the previous results of Rockafellar [SIAM J. Control Optim. 14 (1976), 877–898] and Kamimura and Takahashi [J. Approx. Theory 106 (2000), 226–240]. Finally, we apply our convergence theorem to the convex minimization problem and the variational inequality problem.     

A modified Solodov-Svaiter method for solving nonmonotone variational inequality problems

Numerical Algorithms - In a very interesting paper (SIAM J. Control Optim. 37(3): 765–776, 1999), Solodov and Svaiter introduced an effective projection algorithm with linesearch for finding...     

The prox-Tikhonov regularization method for the proximal point algorithm in Banach spaces

It is known, by Rockafellar (SIAM J Control Optim 14:877–898, 1976), that the proximal point algorithm (PPA) converges weakly to a zero of a maximal monotone operator in a Hilbert space, but it fails to converge strongly. Lehdili and Moudafi (Optimization 37:239–252, 1996) introduced the new prox-Tikhonov regularization method for PPA to generate a strongly convergent sequence and established a convergence property for it by using the technique of variational distance in the same space setting. In this paper, the prox-Tikhonov regularization method for the proximal point algorithm of finding a zero for an accretive operator in the framework of Banach space is proposed. Conditions which guarantee the strong convergence of this algorithm to a particular element of the solution set is provided. An inexact variant of this method with error sequence is also discussed.     

Quasiconvex Minimization on a Locally Finite Union of Convex Sets

Extending the approach initiated in Aussel and Hadjisavvas (SIAM J. Optim. 16:358–367, 2005) and Aussel and Ye (Optimization 55:433–457, 2006), we obtain the existence of a local minimizer of a quasiconvex function on the locally finite union of closed convex subsets of a Banach space. We apply the existence result to some difficult nonconvex optimization problems such as the disjunctive programming problem and the bilevel programming problem. Dedicated to Jean-Pierre Crouzeix on the occasion of his 65th birthday. The authors thank two anonymous referees for careful reading of the paper and helpful suggestions. The research of the second author was partially supported by NSERC/Canada.     

Proximal-Like Algorithm Using the Quasi D-Function for Convex Second-Order Cone Programming

In this paper, we present a measure of distance in a second-order cone based on a class of continuously differentiable strictly convex functions on ℝ₊₊. Since the distance function has some favorable properties similar to those of the D-function (Censor and Zenios in J. Optim. Theory Appl. 73:451–464 [1992]), we refer to it as a quasi D-function. Then, a proximal-like algorithm using the quasi D-function is proposed and applied to the second-cone programming problem, which is to minimize a closed proper convex function with general second-order cone constraints. Like the proximal point algorithm using the D-function (Censor and Zenios in J. Optim. Theory Appl. 73:451–464 [1992]; Chen and Teboulle in SIAM J. Optim. 3:538–543 [1993]), under some mild assumptions we establish the global convergence of the algorithm expressed in terms of function values; we show that the sequence generated by the proposed algorithm is bounded and that every accumulation point is a solution to the considered problem. Research of Shaohua Pan was partially supported by the Doctoral Starting-up Foundation (B13B6050640) of GuangDong Province. Jein-Shan Chen is a member of the Mathematics Division, National Center for Theoretical Sciences, Taipei Office. The author’s work was partially supported by National Science Council of Taiwan.     

Viscosity approximation methods for resolvents of accretive operators in Banach spaces

In this paper, we first prove a strong convergence theorem for resolvents of accretive operators in a Banach space by the viscosity approximation method, which is a generalization of the results of Reich [J. Math. Anal. Appl. 75 (1980), 287–292], and Takahashi and Ueda [J. Math. Anal. Appl. 104 (1984), 546–553]. Further using this result, we consider the proximal point algorithm in a Banach space by the viscosity approximation method, and obtain a strong convergence theorem which is a generalization of the result of Kamimura and Takahashi [Set-Valued Anal. 8 (2000), 361–374]. Dedicated to the memory of Jean Leray     

An infeasible interior-point algorithm with full-Newton step for linear optimization

Recently, Roos (SIAM J Optim 16(4):1110–1136, 2006) presented a primal-dual infeasible interior-point algorithm that uses full-Newton steps and whose iteration bound coincides with the best known bound for infeasible interior-point algorithms. In the current paper we use a different feasibility step such that the definition of the feasibility step in Mansouri and Roos (Optim Methods Softw 22(3):519–530, 2007) is a special case of our definition, and show that the same result on the order of iteration complexity can be obtained.      

Further Results on the Robust Regulation of a One-Dimensional Dam-River System

In this paper, we consider a one-dimensional dam-river system studied by Chentouf and Wang (SIAM J. Control Optim. 47: 2275–2302, 2008). Then, using the frequency multiplier method, we provide a simple and alternative proof of stabilization and regulation results obtained in the work cited above. Moreover, we relax the conditions on the feedback gains involved in the feedback law and give a partial answer to the open problem left by the authors Chentouf and Wang (J. Optim. Theory Appl. 134: 223–239, 2007 and SIAM J. Control Optim. 47: 2275–2302, 2008) concerning the tuning of the gains.     

Pseudomonotone operators and the Bregman Proximal Point Algorithm

To permit the stable solution of ill-posed problems, the Proximal Point Algorithm (PPA) was introduced by Martinet (RIRO 4:154–159, 1970) and further developed by Rockafellar (SIAM J Control Optim 14:877–898, 1976). Later on, the usual proximal distance function was replaced by the more general class of Bregman(-like) functions and related distances; see e.g. Chen and Teboulle (SIAM J Optim 3:538–543, 1993), Eckstein (Math Program 83:113–123, 1998), Kaplan and Tichatschke (Optimization 56(1–2):253–265, 2007), and Solodov and Svaiter (Math Oper Res 25:214–230, 2000). An adequate use of such generalized non-quadratic distance kernels admits to obtain an interior-point-effect, that is, the auxiliary problems may be treated as unconstrained ones. In the above mentioned works and nearly all other works related with this topic it was assumed that the operator of the considered variational inequality is a maximal monotone and paramonotone operator. The approaches of El-Farouq (JOTA 109:311–326, 2001), and Schaible et al. (Taiwan J Math 10(2):497–513, 2006) only need pseudomonotonicity (in the sense of Karamardian in JOTA 18:445–454, 1976); however, they make use of other restrictive assumptions which on the one hand contradict the desired interior-point-effect and on the other hand imply uniqueness of the solution of the problem. The present work points to the discussion of the Bregman algorithm under significantly weaker assumptions, namely pseudomonotonicity [and an additional assumption much less restrictive than the ones used by El-Farouq and Schaible et al. We will be able to show that convergence results known from the monotone case still hold true; some of them will be sharpened or are even new. An interior-point-effect is obtained, and for the generated subproblems we allow inexact solutions by means of a unified use of a summable-error-criterion and an error criterion of fixed-relative-error-type (this combination is also new in the literature).     

A priori error estimates for space–time finite element discretization of semilinear parabolic optimal control problems

In this paper, a priori error estimates for space–time finite element discretizations of optimal control problems governed by semilinear parabolic PDEs and subject to pointwise control constraints are derived. We extend the approach from Meidner and Vexler (SIAM Control Optim 47(3):1150–1177, 2008; SIAM Control Optim 47(3):1301–1329, 2008) where linear-quadratic problems have been considered, discretizing the state equation by usual conforming finite elements in space and a discontinuous Galerkin method in time. Error estimates for controls discretized by piecewise constant functions in time and cellwise constant functions in space are derived in detail and we explain how error estimate for further discretization approaches, e.g., cellwise linear discretization in space, the postprocessing approach from Meyer and R?sch (SIAM J Control Optim 43:970–985, 2004), and the variationally discrete approach from Hinze (J Comput Optim Appl 30:45–63, 2005) can be obtained. In addition, we derive an estimate for a setting with finitely many time-dependent controls.     

On the convergence analysis of inexact hybrid extragradient proximal point algorithms for maximal monotone operators

In this paper we introduce general iterative methods for finding zeros of a maximal monotone operator in a Hilbert space which unify two previously studied iterative methods: relaxed proximal point algorithm [H.K. Xu, Iterative algorithms for nonlinear operators, J. London Math Soc. 66 (2002) 240–256] and inexact hybrid extragradient proximal point algorithm [R.S. Burachik, S. Scheimberg, B.F. Svaiter, Robustness of the hybrid extragradient proximal-point algorithm, J. Optim. Theory Appl. 111 (2001) 117–136]. The paper establishes both weak convergence and strong convergence of the methods under suitable assumptions on the algorithm parameters.     

An inexact Newton method for nonconvex equality constrained optimization

We present a matrix-free line search algorithm for large-scale equality constrained optimization that allows for inexact step computations. For strictly convex problems, the method reduces to the inexact sequential quadratic programming approach proposed by Byrd et al. [SIAM J. Optim. 19(1) 351–369, 2008]. For nonconvex problems, the methodology developed in this paper allows for the presence of negative curvature without requiring information about the inertia of the primal–dual iteration matrix. Negative curvature may arise from second-order information of the problem functions, but in fact exact second derivatives are not required in the approach. The complete algorithm is characterized by its emphasis on sufficient reductions in a model of an exact penalty function. We analyze the global behavior of the algorithm and present numerical results on a collection of test problems.     

Decomposition-based Method for Sparse Semidefinite Relaxations of Polynomial Optimization Problems

We consider polynomial optimization problems pervaded by a sparsity pattern. It has been shown in Lasserre (SIAM J. Optim. 17(3):822–843, 2006) and Waki et al. (SIAM J. Optim. 17(1):218–248, 2006) that the optimal solution of a polynomial programming problem with structured sparsity can be computed by solving a series of semidefinite relaxations that possess the same kind of sparsity. We aim at solving the former relaxations with a decomposition-based method, which partitions the relaxations according to their sparsity pattern. The decomposition-based method that we propose is an extension to semidefinite programming of the Benders decomposition for linear programs (Benders, Comput. Manag. Sci. 2(1):3–19, 2005).     

On the convergence of Newton-type methods under mild differentiability conditions

We introduce the new idea of recurrent functions to provide a new semilocal convergence analysis for Newton-type methods, under mild differentiability conditions. It turns out that our sufficient convergence conditions are weaker, and the error bounds are tighter than in earlier studies in some interesting cases (Chen, Ann Inst Stat Math 42:387–401, 1990; Chen, Numer Funct Anal Optim 10:37–48, 1989; Cianciaruso, Numer Funct Anal Optim 24:713–723, 2003; Cianciaruso, Nonlinear Funct Anal Appl 2009; Dennis 1971; Deuflhard 2004; Deuflhard, SIAM J Numer Anal 16:1–10, 1979; Gutiérrez, J Comput Appl Math 79:131–145, 1997; Hernández, J Optim Theory Appl 109:631–648, 2001; Hernández, J Comput Appl Math 115:245–254, 2000; Huang, J Comput Appl Math 47:211–217, 1993; Kantorovich 1982; Miel, Numer Math 33:391–396, 1979; Miel, Math Comput 34:185–202, 1980; Moret, Computing 33:65–73, 1984; Potra, Libertas Mathematica 5:71–84, 1985; Rheinboldt, SIAM J Numer Anal 5:42–63, 1968; Yamamoto, Numer Math 51: 545–557, 1987; Zabrejko, Numer Funct Anal Optim 9:671–684, 1987; Zinc̆ko 1963). Applications and numerical examples, involving a nonlinear integral equation of Chandrasekhar-type, and a differential equation are also provided in this study.     

Epsilon-proximal decomposition method

We propose a modification of the proximal decomposition method investigated by Spingarn [30] and Mahey et al. [19] for minimizing a convex function on a subspace. For the method to be favorable from a computational point of view, particular importance is the introduction of approximations in the proximal step. First, we couple decomposition on the graph of the epsilon-subdifferential mapping and cutting plane approximations to get an algorithmic pattern that falls in the general framework of Rockafellar inexact proximal-point algorithms [26]. Recently, Solodov and Svaiter [27] proposed a new proximal point-like algorithm that uses improved error criteria and an enlargement of the maximal monotone operator defining the problem. We combine their idea with bundle mecanism to devise an inexact proximal decomposition method with error condition which is not hard to satisfy in practice. Then, we present some applications favorable to our development. First, we give a new regularized version of Benders decomposition method in convex programming called the proximal convex Benders decomposition algorithm. Second, we derive a new algorithm for nonlinear multicommodity flow problems among which the message routing problem in telecommunications data networks.     

Modified Proximal-Point Algorithm for Maximal Monotone Operators in Banach Spaces

We introduce an iterative sequence for finding the solution to 0∈T(v), where T : E⇉E ^* is a maximal monotone operator in a smooth and uniformly convex Banach space E. This iterative procedure is a combination of iterative algorithms proposed by Kohsaka and Takahashi (Abstr. Appl. Anal. 3:239–249, 2004) and Kamamura, Kohsaka and Takahashi (Set-Valued Anal. 12:417–429, 2004). We prove a strong convergence theorem and a weak convergence theorem under different conditions respectively and give an estimate of the convergence rate of the algorithm. An application to minimization problems is given. This work was partially supported by the National Natural Sciences Grant 10671050 and the Heilongjiang Province Natural Sciences Grant A200607. The authors thank the referees for useful comments improving the presentation and Professor K. Kohsaka for pointing out Ref. 7.     

On local convergence of sequential quadratically-constrained quadratic-programming type methods,with an extension to variational problems

We consider the class of quadratically-constrained quadratic-programming methods in the framework extended from optimization to more general variational problems. Previously, in the optimization case, Anitescu (SIAM J. Optim. 12, 949–978, 2002) showed superlinear convergence of the primal sequence under the Mangasarian-Fromovitz constraint qualification and the quadratic growth condition. Quadratic convergence of the primal-dual sequence was established by Fukushima, Luo and Tseng (SIAM J. Optim. 13, 1098–1119, 2003) under the assumption of convexity, the Slater constraint qualification, and a strong second-order sufficient condition. We obtain a new local convergence result, which complements the above (it is neither stronger nor weaker): we prove primal-dual quadratic convergence under the linear independence constraint qualification, strict complementarity, and a second-order sufficiency condition. Additionally, our results apply to variational problems beyond the optimization case. Finally, we provide a necessary and sufficient condition for superlinear convergence of the primal sequence under a Dennis-Moré type condition. Research of the second author is partially supported by CNPq Grants 300734/95-6 and 471780/2003-0, by PRONEX–Optimization, and by FAPERJ.     

A Smoothing Newton Method with Fischer-Burmeister Function for Second-Order Cone Complementarity Problems

The second-order cone complementarity problem (SOCCP) is an important class of problems containing a lot of optimization problems. The SOCCP can be transformed into a system of nonsmooth equations. To solve this nonsmooth system, smoothing techniques are often used. Fukushima, Luo and Tseng (SIAM J. Optim. 12:436–460, 2001) studied concrete theories and properties of smoothing functions for the SOCCP. Recently, a practical computational method using the smoothed natural residual function to solve the SOCCP was given by Chen, Sun and Sun (Comput. Optim. Appl. 25:39–56, 2003). In the present paper, we propose an algorithm to solve the SOCCP by using the smoothed Fischer-Burmeister function. Some preliminary numerical results are given.     

Characterizations of the Nonemptiness and?Boundedness of Weakly Efficient Solution Sets of?Convex Vector Optimization Problems in Real Reflexive?Banach Spaces

Under a weak compactness assumption on the functions involved, which always holds in finite-dimensional normed linear spaces, this paper extends various characterizations of the nonemptiness and boundedness of weakly efficient solution sets of convex vector optimization problems, obtained previously by the author (Deng in J. Optim. Theory Appl. 96:123–131, 1998) in the real finite-dimensional normed linear space setting, to those in the real reflexive Banach space setting.