On necessary conditions for a class of nondifferentiable minimax fractional programming

The Kuhn–Tucker-type necessary optimality conditions are given for the problem of minimizing a max fractional function, where the numerator of the function involved is the sum of a differentiable function and a convex function while the denominator is the difference of a differentiable function and a convex function, subject to a set of differentiable nonlinear inequalities on a convex subset C$C$ of Rⁿ${\mathbb{R}}^n$, under the conditions similar to the Kuhn–Tucker constraint qualification or the Arrow–Hurwicz–Uzawa constraint qualification or the Abadie constraint qualification. Relations with the calmness constraint qualification are given.     

Bilevel multiplicative problems: A penalty approach to optimality and a cutting plane based algorithm

Bilevel programming has been proposed for dealing with decision processes involving two decision makers with a hierarchical structure. They are characterised by the existence of two optimisation problems in which the constraint region of the upper level problem is implicitly determined by the lower level optimisation problem. In this paper we focus on the class of bilevel problems in which the upper level objective function is linear multiplicative, the lower level one is linear and the common constraint region is a bounded polyhedron. After replacing the lower level problem by its Karush–Kuhn–Tucker conditions, the existence of an extreme point which solves the problem is proved by using a penalty function approach. Besides, an algorithm based on the successive introduction of valid cutting planes is developed obtaining a global optimal solution. Finally, we generalise the problem by including upper level constraints which involve both level variables.     

Properties of a family of generalized NCP-functions and a derivative free algorithm for complementarity problems

In this paper, we propose a new family of NCP-functions and the corresponding merit functions, which are the generalization of some popular NCP-functions and the related merit functions. We show that the new NCP-functions and the corresponding merit functions possess a system of favorite properties. Specially, we show that the new NCP-functions are strongly semismooth, Lipschitz continuous, and continuously differentiable; and that the corresponding merit functions have SC¹$S{C}^1$ property (i.e., they are continuously differentiable and their gradients are semismooth) and LC¹$L{C}^1$ property (i.e., they are continuously differentiable and their gradients are Lipschitz continuous) under suitable assumptions. Based on the new NCP-functions and the corresponding merit functions, we investigate a derivative free algorithm for the nonlinear complementarity problem and discuss its global convergence. Some preliminary numerical results are reported.     

Solving the Karush–Kuhn–Tucker system of a nonconvex programming problem on an unbounded set

In the papers [G.C. Feng, B. Yu, Combined homotopy interior point method for nonlinear programming problems, in: H. Fujita, M. Yamaguti (Eds.), Advances in Numerical Mathematics; Proceedings of the Second Japan–China Seminar on Numerical Mathematics, in: Lecture Notes in Numerical and Applied Analysis, vol. 14, Kinokuniya, Tokyo, 1995, pp. 9–16; G.C. Feng, Z.H. Lin, B. Yu, Existence of an interior pathway to a Karush–Kuhn–Tucker point of a nonconvex programming problem, Nonlinear Analysis 32 (1998) 761–768; Z.H. Lin, B. Yu, G.C. Feng, A combined homotopy interior point method for convex programming problem, Applied Mathematics and Computation 84 (1997) 193–211], a combined homotopy interior method was presented and global convergence results obtained for nonconvex nonlinear programming when the feasible set is bounded and satisfies the so called normal cone condition. However, for when the feasible set is not bounded, no result has so far been obtained. In this paper, a combined homotopy interior method for nonconvex programming problems on the unbounded feasible set is considered. Under suitable additional assumptions, boundedness of the homotopy path, and hence global convergence, is proven.     

A capable neural network model for solving the maximum flow problem

This paper presents an optimization technique for solving a maximum flow problem arising in widespread applications in a variety of settings. On the basis of the Karush–Kuhn–Tucker (KKT) optimality conditions, a neural network model is constructed. The equilibrium point of the proposed neural network is then proved to be equivalent to the optimal solution of the original problem. It is also shown that the proposed neural network model is stable in the sense of Lyapunov and it is globally convergent to an exact optimal solution of the maximum flow problem. Several illustrative examples are provided to show the feasibility and the efficiency of the proposed method in this paper.     

Expressions for subdifferential and optimization problems defined by nonsmooth homogeneous functions

In this paper, we prove a theoretical expression for subdifferentials of lower semicontinuous and homogeneous functions. The theoretical expression is a generalization of the Euler formula for differentiable homogeneous functions. As applications of the generalized Euler formula, we consider constrained optimization problems defined by nonsmooth positively homogeneous functions in smooth Banach spaces. Some results concerning Karush–Kuhn–Tucker points and necessary optimality conditions for the optimization problems are obtained.     

Homotopy method for solving variational inequalities with bounded box constraints

In this paper, using the Gabriel–Moré smoothing function of the median function, a smooth homotopy method for solving nonsmooth equation reformulation of bounded box constrained variational inequality problem VIP(l,u,F$l,u,F$) is given. Without any monotonicity condition on the defining map F$F$, for starting point chosen almost everywhere in Rⁿ$R^n$, existence and convergence of the homotopy pathway are proven. Nevertheless, it is also proven that, if the starting point is chosen to be an interior point of the box, the proposed homotopy method can also serve as an interior point method.     

Asymptotic formulas for the derivatives of probability functions and their Monte Carlo estimations

One of the key problems in chance constrained programming for nonlinear optimization problems is the evaluation of derivatives of joint probability functions of the form P(x)=P(_gp(x,Λ)?_cp,p=1,…,_Nc)$P(x)=\mathbb{P}(g_p(x\text{,}\Lambda )?c_p\text{,}p=1\text{,}\dots \text{,}{N}_c)$. Here x∈R^_Nx$x\in {\mathbb{R}}^{N_x}$ is the vector of physical parameters, Λ∈R^_NΛ$\Lambda \in {\mathbb{R}}^{N_{\Lambda }}$ is a random vector describing the uncertainty of the model, g:R^_Nx×R^_NΛ→R^_Nc$g:{\mathbb{R}}^{N_x}\times {\mathbb{R}}^{N_{\Lambda }}\to {\mathbb{R}}^{N_c}$ is the constraints mapping, and c∈R^_Nc$c\in {\mathbb{R}}^{N_c}$ is the vector of constraint levels. In this paper specific Monte Carlo tools for the estimations of the gradient and Hessian of P(x)$P(x)$ are proposed when the input random vector Λ$\Lambda$ has a multivariate normal distribution and small variances. Using the small variance hypothesis, approximate expressions for the first- and second-order derivatives are obtained, whose Monte Carlo estimations have low computational costs. The number of calls of the constraints mapping g   for the proposed estimators of the gradient and Hessian of P(x)$P(x)$ is only 1+2_Nx+2_NΛ$1+2N_x+2N_{\Lambda }$.     

An Augmented Lagrangian Method for a Class of Inverse Quadratic Programming Problems

We consider an inverse quadratic programming (QP) problem in which the parameters in the objective function of a given QP problem are adjusted as little as possible so that a known feasible solution becomes the optimal one. We formulate this problem as a minimization problem with a positive semidefinite cone constraint and its dual is a linearly constrained semismoothly differentiable (SC¹) convex programming problem with fewer variables than the original one. We demonstrate the global convergence of the augmented Lagrangian method for the dual problem and prove that the convergence rate of primal iterates, generated by the augmented Lagrange method, is proportional to 1/r, and the rate of multiplier iterates is proportional to  $1/\sqrt{r}$ , where r is the penalty parameter in the augmented Lagrangian. As the objective function of the dual problem is a SC¹ function involving the projection operator onto the cone of symmetrically semi-definite matrices, the analysis requires extensive tools such as the singular value decomposition of matrices, an implicit function theorem for semismooth functions, and properties of the projection operator in the symmetric-matrix space. Furthermore, the semismooth Newton method with Armijo line search is applied to solve the subproblems in the augmented Lagrange approach, which is proven to have global convergence and local quadratic rate. Finally numerical results, implemented by the augmented Lagrangian method, are reported.     

High resolution of 2D natural convection in a cavity by the DQ method

In this paper, the differential quadrature method (DQ) is applied to solve the benchmark problem of 2D natural convection in a cavity by utilizing the velocity–vorticity form of the Navier–Stokes equations, which is governed by the velocity Poisson equation, continuity equation and vorticity transport equation as well as energy equation. The coupled equations are simultaneously solved by imposing the vorticity definition at boundary without any iterative procedure. The present model is properly utilized to obtain results in the range of Rayleigh number (10³${10}^3$–10⁷${10}^7$) and H/L$H/L$ aspect ratios varying from 1 to 3. Nusselt numbers computed for 10³?Ra?10⁷${10}^3?\text{<italic>Ra</italic>}?{10}^7$ in a cavity show excellent agreement with the results available in the literature. Additionally, the detailed features of flow phenomena such as velocity, temperature, vorticity, and streamline plots are also delineated in this work. Thus, it is convinced that the DQ method is capable of solving coupled differential equations efficiently and accurately.     

Insensitizing controls with one vanishing component for the Navier–Stokes system

In this paper we prove the existence of insensitizing controls, having one vanishing component, for the local L²$L^2$-norm of the solutions of the Navier–Stokes system. This problem can be recast as a null controllability problem for a nonlinear cascade system. We first prove a controllability result, with controls having one vanishing component, for a linear problem. Then, by means of an inverse mapping theorem, we deduce the controllability for the cascade system.     

A Perturbation approach for an inverse quadratic programming problem

We consider an inverse quadratic programming (QP) problem in which the parameters in both the objective function and the constraint set of a given QP problem need to be adjusted as little as possible so that a known feasible solution becomes the optimal one. We formulate this problem as a linear complementarity constrained minimization problem with a positive semidefinite cone constraint. With the help of duality theory, we reformulate this problem as a linear complementarity constrained semismoothly differentiable (SC¹) optimization problem with fewer variables than the original one. We propose a perturbation approach to solve the reformulated problem and demonstrate its global convergence. An inexact Newton method is constructed to solve the perturbed problem and its global convergence and local quadratic convergence rate are shown. As the objective function of the problem is a SC¹ function involving the projection operator onto the cone of positively semi-definite symmetric matrices, the analysis requires an implicit function theorem for semismooth functions as well as properties of the projection operator in the symmetric-matrix space. Since an approximate proximal point is required in the inexact Newton method, we also give a Newton method to obtain it. Finally we report our numerical results showing that the proposed approach is quite effective.     

Well-posedness of a 3D parabolic–hyperbolic Keller–Segel system in the Sobolev space framework

We investigate global strong solution to a 3-dimensional parabolic–hyperbolic system arising from the Keller–Segel model. We establish the global well-posedness and asymptotic behavior in the energy functional setting. Precisely speaking, if the initial difference between cell density and its mean is small in L²$L^2$, and the ratio of the initial gradient of the chemical concentration and the initial chemical concentration is also small in H¹$H^1$, then they remain to be small in L²×H¹$L^2\times H^1$ for all time. Moreover, if the mean value of the initial cell density is smaller than some constant, then the cell density approaches its initial mean and the chemical concentration decays exponentially to zero as t goes to infinity. The proof relies on an application of Fourier analysis to a linearized parabolic–hyperbolic system and the smoothing effect of the cell density and the damping effect of the chemical concentration.     

A descent method for a reformulation of the second-order cone complementarity problem

Analogous to the nonlinear complementarity problem and the semi-definite complementarity problem, a popular approach to solving the second-order cone complementarity problem (SOCCP) is to reformulate it as an unconstrained minimization of a certain merit function over Rⁿ${\mathbb{R}}^n$. In this paper, we present a descent method for solving the unconstrained minimization reformulation of the SOCCP which is based on the Fischer–Burmeister merit function (FBMF) associated with second-order cone [J.-S. Chen, P. Tseng, An unconstrained smooth minimization reformulation of the second-order cone complementarity problem, Math. Programming 104 (2005) 293–327], and prove its global convergence. Particularly, we compare the numerical performance of the method for the symmetric affine SOCCP generated randomly with the FBMF approach [J.-S. Chen, P. Tseng, An unconstrained smooth minimization reformulation of the second-order cone complementarity problem, Math. Programming 104 (2005) 293–327]. The comparison results indicate that, if a scaling strategy is imposed on the test problem, the descent method proposed is comparable with the merit function approach in the CPU time for solving test problems although the former may require more function evaluations.     

High-order compact solution of the one-dimensional heat and advection–diffusion equations

In this work, we propose a high-order accurate method for solving the one-dimensional heat and advection–diffusion equations. We apply a compact finite difference approximation of fourth-order for discretizing spatial derivatives of these equations and the cubic C¹$C^1$-spline collocation method for the resulting linear system of ordinary differential equations. The cubic C¹$C^1$-spline collocation method is an A-stable method for time integration of parabolic equations. The proposed method has fourth-order accuracy in both space and time variables, i.e. this method is of order O(h⁴,k⁴)$O(h^4\text{,}{k}^4)$. Additional to high-order of accuracy, the proposed method is unconditionally stable which will be proved in this paper. Numerical results show that the compact finite difference approximation of fourth-order and the cubic C¹$C^1$-spline collocation method give an efficient method for solving the one-dimensional heat and advection–diffusion equations.     

The natural Banach space for version independent risk measures

Risk measures, or coherent measures of risk, are often considered on the space L^∞$L^{\infty }$, and important theorems on risk measures build on that space. Other risk measures, among them the most important risk measure–the Average Value-at-Risk–are well defined on the larger space L¹$L^1$ and this seems to be the natural domain space for this risk measure. Spectral risk measures constitute a further class of risk measures of central importance, and they are often considered on some L^p$L^p$ space. But in many situations this is possibly unnatural, because any L^p$L^p$ with p>_p0$p>p_0$, say, is suitable to define the spectral risk measure as well. In addition to that, risk measures have also been considered on Orlicz and Zygmund spaces. So it remains for discussion and clarification, what the natural domain to consider a risk measure is?     

An elementary proof of the Fritz-John and Karush–Kuhn–Tucker conditions in nonlinear programming

In this note we give an elementary proof of the Fritz-John and Karush–Kuhn–Tucker conditions for nonlinear finite dimensional programming problems with equality and/or inequality constraints. The proof avoids the implicit function theorem usually applied when dealing with equality constraints and uses a generalization of Farkas lemma and the Bolzano-Weierstrass property for compact sets.     

Comparisons of Stokes/Oseen/Newton iteration methods for Navier–Stokes equations with friction boundary conditions

In this paper, we make the comparison of Stokes/Oseen/Newton finite element iteration methods for solving the numerical solutions to Navier–Stokes equations with friction boundary conditions which are of the weak form of the variational inequality problem of the second kind. The comparison of these methods is reflected by the finite element error estimates in the energy norm for velocity and L²$L^2$ norm for pressure.     

A simple constraint qualification in convex programming

We introduce and characterize a class of differentiable convex functions for which the Karush—Kuhn—Tucker condition is necessary for optimality. If some constraints do not belong to this class, then the characterization of optimality generally assumes an asymptotic form.We also show that for the functions that belong to this class in multi-objective optimization, Pareto solutions coincide with strong Pareto solutions,. This extends a result, well known for the linear case.Research partly supported by the National Research Council of Canada.