Generalization of Primal—Dual Interior-Point Methods to Convex Optimization Problems in Conic Form

We generalize primal—dual interior-point methods for linear programming (LP) problems to the convex optimization problems in conic form. Previously, the most comprehensive theory of symmetric primal—dual interior-point algorithms was given by Nesterov and Todd for feasible regions expressed as the intersection of a symmetric cone with an affine subspace. In our setting, we allow an arbitrary convex cone in place of the symmetric cone. Even though some of the impressive properties attained by Nesterov—Todd algorithms are impossible in this general setting of convex optimization problems, we show that essentially all primal—dual interior-point algorithms for LP can be extended easily to the general setting. We provide three frameworks for primal—dual algorithms, each framework corresponding to a different level of sophistication in the algorithms. As the level of sophistication increases, we demand better formulations of the feasible solution sets. Our algorithms, in return, attain provably better theoretical properties. We also make a very strong connection to quasi-Newton methods by expressing the square of the symmetric primal—dual linear transformation (the so-called scaling) as a quasi-Newton update in the case of the least sophisticated framework. August 25, 1999. Final version received: March 7, 2001.     

New accelerated conjugate gradient algorithms as a modification of Dai-Yuan’s computational scheme for unconstrained optimization

New accelerated nonlinear conjugate gradient algorithms which are mainly modifications of Dai and Yuan’s for unconstrained optimization are proposed. Using the exact line search, the algorithm reduces to the Dai and Yuan conjugate gradient computational scheme. For inexact line search the algorithm satisfies the sufficient descent condition. Since the step lengths in conjugate gradient algorithms may differ from 1 by two orders of magnitude and tend to vary in a very unpredictable manner, the algorithms are equipped with an acceleration scheme able to improve the efficiency of the algorithms. Computational results for a set consisting of 750 unconstrained optimization test problems show that these new conjugate gradient algorithms substantially outperform the Dai-Yuan conjugate gradient algorithm and its hybrid variants, Hestenes-Stiefel, Polak-Ribière-Polyak, CONMIN conjugate gradient algorithms, limited quasi-Newton algorithm LBFGS and compare favorably with CG_DESCENT. In the frame of this numerical study the accelerated scaled memoryless BFGS preconditioned conjugate gradient ASCALCG algorithm proved to be more robust.     

Applying Powell’s symmetrical technique to conjugate gradient methods

A new conjugate gradient method is proposed by applying Powell’s symmetrical technique to conjugate gradient methods in this paper. Using Wolfe line searches, the global convergence of the method is analyzed by using the spectral analysis of the conjugate gradient iteration matrix and Zoutendijk’s condition. Based on this, some concrete descent algorithms are developed. 200s numerical experiments are presented to verify their performance and the numerical results show that these algorithms are competitive compared with the PRP⁺ algorithm. Finally, a brief discussion of the new proposed method is given.     

Regularization by Functions of Bounded Variation and Applications to Image Enhancement

Optimization problems regularized by bounded variation seminorms are analyzed. The optimality system is obtained and finite-dimensional approximations of bounded variation function spaces as well as of the optimization problems are studied. It is demonstrated that the choice of the vector norm in the definition of the bounded variation seminorm is of special importance for approximating subspaces consisting of piecewise constant functions. Algorithms based on a primal—dual framework that exploit the structure of these nondifferentiable optimization problems are proposed. Numerical examples are given for denoising of blocky images with very high noise. Accepted 29 March 1998     

Rotationally symmetric 1-harmonic maps from D 2 to S 2

We consider rotationally symmetric 1-harmonic maps from D ² to S ² subject to Dirichlet boundary conditions. We prove that the corresponding energy—a degenerate non-convex functional with linear growth—admits a unique minimizer, and that the minimizer is smooth in the bulk and continuously differentiable up to the boundary. We also show that, in contrast with 2-harmonic maps, a range of boundary data exists such that the energy admits more than one smooth critical point: more precisely, we prove that the corresponding Euler–Lagrange equation admits a unique (up to scaling and symmetries) global solution, which turns out to be oscillating, and we characterize the minimizer and the smooth critical points of the energy as the monotone, respectively non-monotone, branches of such solution. R. Dal Passo passed away on 8th August 2007. Endowed with great strength, creativity and humanity, Roberta has been an outstanding mathematician, an extraordinary teacher and a wonderful friend. Farewell, Roberta.     

A Characterization of the Existence of Solutions for Hamilton—Jacobi Equations in Ergodic Control Problems with Applications

We give a characterization of the existence of bounded solutions for Hamilton—Jacobi equations in ergodic control problems with state-constraint. This result is applied to the reexamination of the counterexample given in [5] concerning the existence of solutions for ergodic control problems in infinite-dimensional Hilbert spaces and also establishing results on effective Hamiltonians in periodic homogenization of Hamilton—Jacobi equations. Accepted 1 December 1999     

Robust Optimal Stopping-Time Control for Nonlinear Systems

Abstract. We formulate a robust optimal stopping-time problem for a state-space system and give the connection between various notions of lower value function for the associated games (and storage function for the associated dissipative system) with solutions of the appropriate variational inequality (VI) (the analogue of the Hamilton—Jacobi—Bellman—Isaacs equation for this setting). We show that the stopping-time rule can be obtained by solving the VI in the viscosity sense and a positive definite supersolution of the VI can be used for stability analysis.     

Robust Optimal Stopping-Time Control for Nonlinear Systems

   Abstract. We formulate a robust optimal stopping-time problem for a state-space system and give the connection between various notions of lower value function for the associated games (and storage function for the associated dissipative system) with solutions of the appropriate variational inequality (VI) (the analogue of the Hamilton—Jacobi—Bellman—Isaacs equation for this setting). We show that the stopping-time rule can be obtained by solving the VI in the viscosity sense and a positive definite supersolution of the VI can be used for stability analysis.     

Autonomous Integral Functionals with Discontinuous Nonconvex Integrands: Lipschitz Regularity of Minimizers,DuBois—Reymond Necessary Conditions,and Hamilton—Jacobi Equations

This paper is devoted to the autonomous Lagrange problem of the calculus of variations with a discontinuous Lagrangian. We prove that every minimizer is Lipschitz continuous if the Lagrangian is coercive and locally bounded. The main difference with respect to the previous works in the literature is that we do not assume that the Lagrangian is convex in the velocity. We also show that, under some additional assumptions, the DuBois—Reymond necessary condition still holds in the discontinuous case. Finally, we apply these results to deduce that the value function of the Bolza problem is locally Lipschitz and satisfies (in a generalized sense) a Hamilton—Jacobi equation.     

Equivalence between Nonlinear H ∞ Control Problems and Existence of Viscosity Solutions of Hamilton—Jacobi—Isaacs Equations rid="*" id="*" This work was written while the author was visiting the University of California at Santa Barbara. He was partially supported by Consiglio Nazionale delle Ricerche of Italy.

In this paper we extend to completely general nonlinear systems the result stating that the suboptimal control problem is solved if and only if the corresponding Hamilton—Jacobi—Isaacs (HJI) equation has a nonnegative (super)solution. This is well known for linear systems, using the Riccati equation instead of the HJI equation. We do this using the theory of differential games and viscosity solutions. Accepted 14 February 1997     

Scaled conjugate gradient algorithms for unconstrained optimization

In this work we present and analyze a new scaled conjugate gradient algorithm and its implementation, based on an interpretation of the secant equation and on the inexact Wolfe line search conditions. The best spectral conjugate gradient algorithm SCG by Birgin and Martínez (2001), which is mainly a scaled variant of Perry’s (1977), is modified in such a manner to overcome the lack of positive definiteness of the matrix defining the search direction. This modification is based on the quasi-Newton BFGS updating formula. The computational scheme is embedded in the restart philosophy of Beale–Powell. The parameter scaling the gradient is selected as spectral gradient or in an anticipative manner by means of a formula using the function values in two successive points. In very mild conditions it is shown that, for strongly convex functions, the algorithm is global convergent. Preliminary computational results, for a set consisting of 500 unconstrained optimization test problems, show that this new scaled conjugate gradient algorithm substantially outperforms the spectral conjugate gradient SCG algorithm. The author was awarded the Romanian Academy Grant 168/2003.     

Viscosity Solutions of an Infinite-Dimensional Black—Scholes—Barenblatt Equation

We study an infinite-dimensional Black—Scholes—Barenblatt equation which is a Hamilton—Jacobi—Bellman equation that is related to option pricing in the Musiela model of interest rate dynamics. We prove the existence and uniqueness of viscosity solutions of the Black—Scholes—Barenblatt equation and discuss their stochastic optimal control interpretation. We also show that in some cases the solution can be locally uniformly approximated by solutions of suitable finite-dimensional Hamilton—Jacobi—Bellman equations.     

A family of projective splitting methods for the sum of two maximal monotone operators

A splitting method for two monotone operators A and B is an algorithm that attempts to converge to a zero of the sum A + B by solving a sequence of subproblems, each of which involves only the operator A, or only the operator B. Prior algorithms of this type can all in essence be categorized into three main classes, the Douglas/Peaceman-Rachford class, the forward-backward class, and the little-used double-backward class. Through a certain “extended” solution set in a product space, we construct a fundamentally new class of splitting methods for pairs of general maximal monotone operators in Hilbert space. Our algorithms are essentially standard projection methods, using splitting decomposition to construct separators. We prove convergence through Fejér monotonicity techniques, but showing Fejér convergence of a different sequence to a different set than in earlier splitting methods. Our projective algorithms converge under more general conditions than prior splitting methods, allowing the proximal parameter to vary from iteration to iteration, and even from operator to operator, while retaining convergence for essentially arbitrary pairs of operators. The new projective splitting class also contains noteworthy preexisting methods either as conventional special cases or excluded boundary cases. Dedicated to Clovis Gonzaga on the occassion of his 60th birthday.     

A Schwarz domain decomposition method with gradient projection for optimal control governed by elliptic partial differential equations

A domain decomposition method (DDM) is presented to solve the distributed optimal control problem. The optimal control problem essentially couples an elliptic partial differential equation with respect to the state variable and a variational inequality with respect to the constrained control variable. The proposed algorithm, called SA-GP algorithm, consists of two iterative stages. In the inner loops, the Schwarz alternating method (SA) is applied to solve the state and co-state variables, and in the outer loops the gradient projection algorithm (GP) is adopted to obtain the control variable. Convergence of iterations depends on both the outer and the inner loops, which are coupled and affected by each other. In the classical iteration algorithms, a given tolerance would be reached after sufficiently many iteration steps, but more iterations lead to huge computational cost. For solving constrained optimal control problems, most of the computational cost is used to solve PDEs. In this paper, a proposed iterative number independent of the tolerance is used in the inner loops so as to save a lot of computational cost. The convergence rate of L²-error of control variable is derived. Also the analysis on how to choose the proposed iteration number in the inner loops is given. Some numerical experiments are performed to verify the theoretical results.     

A scaled nonlinear conjugate gradient algorithm for unconstrained optimization

The best spectral conjugate gradient algorithm by (Birgin, E. and Martínez, J.M., 2001, A spectral conjugate gradient method for unconstrained optimization. Applied Mathematics and Optimization, 43, 117–128). which is mainly a scaled variant of (Perry, J.M., 1977, A class of Conjugate gradient algorithms with a two step varaiable metric memory, Discussion Paper 269, Center for Mathematical Studies in Economics and Management Science, Northwestern University), is modified in such a way as to overcome the lack of positive definiteness of the matrix defining the search direction. This modification is based on the quasi-Newton BFGS updating formula. The computational scheme is embedded into the restart philosophy of Beale–Powell. The parameter scaling the gradient is selected as spectral gradient or in an anticipative way by means of a formula using the function values in two successive points. In very mild conditions it is shown that, for strongly convex functions, the algorithm is global convergent. Computational results and performance profiles for a set consisting of 700 unconstrained optimization problems show that this new scaled nonlinear conjugate gradient algorithm substantially outperforms known conjugate gradient methods including: the spectral conjugate gradient SCG by Birgin and Martínez, the scaled Fletcher and Reeves, the Polak and Ribière algorithms and the CONMIN by (Shanno, D.F. and Phua, K.H., 1976, Algorithm 500, Minimization of unconstrained multivariate functions. ACM Transactions on Mathematical Software, 2, 87–94).     

The Value Function of Singularly Perturbed Control Systems

The limit as ɛ→ 0 of the value function of a singularly perturbed optimal control problem is characterized. Under general conditions it is shown that limit value functions exist and solve in a viscosity sense a Hamilton—Jacobi equation. The Hamiltonian of this equation is generated by an infinite horizon optimization on the fast time scale. In particular, the limit Hamiltonian and the limit Hamilton—Jacobi equation are applicable in cases where the reduction of order, namely setting ɛ = 0 , does not yield an optimal behavior. Accepted 18 November 1999     

Symmetric Perry conjugate gradient method

A family of new conjugate gradient methods is proposed based on Perry’s idea, which satisfies the descent property or the sufficient descent property for any line search. In addition, based on the scaling technology and the restarting strategy, a family of scaling symmetric Perry conjugate gradient methods with restarting procedures is presented. The memoryless BFGS method and the SCALCG method are the special forms of the two families of new methods, respectively. Moreover, several concrete new algorithms are suggested. Under Wolfe line searches, the global convergence of the two families of the new methods is proven by the spectral analysis for uniformly convex functions and nonconvex functions. The preliminary numerical comparisons with CG_DESCENT and SCALCG algorithms show that these new algorithms are very effective algorithms for the large-scale unconstrained optimization problems. Finally, a remark for further research is suggested.     

A Class of Hamilton—Jacobi Equations with Unbounded Coefficients in Hilbert Spaces

We establish existence and comparison theorems for a class of Hamilton—Jacobi equations. The class of Hamilton—Jacobi equations includes and is broader than those studied in [8] We apply the existence and uniqueness results to characterizing the value functions associated with the optimal control of systems governed by partial differential equations of parabolic type. Accepted 11 May 2001. Online publication 5 October 2001.