改进的ε—次梯度捆集法及其收敛性

提出了一个基于ε－次梯度捆集法的求解非凸非光滑问题的捆集算法,证明了其收敛性,并通过一些较困难的优化问题,验证了算法的计算效率和数值稳定性。     

A new algorithm for solving variational inequalities with application to the traffic assignment problem

The variational inequality problem in Euclidian space is formulated as a nonconvex, nondifferentiable optimization problem. We show that any stationary point is optimal, and we propose a solution algorithm that decreases the nondifferential objective monotonically. Application to the asymmetric traffic assignment problem is considered.Research supported by C.R.S.H. (Canada) grant #410-81-0722-RL and F.C.A.C. (Québec) grant # 83-AS-0026.     

On the convergence of two branch-and-bound algorithms for nonconvex programming problems

This note presents a new convergence property for each of two branch-and-bound algorithms for nonconvex programming problems (Falk-Soland algorithms and Horst algorithms). For each algorithm, it has been shown previously that, under certain conditions, whenever the algorithm generates an infinite sequence of points, at least one accumulation point of this sequence is a global minimum. We show here that, for each algorithm, in fact, under these conditions, every accumulation point of such a sequence is a global minimum.The author would like to thank Professor R. M. Soland for his helpful comments concerning this paper.     

CONVERGENCE OF THE LAX-FRIEDRICHS SCHEME AND STABILITY FOR CONSERVATION LAWS WITH A DISCONTINUOUS SPACE-TIME DEPENDENT FLUX

The authors give the first convergence proof for the Lax-Friedrichs finite differencescheme for non-convex genuinely nonlinear scalar conservation laws of the formu_t f(k(x, t), u)_x = 0,where the coefficient k(x, t) is allowed to be discontinuous along curves in the (x, t)plane. In contrast to most of the existing literature on problems with discontinuouscoefficients, here the convergence proof is not based on the singular mapping approach,but rather on the div-curl lemma (but not the Young measure) and a Lax type en-tropy estimate that is robust with respect to the regularity of k(x, t). Following [14],the authors propose a definition of entropy solution that extends the classical Kruzkovdefinition to the situation where k(x, t) is piecewise Lipschitz continuous in the (x, t)plane, and prove the stability (uniqueness) of such entropy solutions, provided that theflux function satisfies a so-called crossng condition, and that strong traces of the solu-tion exist along the curves where k(x, t) is disco     

On the use of cuts in reverse convex programs

A cutting plane method, using the idea of Tuy cuts, has been suggested in earlier papers as a possible means of solving reverse convex programs. However, the method is fraught with theoretical and numerical difficulties. Stringent sufficient conditions for convergence inn dimensions are given. However, examples of nonconvergence are given and reasons for this nonconvergence are developed. A result of the discussion is a convergent algorithm which combines the idea of the cutting plane method with vertex enumeration procedures in order to numerically improve upon the edge search procedure of Hillestad.     

Nonconvex functions and variational inequalities

In this paper, we study some properties of a class of nonconvex functions, called semipreinvex functions, which includes the classes of preinvex functions and arc-connected convex functions. It is shown that the minimum of an arcwise directionally differentiable semi-invex functions on a semi-invex set can be characterized by a class of variational inequalities, known as variational-like inequalities. We use the auxiliary principle technique to prove the existence of a solution of a variational-like inequality and suggest a novel iterative algorithm.     

On Nash–Cournot oligopolistic market equilibrium models with concave cost functions

We consider Nash–Cournot oligopolistic market equilibrium models with concave cost functions. Concavity implies, in general, that a local equilibrium point is not necessarily a global one. We give conditions for existence of global equilibrium points. We then propose an algorithm for finding a global equilibrium point or for detecting that the problem is unsolvable. Numerical experiments on some randomly generated data show efficiency of the proposed algorithm.     

求一类非凸规划问题全局解的确定性算法

本文对一类非凸规划问题(NP)给出一确定性全局优化算法.这类问题包括:在非凸的可行域上极小化有限个带指数的线性函数乘积的和与差,广义线性多乘积规划,多项式规划等.通过利用等价问题和线性化技巧提出的算法收敛到问题(NP)的全局极小.     

Multi-bang control of elliptic systems

Multi-bang control refers to optimal control problems for partial differential equations where a distributed control should only take on values from a discrete set of allowed states. This property can be promoted by a combination of $L^2$ and $L^0$-type control costs. Although the resulting functional is nonconvex and lacks weak lower-semicontinuity, application of Fenchel duality yields a formal primal-dual optimality system that admits a unique solution. This solution is in general only suboptimal, but the optimality gap can be characterized and shown to be zero under appropriate conditions. Furthermore, in certain situations it is possible to derive a generalized multi-bang principle, i.e., to prove that the control almost everywhere takes on allowed values except on sets where the corresponding state reaches the target. A regularized semismooth Newton method allows the numerical computation of (sub)optimal controls. Numerical examples illustrate the effectiveness of the proposed approach as well as the structural properties of multi-bang controls.     

Fused-MCP With Application to Signal Processing

ABSTRACT

Friedman et al. proposed the fused lasso signal approximator (FLSA) to denoise piecewise constant signals by penalizing the ?₁ differences between adjacent signal points. In this article, we propose a new method, referred to as the fused-MCP, by combining the minimax concave penalty (MCP) with the fusion penalty. The fused-MCP performs better than the FLSA in maintaining the profile of the original signal and preserving the edge structure. We show that, with a high probability, the fused-MCP selects the right change-points and has the oracle property, unlike the FLSA. We further show that the fused-MCP achieves the same l₂ error rate as the FLSA. We develop algorithms to solve fused-MCP problems, either by transforming them into MCP regression problems or by using an adjusted majorization-minimization algorithm. Simulation and experimental results show the effectiveness of our method. Supplementary material for this article is available online.