Stochastic multiobjective problems with complementarity constraints and applications in healthcare management

We consider a class of stochastic multiobjective problems with complementarity constraints (SMOPCCs) in this paper. We derive the first-order optimality conditions including the Clarke/Mordukhovich/strong-type stationarity in the Pareto sense for the SMOPCC. Since these first-order optimality systems involve some unknown index sets, we reformulate them as nonlinear equations with simple constraints. Then, we introduce an asymptotic method to solve these constrained equations. Furthermore, we apply this methodology results to a patient allocation problem in healthcare management.     

Unconstrained minimization approaches to nonlinear complementarity problems

The nonlinear complementarity problem can be reformulated as unconstrained minimization problems by introducing merit functions. Under some assumptions, the solution set of the nonlinear complementarity problem coincides with the set of local minima of the corresponding minimization problem. These results were presented by Mangasarian and Solodov, Yamashita and Fukushima, and Geiger and Kanzow. In this note, we generalize some results of Mangasarian and Solodov, Yamashita and Fukushima, and Geiger and Kanzow to the case where the considered function is only directionally differentiable. Some results are strengthened in the smooth case. For example, it is shown that the strong monotonicity condition can be replaced by the P-uniform property for ensuring a stationary point of the reformulated unconstrained minimization problems to be a solution of the nonlinear complementarity problem. We also present a descent algorithm for solving the nonlinear complementarity problem in the smooth case. Any accumulation point generated by this algorithm is proved to be a solution of the nonlinear complementarity under the monotonicity condition.     

The SC property of an expected residual function arising from stochastic complementarity problems

The stochastic nonlinear complementarity problem has been recently reformulated as an expected residual minimization problem which minimizes an expected residual function defined by an NCP function. In this work, we show that the expected residual function defined by the Fischer–Burmeister function is an function.     

Box-constrained minimization reformulations of complementarity problems in second-order cones

Reformulations of a generalization of a second-order cone complementarity problem (GSOCCP) as optimization problems are introduced, which preserve differentiability. Equivalence results are proved in the sense that the global minimizers of the reformulations with zero objective value are solutions to the GSOCCP and vice versa. Since the optimization problems involved include only simple constraints, a whole range of minimization algorithms may be used to solve the equivalent problems. Taking into account that optimization algorithms usually seek stationary points, a theoretical result is established that ensures equivalence between stationary points of the reformulation and solutions to the GSOCCP. Numerical experiments are presented that illustrate the advantages and disadvantages of the reformulations. Supported by FAPESP (01/04597-4), CNPq, PRONEX-Optimization, FAEPEX-Unicamp.     

Solution of linear complementarity problems using minimization with simple bounds

We define a minimization problem with simple bounds associated to the horizontal linear complementarity problem (HLCP). When the HLCP is solvable, its solutions are the global minimizers of the associated problem. When the HLCP is feasible, we are able to prove a number of properties of the stationary points of the associated problem. In many cases, the stationary points are solutions of the HLCP. The theoretical results allow us to conjecture that local methods for box constrained optimization applied to the associated problem are efficient tools for solving linear complementarity problems. Numerical experiments seem to confirm this conjecture.This work was supported by FAPESP (grants 90-3724-6 and 91-2441-3), CNPq and FAEP (UNICAMP).     

A note on a quadratic formulation for linear complementarity problems

In this note, we discuss some properties of a quadratic formulation for linear complementarity problems. Projected SOR methods proposed by Mangasarian apply to symmetric matrices only. The quadratic formulation discussed here makes it possible to use these SOR methods for solving nonsymmetric LCPs. SOR schemes based on this formulation preserve sparsity. For proper choice of a free parameter, this quadratic formulation also preserves convexity. The value of the quadratic function for the solution of original LCP is also known.     

Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems

We show that a particular pivoting algorithm, which we call the lexicographic Lemke algorithm, takes an expected number of steps that is bounded by a quadratic inn, when applied to a random linear complementarity problem of dimensionn. We present two probabilistic models, both requiring some nondegeneracy and sign-invariance properties. The second distribution is concerned with linear complementarity problems that arise from linear programming. In this case we give bounds that are quadratic in the smaller of the two dimensions of the linear programming problem, and independent of the larger. Similar results have been obtained by Adler and Megiddo.Research partially funded by a fellowship from the Alfred Sloan Foundation and by NSF Grant ECS82-15361.     

Stochastic Nash equilibrium problems: sample average approximation and applications

This paper presents a Nash equilibrium model where the underlying objective functions involve uncertainty and nonsmoothness. The well-known sample average approximation method is applied to solve the problem and the first order equilibrium conditions are characterized in terms of Clarke generalized gradients. Under some moderate conditions, it is shown that with probability one, a statistical estimator (a Nash equilibrium or a Nash-C-stationary point) obtained from sample average approximate equilibrium problem converges to its true counterpart. Moreover, under some calmness conditions of the Clarke generalized derivatives, it is shown that with probability approaching one exponentially fast by increasing sample size, the Nash-C-stationary point converges to a weak Nash-C-stationary point of the true problem. Finally, the model is applied to stochastic Nash equilibrium problem in the wholesale electricity market.     

Nonlinear complementarity as unconstrained and constrained minimization

The nonlinear complementarity problem is cast as an unconstrained minimization problem that is obtained from an augmented Lagrangian formulation. The dimensionality of the unconstrained problem is the same as that of the original problem, and the penalty parameter need only be greater than one. Another feature of the unconstrained problem is that it has global minima of zero at precisely all the solution points of the complementarity problem without any monotonicity assumption. If the mapping of the complementarity problem is differentiable, then so is the objective of the unconstrained problem, and its gradient vanishes at all solution points of the complementarity problem. Under assumptions of nondegeneracy and linear independence of gradients of active constraints at a complementarity problem solution, the corresponding global unconstrained minimum point is locally unique. A Wolfe dual to a standard constrained optimization problem associated with the nonlinear complementarity problem is also formulated under a monotonicity and differentiability assumption. Most of the standard duality results are established even though the underlying constrained optimization problem may be nonconvex. Preliminary numerical tests on two small nonmonotone problems from the published literature converged to degenerate or nondegenerate solutions from all attempted starting points in 7 to 28 steps of a BFGS quasi-Newton method for unconstrained optimization.Dedicated to Phil Wolfe on his 65th birthday, in appreciation of his major contributions to mathematical programming.This material is based on research supported by Air Force Office of Scientific Research Grant AFOSR-89-0410 and National Science Foundation Grant CCR-9101801.     

Some nonlinear complementarity systems algorithms and applications to unilateral boundary-value problems

Summary We consider an open bounded set and the unilateral Dirichlet problem with one or two obstacles, involving a nonlinear differential operator A. Using the finite affine triangular element method, we discretize the corresponding variational inequalities and obtain the complementarity systems with one or two constraints related to a nonlinear finite-dimensional operator F. In [21], [26], we have constructed monotone algorithms for solving such complementarity systems in the linear case, under the hypothesis: F is a P-matrix with nonpositive off-diagonal elements. In the present, we extend the applicability of the mentioned algorithms to the nonlinear case, under the hypothesis: F is continuous, coercive, off-diagonal antitone P-function in R^N. Moreover when F is a convex differentiable operator we apply the Newton method and a global linearization technique to overcome the numerical difficulties due to the nonlinearity of F. Finally we give some applications involving the pseudo-laplace operator [12] and the glaciology operator [24]. In the case of pseudo-laplace operator and a square configuration of , using an optimal regularity theorem due to El Kolli [7] we obtain also an estimate of the discretization error.     

Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory,algorithms and applications

Over the past decade, the field of finite-dimensional variational inequality and complementarity problems has seen a rapid development in its theory of existence, uniqueness and sensitivity of solution(s), in the theory of algorithms, and in the application of these techniques to transportation planning, regional science, socio-economic analysis, energy modeling, and game theory. This paper provides a state-of-the-art review of these developments as well as a summary of some open research topics in this growing field.The research of this author was supported by the National Science Foundation Presidential Young Investigator Award ECE-8552773 and by the AT&T Program in Telecommunications Technology at the University of Pennsylvania.The research of this author was supported by the National Science Foundation under grant ECS-8644098.     

Stochastic analysis and one minimization problem

We consider the problem of finding the form of a functional of an infinite-dimensional argument for which a certain given expression takes the minimum value for a fixed value of the parameter. The equation obtained for an unknown functional resembles equations with extended stochastic integral.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 46, No. 11, pp. 1568–1571, November, 1994.     

Joint additive Kullback–Leibler residual minimization and regularization for linear inverse problems

For the approximate solution of ill‐posed inverse problems, the formulation of a regularization functional involves two separate decisions: the choice of the residual minimizer and the choice of the regularizor. In this paper, the Kullback–Leibler functional is used for both. The resulting regularization method can solve problems for which the operator and the observational data are positive along with the solution, as occur in many inverse problem applications. Here, existence, uniqueness, convergence and stability for the regularization approximations are established under quite natural regularity conditions. Convergence rates are obtained by using an a priori strategy. Copyright © 2007 John Wiley & Sons, Ltd.     

Moreau-yosida approximation of conditional minimization problems and its limit properties

For a family of conditional minimization problems we obtain a representation of its variational S-limits in terms of pointwise limits of Moreau-Yosida approximations. Bibliography: 4 titles. Translated fromObchyslyuval'na ta Prykladna Matematyka, No. 81, 1997, pp. 62–69.     

A decomposition method for convex minimization problems and its application

1. IntroductionConsider the following special convex programming problem(P) adn{f(~) g(z); Ax = z},where f: Re - (--co, co] and g: Re - (--co, co] are closed proper convex functions andA is an m x n matrix. The Lagrangian for problem (P) is defined by L: Rad x Re x Re -- (~co, co] as follows:L(x, z, y) = f(x) g(z) (y, Ax ~ z), (1.1)where (., .) denotes the inner product in the general sense and 'y is the Lagrangian multiplierassociated with the constraint Ax = z. The augmented L…     

A decomposition-dualization approach for solving constrained convex minimization problems with applications to discretized obstacle problems

Summary In this paper, we shall be concerned with the solution of constrained convex minimization problems. The constrained convex minimization problems are proposed to be transformable into a convex-additively decomposed and almost separable form, e.g. by decomposition of the objective functional and the restrictions. Unconstrained dual problems are generated by using Fenchel-Rockafellar duality. This decomposition-dualization concept has the advantage that the conjugate functionals occuring in the derived dual problem are easily computable. Moreover, the minimum point of the primal constrained convex minimization problem can be obtained from any maximum point of the corresponding dual unconstrained concave problem via explicit return-formulas. In quadratic programming the decomposition-dualization approach considered here becomes applicable if the quadratic part of the objective functional is generated byH-matrices. Numerical tests for solving obstacle problems in ¹ discretized by using piecewise quadratic finite elements and in ² by using the five-point difference approximation are presented.     

Errata: On semidefinite linear complementarity problems

We correct an error in the statement of Theorem 8 in [1]. Received: January 3, 2001 / Accepted: February 26, 2001?Published online May 18, 2001     

Quadratic programming problems and related linear complementarity problems

This paper investigates the general quadratic programming problem, i.e., the problem of finding the minimum of a quadratic function subject to linear constraints. In the case where, over the set of feasible points, the objective function is bounded from below, this problem can be solved by the minimization of a linear function, subject to the solution set of a linear complementarity problem, representing the Kuhn-Tucker conditions of the quadratic problem.To detect in the quadratic problem the unboundedness from below of the objective function, necessary and sufficient conditions are derived. It is shown that, when these conditions are applied, the general quadratic programming problem becomes equivalent to the investigation of an appropriately formulated linear complementarity problem.This research was supported by the Hungarian Research Foundation, Grant No. OTKA/1044.