A proximal gradient descent method for the extended second-order cone linear complementarity problem

We consider an extended second-order cone linear complementarity problem (SOCLCP), including the generalized SOCLCP, the horizontal SOCLCP, the vertical SOCLCP, and the mixed SOCLCP as special cases. In this paper, we present some simple second-order cone constrained and unconstrained reformulation problems, and under mild conditions prove the equivalence between the stationary points of these optimization problems and the solutions of the extended SOCLCP. Particularly, we develop a proximal gradient descent method for solving the second-order cone constrained problems. This method is very simple and at each iteration makes only one Euclidean projection onto second-order cones. We establish global convergence and, under a local Lipschitzian error bound assumption, linear rate of convergence. Numerical comparisons are made with the limited-memory BFGS method for the unconstrained reformulations, which verify the effectiveness of the proposed method.     

On strong and weak second-order necessary optimality conditions for nonlinear programming

Second-order necessary optimality conditions play an important role in optimization theory. This is explained by the fact that most numerical optimization algorithms reduce to finding stationary points satisfying first-order necessary optimality conditions. As a rule, optimization problems, especially the high dimensional ones, have a lot of stationary points so one has to use second-order necessary optimality conditions to exclude nonoptimal points. These conditions are closely related to second-order constraint qualifications, which guarantee the validity of second-order necessary optimality conditions. In this paper, strong and weak second-order necessary optimality conditions are considered and their validity proved under so-called critical regularity condition at local minimizers.     

Some Optimization Reformulations of the Extended Linear Complementarity Problem

We consider the extended linear complementarity problem (XLCP) introduced by Mangasarian and Pang [22], of which the horizontal and vertical linear complementarity problems are two special cases. We give some new sufficient conditions for every stationary point of the natural bilinear program associated with XLCP to be a solution of XLCP. We further propose some unconstrained and bound constrained reformulations for XLCP, and study the properties of their stationary points under assumptions similar to those for the bilinear program.     

DC programming approaches for discrete portfolio optimization under concave transaction costs

The paper investigates DC programming and DCA for both modeling discrete portfolio optimization under concave transaction costs as DC programs, and their solution. DC reformulations are established by using penalty techniques in DC programming. A suitable global optimization branch and bound technique is also developed where a DC relaxation technique is used for lower bounding. Numerical simulations are reported that show the efficiency of DCA and the globality of its computed solutions, compared to standard algorithms for nonconvex nonlinear integer programs.     

Nonsmooth optimization reformulations characterizing all solutions of jointly convex generalized Nash equilibrium problems

Generalized Nash equilibrium problems (GNEPs) allow, in contrast to standard Nash equilibrium problems, a dependence of the strategy space of one player from the decisions of the other players. In this paper, we consider jointly convex GNEPs which form an important subclass of the general GNEPs. Based on a regularized Nikaido-Isoda function, we present two (nonsmooth) reformulations of this class of GNEPs, one reformulation being a constrained optimization problem and the other one being an unconstrained optimization problem. While most approaches in the literature compute only a so-called normalized Nash equilibrium, which is a subset of all solutions, our two approaches have the property that their minima characterize the set of all solutions of a GNEP. We also investigate the smoothness properties of our two optimization problems and show that both problems are continuous under a Slater-type condition and, in fact, piecewise continuously differentiable under the constant rank constraint qualification. Finally, we present some numerical results based on our unconstrained optimization reformulation.     

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 lifting method for generalized semi-infinite programs based on lower level Wolfe duality

This paper introduces novel numerical solution strategies for generalized semi-infinite optimization problems (GSIP), a class of mathematical optimization problems which occur naturally in the context of design centering problems, robust optimization problems, and many fields of engineering science. GSIPs can be regarded as bilevel optimization problems, where a parametric lower-level maximization problem has to be solved in order to check feasibility of the upper level minimization problem. The current paper discusses several strategies to reformulate this class of problems into equivalent finite minimization problems by exploiting the concept of Wolfe duality for convex lower level problems. Here, the main contribution is the discussion of the non-degeneracy of the corresponding formulations under various assumptions. Finally, these non-degenerate reformulations of the original GSIP allow us to apply standard nonlinear optimization algorithms.     

Tabu Guided Generalized Hill Climbing Algorithms

This paper formulates tabu search strategies that guide generalized hill climbing (GHC) algorithms for addressing NP-hard discrete optimization problems. The resulting framework, termed tabu guided generalized hill climbing (TG²HC) algorithms, uses a tabu release parameter that probabilistically accepts solutions currently on the tabu list. TG²HC algorithms are modeled as a set of stationary Markov chains, where the tabu list is fixed for each outer loop iteration. This framework provides practitioners with guidelines for developing tabu search strategies to use in conjunction with GHC algorithms that preserve some of the algorithms known performance properties. In particular, sufficient conditions are obtained that indicate how to design iterations of problem-specific tabu search strategies, where the stationary distributions associated with each of these iterations converge to the distribution with zero weight on all non-optimal solutions.     

Expected Value and Sample Average Approximation Method for Solving Stochastic Second-Order Cone Complementarity Problems

In this paper, we consider the stochastic second-order cone complementarity problems (SSOCCP). We first formulate the SSOCCP contained expectation as an optimization problem using the so-called second-order cone complementarity function. We then use sample average approximation method and smoothing technique to obtain the approximation problems for solving this reformulation. In theory, we show that any accumulation point of the global optimal solutions or stationary points of the approximation problems are global optimal solution or stationary point of the original problem under suitable conditions. Finally, some numerical examples are given to explain that the proposed methods are feasible.     

Quasi-Newton acceleration for equality-constrained minimization

Optimality (or KKT) systems arise as primal-dual stationarity conditions for constrained optimization problems. Under suitable constraint qualifications, local minimizers satisfy KKT equations but, unfortunately, many other stationary points (including, perhaps, maximizers) may solve these nonlinear systems too. For this reason, nonlinear-programming solvers make strong use of the minimization structure and the naive use of nonlinear-system solvers in optimization may lead to spurious solutions. Nevertheless, in the basin of attraction of a minimizer, nonlinear-system solvers may be quite efficient. In this paper quasi-Newton methods for solving nonlinear systems are used as accelerators of nonlinear-programming (augmented Lagrangian) algorithms, with equality constraints. A periodically-restarted memoryless symmetric rank-one (SR1) correction method is introduced for that purpose. Convergence results are given and numerical experiments that confirm that the acceleration is effective are presented. This work was supported by FAPESP, CNPq, PRONEX-Optimization (CNPq / FAPERJ), FAEPEX, UNICAMP.     

Convergence Analysis of a Class of Penalty Methods for Vector Optimization Problems with Cone Constraints

In this paper, we consider convergence properties of a class of penalization methods for a general vector optimization problem with cone constraints in infinite dimensional spaces. Under certain assumptions, we show that any efficient point of the cone constrained vector optimization problem can be approached by a sequence of efficient points of the penalty problems. We also show, on the other hand, that any limit point of a sequence of approximate efficient solutions to the penalty problems is a weekly efficient solution of the original cone constrained vector optimization problem. Finally, when the constrained space is of finite dimension, we show that any limit point of a sequence of stationary points of the penalty problems is a KKT stationary point of the original cone constrained vector optimization problem if Mangasarian–Fromovitz constraint qualification holds at the limit point.This work is supported by the Postdoctoral Fellowship of Hong Kong Polytechnic University.     

Necessary and sufficient conditions for weak efficiency in non-smooth vectorial optimization problems

By using the concepts of local cone approximations and K-directional derivatives, we obtain necessary conditions of optimality for the weak efficiency of the vectorial optimization problems with the inequalities and abstract constraints. We introduce the notion of stationary point (weak and strong) and we prove that, under suitable hypotheses of K-invexity, the stationary points are weakly efficient solutions (global).     

Solution of Finite-Dimensional Variational Inequalities Using Smooth Optimization with Simple Bounds

The variational inequality problem is reduced to an optimization problem with a differentiable objective function and simple bounds. Theoretical results are proved, relating stationary points of the minimization problem to solutions of the variational inequality problem. Perturbations of the original problem are studied and an algorithm that uses the smooth minimization approach for solving monotone problems is defined.     

Optimization reformulations of the generalized Nash equilibrium problem using regularized indicator Nikaidô–Isoda function

In this paper, we extend the literature by adapting the Nikaidô–Isoda function as an indicator function termed as regularized indicator Nikaidô–Isoda function, and this is demonstrated to guarantee existence of a solution. Using this function, we present two constrained optimization reformulations of the generalized Nash equilibrium problem (GNEP for short). The first reformulation characterizes all the solutions of GNEP as global minima of the optimization problem. Later this approach is modified to obtain the second optimization reformulation whose global minima characterize the normalized Nash equilibria. Some numerical results are also included to illustrate the behaviour of the optimization reformulations.     

On the solution of bounded and unbounded mixed complementarity problems

A reformulation of the bounded mixed complementarity problem is introduced. It is proved that the level sets of the objective function are bounded and, under reasonableassumptions, stationary points coincide with solutions of the original variationalinequality problem. Therefore, standard minimization algorithms applied to the new reformulation must succeed. This result is applied to the compactification of unboundedmixed complementarity problems     

Inexact restoration method for minimization problems arising in electronic structure calculations

An inexact restoration (IR) approach is presented to solve a matricial optimization problem arising in electronic structure calculations. The solution of the problem is the closed-shell density matrix and the constraints are represented by a Grassmann manifold. One of the mathematical and computational challenges in this area is to develop methods for solving the problem not using eigenvalue calculations and having the possibility of preserving sparsity of iterates and gradients. The inexact restoration approach enjoys local quadratic convergence and global convergence to stationary points and does not use spectral matrix decompositions, so that, in principle, large-scale implementations may preserve sparsity. Numerical experiments show that IR algorithms are competitive with current algorithms for solving closed-shell Hartree-Fock equations and similar mathematical problems, thus being a promising alternative for problems where eigenvalue calculations are a limiting factor.     

Finding preferred subsets of Pareto optimal solutions

Multi-objective optimization algorithms can generate large sets of Pareto optimal (non-dominated) solutions. Identifying the best solutions across a very large number of Pareto optimal solutions can be a challenge. Therefore it is useful for the decision-maker to be able to obtain a small set of preferred Pareto optimal solutions. This paper analyzes a discrete optimization problem introduced to obtain optimal subsets of solutions from large sets of Pareto optimal solutions. This discrete optimization problem is proven to be NP-hard. Two exact algorithms and five heuristics are presented to address this problem. Five test problems are used to compare the performances of these algorithms and heuristics. The results suggest that preferred subset of Pareto optimal solutions can be efficiently obtained using the heuristics, while for smaller problems, exact algorithms can be applied.     

Disjunctive Optimization: Critical Point Theory

In this paper, we introduce the concepts of (nondegenerate) stationary points and stationary index for disjunctive optimization problems. Two basic theorems from Morse theory, which imply the validity of the (standard) Morse relations, are proved. The first one is a deformation theorem which applies outside the stationary point set. The second one is a cell-attachment theorem which applies at nondegenerate stationary points. The dimension of the cell to be attached equals the stationary index. Here, the stationary index depends on both the restricted Hessian of the Lagrangian and the set of active inequality constraints. In standard optimization problems, the latter contribution vanishes.     

On the Use of Augmented Lagrangians in the Solution of Generalized Semi-Infinite Min-Max Problems

We present an approach for the solution of a class of generalized semi-infinite optimization problems. Our approach uses augmented Lagrangians to transform generalized semi-infinite min-max problems into ordinary semi-infinite min-max problems, with the same set of local and global solutions as well as the same stationary points. Once the transformation is effected, the generalized semi-infinite min-max problems can be solved using any available semi-infinite optimization algorithm. We illustrate our approach with two numerical examples, one of which deals with structural design subject to reliability constraints.