Interval Methods for Semi-Infinite Programs

A new approach for the numerical solution of smooth, nonlinear semi-infinite programs whose feasible set contains a nonempty interior is presented. Interval analysis methods are used to construct finite nonlinear, or mixed-integer nonlinear, reformulations of the original semi-infinite program under relatively mild assumptions on the problem structure. In certain cases the finite reformulation is exact and can be solved directly for the global minimum of the semi-infinite program (SIP). In the general case, this reformulation is over-constrained relative to the SIP, such that solving it yields a guaranteed feasible upper bound to the SIP solution. This upper bound can then be refined using a subdivision procedure which is shown to converge to the true SIP solution with finite -optimality. In particular, the method is shown to converge for SIPs which do not satisfy regularity assumptions required by reduction-based methods, and for which certain points in the feasible set are subject to an infinite number of active constraints. Numerical results are presented for a number of problems in the SIP literature. The solutions obtained are compared to those identified by reduction-based methods, the relative performances of the nonlinear and mixed-integer nonlinear formulations are studied, and the use of different inclusion functions in the finite reformulation is investigated.     

A QP Free Feasible Method

In [12], a QP free feasible method was proposed for the minimization of a smooth function subject to smooth inequality constraints. This method is based on the solutions of linear systems of equations, the reformulation of the KKT optimality conditions by using the Fischer-Burmeister NCP function. This method ensures the feasibility of all iterations. In this paper, we modify the method in [12] slightly to obtain the local convergence under some weaker conditions. In particular, this method is implementable and globally convergent without assuming the linear independence of the gradients of active constrained functions and the uniformly positive definiteness of the submatrix obtained by the Newton or Quasi Newton methods. We also prove that the method has superlinear convergence rate under some mild conditions. Some preliminary numerical results indicate that this new QP free feasible method is quite promising.     

Relationships between interval-valued vector optimization problems and vector variational inequalities

In this paper, we study some relationships between interval-valued vector optimization problems and vector variational inequalities under the assumptions of LU-convex smooth and non-smooth objective functions. We identify the weakly efficient points of the interval-valued vector optimization problems and the solutions of the weak vector variational inequalities under smooth and non-smooth LU-convexity assumptions.     

Local linear convergence analysis of Primal–Dual splitting methods

In this paper, we study the local linear convergence properties of a versatile class of Primal–Dual splitting methods for minimizing composite non-smooth convex optimization problems. Under the assumption that the non-smooth components of the problem are partly smooth relative to smooth manifolds, we present a unified local convergence analysis framework for these methods. More precisely, in our framework, we first show that (i) the sequences generated by Primal–Dual splitting methods identify a pair of primal and dual smooth manifolds in a finite number of iterations, and then (ii) enter a local linear convergence regime, which is characterized based on the structure of the underlying active smooth manifolds. We also show how our results for Primal–Dual splitting can be specialized to cover existing ones on Forward–Backward splitting and Douglas–Rachford splitting/ADMM (alternating direction methods of multipliers). Moreover, based on these obtained local convergence analysis result, several practical acceleration techniques are discussed. To exemplify the usefulness of the obtained result, we consider several concrete numerical experiments arising from fields including signal/image processing, inverse problems and machine learning. The demonstration not only verifies the local linear convergence behaviour of Primal–Dual splitting methods, but also the insights on how to accelerate them in practice.     

Non-linear second-order periodic systems with non-smooth potential

In this paper we study second order non-linear periodic systems driven by the ordinary vectorp-Laplacian with a non-smooth, locally Lipschitz potential function. Our approach is variational and it is based on the non-smooth critical point theory. We prove existence and multiplicity results under general growth conditions on the potential function. Then we establish the existence of non-trivial homoclinic (to zero) solutions. Our theorem appears to be the first such result (even for smooth problems) for systems monitored by thep-Laplacian. In the last section of the paper we examine the scalar non-linear and semilinear problem. Our approach uses a generalized Landesman-Lazer type condition which generalizes previous ones used in the literature. Also for the semilinear case the problem is at resonance at any eigenvalue.     

On an inverse problem: Recovery of non-smooth solutions to backward heat equation

We have recently developed two quasi-reversibility techniques in combination with Euler and Crank–Nicolson schemes and applied successfully to solve for smooth solutions of backward heat equation. In this paper, we test the viability of using these techniques to recover non-smooth solutions of backward heat equation. In particular, we numerically integrate the backward heat equation with smooth initial data up to a time of singularity (corners and discontinuities) formation. Using three examples, it is shown that the numerical solutions are very good smooth approximations to these singular exact solutions. The errors are shown using pseudo-L- and U-curves and compared where available with existing works. The limitations of these methods in terms of time of simulation and accuracy with emphasis on the precise set of numerical parameters suitable for producing smooth approximations are discussed. This paper also provides an opportunity to gain some insight into developing more sophisticated filtering techniques that can produce the fine-scale features (singularities) of the final solutions. Techniques are general and can be applied to many problems of scientific and technological interests.     

Exact penalties for variational inequalities with applications to nonlinear complementarity problems

In this paper, we present a new reformulation of the KKT system associated to a variational inequality as a semismooth equation. The reformulation is derived from the concept of differentiable exact penalties for nonlinear programming. The best theoretical results are presented for nonlinear complementarity problems, where simple, verifiable, conditions ensure that the penalty is exact. We close the paper with some preliminary computational tests on the use of a semismooth Newton method to solve the equation derived from the new reformulation. We also compare its performance with the Newton method applied to classical reformulations based on the Fischer-Burmeister function and on the minimum. The new reformulation combines the best features of the classical ones, being as easy to solve as the reformulation that uses the Fischer-Burmeister function while requiring as few Newton steps as the one that is based on the minimum.     

A nonmonotone Jacobian smoothing inexact Newton method for NCP

In this paper we propose Jacobian smoothing inexact Newton method for nonlinear complementarity problems (NCP) with derivative-free nonmonotone line search. This nonmonotone line search technique ensures globalization and is a combination of Grippo-Lampariello-Lucidi (GLL) and Li-Fukushima (LF) strategies, with the aim to take into account their advantages. The method is based on very well known Fischer-Burmeister reformulation of NCP and its smoothing Kanzow’s approximation. The mixed Newton equation, which combines the semismooth function with the Jacobian of its smooth operator, is solved approximately in every iteration, so the method belongs to the class of Jacobian smoothing inexact Newton methods. The inexact search direction is not in general a descent direction and this is the reason why nonmonotone scheme is used for globalization. Global convergence and local superlinear convergence of method are proved. Numerical performances are also analyzed and point out that high level of nonmonotonicity of this line search rule enables robust and efficient method.     

Smoothing inexact Newton methods for NCP with various nonmonotone techniques

Various iterative methods for solving nonlinear complementarity problems (NCP) are developed in recent years. In this paper we propose Jacobian smoothing inexact Newton methods for NCP with different nonmonotone strategies. The methods are based on semismooth equation reformulation of NCP by Fischer-Burmeister function. Nonmonotone line-search techniques are used for globalization procedure. Numerical performance of algorithms are compared. (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

First-order methods of smooth convex optimization with inexact oracle

We introduce the notion of inexact first-order oracle and analyze the behavior of several first-order methods of smooth convex optimization used with such an oracle. This notion of inexact oracle naturally appears in the context of smoothing techniques, Moreau–Yosida regularization, Augmented Lagrangians and many other situations. We derive complexity estimates for primal, dual and fast gradient methods, and study in particular their dependence on the accuracy of the oracle and the desired accuracy of the objective function. We observe that the superiority of fast gradient methods over the classical ones is no longer absolute when an inexact oracle is used. We prove that, contrary to simple gradient schemes, fast gradient methods must necessarily suffer from error accumulation. Finally, we show that the notion of inexact oracle allows the application of first-order methods of smooth convex optimization to solve non-smooth or weakly smooth convex problems.     

A Gauss–Newton Approach for Solving Constrained Optimization Problems Using Differentiable Exact Penalties

We propose a Gauss–Newton-type method for nonlinear constrained optimization using the exact penalty introduced recently by André and Silva for variational inequalities. We extend their penalty function to both equality and inequality constraints using a weak regularity assumption, and as a result, we obtain a continuously differentiable exact penalty function and a new reformulation of the KKT conditions as a system of equations. Such reformulation allows the use of a semismooth Newton method, so that local superlinear convergence rate can be proved under an assumption weaker than the usual strong second-order sufficient condition and without requiring strict complementarity. Besides, we note that the exact penalty function can be used to globalize the method. We conclude with some numerical experiments using the collection of test problems CUTE.     

On the Finite Convergence of Newton-type Methods for P0 Atone Variational Inequalities

Based on the techniques used in non-smooth Newton methods and regularized smoothing Newton methods, a Newton-type algorithm is proposed for solving the P0 affine variational inequality problem. Under mild conditions, the algorithm can find an exact solution of the P0 affine variational inequality problem in finite steps. Preliminary numerical results indicate that the algorithm is promising.     

On the Hénon equation: Asymptotic profile of ground states, II

This paper is concerned with analyzing the limiting behavior of the least energy solutions for the Hénon equation. We study the problems in bounded domains with smooth or non-smooth boundaries, and in particular we examine the effect of the boundary on the limiting profile of the solutions.     

Efficiently solving total least squares with Tikhonov identical regularization

The Tikhonov identical regularized total least squares (TI) is to deal with the ill-conditioned system of linear equations where the data are contaminated by noise. A standard approach for (TI) is to reformulate it as a problem of finding a zero point of some decreasing concave non-smooth univariate function such that the classical bisection search and Dinkelbach’s method can be applied. In this paper, by exploring the hidden convexity of (TI), we reformulate it as a new problem of finding a zero point of a strictly decreasing, smooth and concave univariate function. This allows us to apply the classical Newton’s method to the reformulated problem, which converges globally to the unique root with an asymptotic quadratic convergence rate. Moreover, in every iteration of Newton’s method, no optimization subproblem such as the extended trust-region subproblem is needed to evaluate the new univariate function value as it has an explicit expression. Promising numerical results based on the new algorithm are reported.     

非线性规划的QP-free方法

该文提出一种QP-free可行域方法用来解满足光滑不等式约束的最优化问题.此方法把QP-free方法和3-1线性互补函数相结合一个等价于原约束问题的一阶KKT条件的方程组,并在此基础上给出解这个方程组的迭代算法. 这个方法的每一步迭代都可以看作是对求KKT条件解的牛顿或拟牛顿迭代的扰动,且在该方法中每一步的迭代均具有可行性. 该方法是可实行的且具有全局性, 且不需要严格互补条件、聚点的孤立性和积极约束函数梯度的线性独立等假设. 在与文献[2]中相同的适当条件下,此方法还具有超线性收敛性. 数值检验结果表示,该文提出的QP-free可行域方法是切实有效的方法.     

On the iteratively regularized Gauss–Newton method in Banach spaces with applications to parameter identification problems

In this paper we propose an extension of the iteratively regularized Gauss–Newton method to the Banach space setting by defining the iterates via convex optimization problems. We consider some a posteriori stopping rules to terminate the iteration and present the detailed convergence analysis. The remarkable point is that in each convex optimization problem we allow non-smooth penalty terms including $L^1$ and total variation like penalty functionals. This enables us to reconstruct special features of solutions such as sparsity and discontinuities in practical applications. Some numerical experiments on parameter identification in partial differential equations are reported to test the performance of our method.     

SSVM: A Smooth Support Vector Machine for Classification

Smoothing methods, extensively used for solving important mathematical programming problems and applications, are applied here to generate and solve an unconstrained smooth reformulation of the support vector machine for pattern classification using a completely arbitrary kernel. We term such reformulation a smooth support vector machine (SSVM). A fast Newton–Armijo algorithm for solving the SSVM converges globally and quadratically. Numerical results and comparisons are given to demonstrate the effectiveness and speed of the algorithm. On six publicly available datasets, tenfold cross validation correctness of SSVM was the highest compared with four other methods as well as the fastest. On larger problems, SSVM was comparable or faster than SVM ^light (T. Joachims, in Advances in Kernel Methods—Support Vector Learning, MIT Press: Cambridge, MA, 1999), SOR (O.L. Mangasarian and David R. Musicant, IEEE Transactions on Neural Networks, vol. 10, pp. 1032–1037, 1999) and SMO (J. Platt, in Advances in Kernel Methods—Support Vector Learning, MIT Press: Cambridge, MA, 1999). SSVM can also generate a highly nonlinear separating surface such as a checkerboard.     

Optimization reformulations of the generalized Nash equilibrium problem using Nikaido-Isoda-type functions

We consider the generalized Nash equilibrium problem which, in contrast to the standard Nash equilibrium problem, allows joint constraints of all players involved in the game. Using a regularized Nikaido-Isoda-function, we then present three optimization problems related to the generalized Nash equilibrium problem. The first optimization problem is a complete reformulation of the generalized Nash game in the sense that the global minima are precisely the solutions of the game. However, this reformulation is nonsmooth. We then modify this approach and obtain a smooth constrained optimization problem whose global minima correspond to so-called normalized Nash equilibria. The third approach uses the difference of two regularized Nikaido-Isoda-functions in order to get a smooth unconstrained optimization problem whose global minima are, once again, precisely the normalized Nash equilibria. Conditions for stationary points to be global minima of the two smooth optimization problems are also given. Some numerical results illustrate the behaviour of our approaches.     

A Smoothing Newton Method for General Nonlinear Complementarity Problems

Smoothing Newton methods for nonlinear complementarity problems NCP(F) often require F to be at least a P ₀-function in order to guarantee that the underlying Newton equation is solvable. Based on a special equation reformulation of NCP(F), we propose a new smoothing Newton method for general nonlinear complementarity problems. The introduction of Kanzow and Pieper's gradient step makes our algorithm to be globally convergent. Under certain conditions, our method achieves fast local convergence rate. Extensive numerical results are also reported for all complementarity problems in MCPLIB and GAMSLIB libraries with all available starting points.     

Properties of the Central Points in Linear Programming Problems

In this paper we list several useful properties of central points in linear programming problems. We study the logarithmic barrier function, the analytic center and the central path, relating the proximity measures and scaled Euclidean distances defined for the primal and primal–dual problems. We study the Newton centering steps, and show how large the short steps used in path following algorithms can actually be, and what variation can be ensured for the barrier function in each iteration of such methods. We relate the primal and primal–dual Newton centering steps and propose a primal-only path following algorithm for linear programming.