Solutions and optimality criteria for nonconvex quadratic-exponential minimization problem

This paper presents a set of complete solutions and optimality conditions for a nonconvex quadratic-exponential optimization problem. By using the canonical duality theory developed by the first author, the nonconvex primal problem in n-dimensional space can be converted into an one-dimensional canonical dual problem with zero duality gap, which can be solved easily to obtain all dual solutions. Each dual solution leads to a primal solution. Both global and local extremality conditions of these primal solutions can be identified by the triality theory associated with the canonical duality theory. Several examples are illustrated.     

Bundle Relaxation and Primal Recovery in Unit Commitment Problems. The Brazilian Case

We consider the inclusion of commitment of thermal generation units in the optimal management of the Brazilian power system. By means of Lagrangian relaxation we decompose the problem and obtain a nondifferentiable dual function that is separable. We solve the dual problem with a bundle method. Our purpose is twofold: first, bundle methods are the methods of choice in nonsmooth optimization when it comes to solve large-scale problems with high precision. Second, they give good starting points for recovering primal solutions. We use an inexact augmented Lagrangian technique to find a near-optimal primal feasible solution. We assess our approach with numerical results.     

Models and algorithms for the 2-dimensional cell suppression problem in statistical disclosure control

Lagrangean dualization and subgradient optimization techniques are frequently used within the field of computational optimization for finding approximate solutions to large, structured optimization problems. The dual subgradient scheme does not automatically produce primal feasible solutions; there is an abundance of techniques for computing such solutions (via penalty functions, tangential approximation schemes, or the solution of auxiliary primal programs), all of which require a fair amount of computational effort. We consider a subgradient optimization scheme applied to a Lagrangean dual formulation of a convex program, and construct, at minor cost, an ergodic sequence of subproblem solutions which converges to the primal solution set. Numerical experiments performed on a traffic equilibrium assignment problem under road pricing show that the computation of the ergodic sequence results in a considerable improvement in the quality of the primal solutions obtained, compared to those generated in the basic subgradient scheme. Received February 11, 1997 / Revised version received June 19, 1998?Published online June 28, 1999     

A comparison of alternative c-conjugate dual problems in infinite convex optimization

In this work, we obtain a Fenchel–Lagrange dual problem for an infinite dimensional optimization primal one, via perturbational approach and using a conjugation scheme called c-conjugation instead of classical Fenchel conjugation. This scheme is based on the generalized convex conjugation theory. We analyse some inequalities between the optimal values of Fenchel, Lagrange and Fenchel–Lagrange dual problems and we establish sufficient conditions under which they are equal. Examples where such inequalities are strictly fulfilled are provided. Finally, we study the relations between the optimal solutions and the solvability of the three mentioned dual problems.     

Ergodic,primal convergence in dual subgradient schemes for convex programming,II: the case of inconsistent primal problems

Consider the utilization of a Lagrangian dual method which is convergent for consistent convex optimization problems. When it is used to solve an infeasible optimization problem, its inconsistency will then manifest itself through the divergence of the sequence of dual iterates. Will then the sequence of primal subproblem solutions still yield relevant information regarding the primal program? We answer this question in the affirmative for a convex program and an associated subgradient algorithm for its Lagrange dual. We show that the primal–dual pair of programs corresponding to an associated homogeneous dual function is in turn associated with a saddle-point problem, in which—in the inconsistent case—the primal part amounts to finding a solution in the primal space such that the Euclidean norm of the infeasibility in the relaxed constraints is minimized; the dual part amounts to identifying a feasible steepest ascent direction for the Lagrangian dual function. We present convergence results for a conditional \(\varepsilon \)-subgradient optimization algorithm applied to the Lagrangian dual problem, and the construction of an ergodic sequence of primal subproblem solutions; this composite algorithm yields convergence of the primal–dual sequence to the set of saddle-points of the associated homogeneous Lagrangian function; for linear programs, convergence to the subset in which the primal objective is at minimum is also achieved.     

Some characterizations of robust optimal solutions for uncertain convex optimization problems

In this paper, we consider robust optimal solutions for a convex optimization problem in the face of data uncertainty both in the objective and constraints. By using the properties of the subdifferential sum formulae, we first introduce a robust-type subdifferential constraint qualification, and then obtain some completely characterizations of the robust optimal solution of this uncertain convex optimization problem. We also investigate Wolfe type robust duality between the uncertain convex optimization problem and its uncertain dual problem by proving duality between the deterministic robust counterpart of the primal model and the optimistic counterpart of its dual problem. Moreover, we show that our results encompass as special cases some optimization problems considered in the recent literature.     

Conjugate maps and duality in multiobjective optimization

This paper considers duality in convex vector optimization. A vector optimization problem requires one to find all the efficient points of the attainable value set for given multiple objective functions. Embedding the primal problem into a family of perturbed problems enables one to define a dual problem in terms of the conjugate map of the perturbed objective function. Every solution of the stable primal problem is associated with a certain solution of the dual problem, which is characterized as a subgradient of the perturbed efficient value map. This pair of solutions also provides a saddle point of the Lagrangian map.     

A branch-and-price algorithm for the capacitated facility location problem

The capacitated facility location problem (CFLP) is a well-known combinatorial optimization problem with applications in distribution and production planning. It consists in selecting plant sites from a finite set of potential sites and in allocating customer demands in such a way as to minimize operating and transportation costs. A number of solution approaches based on Lagrangean relaxation and subgradient optimization has been proposed for this problem. Subgradient optimization does not provide a primal (fractional) optimal solution to the corresponding master problem. However, in order to compute optimal solutions to large or difficult problem instances by means of a branch-and-bound procedure information about such a primal fractional solution can be advantageous. In this paper, a (stabilized) column generation method is, therefore, employed in order to solve a corresponding master problem exactly. The column generation procedure is then employed within a branch-and-price algorithm for computing optimal solutions to the CFLP. Computational results are reported for a set of larger and difficult problem instances.     

A general algorithm for solving Generalized Geometric Programming with nonpositive degree of difficulty

In this paper, a general algorithm for solving Generalized Geometric Programming with nonpositive degree of difficulty is proposed. It shows that under certain assumptions the primal problem can be transformed and decomposed into several subproblems which are easy to solve, and furthermore we verify that through solving these subproblems we can obtain the optimal value and solutions of the primal problem which are global solutions. At last, some examples are given to vindicate our conclusions.     

Goal-oriented r-adaptivity based on the evaluation of the physical and material residual

This contribution is concerned with goal–oriented r-adaptivity based on energy minimization principles for the primal and the dual problem. We obtain a material residual of the primal and of the dual problem, which are indicators for non–optimal finite element meshes. For goal–oriented r-adaptivity we have to optimize the mesh with respect to the dual solution, because the error of a local quantity of interest depends on the error in the corresponding dual solution. We use the material residual of the primal and dual problem in order to obtain a procedure for mesh optimization with respect to a local quantity of interest. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Approximate duality for vector quasi-equilibrium problems and applications

In this paper, we introduce new versions of ?-dual problems of a vector quasi-equilibrium problem with set-valued maps, and we give an ?-duality result between approximate solutions of the primal and dual problems. As the first application of the main result, we obtain an ?-duality for a vector quasi-equilibrium problem whose ?-solutions are understood in the sense of proper efficiency. The second application is devoted to an?-duality for a vector optimization problem with set-valued maps.     

On the behavior of the homogeneous self-dual model for conic convex optimization

There is a natural norm associated with a starting point of the homogeneous self-dual (HSD) embedding model for conic convex optimization. In this norm two measures of the HSD model's behavior are precisely controlled independent of the problem instance: (i) the sizes of ɛ-optimal solutions, and (ii) the maximum distance of ɛ-optimal solutions to the boundary of the cone of the HSD variables. This norm is also useful in developing a stopping-rule theory for HSD-based interior-point solvers such as SeDuMi. Under mild assumptions, we show that a standard stopping rule implicitly involves the sum of the sizes of the ɛ-optimal primal and dual solutions, as well as the size of the initial primal and dual infeasibility residuals. This theory suggests possible criteria for developing starting points for the homogeneous self-dual model that might improve the resulting solution time in practice. This research has been partially supported through the MIT-Singapore Alliance.     

Vector duality for convex vector optimization problems by means of the quasi-interior of the ordering cone

We define weakly minimal elements of a set with respect to a convex cone by means of the quasi-interior of the cone and characterize them via linear scalarization, generalizing the classical weakly minimal elements from the literature. Then we attach to a general vector optimization problem, a dual vector optimization problem with respect to (generalized) weakly efficient solutions and establish new duality results. By considering particular cases of the primal vector optimization problem, we derive vector dual problems with respect to weakly efficient solutions for both constrained and unconstrained vector optimization problems and the corresponding weak, strong and converse duality statements.     

Experiments with primal - dual decomposition and subgradient methods for the uncapacitatied facility location problem

For optimization problems that are structured both with respect to the constraints and with respect to the variables, it is possible to use primal–dual solution approaches, based on decomposition principles. One can construct a primal subproblem, by fixing some variables, and a dual subproblem, by relaxing some constraints and king their Lagrange multipliers, so that both these problems are much easier to solve than the original problem. We study methods based on these subproblems, that do not include the difficult Benders or Dantzig-Wolfe master problems, namely primal–dual subgradient optimization methods, mean value cross decomposition, and several comtbinations of the different techniques. In this paper, these solution approaches are applied to the well-known uncapacitated facility location problem. Computational tests show that some combination methods yield near-optimal solutions quicker than the classical dual ascent method of Erlenkotter     

SOP: parallel surrogate global optimization with Pareto center selection for computationally expensive single objective problems

This paper presents a canonical dual approach for solving a nonconvex global optimization problem governed by a sum of 4th-order polynomial and a log-sum-exp function. Such a problem arises extensively in engineering and sciences. Based on the canonical duality–triality theory, this nonconvex problem is transformed to an equivalent dual problem, which can be solved easily under certain conditions. We proved that both global minimizer and the biggest local extrema of the primal problem can be obtained analytically from the canonical dual solutions. As two special cases, a quartic polynomial minimization and a minimax problem are discussed. Existence conditions are derived, which can be used to classify easy and relative hard instances. Applications are illustrated by several nonconvex and nonsmooth examples.     

约束向量优化问题的Fenchel-Lagrange对偶及鞍点

The aim of this paper is to apply a perturbation approach to deal with Fenchel- Lagrange duality based on weak efficiency to a constrained vector optimization problem. Under the stability criterion, some relationships between the solutions of primal problem and the Fenchel-Lagrange duality are discussed. Moreover, under the same condition, two saddle-points theorems are proved.     

Dynamic Network Flow with Uncertain Arc Capacities: Decomposition Algorithm and Computational Results

In a multiperiod dynamic network flow problem, we model uncertain arc capacities using scenario aggregation. This model is so large that it may be difficult to obtain optimal integer or even continuous solutions. We develop a Lagrangian decomposition method based on the structure recently introduced in G.D. Glockner and G.L. Nemhauser, Operations Research, vol. 48, pp. 233–242, 2000. Our algorithm produces a near-optimal primal integral solution and an optimum solution to the Lagrangian dual. The dual is initialized using marginal values from a primal heuristic. Then, primal and dual solutions are improved in alternation. The algorithm greatly reduces computation time and memory use for real-world instances derived from an air traffic control model.     

Aggregation of scale efficiency

In this article we generalize the aggregation theory in efficiency and productivity analysis by deriving solutions to the problem of aggregation of individual scale efficiency measures, primal and dual, into aggregate primal and dual scale efficiency measures of a group (e.g., industry). The new aggregation result is coherent with aggregation framework and solutions that were earlier derived for other related efficiency measures and can be used in practice for estimation of scale efficiency of an industry or other groups of firms within it.     

New approaches for optimizing over the semimetric polytope

The semimetric polytope is an important polyhedral structure lying at the heart of several hard combinatorial problems. Therefore, linear optimization over the semimetric polytope is crucial for a number of relevant applications. Building on some recent polyhedral and algorithmic results about a related polyhedron, the rooted semimetric polytope, we develop and test several approaches, based over Lagrangian relaxation and application of Non Differentiable Optimization algorithms, for linear optimization over the semimetric polytope. We show that some of these approaches can obtain very accurate primal and dual solutions in a small fraction of the time required for the same task by state-of-the-art general purpose linear programming technology. In some cases, good estimates of the dual optimal solution (but not of the primal solution) can be obtained even quicker.     

Analytic solutions for the approximated 1-D Monge–Kantorovich mass transfer problems

This paper mainly investigates the approximation of a global maximizer of the 1-D Monge–Kantorovich mass transfer problem through the approach of nonlinear differential equations with Dirichlet boundary. Using an approximation mechanism, the primal maximization problem can be transformed into a sequence of minimization problems. By applying the canonical duality theory, one is able to derive a sequence of analytic solutions for the minimization problems. In the final analysis, the convergence of the sequence to a global maximizer of the primal Monge–Kantorovich problem will be demonstrated.