Search

The focal point of this paper is the probabilistically constrained linear program (PCLP) and how it can be applied to control system, design under risk constraints. The PCLP is the counterpart of the classical linear program, where it is assumed that there is random uncertainty in the constraints and, therefore, the deterministic constraints are replaced by probabilistic ones. It is shown that for a wide class of probability density functions, called log-concave symmetric densities, the PCLP is a convex program. An equivalent formulation of the PCLP is also presented which provides insight into numerical implementation. This concept is applied to control system design. It is shown how the results in this paper can be applied to the design of controllers for discrete-time systems to obtain a closed loop system with a well-defined risk of violating the so-called property of svperstability. Furthermore, we address the problem of risk-adjusted pole placement. [ABSTRACT FROM AUTHOR]

This paper deals with a problem of guaranteed (robust) financial decision-making under model uncertainty. An efficient method is proposed for determining optimal robust portfolios of risky financial instruments in the presence of ambiguity (uncertainty) on the probabilistic model of the returns. Specifically, it is assumed that a nominal discrete return distribution is given, while the true distribution is only known to lie within a distance d from the nominal one, where the distance is measured according to the Kullback-Leibler divergence. The goal in this setting is to compute portfolios that are worst-case optimal in the mean-risk sense, that is, to determine portfolios that minimize the maximum with respect to all the allowable distributions of a weighted risk-mean objective. The analysis in the paper considers both the standard variance measure of risk and the absolute deviation measure. [ABSTRACT FROM AUTHOR]

In this paper we use the penalty approach to study three constrained minimization problems. A penalty function is said to have the exact penalty property [J.-B. Hiriart-Urruty and C. Lemarechal, Convex Analysis and Minimization Algorithms, 2 vols., Springer-Verlag, Berlin, 1993] if there exists a penalty coefficient for which a solution of an unconstrained penalized problem is a solution of the corresponding constrained problem. In this paper we establish a very simple sufficient condition for the exact penalty property. [ABSTRACT FROM AUTHOR]

This paper concerns applications of advanced techniques of variational analysis and generalized differentiation to parametric problems of semi-infinite and infinite programming, where decision variables run over finite-dimensional and infinite-dimensional spaces, respectively. Part I is primarily devoted to the study of robust Lipschitzian stability of feasible solutions maps for such problems described by parameterized systems of infinitely many linear inequalities in Banach spaces of decision variables indexed by an arbitrary set T. The parameter space of admissible perturbations under consideration is formed by all bounded functions on T equipped with the standard supremum norm. Unless the index set T is finite, this space is intrinsically infinite-dimensional (nonreflexive and nonseparable) of the l∞ type. By using advanced tools of variational analysis and exploiting specific features of linear infinite systems, we establish complete characterizations of robust Lipschitzian stability entirely via their initial data with computing the exact bound of Lipschitzian moduli. A crucial part of our analysis addresses the precise computation of the coderivative of the feasible set mapping and its norm. The results obtained are new in both semi-infinite and infinite frameworks. [ABSTRACT FROM AUTHOR]

This paper proposes a method for finding the global infimum of a multivariate polynomial f via sum of squares (SOS) relaxation over its truncated tangency variety. This variety is truncated of the set of all points x ∈ Rn where the level sets of f are tangent to the sphere in Rn centered in the origin and with radius x. It is demonstrated that: • The infimum of f on Rn and on its truncated tangency variety coincide. • A sums of squares certificate for nonnegativity of f on its truncated tangency variety. These facts imply that we can find a natural sequence of semidefinite programs whose optimal values converge monotonically, increasing to the infimum of f. This opens up the possibility of solving previously intractable polynomial optimization problems. [ABSTRACT FROM AUTHOR]

In this paper we discuss the issue of solving stochastic optimization problems by means of sample average approximations. Our focus is on rates of convergence of estimators of optimal solutions and optimal values with respect to the sample size. This is a well-studied problem in case the samples are independent and identically distributed (i.e., when standard Monte Carlo simulation is used); here we study the case where that assumption is dropped. Broadly speaking, our results show that, under appropriate assumptions, the rates of convergence for pointwise estimators under a sampling scheme carry over to the optimization case, in the sense that convergence of approximating optimal solutions and optimal values to their true counterparts has the same rates as in pointwise estimation. We apply our results to two well-established sampling schemes, namely, Latin hypercube sampling and randomized quasi-Monte Carlo (QMC). The novelty of our work arises from the fact that, while there has been some work on the use of variance reduction techniques and QMC methods in stochastic optimization, none of the existing work--to the best of our knowledge--has provided a theoretical study on the effect of these techniques on rates of convergence for the optimization problem. We present numerical results for some two-stage stochastic programs from the literature to illustrate the discussed ideas. [ABSTRACT FROM AUTHOR]

In this paper, we consider the Lagrangian-dual problem of a class of convex optimization problems. We first discuss the semismoothness of the Lagrangian-dual function φ. This property is then used to investigate the second-order properties of the Moreau--Yosida regularization ? of the function φ, e.g., the semismoothness of the gradient g of the regularized function ?. We show that φ and g are piecewise C² and semismooth, respectively, for certain instances of the optimization problem. We establish a relationship between the original problem and the Fenchel conjugate of the regularization of the corresponding Lagrangian dual problem. We also find some instances of the optimization problem whose Lagrangian-dual function φ is not piecewise smooth. However, its regularized function still possesses nice second-order properties. Finally, we provide an alternative way to study the semismoothness of the gradient under the structure of the epigraph of the dual function. [ABSTRACT FROM AUTHOR]

In this paper we discuss the polynomiality of a feasible version of Mehrotra's predictor-corrector algorithm whose variants have been widely used in several interior point method (IPM)-based optimization packages. A numerical example is given that shows that the adaptive choice of centering parameter and correction terms in this algorithm may lead to small steps being taken in order to keep the iterates in a large neighborhood of the central path, which is important for proving polynomial complexity properties of this method. Motivated by this example, we introduce a safeguard in Mehrotra's algorithm that keeps the iterates in the prescribed neighborhood and allows us to obtain a positive lower bound on the step size. This safeguard strategy is also used when the affine scaling direction performs poorly. We prove that the safeguarded algorithm will terminate after at most O(n2log(x°}T s° /e) iterations. By modestly modifying the corrector direction, we reduce the iteration complexity to O(nlog(x°}T s° /e). To ensure fast asymptotic convergence of the algorithm, we changed Mehrotra's updating scheme of the centering parameter slightly while keeping the safeguard. The new algorithms have the same order of iteration complexity as the safeguarded algorithms but enjoy superlinear convergence as well. Numerical results using the McIPM and LIPSOL software packages are reported. [ABSTRACT FROM AUTHOR]

The paper considers different problem formulations of topology optimization of discrete or discretized structures with eigenvalues as constraints or as objective functions. We study multiple-load case formulations of minimum volume or weight, minimum compliance problems, and the problem of maximizing the minimal eigenvalue of the structure, including the effect of nonstructural mass. The paper discusses interrelations of the problems and, in particular, shows how solutions of one problem can be derived from solutions of the others. Moreover, we present equivalent reformulations as semidefinite programming problems with the property that, for the minimum volume and minimum compliance problem, each local optimizer of these problems is also a global one. This allows for the calculation of guaranteed global optimizers of the original problems through the use of modern solution techniques of semidefinite programming. For the problem of maximization of the minimum eigenvalue we show how to verify the global optimality and present an algorithm for finding a tight approximation of a globally optimal solution. Numerical examples are provided for truss structures. Both academic and larger-size examples illustrate the theoretical results achieved and demonstrate the practical use of this approach. We conclude with an extension on multiple nonstructural mass conditions. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of minimization of a nonsmooth function under general nonsmooth constraints when no derivatives of the objective or constraint functions are available. We introduce the mesh adaptive direct search (MADS) class of algorithms which extends the generalized pattern search (GPS) class by allowing local exploration, called polling, in an asymptotically dense set of directions in the space of optimization variables. This means that under certain hypotheses, including a weak constraint qualification due to Rockafellar, MADS can treat constraints by the extreme barrier approach of setting the objective to infinity for infeasible points and treating the problem as unconstrained. The main GPS convergence result is to identify limit points x0302;, where the Clarke generalized derivatives are nonnegative in a finite set of directions, called refining directions. Although in the unconstrained case, nonnegative combinations of these directions span the whole space, the fact that there can only be finitely many GPS refining directions limits rigorous justification of the barrier approach to finitely many linear constraints for GPS. The main result of this paper is that the general MADS framework is flexible enough to allow the generation of an asymptotically dense set of refining directions along which the Clarke derivatives are nonnegative. We propose an instance of MADS for which the refining directions are dense in the hypertangent cone at x0302; with probability 1 whenever the iterates associated with the refining directions converge to a single x0302;. The instance of MADS is compared to versions of GPS on some test problems. We also illustrate the limitation of our results with examples. [ABSTRACT FROM AUTHOR]

This paper presents a new verified optimization method for the problem of finding the densest packings of nonoverlapping equal circles in a square. In order to provide reliable numerical results, the developed algorithm is based on interval analysis. As one of the most efficient parts of the algorithm, an interval-based version of a previous elimination procedure is introduced. This method represents the remaining areas still of interest as polygons fully calculated in a reliable way. Currently the most promising strategy of finding optimal circle packing configurations is to partition the original problem into subproblems. Still, as a result of the highly increasing number of subproblems, earlier computer-aided methods were not able to solve problem instances where the number of circles was greater than 27. The present paper provides a carefully developed technique resolving this difficulty by eliminating large groups of subproblems together. As a demonstration of the capabilities of the new algorithm the problems of packing 28, 29, and 30 circles were solved within very tight tolerance values. Our verified procedure decreased the uncertainty in the location of the optimal packings by more than 700 orders of magnitude in all cases. [ABSTRACT FROM AUTHOR]

In this paper we study optimization problems with, equality and inequality constraints on a Banach space where the objective function and the binding constraints are either differentiable at the optimal solution or Lipschitz near the optimal solution. Necessary and sufficient optimality conditions and constraint qualifications in terms of the Michel-Penot subdifferential are given, and the results are applied to bilevel optimization problems. [ABSTRACT FROM AUTHOR]

This paper contains a new convergence analysis for the Lewis and Torczon generalized pattern search (GPS) class of methods for unconstrained and linearly constrained optimization. This analysis is motivated by a desire to understand the successful behavior of the algorithm under hypotheses that are satisfied by many practical problems. Specifically, even if the objective function is discontinuous or extended-valued, the methods find a limit point with some minimizing properties. Simple examples show that the strength of the optimality conditions at a limit point depends not only on the algorithm, but also on the directions it uses and on the smoothness of the objective at the limit point in question. The contribution of this paper is to provide a simple convergence analysis that supplies detail about the relation of optimality conditions to objective smoothness properties and to the defining directions for the algorithm, and it gives previous results as corollaries. [ABSTRACT FROM AUTHOR]

The BFGS method is one of the most, famous quasi-Newton algorithms for unconstrained optimization. In 1984, Powell presented an example of a function of two variables that shows that the Polak Ribi[egrave;]re Polyak (PRP) conjugate gradient method and the BFGS quasi-Newt, on method may cycle around eight nonstationary points if each line search picks a local minimum that provides a reduction in the objective function. In this paper, a new technique of choosing parameters is introduced, and an example with only six cyclic points is provided. It is also noted through the examples that the BFGS method with Wolfe line searches need not converge for nonconvex objective functions. [ABSTRACT FROM AUTHOR]

Gauge functions significantly generalize the notion of a norm, and gauge optimization, as defined by [R. M. Freund, Math. Programming, 38 (1987), pp. 47-67], seeks the element of a convex set that is minimal with respect to a gauge function. This conceptually simple problem can be used to model a remarkable array of useful problems, including a special case of conic optimization, and related problems that arise in machine learning and signal processing. The gauge structure of these problems allows for a special kind of duality framework. This paper explores the duality framework proposed by Freund, and proposes a particular form of the problem that exposes some useful properties of the gauge optimization framework (such as the variational properties of its value function), and yet maintains most of the generality of the abstract form of gauge optimization. [ABSTRACT FROM AUTHOR]

The multiobjective optimization model studied in this paper deals with simultaneous minimization of finitely many linear functions subject to an arbitrary number of uncertain linear constraints. We first provide a radius of robust feasibility guaranteeing the feasibility of the robust counterpart under affine data parametrization. We then establish dual characterizations of robust solutions of our model that are immunized against data uncertainty by way of characterizing corresponding solutions of robust counterpart of the model. Consequently, we present robust duality theorems relating the value of the robust model with the corresponding value of its dual problem. [ABSTRACT FROM AUTHOR]

In [SIAM J. Optim., 17 (2006), pp. 188-217] Audet and Dennis proposed the class of mesh adaptive direct search (MADS) algorithms for minimization of a nonsmooth function under general nonsmooth constraints. The notation used in the paper evolved since the preliminary versions, and, unfortunately, even though the statement of Proposition 4.2 is correct, it is not compatible with the final notation. The purpose of this note is to show that the proposition is valid. [ABSTRACT FROM AUTHOR]

In this paper, we propose an explicit exchange algorithm for solving the semi-infinite programming problem (SIP) with second-order cone (SOC) constraints. We prove, by using the complementarity slackness conditions, that the algorithm terminates in a finite number of iterations and the obtained solution sufficiently approximates the original SIP solution. In existing studies on SIPs, only the nonnegative constraints were considered, and hence, the complementarity slackness conditions were separable to each scalar component. However, in our study, the existing componentwise analyses are no longer applicable since the complementarity slackness conditions are associated with SOCs. In order to overcome such a difficulty, we introduce a certain coordinate system based on the spectral factorization. In the numerical experiments, we solve some test problems to see the effectiveness of the proposed algorithm. First, we compare our algorithm with two other algorithms based on the linear SIP (LSIP) reformulation and observe that, by exploiting the SDPT3 solver for subproblems, our algorithm finds the solution much faster than LSIP reformulation approaches when the size of the problem is large. Also, we apply the algorithm to some filter design problems and see that those problems can be solved efficiently. [ABSTRACT FROM AUTHOR]

This paper proposes two new constraint qualification conditions (CQs) which are useful for a unified study of CQs from both a convex analysis and a nonsmooth analysis point of view. Our CQs cover the existing CQs of Mangasarian–Fromovitz and Farkas–Minkowski types. Some sufficient conditions for the validity of the new CQs are given. Under these CQs, we derive formulae for computing and/or estimating the (basic and singular) subdifferentials of marginal/optimal value function in semi-infinite programming from some results of modern variational analysis and generalized differentiation. Examples are given to illustrate the obtained formulae. [ABSTRACT FROM AUTHOR]

We consider methods for large-scale unconstrained minimization based on finding an approximate minimizer of a quadratic function subject to a two-norm trust-region constraint. The Steihaug–Toint method uses the conjugate-gradient method to minimize the quadratic over a sequence of expanding subspaces until the iterates either converge to an interior point or cross the constraint boundary. However, if the conjugate-gradient method is used with a preconditioner, the Steihaug–Toint method requires that the trust-region norm be defined in terms of the preconditioning matrix. If a different preconditioner is used for each subproblem, the shape of the trust-region can change substantially from one subproblem to the next, which invalidates many of the assumptions on which standard methods for adjusting the trust-region radius are based. In this paper we propose a method that allows the trust-region norm to be defined independently of the preconditioner. The method solves the inequality constrained trust-region subproblem over a sequence of evolving low dimensional subspaces. Each subspace includes an accelerator direction defined by a regularized Newton method for satisfying the optimality conditions of a primal-dual interior method. A crucial property of this direction is that it can be computed by applying the preconditioned conjugate gradient method to a positive-definite system in both the primal and dual variables of the trust-region subproblem. Numerical experiments on problems from the CUTEr test collection indicate that the method can require significantly fewer function evaluations than other methods. In addition, experiments with general-purpose preconditioners show that it is possible to significantly reduce the number of matrix-vector products relative to those required without preconditioning. [ABSTRACT FROM AUTHOR]

In this paper we study some second order conditions that may be added to the first order nessessary optimality condition 0 ∈ ∂p&fnop;(¯X) (with ∂pƒ denoting the proximal subdifferential) in order to obtain a sufficient condition for a strict local minimum for extended--real-valued, nonsmooth functions. Three different types of second order conditions are investigated, all based on a different second order subdifferential. Namely, the subhessian, the graphical derivative, and the (contingent) coderivative to the proximal subdifferential. [ABSTRACT FROM AUTHOR]

The question of determining strong convex underestimators for nonlinear functions is theoretically and practically of major interest. Unfortunately, results along these lines are quite limited as very few general procedures are at hand that can be applied to general classes of functions. In this paper we show how to reduce the question of determining a convex envelope to lower-dimensional optimization problems when the underlying function is indefinite and (n-1)-convex. Our structural result about this reduction technique enables us to give descriptions for the convex envelope of a variety of two-dimensional functions. [ABSTRACT FROM AUTHOR]

The recently introduced proximal average of two convex functions is a convex function with many useful properties. In this paper, we introduce and systematically study the proximal average for finitely many convex functions. The basic properties of the proximal average with respect to the standard convex-analytical notions (domain, Fenchel conjugate, subdifferential, proximal mapping, epi-continuity, and others) are provided and illustrated by several examples. [ABSTRACT FROM AUTHOR]

Recently, a semidefinite programming (SDP) relaxation approach has been proposed to solve the sensor network localization problem. Although it achieves high accuracy in estimating the sensor locations, the speed of the SDP approach is not satisfactory for practical applications. In this paper we propose methods to further relax the SDP relaxation, more precisely, to relax the single semidefinite matrix cone into a set of small-size semidefinite submatrix cones, which we call a sub-SDP (SSDP) approach. We present two such relaxations. Although they are weaker than the original SDP relaxation, they retain the key theoretical property, and numerical experiments show that they are both efficient and accurate. The speed of the SSDP is even faster than that of other approaches based on weaker relaxations. The SSDP approach may also pave a way to efficiently solving general SDP problems without sacrificing the solution quality. [ABSTRACT FROM AUTHOR]

We investigate hierarchies of semidefinite approximations for the chromatic number X(G) of a graph G. We introduce an operator Ϋ mapping any graph parameter ß(G), nested between the stability number α(G) and X(Ḡ), to a new graph parameter Ϋß(G), nested between α(Ḡ) and X(G); Ϋß(G) is polynomial time computable if ß(G) is. As an application, there is no polynomial time computable graph parameter nested between the fractional chromatic number X*(·) and X(·) unless P = NP. Moreover, based on the Motzkin-Straus formulation for α(G), we give (quadratically constrained) quadratic and copositive programming formulations for X(G). Under some mild assumptions, n/ß(G) ≤ Ϋß(G), but, while n/ß(G) remains below X*(G), Ϋß(G) can reach X(G) (e.g., for ß(·) = α(·)). We also define new polynomial time computable lower bounds for X(G), improving the classic Lovász theta number (and its strengthenings obtained by adding nonnegativity and triangle inequalities); experimental results on Hamming graphs, Kneser graphs, and DIMACS benchmark graphs will be given in the follow-up paper [N. Gvozdenović and M. Laurent, SIAM J. Optim., 19 (2008), pp. 592-615]. [ABSTRACT FROM AUTHOR]

This paper studies the relationship between the optimal value of a homogeneous quadratic optimization problem and its semidefinite programming (SDP) relaxation. We consider two quadratic optimization models: (1) min{x*Cx | x *Akx≥ 1, k = 0, 1,. . ., m, x ∈ Fn} and (2) max {x*Cx | x*Akχ ≤ 1, k = 0, 1,. . ., m, x ∈ 픞n}, where F is either the real field ℝ or the complex field ℂ, and Ak, C are symmetric matrices. For the minimization model (1), we prove that if the matrix C and all but one of the Ak's are positive semidefinite, then the ratio between the optimal value of (1) and its SDP relaxation is upper bounded by O(m²) when 픞 = ℝ, and by O(m) when 픞 = ℂ. Moreover, when two or more of the Ak's are indefinite, this ratio can be arbitrarily large. For the maximization model (2), we show that if C and at most one of the Ak's are indefinite while other Ak's are positive semidefinite, then the ratio between the optimal value of (2) and its SDP relaxation is bounded from below by O(1/ logm) for both the real and the complex case. This result improves the bound based on the so-called approximate S-Lemma of Ben-Tal, Nemirovski, and Roos [SIAM J. Optim., 13 (2002), pp. 535-560]. When two or more of the Ak's in (2) are indefinite, we derive a general bound in terms of the problem data and the SDP solution. For both optimization models, we present examples to show that the derived approximation bounds are essentially tight. [ABSTRACT FROM AUTHOR]

Abstract. Let A : Y —• X be a linear map and K ⊆ X be a regular closed convex cone. Consider the problem of finding a nontrivial solution to the conic feasibility problem Ay ∈ K. Condition numbers for this problem (as well as for related ones) are studied to quantify various issues concerning properties of the conic feasibility problem. Some issues especially relevant are the behavior of the problem under data perturbations, the geometry of the set of solutions, and the complexity analyses of algorithms that solve the problem. In this paper we define and characterize a condition number that exploits the possible factorization of K as a product of simpler cones. This condition number extends both Renegar's condition number and the one we defined in [Math. Program., 91 (2001), pp. 163-174] for polyhedral conic systems. We see these results as a step in developing a theory of conditioning that takes into account the structure of the problem. [ABSTRACT FROM AUTHOR]

In this paper, we present new convergence properties of the primal-dual method based on four types of augmented Lagrangian functions in the context of constrained global optimization. Convergence to a global optimal solution is first established for a basic primal-dual scheme under standard conditions. We then prove this convergence property for a modified augmented Lagrangian method using a safeguarding strategy without appealing to the boundedness assumption of the multiplier sequence. We further show that, under the same weaker conditions, the convergence to a global optimal solution can still be achieved by either modifying the multiplier updating rule or normalizing the multipliers in augmented Lagrangian methods. [ABSTRACT FROM AUTHOR]

Approximability of sliding motions for control systems governed by nonlinear finite-dimensional differential equations is considered. This regularity property is shown to be equivalent to Tikhonov well-posedness of a related minimization problem in the context of relaxed controls. This allows the derivation of a general approximability result, which in the autonomous case has an easy to verify geometrical formulation. In the second part of the paper, we consider nonapproximable sliding mode control systems. In the flavor of regularization of ill-posed problems, we propose a method of selection of well-behaved approximating trajectories converging to a prescribed ideal sliding. [ABSTRACT FROM AUTHOR]

This paper is concerned with the Lipschitzian behavior of the optimal set of convex semi-infinite optimization problems under continuous perturbations of the right-hand side of the constraints and linear perturbations of the objective function. In this framework we provide a sufficient condition for the metric regularity of the inverse of the optimal set mapping. This condition consists of the Slater constraint qualification, together with a certain additional requirement in the Karush-Kuhn-Tucker conditions. For linear problems this sufficient condition turns out to be also necessary for the metric regularity, and it is equivalent to some well-known stability concepts. [ABSTRACT FROM AUTHOR]

We present a new generating set search (GSS) approach for minimizing functions subject to linear constraints. GSS is a class of direct search optimization methods that includes generalized pattern search. One of our main contributions in this paper is a new condition to define the set of conforming search directions that admits several computational advantages. For continuously differentiable functions we also derive a bound relating a measure of stationarity, which is equivalent to the norm of the gradient of the objective in the unconstrained case, and a parameter used by GSS algorithms to control the lengths of the steps. With the additional assumption that the derivative is Lipschitz, we obtain a big-O bound. As a consequence of this relationship, we obtain subsequence convergence to a KKT point, even though GSS algorithms lack explicit gradient information. Numerical results indicate that the bound provides a reasonable estimate of stationarity. [ABSTRACT FROM AUTHOR]

The group Steiner tree problem consists of, given a graph G, a collection R of subsets of V (G), and a positive cost ce for each edge e of G, finding a minimum-cost tree in G that contains at least one vertex from each R ∈ R. We call the sets in R groups. The well-known Steiner tree problem is the special case of the group Steiner tree problem in which each set in R is unitary. In this paper, we present a general reduction test designed to remove group vertices, that is, vertices belonging to some group. Through the use of these tests we can conclude that a given group vertex can be considered a nonterminal and hence can be removed from its group. We also present some computational results on instances from SteinLib [T. Koch, A. Martin, and S. Voss, SteinLib: An updated library on Steiner tree problems in graphs, in Steiner Trees in Industry, Kluwer Academic Publishers, Dordrecht, The Netherlands, 2001, pp. 285-325]. [ABSTRACT FROM AUTHOR]

This paper deals with approximate (ε-efficient) solutions of vector optimization problems. We introduce a new ε-efficiency concept which extends and unifies different approximate solution notions introduced in the literature. We obtain necessary and sufficient conditions via nonlinear scalarization, which allow us to study this new class of approximate solutions in a general framework, since any convexity hypothesis is required. Several examples are proposed to show the concepts introduced and the results attained. [ABSTRACT FROM AUTHOR]

The objectives of this paper are twofold. We devise a general framework for identifying locally optimal algorithmic parameters. Algorithmic parameters are treated as decision variables in a problem for which no derivative knowledge or existence is assumed. A derivative-free method for optimization seeks to minimize some measure of performance of the algorithm being fine-tuned. This measure is treated as a black-box and may be chosen by the user. Examples are given in the text. The second objective is to illustrate this framework by specializing it to the identification of locally optimal trust-region parameters in unconstrained optimization. The derivative-free method chosen to guide the process is the mesh adaptive direct search, a generalization of pattern search methods. We illustrate the flexibility of the latter and in particular make provision for surrogate objectives. Locally, optimal parameters with respect to overall computational time on a set of test problems are identified. Each function call may take several hours and may not always return a predictable result. A tailored surrogate function is used to guide the search towards a local solution. The parameters thus identified differ from traditionally used values, and allow one to solve a problem that remained otherwise unsolved in a reasonable time using traditional values. [ABSTRACT FROM AUTHOR]

In this paper, we consider Levitin--Polyak-type well-posedness for a general constrained optimization problem. We introduce generalized Levitin--Polyak well-posedness and strongly generalized Levitin--Polyak well-posedness. Necessary and sufficient conditions for these types of well-posedness are given. Relations among these types of well-posedness are investigated. Finally, we consider convergence of a class of penalty methods and a class of augmented Lagrangian methods under the assumption of strongly generalized Levitin--Polyak well-posedness. [ABSTRACT FROM AUTHOR]

The problem of minimizing a conic function subject to an ellipsoidal constraint is discussed in this paper. The feasible set of this problem is divided into three different cases. Necessary and sufficient optimality conditions are obtained for different cases where there is a characterization of optimality for the basic case. These conditions provide a sound basis for the further development of efficient methods for trust-region subproblems of a conic model. [ABSTRACT FROM AUTHOR]

In this paper we consider a general optimization problem (OP) and study the convergence and approximation of optimal values and optimal solutions to changes in the cost function and the set of feasible solutions. By a "general" OP we mean that the cost function and the constraints are defined on a Hausdorff topological space. First we obtain convergence results for a general OP, and then we present an application of these results on the approximation of the optimal value and the optimal solutions for the so-called general capacity problem in metric spaces. [ABSTRACT FROM AUTHOR]

In this paper we propose a global algorithm for solving nonlinear semidefinite programming problems. This algorithm, inspired by the classic SQP {sequentially quadratic programming) method, modifies the S-SDP {sequentially semidefinite programming) local method by using a nondifferentiable merit function combined with a line search strategy. [ABSTRACT FROM AUTHOR]

In this paper we prove global convergence for asynchronous parallel pattern search. In standard pattern search, decisions regarding the update of the iterate and the step-length control parameter are synchronized implicitly across all search directions. We lose this feature in asynchronous parallel pattern search since the search along each direction proceeds semiautonomously. By bounding the value of the step-length control parameter after any step that produces decrease along a single search direction, we can prove that all the processes share a common accumulation point and, if the function is continuously differentiable, that such a point is a stationary point of the standard nonlinear unconstrained optimization problem. [ABSTRACT FROM AUTHOR]

In this paper we introduce different relaxations of the concept of active constraint at a given point with respect to a certain linear inequality system with an arbitrary number of constraints. We show that these concepts provide useful local information in linear optimization, for instance conditions for a given feasible solution to be a unique, extreme point, optimal solution or a strongly unique optimal solution. [ABSTRACT FROM AUTHOR]

In this paper, by means of the concept of the working set, which is an estimate of the active set, we propose a feasible sequential linear equation algorithm for solving inequality constrained optimization problems. At each iteration of the proposed algorithm, we first solve one system of linear equations with a coefficient matrix of size m x m (where m is the number of constraints) to compute the working set; we then solve a subproblem which consists of four reduced systems of linear equations with a common coefficient matrix. Unlike existing QP-free algorithms, the subproblem is concerned with only the constraints corresponding to the working set. The constraints not in the working set are neglected. Consequently, the dimension of each subproblem is not of full dimension. Without assuming the isolatedness of the stationary points, we prove that every accumulation point of the sequence generated by the proposed algorithm is a KKT point, of the problem. Moreover, after finitely many iterations, the working set becomes independent of the iterates and is essentially the same as the active set of the KKT point. In other words, after finitely many steps, only those constraints which are active at the solution will be involved in the subproblem. Under some additional conditions, we show that the convergence rate is two-step superlinear or even Q-superlinear. We also report some preliminary numerical experiments to show that the proposed algorithm is practicable and effective for the test problems. [ABSTRACT FROM AUTHOR]

This paper gives conditions ensuring the epiconvergence or P-convergence of sequences of convexly composite functions via the study of Painlevé-Kuratowski convergence of inverse images of sets. The convergence of multipliers of optimization problems associated with convexly composite functions is also established. [ABSTRACT FROM AUTHOR]

Duality and penalty methods are popular in optimization. The study on duality and penalty methods for nonconvex multiobjective optimization problems is very limited, in this paper, we introduce vector valued nonlinear Lagrangian and penalty functions and formulate nonlinear Lagrangian dual problems and nonlinear penalty problems for multiobjective constrained optimization problems. We establish strong duality and exact penalization results. The strong duality is an inclusion between the set of infimum points of the original multiobjective constrained optimization problem and that of the nonlinear Lagrangian dual problem. Exact penalization is established via. a generalized calmness-type condition. [ABSTRACT FROM AUTHOR]

In this paper, we present, first- and second-order variational conditions for a convex composite function go F, where g is a nonsmooth convex function and F is a vector valued map. The first-order results, which apply to (not, necessarily locally Lipsehitz) continuous maps F, not only recapture the results of the special cases where F is locally Lipschitz or Gâteaux differentiable but also yield sharp necessary variational conditions in these eases. The result, s arc achieved by applying a new strengthened notion of approximate Jacobian, called a Gâteaux (G) approximate Jacobian, without the use of the upper semicontinuity of the approximate Jacobian. These variational results are generally derived by using a chain rule formula or by constructing upper convex approximations to the composite function. These approaches often need the upper semicontinuity requirement of a generalized Jacobian map. Such a requirement not only limits the derivation of sharp optimality conditions, as the "small" approximate Jacobians (or generalized subdifferentials) lack an upper semi-continuity property, but also restricts the treatment of Gâteaux differentiable maps F. This situation is overcome by the use of G-approximate Jacobians. The second order variational conditions are shown to hold, in particular, in the case where F is continuously Gâteaux differentiable. [ABSTRACT FROM AUTHOR]

We outline a new approach for radiosurgery treatment planning, based on solving a series of optimization problems. We consider a specific treatment planning problem for a specialized device known as the gamma knife which provides an advanced stereotactic approach to the treatment, of tumors, vascular malformations, and pain disorders within the head. Tile sequence of optimization problems involves nonlinear and mixed integer programs whose solution is required in a given planning time (typically less than 30 minutes). This paper outlines several modeling decisions that result in more efficient and robust, solutions. Furthermore, it, outlines a new approach for determining starting points for the nonlinear programs, based on a skeletonization of the target volume. Treatment plans generated for real patient data show the efficiency of the approach. [ABSTRACT FROM AUTHOR]

We introduce a new barrier-type function which is not, a barrier function in the usual sense: it has finite value at the boundary of the feasible region. Despite this, the iteration bound of a large-update interior-point method based on this function is shown to be O(square root of n (log n) log n/epsilon), which is as good as tile currently best known bound for large update methods. The recently introduced properly of exponential convexity for the kernel function underlying the barrier function, as well as the strong convexity of the kernel function, are crucial in the analysis. [ABSTRACT FROM AUTHOR]

Cubic-regularization and trust-region methods with worst-case first-order complexity O(ε-3/2) and worst-case second-order complexity O(ε-3/2) have been developed in the last few years. In this paper it is proved that the same complexities are achieved by means of a quadratic-regularization method with a cubic sufficient-descent condition instead of the more usual predicted-reduction based descent. Asymptotic convergence and order of convergence results are also presented. Finally, some numerical experiments comparing the new algorithm with a well-established quadratic regularization method are shown. [ABSTRACT FROM AUTHOR]

We present efficiency criteria for multicriteria problems with 힎(T)-valued maps via directional derivatives and subdifferentials. It turns out that the essential structure of similar results known for ℝn-valued optimization problems remains valid. As an improvement, our formulas allow us to distinguish between efficient and weakly efficient elements. [ABSTRACT FROM AUTHOR]

We present an algorithm for large-scale equality constrained optimization. The method is based on a characterization of inexact sequential quadratic programming (SQP) steps that can ensure global convergence. Inexact SQP methods are needed for large-scale applications for which the iteration matrix cannot be explicitly formed or factored and the arising linear systems must be solved using iterative linear algebra techniques. We address how to determine when a given inexact step makes sufficient progress toward a solution of the nonlinear program, as measured by an exact penalty function. The method is globalized by a line search. An analysis of the global convergence properties of the algorithm and numerical results are presented. [ABSTRACT FROM AUTHOR]