Recent Advances in Optimization

We investigate the behavior at infinity of a special dissipative system, which consists of two steepest descent equations coupled by a non-autonomous conservative repulsion. The repulsion term is parametrized in time by an asymptotically vanishing factor. We show that under a simple slow parametrization assumption the limit points, if any, must satisfy an optimality condition involving the repulsion potential. Under some additional restrictive conditions, requiring in particular the equilibrium set to be one-dimensional, we obtain an asymptotic convergence result. Finally, some open problems are listed.

Let Ψ(b, c) be the solution set mapping of a linear parametric optimization problem with parameters b in the right hand side and c in the objective function. Then, given a point x⁰ we search for parameter values b̄ and c̄ as well as for an optimal solution x̄ ∈ Ψ (b̄, c̄) such that ‖x̄ − x⁰‖ is minimal. This problem is formulated as a bilevel programming problem. Focus in the paper is on optimality conditions for this problem. We show that, under mild assumptions, these conditions can be checked in polynomial time.

The present paper studies the following constrained vector optimization problem: min_C f (x), g(x) ∈ −K, h(x) = 0, where f : ℝⁿ → ℝ^m g : ℝⁿ → ℝ^p are C ^1,1 functions, h : ℝⁿ → ℝ^q is C ² function, and C ⊂ ℝ^m and K ⊂ ℝ^p are closed convex cones with nonempty interiors. Two type of solutions are important for the consideration, namely w-minimizers (weakly efficient points) and i-minimizers (isolated minimizers). In terms of the second-order Dini directional derivative second-order necessary conditions a point x ⁰ to be a w-minimizer and second-order sufficient conditions x ⁰ to be an i-minimizes of order two are formulated and proved. The effectiveness of the obtained conditions is shown on examples.

In this work, a notion of cone-subconvexlikeness of set-valued maps on linear spaces is given and several characterizations are obtained. An alternative theorem is also established for this kind of set-valued maps. Using the notion of vector closure introduced recently by Adán and Novo, we also provide, in this framework, an adaptation of the proper efficiency in the sense of Benson for set-valued maps. The previous results are then applied to obtain different optimality conditions for this Benson-vectorial proper efficiency by using scalarization and multiplier rules.

We discuss some ideas for improvement, extension and application of proximal point methods and the auxiliary problem principle to variational inequalities in Hilbert spaces. These methods are closely related and will be joined in a general framework, which admits a consecutive approximation of the problem data including applications of finite element techniques and the ε-enlargement of monotone operators. With the use of a ”reserve of monotonicity” of the operator in the variational inequality, the concepts of weak- and elliptic proximal regularization are developed. Considering Bregman-function-based proximal methods, we analyze their convergence under a relaxed error tolerance criterion in the subproblems. Moreover, the case of variational inequalities with non-paramonotone operators is investigated, and an extension of the auxiliary problem principle with the use of Bregman functions is studied. To emphasize the basic ideas, we renounce all the proofs and sometimes precise descriptions of the convergence results and approximation techniques. Those can be found in the referred papers.

We consider a general system of equilibrium type problems which can be viewed as an extension of Lagrangean primal-dual equilibrium problems. We propose to solve the system by an inexact proximal point method, which converges to a solution under monotonicity assumptions. In order to make the method implementable, we suggest to make use of a dual descent algorithm and utilize gap functions for ensuring satisfactory accuracy of certain auxiliary problems. Some examples of applications are also given.

The paper considers a general multistage stochastic decision problem which contains Markovian decision processes and multistage stochastic programming problems as special cases. The objective functions, the constraint sets and the probability measures are approximated. Making use of the Bellman Principle, (semi) convergence statements for the optimal value functions and the optimal decisions at each stage are derived. The considerations rely on stability assertions for parametric programming problems which are extended and adapted to the multistage case. Furthermore, new sufficient conditions for the convergence of objective functions which are integrals with respect to decision-dependent probability measures are presented. The paper generalizes results by Langen(1981) with respect to the convergence notions, the integrability conditions and the continuity assumptions.

In this paper one generalizes various types of constrained extremism, keeping the Lagrange or Kuhn-Tucker multipliers rule. The context which supports this development is the nonholonomic optimization theory which requires a holonomic or nonholonomic objective function subject to nonholonomic or holonomic constraints. We refined such a problem using two new ideas: the replacement of the point or velocity constraints by a curve selector, and the geometrical interpretation of the Lagrange and Kuhn-Tucker parameters. The classical optimization theory is recovered as a particular case of extremism constrained by a curve selector.

We consider the interior penalty methods based on the logarithmic and inverse barriers. Under the Mangasarian-Fromovitz constraint qualification and appropriate growth conditions on the objective function, we derive computable estimates for the distance from the subproblem solution to the solution of the original problem. Some of those estimates are shown to be sharp.

In this paper, the problem to control a finite string to the zero state in finite time from a given initial state by controlling the state at the two boundary points is considered. The corresponding optimal control problem where the objective function is the L^l-norm of the controls is solved in the sense that the controls that are successful and minimize at the same time the objective function are determined as functions of the initial state.

Among optimal control problems, singular arcs problems are interesting and difficult to solve with indirect methods, as they involve a multi-valued control and differential inclusions. Multiple shooting is an efficient way to solve this kind of problems, but typically requires some a priori knowledge of the control structure. We limit here ourselves to the case where the Hamiltonian is linear with respect to the control u, and primarily use a quadratic (u ²) perturbation of the criterion. The aim of this continuation approach is to obtain an approximate solution that can provide reliable information concerning the singular structure. We choose to use a PL (simplicial) continuation method, which can be more easily adapted to the multi-valued case. We will first present some convergence results regarding the continuation, and then study the numerical resolution of two example problems. All numerical experiments were conducted with the Simplicial package we developed.

A nonlinear elliptic control problem with pointwise control-state constraints is considered. Existence of regular Lagrange multipliers, first-order necessary and and second-order sufficient optimality conditions are derived. The theory is verified by numerical examples.

The aim of this paper is to extend and generalize the known necessary optimality conditions to non-smooth as well as higher-order setting concerning the optimization problem (which is called an abstract control problem) where D is an open set of a Banach space X, U is a nonempty set, and the data fulfill a certain convexity condition which can often be verified in the context of ordinary optimal control problems.

We provide two examples concerning the relaxation properties of a model problem in multidimensional control: , Ω ⊂ ℝ^m, x ∈ W{sk0/1,∞} (Ω, ℝⁿ), Jx(t) ∈ K ⊂ ℝ^nm a. e. where n ≤ 2, m ≤ 2, Jx(t) is the Jacobian of x, and K is a convex body. The first example justifies the use of quasiconvex functions with infinite values in the relaxation process. In the second one, we examinate the relaxation properties of a restricted quasiconvex envelope function ƒ* introduced by Dacorogna/Marcellini.

In this paper we consider autonomous discrete time optimal control problems. We discuss the reduction to finite cost and the representation formula, the existence of optimal solutions on infinite horizon and their structure, and the structure of optimal solutions on finite intervals.

We investigate possibilities to deal with optimal control problems that have special integer restrictions on the time dependent control functions, namely to take only the values of 0 or 1 on given time intervals. A heuristic penalty term homotopy and a Branch and Bound approach are presented, both in the context of the direct multiple shooting method for optimal control. A tutorial example from population dynamics is introduced as a benchmark problem for optimal control with 0 –1 controls and used to compare the numerical results of the different approaches.

Several characterizations of convexity for totally balanced games are presented. As a preliminary result, it is first shown that the core of any subgame of a nonnegative totally balanced game can be easily obtained from the maximum average value (MAV) function of the game. This result is then used to get a characterization of convex games in terms of MAV functions. It is also proved that a game is convex if and only if all of its marginal games are totally balanced.

A new way is presented to define for minimum cost spanning tree (mcst) games the irreducible core, which is introduced by Bird in 1976. The Bird core correspondence turns out to have interesting monotonicity and additivity properties and each stable cost monotonic allocation rule for mcst-problems is a selection of the Bird core correspondence. Using the additivity property an axiomatic characterization of the Bird core correspondence is obtained.

We introduce here a family of mixed coalitional values. They extend the binomial semivalues to games endowed with a coalition structure, satisfy the property of symmetry in the quotient game and the quotient game property, generalize the symmetric coalitional Banzhaf value introduced by Alonso and Fiestras and link and merge the Shapley value and the binomial semivalues. A computational procedure in terms of the multilinear extension of the original game is also provided and an application to political science is sketched.

The restructuring of the gas industry did not so far generate the same modeling activity as in electricity. While the literature of activity in electricity market models is now abundant, it is still rather scant on the gas side. This paper surveys some of the existing models and attempts to take advantage of the wealth of knowledge available in electricity in order to develop relevant models of restructured gas markets. The presentation is in three parts. The first one gives a blueprint of the market architectures inherited from the European and North American gas legislation. It also introduces a prototype optimization model and its interpretation in terms of perfect competition between agents operating on the restructured market. The second part extends the model to the case where marketers have market power. The third part considers more complex issues related to regulation of access to the network and existence of market power with different types of agents. Equilibrium models are commonly formulated as complementarity problems and the same mathematical programming framework is adopted here. Many models are single stage, there are generally easy to formulate and well known computationally. But many phenomena require two stage models that are much more intricate and on which much less is known. The paper is thus also aimed at pinpointing possible avenues for mathematical programming research.

This paper deals with a hard nonlinear biobjective optimization problem: finding the optimal location and design for a new franchised facility within a region where facilities (both of the franchise and not) already exist and compete for the market. The franchisor and the new franchisee both want to maximise their own profit in the market, but these two objectives are in conflict. Customers patronize all the facilities, old and new, proportionally to their attraction to them. Both resulting objective functions are neither convex nor concave. An interval branch and bound method is proposed to obtain an outer approximation of the whole set of efficient solutions. Computational experiments highlight the different kinds of information provided by this method and by a variation of the lexicographic method.

In this paper we describe how robot trajectory planning, using cubic splines to generate the trajectory, can be formulated as standard semi-infinite programming (SIP) problems and efficiently solved by a discretization method. These formulated problems were coded in the publicly available SIPAMPL environment and to allow the codification of these problems a cubic splines dynamic library for AMPL was developed. The discretization method used to solve the formulated problems is implemented in the NSIPS solver and numerical results with four particular problems are shown.

MPCC can be solved with specific MPCC codes or in its nonlinear equivalent formulation (NLP) using NLP solvers. Two NLP solvers - NPSOL and the line search filter SQP - are used to solve a collection of test problems in AMPL. Both are based on SQP (Sequential Quadratic Programming) philosophy but the second one uses a line search filter scheme.

A new algorithm based on filter SQP with line search to solve nonlinear constrained optimization problems is presented. The filter replaces the merit function avoiding the penalty parameter estimation. This new concept works like an oracle estimating the trial approximation of the iterative SQP algorithm. A collection of AMPL test problems is solved by this new code as well as NPSOL and LOQO solvers. A comparative analysis is made - the filter SQP with line search presents good performance.

This paper describes the optimization of an activated sludge system which comprises an aeration tank and a secondary settler. This system is by far the most widely used biological process in wastewater treatment plants. The optimization process is represented as a smooth nonlinear problem with highly nonlinear equality constraints, some linear equality constraints, one inequality constraint and simple bounds, in which the objective is to minimize the total cost associated with the installation and operation of the biological process. We use the software LOQO to solve the problem. Several computational results show that the quality of the effluent, especially in terms of carbonaceous matter, influences directly the cost and the main contribution to the total cost is the air flow, due to the acquirement of the electromechanical equipment and spent energy.