GENERAL INFORMATION

We characterize the convex envelope of a given function f as the unique solution of a convex programming problem. It allows us to build a sequence of convex and polygonal function ^un that converges uniformly to the convex envelope of f.     

A class of quasi-variational inequalities for adaptive image denoising and decomposition

We introduce a class of adaptive non-smooth convex variational problems for image denoising in terms of a common data fitting term and a support functional as regularizer. Adaptivity is modeled by a set-valued mapping with closed, compact and convex values, that defines and steers the regularizer depending on the variational solution. This extension gives rise to a class of quasi-variational inequalities. We provide sufficient conditions for the existence of fixed points as solutions, and an algorithm based on solving a sequence of variational problems. Denoising experiments with spatial and spatio-temporal image data and an adaptive total variation regularizer illustrate our approach.     

Sequential optimality conditions for composed convex optimization problems

Using a general approach which provides sequential optimality conditions for a general convex optimization problem, we derive necessary and sufficient optimality conditions for composed convex optimization problems. Further, we give sequential characterizations for a subgradient of the precomposition of a K-increasing lower semicontinuous convex function with a K-convex and K-epi-closed (continuous) function, where K is a nonempty convex cone. We prove that several results from the literature dealing with sequential characterizations of subgradients are obtained as particular cases of our results. We also improve the above mentioned statements.     

Simplex-inspired algorithms for solving a class of convex programming problems

We consider a class of convex programming problems whose objective function is given as a linear function plus a convex function whose arguments are linear functions of the decision variables and whose feasible region is a polytope. We show that there exists an optimal solution to this class of problems on a face of the constraint polytope of dimension not more than the number of arguments of the convex function. Based on this result, we develop a method to solve this problem that is inspired by the simplex method for linear programming. It is shown that this method terminates in a finite number of iterations in the special case that the convex function has only a single argument. We then use this insight to develop a second algorithm that solves the problem in a finite number of iterations for an arbitrary number of arguments in the convex function. A computational study illustrates the efficiency of the algorithm and suggests that the average-case performance of these algorithms is a polynomial of low order in the number of decision variables. The work of T. C. Sharkey was supported by a National Science Foundation Graduate Research Fellowship. The work of H. E. Romeijn was supported by the National Science Foundation under Grant No. DMI-0355533.     

Duality for location problems with unbounded unit balls

Given an optimization problem with a composite of a convex and componentwise increasing function with a convex vector function as objective function, by means of the conjugacy approach based on the perturbation theory, we determine a dual to it. Necessary and sufficient optimality conditions are derived using strong duality. Furthermore, as special case of this problem, we consider a location problem, where the “distances” are measured by gauges of closed convex sets. We prove that the geometric characterization of the set of optimal solutions for this location problem given by Hinojosa and Puerto in a recently published paper can be obtained via the presented dual problem. Finally, the Weber and the minmax location problems with gauges are given as applications.     

A hierarchy of relaxations for nonlinear convex generalized disjunctive programming

We propose a framework to generate alternative mixed-integer nonlinear programming formulations for disjunctive convex programs that lead to stronger relaxations. We extend the concept of “basic steps” defined for disjunctive linear programs to the nonlinear case. A basic step is an operation that takes a disjunctive set to another with fewer number of conjuncts. We show that the strength of the relaxations increases as the number of conjuncts decreases, leading to a hierarchy of relaxations. We prove that the tightest of these relaxations, allows in theory the solution of the disjunctive convex program as a nonlinear programming problem. We present a methodology to guide the generation of strong relaxations without incurring an exponential increase of the size of the reformulated mixed-integer program. Finally, we apply the theory developed to improve the computational efficiency of solution methods for nonlinear convex generalized disjunctive programs (GDP). This methodology is validated through a set of numerical examples.     

A direct method of linearization for continuous minimax problems

We consider the problem of minimizing a nondifferentiable function that is the pointwise maximum over a compact family of continuously differentiable functions. We suppose that a certain convex approximation to the objective function can be evaluated. An iterative method is given which uses as successive search directions approximate solutions of semi-infinite quadratic programming problems calculated via a new generalized proximity algorithm. Inexact line searches ensure global convergence of the method to stationary points.This work was supported by Project No. CPBP-02.15/2.1.1.     

Primal-dual row-action method for convex programming

We present a primal-dual row-action method for the minimization of a convex function subject to general convex constraints. Constraints are used one at a time, no changes are made in the constraint functions and their Jacobian matrix (thus, the row-action nature of the algorithm), and at each iteration a subproblem is solved consisting of minimization of the objective function subject to one or two linear equations. The algorithm generates two sequences: one of them, called primal, converges to the solution of the problem; the other one, called dual, approximates a vector of optimal KKT multipliers for the problem. We prove convergence of the primal sequence for general convex constraints. In the case of linear constraints, we prove that the primal sequence converges at least linearly and obtain as a consequence the convergence of the dual sequence.The research of the first author was partially supported by CNPq Grant No. 301280/86.     

Convex programming with single separable constraint and bounded variables

In this paper a minimization problem with convex objective function subject to a separable convex inequality constraint “≤” and bounded variables (box constraints) is considered. We propose an iterative algorithm for solving this problem based on line search and convergence of this algorithm is proved. At each iteration, a separable convex programming problem with the same constraint set is solved using Karush-Kuhn-Tucker conditions. Convex minimization problems subject to linear equality/ linear inequality “≥” constraint and bounds on the variables are also considered. Numerical illustration is included in support of theory.     

Generating Convex Polynomial Inequalities for Mixed 0–1 Programs

We develop a method for generating valid convex quadratic inequalities for mixed0–1 convex programs. We also show how these inequalities can be generated in the linear case by defining cut generation problems using a projection cone. The basic results for quadratic inequalities are extended to generate convex polynomial inequalities.     

Uniform duality in semi-infinite convex optimization

We study infinite sets of convex functional constraints, with possibly a set constraint, under general background hypotheses which require closed functions and a closed set, but otherwise do not require a Slater point. For example, when the set constraint is not present, only the consistency of the conditions is needed. We provide hypotheses, which are necessary as well as sufficient, for the overall set of constraints to have the property that there is no gap in Lagrangean duality for every convex objective function defined on ℝⁿ. The sums considered for our Lagrangean dual are those involving only finitely many nonzero multipliers. In particular, we recover the usual sufficient condition when only finitely many functional constraints are present. We show that a certain compactness condition in function space plays the role of finiteness, when there are an infinite number of functional constraints. The author's research has been partially supported by Grant ECS8001763 of the National Science Foundation.     

Descent methods for convex essentially smooth minimization

Consider the problem of minimizing a convex essentially smooth function over a polyhedral set. For the special case where the cost function is strictly convex, we propose a feasible descent method for this problem that chooses the descent directions from a finite set of vectors. When the polyhedral set is the nonnegative orthant or the entire space, this method reduces to a coordinate descent method which, when applied to certain dual of linearly constrained convex programs with strictly convex essentially smooth costs, contains as special cases a number of well-known dual methods for quadratic and entropy (either –logx orx logx) optimization. Moreover, convergence of these dual methods can be inferred from a general convergence result for the feasible descent method. When the cost function is not strictly convex, we propose an extension of the feasible descent method which makes descent along the elementary vectors of a certain subspace associated with the polyhedral set. The elementary vectors are not stored, but generated using the dual rectification algorithm of Rockafellar. By introducing an -complementary slackness mechanism, we show that this extended method terminates finitely with a solution whose cost is within an order of of the optimal cost. Because it uses the dual rectification algorithm, this method can exploit the combinatorial structure of the polyhedral set and is well suited for problems with a special (e.g., network) structure.This work was partially supported by the US Army Research Office Contract No. DAAL03-86-K-0171 and by the National Science Foundation Grant No. ECS-85-19058.     

A survey on the continuous nonlinear resource allocation problem

Our problem of interest consists of minimizing a separable, convex and differentiable function over a convex set, defined by bounds on the variables and an explicit constraint described by a separable convex function. Applications are abundant, and vary from equilibrium problems in the engineering and economic sciences, through resource allocation and balancing problems in manufacturing, statistics, military operations research and production and financial economics, to subproblems in algorithms for a variety of more complex optimization models. This paper surveys the history and applications of the problem, as well as algorithmic approaches to its solution. The most common techniques are based on finding the optimal value of the Lagrange multiplier for the explicit constraint, most often through the use of a type of line search procedure. We analyze the most relevant references, especially regarding their originality and numerical findings, summarizing with remarks on possible extensions and future research.     

A Finite Algorithm for a Class of Nonlinear Multiplicative Programs

The nonconvex problem of minimizing the product of a strictly convex quadratic function and the p-th power of a linear function over a convex polyhedron is considered. Some theoretical properties of the problem, such as the existence of minimum points and the generalized convexity of the objective function, are deepened on and a finite algorithm which solves the problem is proposed.     

Stochastic dual dynamic programming with stagewise-dependent objective uncertainty

We present a new algorithm for solving linear multistage stochastic programming problems with objective function coefficients modeled as a stochastic process. This algorithm overcomes the difficulties of existing methods which require discretization. Using an argument based on the finiteness of the set of possible cuts, we prove that the algorithm converges almost surely. Finally, we demonstrate the practical application of the algorithm on a hydro-bidding example with the spot-price modeled as an auto-regressive process.     

A Global Optimization Method for Solving Convex Quadratic Bilevel Programming Problems

We use the merit function technique to formulate a linearly constrained bilevel convex quadratic problem as a convex program with an additional convex-d.c. constraint. To solve the latter problem we approximate it by convex programs with an additional convex-concave constraint using an adaptive simplicial subdivision. This approximation leads to a branch-and-bound algorithm for finding a global optimal solution to the bilevel convex quadratic problem. We illustrate our approach with an optimization problem over the equilibrium points of an n-person parametric noncooperative game.     

Parametric Disjunctive Programming: One-Sided Differentiability of the Value Function

We consider a countable family of one-parameter convex programs and give sufficient conditions for the one-sided differentiability of its optimal value function. The analysis is based on the Borwein dual problem for a family of convex programs (a convex disjunctive program). We give conditions that assure stability of the situation of perfect duality in the Borwein theory.For the reader's convenience, we start with a review of duality results for families of convex programs. A parametric family of dual problems is introduced that contains the dual problems of Balas and Borwein as special cases. In addition, a vector optimization problem is defined as a dual problem. This generalizes a result by Helbig about families of linear programs.     

Complete characterizations of stable Farkas’ lemma and cone-convex programming duality

We establish necessary and sufficient conditions for a stable Farkas’ lemma. We then derive necessary and sufficient conditions for a stable duality of a cone-convex optimization problem, where strong duality holds for each linear perturbation of a given convex objective function. As an application, we obtain stable duality results for convex semi-definite programs and convex second-order cone programs. The authors are grateful to the referees for their valuable suggestions and helpful detailed comments which have contributed to the final preparation of the paper. The first author was supported by the Australian Research Council Linkage Program. The second author was supported by the Basic Research Program of KOSEF (Grant No. R01-2006-000-10211-0).     

Convex approximations to sparse PCA via Lagrangian duality

We derive a convex relaxation for cardinality constrained Principal Component Analysis (PCA) by using a simple representation of the L₁ unit ball and standard Lagrangian duality. The resulting convex dual bound is an unconstrained minimization of the sum of two nonsmooth convex functions. Applying a partial smoothing technique reduces the objective to the sum of a smooth and nonsmooth convex function for which an efficient first order algorithm can be applied. Numerical experiments demonstrate its potential.     

Convergence analysis of a proximal point algorithm for minimizing differences of functions

Several optimization schemes have been known for convex optimization problems. However, numerical algorithms for solving nonconvex optimization problems are still underdeveloped. A significant progress to go beyond convexity was made by considering the class of functions representable as differences of convex functions. In this paper, we introduce a generalized proximal point algorithm to minimize the difference of a nonconvex function and a convex function. We also study convergence results of this algorithm under the main assumption that the objective function satisfies the Kurdyka–?ojasiewicz property.