• Invited Lectures
• 30-min Contributed Lectures
• 20-min Short Communications

Timetable

AUSLENDER, Alfred
Entropic proximal methods

Abstract : We present some new applications of the logarithmic-quadratic proximal kernel introduced for solving variational inequalities and for generating new augmented Lagrangian methods.  These applications concern bundle methods for convex nondifferentiable minimization, projections methods for convex feasibility problems, bloc decomposition methods for linearly constained convex minimization.

Abstract : Many interesting non-smooth functions on Euclidean space are in fact differentiable almost everywhere.  All Lipschitz function have this property, but so do non-Lipschitzian functions such as the spectral abscissa of a matrix.  In practise, the gradient, when it exists, is often easy to compute.  In this talk, we investigate to what extent one can approximate the Clarke subdifferential of such functions by the convex hull of randomly sampled gradients in the neighborhood of a point of interest.  We also show how these ideas can be used to construct successful numerical methods for minimizing non-smooth and potentially non-Lipschitzian objective functions.

Abstract : A new concept of nondominated solutions and a new nonlinear scalarization function are introduced for vector optimization problems with variable domination structures.  Characterizations of nondominated solutions of the vector optimization problems in terms of vector variational inequalities and the scalarization are established.

Abstract : There are several approaches to solving constrained optimization problems in Mathematical Programming. Some of them exploit tools related to properties of the set of constraints (tangent cones, conjugate cones etc.).  Another idea is to reduce the given constrained optimization problem to an unconstrained one.  In such a case, one can use well-developed and powerful methods and algorithms available for unconstrained optimization.

In this direction a very popular and effective is the usage of Lagrange functions (Lagrange multipliers etc.).  This approach enables one to derive necessary (and sometimes) sufficient optimality conditions and, in many cases, to find an optimizer.  However, very often the problem of difining the required Lagrange multipliers becomes quite difficult.  This problem can be overcome by employing Exact Penalty functions.  Unfortunately, the exact penalty functions are often nonsmooth.  Nevertheless, the present development of Nonsmooth Analysis makes it possible to recommend the exact penalization for practical purposes.  It is important to find a proper penalty function.

The above considerations are even more important and acute for solving the problems of Optimal Control and Calculus of Variations.  In the lecture it is demonstrated how to reformulate the classical variational and control problems by means of exact penalization as unconstrained optimization problems.  It is shown that most known necessary conditions can be stated by considering the related unconstrained problems.  An important advantage of such an approach is the possibility to construct numerical algorithms.

Abstract : The Barzilai Borwein method is a steepest descent method for unconstrained optimization that differs from the usual steepest descent method in the way that the step length is chosen.  Recent research has shown that it is competitive with conjugate gradients and has some advantages in certain situations.  It is capable of solving problems of $10^6$ variables arising from elliptic 3D pdes in reasonable time.  A feature of the method is its non-monotonic progress, which requires the use of a non-monotonic line search when solving non-quadratic problems.  The talk will review the current state of the art and point to some open questions.

Abstract : We first give a short review on some proximal-like methods for the solution of convex programs.  These proximal-like methods have nice global convergence properties under very mild assumptions.  However, in case of a constrained problem, they require knowledge of a strictly feasible starting point.  However, finding such a starting point is sometimes difficult. Moreover, such a strictly feasible point may not exist.

The algorithm proposed in this talk is an infeasible proximal-like method.  It allows infeasible iterates and does not need the assumption that the underlying optimization problem satisfies a Slater-type condition.  We establish global convergence of the proposed algorithm under appropriate assumptions.  Furthermore, it is planned to illustrate the numerical behaviour of the algorithm on some examples from optimal control.

(This talk is partially based on joint work with Nobuo Yamashita, Tomoyuki Morimoto, and Masao Fukushima.)

Abstract : Many inverse problems in Optics give rise to interesting optimization problems.  Some of them will be described in this talk.  The direct problems will be described, which is generally based in Maxwell equations, boundary conditions and sparse techniques for solving linear systems.  This problem involves multilayer structures.  One inverse problem is to determine the thickness of each layer that allows one to obtain a "desired" or "observed" optical response.  Different mathematical formulations for this problem will be given.  These formulations lead one to bilevel optimization problems and to the minimization of discontinuous functions.  Adequate algorithms will be described and smoothing techniques for dealing with discontinuities.  According to this, the inexact-restoration technique will be reviewed.  Recent improvements in box-constrained minimization will also be commented.Inexact restoration: advances and perspectives

Abstract : For details, please click here.

Abstract : There are classes of optimal control problems, with either ODE or PDE dynamics, such as two-point boundary value problems, for which the function and derivative values of the explicitly discretized problems, via Runge-Kutta or FEM methods, have to be approximated by the outcome of $N$ iterations of a solver.  Consequently, the disretization of these problems is controlled by {\em two} parameters: the mesh size and the number of iterations of the solver.

In our earlier work, we find a theory for solving optimization problems that require discretizations.  It deals with two situations.  In the first, which is referred to as that of {\em consistent approximations}, it is assumed that an infinite dimensional optimization problem can be suitably approximated by a family of progressively higher dimensional optimization problems.  In this case, strategies, in the form of algorithm models, are presented for "diagonalizing" the solution process.  In the second situation, it is assumed that numerical solution of the dynamic equations does not result in a family of finite dimensional consistent approximations (e. g., when implicit integration methods are used).  For this case, the theory provides models for the implementation of {\em conceptual} algorithms.  Unfortunately, neither of these situations envisions the possibility of two discretization parameters.

In this paper we present new algorithm models that can be used with two discretization parameters.  The first one controlling the mesh size of an explicit integration scheme, and the second one controlling the precision with which functions and gradients associated with a fixed mesh size are computed.  The result can be seen as a framework of {\em quasi consistent approximations}.

We implemented these new algorithm models using an approximate steepest descent method for the solution of two problems:  a two point boundary value problem where the linear system corresponding to the ODE is solved approximately only, and a distributed control problem in which the discretized dynamics are solved using a Domain Decomposition algorithm which can be implemented on parallelized computers.  Our numerical results show that these new algorithms perform quite well and are fairly insensitive to the selection of user-set parameters.  Also, they appear to be superior to some alternative, {\em ad hoc}
schemes.

Abstract : For details, please click here.

Abstract : Interior-point methods (IPMs) for linear optimization (LO) can use small or large updates of the barrier parameter. Contrary to theoretical results, large-update IPMs are more efficient in practice than  small-update IPMs.  In this talk we partially close this gap between theory and practice.  The extension to semidefinite optimization is almost straightforward.

Speaker: Kees Roos, ITS/TWI/SSOR, TU Delft, Mekelweg 4, 2628 CD Delft, The Netherlands,
E-mail: C.Roos@its.tudelft.nl, Phone: +31 15 278 2530, Fax: +31 15 278 7255.

Co-authors: Jiming Peng, ITS/TWI/SSOR, TU Delft, Mekelweg 4, 2628 CD Delft, The Netherlands,
E-mail: J.Peng@its.tudelft.nl, Phone: +31 15 278 7271, Fax: +31 15 278 7255.
Tamás Terlaky, Department of Computing and Software, McMaster University Hamilton, Ontario, Canada, L8S 4L7,
E-mail: terlaky@cas.mcmaster.ca, Phone: +1-905 525-9140, Fax: +1-905 524-0340.

Abstract : Many problems of data classification (both supervised and unsupervised) can be reduced to unconstrained optimization of saw-tooth functions, which are expressed as the sum or the maximum of a large number (some hundreds or even thousands) of fairly simple terms.  These functions have very many shallow local minimizers, which are very close each to other.  We discuss the bundle Cutting Angle Method – Discrete Gradient Method, which has been applied for solving these problems.  The local derivative-free Discrete  Gradient Method, which is  based on the quasidifferential, allows one to jump over many shallow local minima and to find a fairly deep local minimizer.  Using the global Cutting Angle Method one can leave this minimizer and start a local search again.

Abstract : We report on some recent results on the existence of a solution for vector equilibrium problems under generalized convexity and generalized monotonicity assumptions.  The results were obtained jointly with M.Bianchi and N.Hadjisavvas.  In a second part we introduce the system of vector equilibrium problems and establish existence of a solution under generalized convexity assumptions.  As an application we obtain an existence result for Nash equilibrium problems with vector-valued functions.  This is joint work with Q.H.Ansari and J.C.Yao.

Abstract : The lecture introduces a class of optimization methods that have been invented by engineers to solve mechanical structural design problems and that are in practical use since many years.  They are based on a successive convex approximation of the original nonlinear programming problem and are called sequential convex programming or SCP methods.  It turns out that these methods are very efficient for certain classes of problems.  They  can be extended to very large nonlinear optimization problems, if the convex and separable subproblems are solved by an interior point algorithm.

The methods are analysed and their theoretical and numerical properties are compared to that of the well-known sequential quadratic programming algorithms (SQP).  These algorithms are also widely used in mechanical engineering, but are general purpose methods in the sense that any model dependent features are not exploited.  It is shown that both methods can be treated in the same way when introducing a line search to stabilize the algorithm, i.e. to enforce convergence even from bad initial values.

Some industrial applications are presented which are typical for the corresponding class of algorithms.  We show how the total weight of a cruise ship is reduced, and how very large topology optimization problems can be solved by SCP methods.  SQP methods are preferred for small dimensional, highly nonlinear problems, where evaluation of model functions and gradients is expensive. Industrial applications presented, are the design of satellite antennas and electro-acustic filters, and the control of tubular reactors.

Abstract : Consider minimization of an objective function f(x) subject to the constraint that  the image of a mapping G(x) belongs to a convex cone K.  First order optimality conditions for such problems can be formulated in a form of variational inequality. Second order optimality conditions and sensitivity analysis of such optimization problems involve an additional term associated with the curvature of the cone K.  The analysis is based on duality theory of optimization problems and cannot be easily extended to variational inequalities.  In this talk we discuss a reduction approach which allows to deal with that problem. In particular, it applies to semi-definite programming problems.

Abstract : We review basic results on ABS methods for linear systems and optimization, including recent results on Diophantine systems, inequalities and integer LP problems (the ABS approach provides a generalization to systems of the classical Euclides/Diophantus/Euler existence condition for integer solutions and a large class of solution methods).  We discuss the performance of the package ABSPACK for linear and nonlinear equations and optimization under development.

Abstract : Recent development in semidefinite optimization provides an interesting source for the study of semismooth matrix-valued equations.  For example, let $X$ and $Y$ be symmetric real matrices and let $[X-Y]_+$ be the projection of $X-Y$ onto the cone of positive semidefinite matrices.  Tseng has shown that the complementarity condition $$X, Y\succeq0, XY=0$$ is equivalent to the matrix-valued equation $$X-[X-Y]_+=0, $$ where $X, Y\succeq0$ means that $X$ and $Y$ are positive semidefinite.  Thus, if the function $[X-Y]_+$ is semismooth (definition will be given in the talk), then it is possible to design a Newton's method for the matrix complementarity problem.  The speaker will give a brief introduction to the development of Newton's method for semismooth equations and present some recent results on semismooth matrix-valued equations.

Abstract : We discuss primal-dual interior-point methods for semidefinite programming and related problems, and the SDPT3 code of Toh, Tutuncu, and Todd.  We provide some computational results for semidefinite programming problems from SDPLIB and some SQL (semidefinite-quadratic-linear) programming problems from a recent DIMACS challenge.

Abstract : The simplest and earliest example of an interior point algorith for linear programming is the affine scaling algorithm of Dikin.  This algorithm has been much studied and readily extends to (nonconvex) quadratic programs (QP).  However, little is known is about its behavior on nonconvex QP, even in the case of box constraints.  We will present new results on the convergence and rate of convergence of the generated iterates and optimality properties of the limit points.  We will also discuss a branch-and-bound strategy for finding global minimum in the case of box constraints.
[The second part of the talk is based on a joint work with Yinyu Ye.]

Abstract : We introduce a type of complementarity problems posed over a measure space.  Some examples of its applications are given.  We give some conditions under which there exists a solution for the problem.  Several algorithms for its solution are described and convergence results for these algorithms are derived.

Abstract : A resource allocation model (RAM) of a not-for-profit organization in the framework of Data Envelopment Analysis (DEA) was introduced by Zhang and Cui.  The model is an inverse formulation to the DEA model, as it is pointed in Wei, Zhang's paper, and can be transformed into a parametric linear programming problem or a multi-objective programming problem to solve when the efficiency index of the discussed organization is less than one. In this paper, inadequacy of the original RAM model is discussed and an improved model then is presented.  The new model can be transformed into a multi-objective programming problem or a linear programming problem for any efficiency index value of the organization.

Key words : resource allocation model, Data Envelopment Analysis, prediction model, not-for-profit organizations, multi-objective programming.

BONNEL, Henri
Relations Between Almost Pareto and Almost Kuhn-Tucker in Vector Opimization

Abstract : For details, please click here.

Abstract : In this paper we consider a parametric family of linear inequality systems, in the Euclidean space, with a same fixed index set T, and with the parameter running over a separable metric space.  In this context, T is assumed to be an arbitrary infinite set (with no topological structure).  The coefficient vectors present a continuous dependence on the parameter, while the dependence on the index has no particular property.  In the paper the possibility of solving a nominal system by means of sequences of finite subsystems associated to proximal parameters is analyzed by considering a double parameter: the original one and the own finite subset of indices.  The role played by the lower semicontinuity (lsc) of the feasible set mapping along this process is also studied.  In a first stage, we prove that the lsc of the original feasible set mapping at a nominal parameter is equivalent to the same property for the feasible set mapping associated to a suitably chosen countable subset of T,  (note that, as a last resort, the process only considers a countable amount of constraints).  In order to consider the double parameter space a metric space, we define a distance in the set of finite and non-empty subsets of N (set of all natural numbers), entailing desirable properties in relation to the approximation theory of infinite systems by finite ones.

Co-authors: M. A. López and J. Parra.

Abstract : For details, please click here.

Abstract : The Barzilai and Borwein gradient method does not guarantee descent in the objective function, but performs better than the classical steepest-descent method in practical computations.  Combined with the technique of nonmonotone line search etc., such a method has found successful applications in unconstrained optimization, convex constrained optimization and stochastic optimization.  In this paper, we propose a new gradient method that uses the steepest-descent stepsize and the Barzilai-Borwein stepsize alternatively.  Hence the name "alternative stepsize gradient method".  Convergence-rate of this method is analyzed in this paper.  For quadratics, the method is shown to be much faster than the Barzilai and Borwein gradient method.  Our numerical experiments also demonstrated its efficiency for general objective functions.

Abstract : A simplicial algorithm for computing an integer point of a class of polytopes is proposed in this paper.  The algorithm subdivides the space into integer simplices and assigns to each point of the space an integer label out of 0, 1, …, n+1.  The algorithm starts at an arbitrary integer point and follows a path that either leads to an integer point of the polytope or proves that no such point exists.  Numerical results show that the algorithm is efficient.

Abstract : A second order subderivative of a nonsmooth function $f: \Re^n \to \overline{\Re}$ may be arrived at by taking some tangent or normal cone $C_{\mbox{\small Graph}\, \partial f}(x,y)$ at a point $(x,y)$ in the graph of a subdifferential $\partial f$.  Using this as the graph of a set valued mapping $D(\partial f)(x,y)$ this leads to a theory which appears to be quite unrelated to notions of symmetric operators, except for the case when $f$ is actually a smooth function.  On the other hand the subjet and limiting subhessians from viscosity theory naturally lead to convex sets of symmetric operators.

To relate such notions one could look for a set $\cal A$ of symmetric operators to generate this set valued mapping via $$D(\partial f)(x,y)(h)=\{Qh \mid  Q \in {\cal A} \}$$ It is well known that this is not possible, except in the most trivial cases.  Despite this we find that in certain directions it is possible to look for a convex set $\cal A$ of symmetric operators which rank one select from such second order subdifferentials in the following sense.  Let $$E({\cal A},h):=\{Q \in {\cal A} \mid q({\cal A})(h)=\langle Q, hh^t \rangle \}\quad  \mbox{where }\quad q({\cal A})(h):=\sup \{ \langle Q, hh^t \rangle \mid Q \in {\cal A} \}$$ be respectively the rank one exposed points of ${\cal A}$ and its rank one support (here $\langle Q, hh^t \rangle$ denotes the Frobenius inner product with a rank one form).  Then we consider when $$\{ z = Q h \mid Q \in E({\cal A}, h) \}\subseteq D(\partial f)(x,y)(h)\mbox{ .}$$  Indeed when we take $h$ to be a direction at which the subjet is supported, in a rank one sense, by the second order lower Dini--directional derivative, this may be quite generally achieved when  ${\cal A}= \partial^{2,-}f(x,y)$ (the subjet) and we take $C_{\mbox{\small Graph}\, \partial_p f}$ to be the contingent cone to the graph of the proximal subdifferential $\partial_p f$.  Under a prox-regularity assumption we are able to use these observations to explore the symmetry properties of coderivative as introduced by R.T. Rockafellar and Zagrondy and establish an number of new inclusions.

Finally we consider the case when $C_{\mbox{\small Graph}\, \partial f}$ is  the Clarke tangent cone to the graph of the basic subdifferential $\partial f$ and ${\cal A}=(\partial^2 f(x,y))^1$, the rank one hull of the limiting subhessians of $f$.  Via the characterization of the rank one support of the limiting subhessians we are able to obtain a similar inclusion for prox-regular functions.  If time permits an application to viscosity solutions will be discussed.

Abstract : A class of trust-region algorithms is suggested and applied to complementarity problems reformulated as minimization problems. By particular scaling techniques the subproblems are solved exactly and efficiently (exploiting sparsity).  Numerical results will be reported as well.

(Author(speaker): Andreas Fischer, University of Dortmund, Germany and
Co-Author: Christian Frost, University of Dortmund, Germany)

Abstract : For details, please click here.

Abstract : Complementarity and related problems can be solved via smooth bound constrained optimization.  We discuss the important features involved in this strategy and present computational results that show that this approach is efficient and encourage the use of available optimization software for these problems.

Authors:
         Mituhiro Fukuda, Dept. Mathematical and Computing Sciences, Tokyo Institute of Technology;
         Masakazu Kojima, Dept. Mathematical and Computing Sciences, Tokyo Institute of Technology;
         Kazuo Murota, Research Institute for Mathematical Sciences, Kyoto University;
         Satoshi Nakamura, Dept. Mathematical and Computing Sciences, Tokyo Institute of Technology;
         Kazuhide Nakata, Dept. Applied Physics, The University of Tokyo;

Abstract : Positive (semi)definite matrix completion theory allows to solve sparse semidefinite programs (SDPs) by primal-dual interior-point methods in an elegant and efficient manner [1,2]. In particular, the conversion method proposed in these papers converts sparse SDPs in a more compact and equivalent SDP which can be solved faster by any existing software.  We will present several heuristic procedures, which involve the problem structure (chordal graphs, clique trees) and computational cost, in order to obtain an equivalent SDP which can be solved efficiently.  Some numerical experiments on sparse SDPs are included.

[1] M. Fukuda, M. Kojima, K. Murota and K. Nakata, "Exploiting sparsity in semidefinite programming via matrix completion I: General framework", SIAM Journal on Optimization 11 (2000) pp. 647-674.

[2] K. Nakata, K. Fujisawa, M. Fukuda, M. Kojima and K. Murota, "Exploiting sparsity in semidefinite programming via matrix completion II: Implementation and numerical results", Research Report, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, 2-12-1 Oh-Okayama, Meguro, Tokyo 152-8552 Japan, February 2001.

Abstract : This talk deals with systems of an arbitrary number of weak linear inequalities posed on finite dimensional spaces. First, we consider the characterisation of different elements of the solution set of such kind of systems (as the dimension, the absolute and relative boundary and its facial structure), and we sketch some applications to linear semi-infinite programming (LSIP).  Most of  the mentioned desirable properties are only valid for certain classes of linear semi-infinite systems.  Thus, two challenging theoretical problems naturally arise: 1.  Find the class of closed convex sets which can be represented by means of a given family of linear semi-infinite systems.  2.  Find the family of  linear semi-infinite systems that represent a given class of closed convex sets.

Some results concerning these problems are established and some LSIP applications are shown.  The last part of  the talk deals with linear inequality systems containing strict inequalities, whose solution sets are the so-called evenly convex sets.  For this class of sets, new properties are established whose geometric and optimization applications are also discussed.

Abstract : Given a real $n\times n$  matrix $A$, we consider the corresponding Lyapunov and Stein transformations $L_A(X):=AX+XA^T$ and $S_A(X):=X-AXA^T$ defined on the space of all real symmetric $n\times n$ matrices.  These transformations appear in the study of continuous and discrete dynamical systems.  In this talk, we describe (semidefinite) complementarity properties of $L_A$ and $S_A$, specifically addressing  $P$, GUS, nondegenerate, and monotone properties.

Abstract : In this talk we review and extend recent results on existence (see [1,2]) and discretization by Galerkin's method
for pseudomonotone variational inequalities, thus generalizing earlier results [3] to a larger class of problems.

References :
[1] Hadjisavvas, Nicolas; Schaible, Siegfried: Quasimonotonicity and pseudomonotonicity in variational inequalities and
equilibrium problems. In: Crouzeix, Jean-Pierre (ed.) et al., Generalized convexity, generalized monotonicity: recent results.
Nonconvex Optim. Appl. 27, 257-275 (1998)
[2] Gwinner, J.: A note on pseudomonotone functions, regularization, and relaxed coerciveness. Nonlinear Anal., Theory Methods Appl. 30,4217-4227 (1997)
[3] Gwinner, J.: A discretization theory for monotone semicoercive problems and finite element convergence for p-harmonic Signorini problems, Z. Angew. Math. Mech. 74, 417 - 427 (1994)

Absract : Given a Banach space $X$, a pseudomonotone map in the sense of Karamardian is a multivalued map $A:X\rightarrow X^{\ast}$ such that for all $(x,x^{\ast})$ and $(y,y^{\ast})$ in its graph, the following implication holds: $\left\langle x^{\ast},y-x\right\rangle \geq0\Rightarrow\left\langle y^{\ast},y-x\right\rangle \geq0$. A characteristic aspect of these maps is that a pseudomonotone map, if multiplied by any positive function, remains pseudomonotone. Based on this fact, we define and investigate the maximality properties of such maps. In particular, we show that the Clarke subdifferential of a locally Lipschitz function is maximal pseudomonotone. Also some results on their continuity are established; for instance, a hemicontinuous pseudomonotone operator on a finite-dimensional space can be written as a product of a positive function and a continuous pseudomonotone operator.

Abstract : Based on a variation of Fan's geometric lemma, an existence theorem of solutions for set-valued vector equilibrium problem is given in this paper.

Abstract : In this paper, we investigate the relationships among three classes of exact penalty functions for a constrained optimization problem.  The first class of penalty functions is a class of augmented Lagrangian functions for a constrained program.  The second class of penalty functions is a class of nonlinear Lagrangian functions which were recently introduced for constrained nonlinear programming.  The third class of penalty functions are closely related to the so-called error bounds, which have been substantially studied in the literature.  Necessary and sufficient conditions for these three classes of (local or global) exact penalty functions are derived.  Using these conditions, several relationships among these three classes of (local or global) exact penalty functions are established.

Abstract : Many filtering design problems are formulated in the form of linear semi-infinite programming.  We present in this talk a numerical method for solving this type of problem.  The proposed method is based on our dual parametrization algorithmic framework and is also applicable to non-strictly-convex quadratic semi-infinite programming problems.

Abstract : For details, please click here.

Abstract : In this talk two computational algorithms for solving a class of optimal control problems are presented with recent extensions, and these algorithms are illustrated through example applications.

The leapfrog algorithm, which was previously proposed for solving the problem of finding geodesics, is described as a method for solving the much more general optimal control problems.  Initially a feasible trajectory is given and subdivided into smaller pieces.  In each subdivision, with the assumption that local optimal controls can easily be calculated, a piecewise-optimal trajectory is obtained.  Then the junctions of these smaller pieces of optimal control trajectories are updated through a scheme of midpoint maps.

The second algorithm, the time optimal switching (TOS) algorithm, is proposed for solving the problems of time-optimal bang-bang control.  A feasible bang-bang control (not necessarily optimal) is found using the switching time computation (STC) method previously developed by the speaker and a co-worker to get from an initial point to a target point with a given number of switchings.  Then by means of constrained optimization techniques, a minimum time switching control solution is obtained. Recent extensions to both STC and TOS algorithms such as an alternative lagrangian technique, multiple-shooting, and multi-input cases developed by the speaker and his co-workers are presented.

Both algorithms will be illustrated through example applications.  One notable example system involves the cocaine epidemic in the US.  The speaker will present a solution for the optimal allocation of resources to treatment and prevention through an optimal control formulation.

Abstract : A manpower planning problem is studied in this paper.  The model includes scheduling different types of workers over different tasks, employing and terminating different types of workers, and assigning different types of workers to various trainning programmes.  The aim is to find an optimal way to do all these while keeping the time-varying demand for minimum number of workers working on each different tasks satisfied.  The problem is posed as an optimal discrete-valued control problem in discrete time.  A novel numerical scheme is proposed to solve the problem, and an illustrative example is provided.

Abstract : We call a linear map "ill-conditioned" when a small perturbation makes it non-surjective.  The "condition number" quantifies this, and is fundamental in computational techniques for equations involving the map.  In 1995, Renegar generalized this theory to linear inequalities and associated interior point methods, sparking renewed interest in condition measures.  I will outline a concise regularity theory for generalized equations, subsuming Renegar's idea.

(Joint work with A.L. Dontchev and R.T. Rockafellar.)

Abstract : For details, please click here.

Abstract : Dynamic (or ode) system and neural network approaches for optimization have been co-existed for two decades.  The main feature of the two approaches is that a continuous path starting from the initial point can be generated and eventually the path will converge to the solution. This feature is quite different from the conventional optimization methods where a sequence of points, or a discrete path, is generated.  Even dynamic system and neural network approaches share many common features and structures, yet a complete comparison for the two approaches has not been available.  In this paper, based on a detailed study on the two approaches, a new approach, termed Neurodynamic approach, is introduced. The new neurodynamic approach maintains the attractive features in both dynamic (or ode) system and neural network approaches. In addition, the new approach has a systematic framework on how to construct a neurodynamic system for both unconstrained and constrained problems.  In analyzing the stability issues of the underlying dynamic (or ode) system, the neurodynamic approach adopts a new strategy, which avoids the Lyapunov function. Under the framework of this neurodynamic approach, strong theoretical results as well as promising numerical results are obtained.

Abstract : Support vector machine is an effective classification paradigm.  In real-world applications, the common occurrance of uneven training class sizes has resulted in trained support vector machines with biases towards the class with larger training set.  We use a noval dual nu support vector machine to overcome this major difficulty.  In addition, we devise a decomposition method for the dual nu machine for large scale applications to satisfy memory and storage restriction.

Abstract : In this paper, the $H_{\infty}$ control problem based on state observer for descriptor systems is investigated.  The motivation of this paper is two-folds.  One is to extend the corresponding $H_{\infty}$ results for linear time invariant systems to the case for descriptor systems; The other is to obtain more explicit results compared to those in the existing literature.  From the results obtained here, one can figure out some special features for singular systems, which are different from normal linear systems.  Also the approach adopted here is pure algebraic, which is easy to understand.  As to the results, a necessary and sufficient condition for the solvability of the $H_{\infty}$ control problem based observer design is obtained in terms of Generalized Algebraic Riccati Inequality (GARI).  Moreover, the desired controller is also explicitly constructed in this case.

Abstract : In this paper we provide characterizations of the upper semicontinuity property for the feasible set mapping in linear semi-infinite programming.  We deal with this property in two different frameworks.  First we consider the parameter space of all the linear inequality systems, in the Euclidean space, with a fixed index set (the parameter is identified with the whole coefficients set).  A second setting is built by considering that the coefficients of the system are continuously dependent on an external parameter, running in a metric space.  In both cases, it turns out that the studied property strongly relies on the recession properties of the feasible set corresponding to the nominal problem, and the approach comes through the idea of the so-called reinforced systems.

Co-authors: M.J. Canovas and J. Parra

Abstract : Several time optimal control problems are solved by iterative dynamic programming (IDP) and by Luus-Jaakola (LJ) optimization procedure.  Although systems of low dimension can be solved quite readily with the LJ optimization procedure, as the dimension increases, IDP which employs sequential optimization becomes increasingly more efficient than the LJ optimization procedure.  In both procedures, stages of varying length are used to allow accurate switching.  Since the computations with IDP can be done very fast with our present-day personal computers, it is shown that the method can be used on-line where the time optimal control problem is solved repeatedly within each sampling period as the desired state is approached, yielding in essence feed-back control.

Abstract : We start by considering, as a parameter space, the family of all the linear inequality systems, in the Euclidean space, with the same fixed index set, T, and satisfying the following conditions: T is arbitrary (possibly infinite) and, so, the function assigning to each index the associated coefficient vector has no particular property at all. In this parameter space, endowed with the topology of the uniform convergence of the coefficient vectors, the fulfillment of the Strong Slater Condition (SSC) at the nominal system is equivalent to the lower semicontinuity (lsc) of the feasible set mapping at this system.  When we change this scenario and we assume that the coefficient vectors continuously depend on an external parameter (running over an arbitrary metric space), the SSC and the lsc of the feasible set mapping turn out to be independent properties.  If we require, as an additional hypothesis, the equicontinuity of the family of coefficient functions at the nominal parameter, the SSC is sufficient for the lsc of the feasible set mapping at this parameter.  The absence of the SSC gives rise to the trivial inequality as a limit of convex combinations of coefficient vectors, which may cause instability in relation to the feasible set. In this paper we characterize the lsc of the feasible set mapping in this situation, and when one is confined to the finite case, our characterization can be stated in terms of the so-called carrier index set, which allow us to go deeply in the stability theory.

Co-authors: M. J. Cánovas and M. A. López

Abstract : A number of recent results, such as mean value inequalities, fuzzy sum rules have been given striking applications to Hamilton-Jacobi equations.  We survey such results.  We also deal with generalized convexity techniques, in particular duality theories, to study explicit formulae for solutions in the presence of mild convexity assumptions.

Abstract : We investigate the potential and opportunities offered by quantum algorithm for solving the general global optimization problem (GOP).  We first review Grover's quantum algorithm and several of its variants.  We then identify the sufficient information needed on an optimization function depending on d variables in order to apply this class of algorithms.  If the algorithms are applicable, the speed up is extremely significant.  Several counterexamples are also discussed which show the applicability limit of Grover-like algorithms for the GOP.

Abstract : The KKT system of the variational inequality problem over a set defined by inequality and equality constraints can be reformulated as a system of semismooth equations by some NCP functions.  We give a sufficient condition for the level sets of the norm function of this system of semismooth equations to be bounded when the NCP function is metrically equivalent to the minimum function; and a sufficient and necessary condition when the NCP function is the minimum function.  Nonsingularity properties identified by Facchinei, Fischer and Kanzow (1998) for the semismooth reformulation of the variational inequality problem via the Fischer-Burmeister function, hold for the reformulation based any regular pseudo-smooth NCP function, while the Fischer-Burmeister function is an irrational regular pseudo-smooth NCP function.  We propose a new regular pseudo-smooth NCP function, which is piecewise linear-rational and metrically equivalent to the minimum NCP function.  When it is used to the generalized Newton method for solving the variational inequality problem, an auxiliary step can be added to each iteration to reduce the value of the merit function by adjusting the Lagrangian multipliers only.

Abstract : The spectral gradient method has proved to be effective for solving large-scale optimization problems.  In this work we extend the spectral choice of steplength to solve nonlinear systems of equations.  We consider different strategies based on nonmonotone line search techniques to guarantee global convergence.  We discuss implementation details for solving large-scale problems.  In particular, we describe the application of this new method for solving the nonlinear systems that appear when discretizing the wave equation associated with 3D ray tracing in seismic tomography.

Abstract : We propose a new technique for a class of optimal control problems involving a choice between different system dynamics. The aim is to choose a the number and exact value of time points at which the dynamics of the problem are switched, as well as the optimal switching sequence. We find suboptimal solutions to the problem by first applying the Control Parametrization Enhancing Transform (CPET) to convert it into a standard form suitable for standard optimal control software.  A numerical example is solved and we compare the results to those from an alternative computational method.

Abstract : For details, please click here.

Abstract : For details, please click here.

Abstract : I introduce an iterative algorithm using ideas from interior point methods in order to solve the following Equilibrium Problem (EP in short): Find x in K such that f(x,y) is nonnegative for all y in K, where K is a nonempty closed convex subset of R^n and f defined on KxK with real values is upper semicontinuous in the first variable, lower semicontinuous and convex in the second one and f(x,x) = 0 for all x in K.  This problem has as particular cases (among others): variational inequality problems, fixed point problems, complementarity problems, convex-concave constrained saddle point problems, convex minimization problems, Nash equilibria problems for noncooperative games and vectorial equilibrium problems.

Abstract : Let N be the number of available sensor sources.  Noisy observations of an underlying state process are available for these N sources.  We consider the continuous time sensor scheduling problem in which N₁ of these N sources are to be chosen to collect data at each time point.  This sensor scheduling problem (with switching costs and switching constraints) is formulated as a constrained optimal control problem.  In this framework, the controls represent the sensors that are chosen at a particular time.  Thus, the control variables are constrained to take values in a discrete set, and switchings between sensors can occur in continuous time.  By incorporating recent results on discrete valued optimal control, we show that this problem can be transformed into an equivalent continuous optimal control problem.  In this way, we obtain the sensor scheduling policy as well as the associated switching times.

Abstract : In this presentation, which is a joint work with T.PENNANEN and T.ROCKAFELLAR, we will  give sufficient conditions for the graphical convergence of sums of maximal monotone mappings.  The main result concerns finite-dimensional spaces and it generalizes known convergence results for sums.  The proof is based on a duality argument and a new boundedness result for sequences of monotone mappings which is of interest on its own.  An application to the epi-convergence theory of convex functions is given.  Counterexamples are used to show that the results cannot be directly extended to infinite dimensions.

Abstract : Consider a single-server queue operating in a deterministic setting, and its processing of a given number (N) of jobs. Suppose that the jobs' service order and service times are known, and it remains to determine their arrival times.  With each job there is an associated convex performance function that measures a cost of the discrepancy between the job's departure time  and a given due date.  The sum of these performance functions is the cost functional which has to be minimized by a proper choice of the jobs' release times.

We have here an optimal control problem which is neither differentiable nor convex.  However, it is shown to have a unique local minimum.  The problem can be decomposed into a number (M) of smaller subproblems, each of which can be transformed into a differentiable and convex nonlinear program.  The number M is exponential in N, and hence such decomposition may be impractical.  However, there is a way to iterate among a number (K), linear in N, of the above nonlinear programs in order to solve the optimal control problem.

The state equations of the underlying dynamical system are nonlinear in the usual sense, but they are linear in the max-plus algebra.  If the cost functions are quadratic, then the optimal control is shown to be given  by a state feedback law that is also  linear in the max-plus algebra.  Moreover, the feedback "gains" are computable off line via a recursive procedure that evolves backwards in time.  This constitutes an extension of the classical LQR theory from the domain of linear systems to a particular  setting of max-plus algebras.

Similar results exist for the case where the jobs' arrival times are known, and the control variables consist of their service times. Here too the optimal control problem can be decomposed into lower-dimension, differentiable and convex subproblems. Although the number of subproblems appears to be exponential in N, an algorithm that is linear in N has been developed.

The talk will present the above results as well as extensions to multi-stage systems like queueing networks and Petri nets, and discuss applications in manufacturing.

Abstract : Several classes of time-delayed optimal control problems are considered.  Three different algorithms are developed to find feedback gains for these time-delayed optimal control problems.  Several examples are solved to compare the efficiency of each of these algorithms.

Abstract : The conventional Lagrangian dual problem may present a different optimal value from the one of the original nonconvex optimization problem (known as a nonzero duality gap).  A nonlinear Lagrangian function has been introduced recently with the aim of providing a dual problem which has the same optimal value as that of any nonconvex optimization problem.

In this talk I will present some results in this line, such as the zero duality gap, exact penalty functions, and the convergence of the sequence of stationary points of nonlinear penalty problems.  I will present some applications of the nonlinear Lagrangian function to inequality constrained variational inequality problems.

Abstract : In this presentation, which is a joint work with S.H. Hou, X.Q. Yang and K.L. Teo, we introduce two new pairs of second order symmetric models for a class of nondifferentiable nonlinear programs in Part I.  To study the formulations of the second order symmetric dual models and their duality results, we introduce the concepts of second order F-convexity and second order F-pseudoconvexity.  Both the weak and strong duality theorems are obtained under second order F-convexity (respectively, second-order F-pseudoconvexity) assumption.  Our results extend some of the known results obtained by Bector and Chandra (Opsearch, 23 1986), Mond and Schechter (Bull. Austral. Math. Soc., 53 1996), Gulati and Ahmad (European J. OR, 101 1997), Mishra (European J. OR, 127 2000) and Yang (Opsearch, 32 1995).  Furthermore, our model and duality results can be reduced to the corresponding first order model and its duality results established in Mond and Schechter (Bull. Austral. Math. Soc., 53 1996).  In addition, a deficiency contained in Bector and Chandra (Opsearch and Yang (Opsearch, 32 1995) is overcome.

Based on Kim, Yun and Kuk's ideas reported by Kim, Yun and Kuk (Appl. Math. Letters, 10 1997), we propose a pair of second order symmetric dual models for a multiobjective nonlinear programming problem in Part II.  Under F-convexity conditions, we obtain the weak, strong and converse duality theorems.  On the basis of the model and the results obtained in this chapter, the two deficiencies observed in Kim, Yun and Kuk (Appl. Math. Letters, 10 1997) have been overcome.  These two deficiencies are: (i) an assumption made in Kim, Yun and Kuk (Appl. Math. Letters, 10 1997) requiring two specific variables to be of same dimension, and (ii) the errors made in the proof of Theorem 2 ( respectively, Theorem 3) of Kim, Yun and Kuk (Appl. Math. Letters, 10 1997).

Abstract : As well-known, there is a link between the condition number of a matrix and its distance from the set of the singular matrices.  We present some extensions and generalizations of this result in the frame of optimization problems in Banach spaces, taking into account the geometrical significance (and the bearing on computational complexity issues).

A suitable notion of conditioning under linear perturbations leads to the condition number theorem in the setting of optimization of convex quadratic forms, thereby extending the classical Eckart-Young formula: the distance to ill-conditioning equals the reciprocal of the condition number.  Partial results are presented for more general optimization problems involving Lipschitz continuous functions. A link with metric regularity is briefly discussed.

ALLEVI, Elisabetta
Generalized Monotone Vector Variational Inequalities Over Product Sets

Abstract : For details, please click here.

Abstract : This work establishes new connections between maximal monotone operators and convex functions.  Associated to each maximal monotone operator, there is a family of convex functions, each of which characterizes the operator.  The basic tool in our analysis is a family of enlargements, recently introduced by Svaiter.  This family of convex functions is in a one-to-one relation with a subfamily of these enlargements.  We study the family of convex functions, and determine its extremal elements.  The  particular case in which the operator is a subdifferential of a convex function is discussed.

Abstract : We propose a Cauchy-like method for solving smooth unconstrained vector optimization problems in finite dimensional spaces.  We prove that every accumulation point of any generated sequence satisfies a certain first order necessary condition for optimality, which extends to the vector case the well known "gradient equal zero" condition for real-valued minimization.  Finally, under some reasonable additional hypotheses (basically K-convexity of the objective function), we prove global convergence to a weak unconstrained Pareto minimizer.  Furthermore, we establish connections between the scalarization approach and our procedure, and between constrained vector optimization problems and abstract equilibrium problems.

Abstract : In this paper we use a sharp Lagrangian approach in order to construct a dual problem to the nonconvex minimization problem with equality constraints.  By using the saddle point optimality conditions and strong duality results we modify the subgradient and cutting plane methods for solving the dual problem constructed here.  The algorithms proposed in this paper has some advantages.  We do not use any convexity and differentiability conditions, and show that the dual problem is always concave regardless of properties the primal problem satisfies.  The subgradient of the dual function along which its value increases is calculated without solving any additional problem. In contrast with the penalty or multiplier methods, for improving the value of the dual function, one need not to take the "penalty like parameter" to infinity in the new methods.  In both methods the value of the dual function strongly increases at each iteration.  The convergence and rate of convergence results for optimal solutions are also presented.  In contrast, by using the primal-dual gap, the proposed algorithms possesses a natural stopping criteria.

Abstract : The present talk deals with the envelope of a variational inequality and some connections among image space analysis and regularization for quasi variational inequalities.  The quasi variational inequalities are considered with multivalued monotone operators.  The operator involved  is taken to be non-coercive and the data are assumed to be known approximately only.

Abstract : For details, please click here.

Abstract : In this paper, we study uniform duality for the semi-definite and semi-infinite programming problems.  We propose an algorithm to compute the problems and show the approach is an efficient method for relaxation problems of semi-infinite quadratically constrained quadratic programming problems and min-max eigenvalue problems.

Abstract : We analyse the role of general embedding schemes in the definition of iterative methods for Variational Inequalities.  In particular, we consider the Auxiliary Problem Principle introduced by Cohen [1], and the gap function approach for Variational Inequalities [2,3], providing suitable extensions to general equilibrium problems.

References
[1] Cohen G., Auxiliary problem principle extended to variational inequalities, J.O.T.A., Vol. 59, pp. 325-333, 1988.

[2] Fukushima M., Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problem, Mathem. Progr. Vol. 53, pp. 99-110, 1992.

[3] Zhu D.L., Marcotte P., An extended descent framework for variational inequalities, J.O.T.A., Vol. 80, pp. 349-366, 1994.

Abstract : For details, please click here.

Abstract : For details, please click here.

Abstract : some connections between solutions to variational inequalities and stationary points of projected dynamical system are shown.  Furthermore some stability questions arising in this topic are analysed. By means of the Minty variational inequality and suitable monotonicity conditions, the stability analysis for locally projected dynamical systems is developed, globally projected dynamical systems are treated by Lyapunov function method and Fukushima's gap function for variational  inequalities. Finally a result is obtained, for both types  of projected dynamical systems, which is analogous to the nonlinear sink  theorem for classical dynamical systems.

Abstract : For details, please click here.

Abstract : In this talk, we first prove a fixed point theorem extending the Fan-Browder and Tarafdar's fixed point theorem.  Then we introduce the concept of a monotone family of functions, indexed by a possibly uncountable set I and apply our results to show the existence of solutions to an uncountable system of variational inequalities associated with this family.  Finally we consider a more general family of mappings, namely a pseudo-monotone family, and show the existence of solutions to the system of variational inequalities associated with this family too.

Abstract : The hybrid extragradient proximal point algorithm proposed by M.Solodov and B.F.Svaiter has the feature of allowing a constant relative error tolerance.  We generalize the error tolerance of this algorithm, proving that it converges even if a summable error is added to the constant relative error.  Furthermore, the extragradient step may also be performed inexactly, with a summable erro.  We present a convergence analysis, which encompasses other well known variations of the proximal point method, previously unrelated.  We establish weak global convergence under mild assumptions.

Abstract : In this paper we consider the parameter space of all the linear inequality systems, in the n-dimensional Euclidean space, with a fixed and arbitrary (possibly infinite) index set.  This parameter space is endowed with the topology of the uniform
convergence of the coefficient vectors by means of an extended distance.  Some authors, in a different context in which the index set is finite and, accordingly, the coefficients are bounded, consider the boundary of the set of consistent systems as the set of ill-posed systems.  The distance from the nominal system to this boundary ("distance to ill-posedness"), which constitutes itself a measure of the stability of the system, plays a decisive role in the complexity analysis of certain algorithms for finding a solution of the system.  In our context, the presence of infinitely many constraints would leads us to consider separately two subsets of inconsistent systems, the so-called strongly inconsistent systems and the weakly inconsistent systems.  Moreover, the possible unboundedness of the coefficient vectors of a system gives rise to a special subset formed by those systems whose distance to ill-posedness is infinite.  Attending to these two facts, and according to the idea that a system is ill-posed when small changes in the system's data yield different types of systems, now the boundary of the set of strongly inconsistent systems arises as the "generalized ill-posedness" set. The paper characterizes this generalized ill-posedness of a system in terms of the so-called associated hypographical set, leading to an explicit formula for the "distance to generalized ill-posedness".  On the other hand, the consistency value of a system, also introduced in the paper, provides an alternative way to determine its distance to ill-posedness (in the original sense), and additionally allows us to distinguish the consistent well-posed systems from the
inconsistent well-posed ones.  The finite case is shown to be a meeting point of our linear semi-infinite approach to the distance to ill-posedness with certain results derived for conic linear systems.

Co-authors: M.J. Cánovas, M.A. López and J. Parra