Search

In this paper, we investigate the separations and optimality conditions for the optimal solution defined by the improvement set of a constrained multiobjective optimization problem. We introduce a vector-valued regular weak separation function and a scalar weak separation function via a nonlinear scalarization function defined in terms of an improvement set. The nonlinear separation between the image of the multiobjective optimization problem and an improvement set in the image space is established by the scalar weak separation function. Saddle point type optimality conditions for the optimal solution of the multiobjective optimization problem are established, respectively, by the nonlinear and linear separation methods. We also obtain the relationships between the optimal solution and approximate efficient solution of the multiobjective optimization problem. Finally, sufficient and necessary conditions for the (regular) linear separation between the approximate image of the multiobjective optimization problem and a convex cone are also presented. [ABSTRACT FROM AUTHOR]

This paper considers a class of vector variational inequalities. First, we present an equivalent formulation, which is a scalar variational inequality, for the deterministic vector variational inequality. Then we concentrate on the stochastic circumstance. By noting that the stochastic vector variational inequality may not have a solution feasible for all realizations of the random variable in general, for tractability, we employ the expected residual minimization approach, which aims at minimizing the expected residual of the so-called regularized gap function. We investigate the properties of the expected residual minimization problem, and furthermore, we propose a sample average approximation method for solving the expected residual minimization problem. Comprehensive convergence analysis for the approximation approach is established as well. [ABSTRACT FROM AUTHOR]

A nonlinear stepsize control (NSC) framework has been proposed by Toint (Optim Methods Softw 28:82-95, 2013) for unconstrained optimization, generalizing several trust-region and regularization algorithms. More recently, worst-case complexity bounds to achieve approximate first-order optimality were proved by Grapiglia, Yuan and Yuan (Math Program 152:491-520, 2015) for the generic NSC framework. In this paper, improved complexity bounds for first-order optimality are obtained. Furthermore, complexity bounds for second-order optimality are also provided. [ABSTRACT FROM AUTHOR]

In this paper, we consider first the most important classes of cone convexlike vector-valued functions and give a dual characterization for some of these classes. It turns out that these characterizations are strongly related to the closely convexlike and Ky Fan convex bifunctions occurring within minimax problems. Applying the Lagrangian perturbation approach, we show that some of these classes of cone convexlike vector-valued functions show up naturally in verifying strong Lagrangian duality for finite-dimensional optimization problems. This is achieved by extending classical convexity results for biconjugate functions to the class of so-called almost convex functions. In particular, for a general class of finite-dimensional optimization problems, strong Lagrangian duality holds if some vector-valued function related to this optimization problem is closely K-convexlike and satisfies some additional regularity assumptions. For K a full-dimensional convex cone, it turns out that the conditions for strong Lagrangian duality simplify. Finally, we compare the results obtained by the Lagrangian perturbation approach worked out in this paper with the results achieved by the so-called image space approach initiated by Giannessi. [ABSTRACT FROM AUTHOR]

This paper deals with optimal control problems described by higher index DAEs. We introduce a class of problems which can be transformed to index one control problems. For these problems we show in the accompanying paper that, if the solutions to the adjoint equations are well-defined, then the first-order approximations to the functionals defining the problem can be expressed in terms of the adjoint variables. In this paper we show that the solutions to the adjoint equations are essentially bounded measurable functions. Then, based on the first order approximations, we derive the necessary optimality conditions for the considered class of control problems. These conditions do not require the transformation of the DAEs to index-one system; however, higher-index DAEs and their associated adjoint equations have to be solved. [ABSTRACT FROM AUTHOR]

This paper deals with optimal control problems described by higher index DAEs. We introduce a class of these problems which can be transformed to index one control problems. For this class of higher index DAEs, we derive first-order approximations and adjoint equations for the functionals defining the problem. These adjoint equations are then used to state, in the accompanying paper, the necessary optimality conditions in the form of a weak maximum principle. The constructive way used to prove these optimality conditions leads to globally convergent algorithms for control problems with state constraints and defined by higher index DAEs. [ABSTRACT FROM AUTHOR]

In this paper, we study quasistatic abstract variational inequalities with time-dependent constraints. We prove existence results and present an approximation method valid for nonsmooth constraints. Then, we apply our results to the approximation of the quasistatic evolution of an elastic body in bilateral contact with a rigid foundation. The contact involves viscous friction of the Tresca or Coulomb type.We prove existence results for approximate problems and give a full asymptotic analysis, proving strong or weak convergence results. Our work is motivated by the numerical study in the paper [Delost, M.: Quasistatic Problem with Frictional Contact: Comparison between Numerical Methods and Asymptotic Analysis Related to Semi Discrete and Fully Discrete Approximations. University of Nice, Nice (2007, to appear)] and explains the choice of the approximation made in it. [ABSTRACT FROM AUTHOR]

The paper discusses several versions of the method of shortest residuals, a specific variant of the conjugate gradient algorithm, first introduced by Lemaréchal and Wolfe and discussed by Hestenes in a quadratic case. In the paper we analyze the global convergence of the versions considered. Numerical comparison of these versions of the method of shortest residuals and an implementation of a standard Polak–Ribière conjugate gradient algorithm is also provided. It supports the claim that the method of shortest residuals is a viable technique, competitive to other conjugate gradient algorithms. [ABSTRACT FROM AUTHOR]

The approximation of a multivector by a decomposable one is a distance-optimization problem between the multivector and the Grassmann variety of lines in a projective space. When the multivector diverges from the Grassmann variety, then the approximate solution sought is the worst possible. In this paper, it is shown that the worst solution of this problem is achieved, when the eigenvalues of the matrix representation of a related two-vector are all equal. Then, all these pathological points form a projective variety. We derive the equation describing this projective variety, as well as its maximum distance from the corresponding Grassmann variety. Several geometric and algebraic properties of this extremal variety are examined, providing a new aspect for the Grassmann varieties and the respective projective spaces. [ABSTRACT FROM AUTHOR]

Dual decomposition has been successfully employed in a variety of distributed convex optimization problems solved by a network of computing and communicating nodes. Often, when the cost function is separable but the constraints are coupled, the dual decomposition scheme involves local parallel subgradient calculations and a global subgradient update performed by a master node. In this paper, we propose a consensus-based dual decomposition to remove the need for such a master node and still enable the computing nodes to generate an approximate dual solution for the underlying convex optimization problem. In addition, we provide a primal recovery mechanism to allow the nodes to have access to approximate near-optimal primal solutions. Our scheme is based on a constant stepsize choice, and the dual and primal objective convergence are achieved up to a bounded error floor dependent on the stepsize and on the number of consensus steps among the nodes. [ABSTRACT FROM AUTHOR]

This paper presents a real-time solution method of the maximum divert trajectory optimization problem for planetary landing. In mid-course, the vehicle is to abort and retarget to a landing site as far from the nominal as physically possible. The divert trajectory must satisfy velocity constraints in the range and cross range directions and a total speed constraint. The thrust magnitude is bounded above and below so that once on, the engine cannot be turned off. Because this constraint is not convex, it is relaxed to a convex constraint and lossless convexification is proved. A transformation of variables is introduced in the nonlinear dynamics and an approximation is made so that the problem becomes a second-order cone problem, which can be solved to global optimality in polynomial time whenever a feasible solution exists. A number of examples are solved to illustrate the effectiveness and efficiency of the solution method. [ABSTRACT FROM AUTHOR]

In this paper, as an extension of a previous study, an improved approximation for the Gaussian Q-function is presented. The nonlinear least squares algorithm is employed to optimize the coefficients of the proposed approximation. The accuracy of the presented approximation is evaluated using extensive computer simulations. Results show that the proposed approximation has superior accuracy in high arguments' region when compared to the performance of other approaches introduced in the literature. [ABSTRACT FROM AUTHOR]

The set of polynomials that are nonnegative over a subset of the nonnegative orthant (we call them set-semidefinite) have many uses in optimization. A common example of this type set is the set of copositive matrices, where we are effectively considering nonnegativity over the entire nonnegative orthant and are restricted to homogeneous polynomials of degree two. Lasserre (SIAM J. Optim., 21(3):864-885, ) has previously considered a method using moments in order to provide an outer approximation to this set, for nonnegativity over a general subset of the real space. In this paper, we shall show that, in the special case of considering nonnegativity over a subset of the nonnegative orthant, we can provide a new outer approximation hierarchy. This is based on restricting moment matrices to be completely positive, and it is at least as good as Lasserre's method. This can then be relaxed to give tractable approximations that are still at least as good as Lasserre's method. In doing this, we also provide interesting new insights into the use of moments in constructing these approximations. [ABSTRACT FROM AUTHOR]

The majority of engineering optimization problems (design, identification, design of controlled systems, optimization of large-scale systems, operational development of prototypes, and so on) are essentially multicriteria. The correct determination of the feasible solution set is a major challenge in engineering optimization problems. In order to construct the feasible solution set, a method called PSI (Parameter Space Investigation) has been created and successfully integrated into various fields of industry, science, and technology. Owing to the PSI method, it has become possible to formulate and solve a wide range of multicriteria optimization problems. In addition to giving an overview of the PSI method, this paper also describes the methods for approximation of the feasible and Pareto optimal solution sets, identification, decomposition, and aggregation of the large-scale systems. [ABSTRACT FROM AUTHOR]

In this paper, we propose and analyze an algorithm that couples the gradient method with a general exterior penalization scheme for constrained or hierarchical minimization of convex functions in Hilbert spaces. We prove that a proper but simple choice of the step sizes and penalization parameters guarantees the convergence of the algorithm to solutions for the optimization problem. We also establish robustness and stability results that account for numerical approximation errors, discuss implementation issues and provide examples in finite and infinite dimension. [ABSTRACT FROM AUTHOR]

In partitioning methods such as branch and bound for solving global optimization problems, the so-called bisection of simplices and hyperrectangles is used since almost 40 years. Bisections are also of interest in finite-element methods. However, as far as we know, no proof has been given of the optimality of bisections with respect to other partitioning strategies. In this paper, after generalizing the current definition of partition slightly, we show that bisection is not optimal. Hybrid approaches combining different subdivision strategies with inner and outer approximation techniques can be more efficient. Even partitioning a polytope into simplices has important applications, for example in computational convexity, when one wants to find the inequality representation of a polytope with known vertices. Furthermore, a natural approach to the computation of the volume of a polytope P is to generate a simplex partition of P, since the volume of a simplex is given by a simple formula. We propose several variants of the partitioning rules and present complexity considerations. Finally, we discuss an approach for the volume computation of so-called H-polytopes, i.e., polytopes given by a system of affine inequalities. Upper bounds for the number of iterations are presented and advantages as well as drawbacks are discussed. [ABSTRACT FROM AUTHOR]

This paper is devoted to the study of a new necessary condition in variational inequality problems: approximated gradient projection (AGP). A feasible point satisfies such condition if it is the limit of a sequence of the approximated solutions of approximations of the variational problem. This condition comes from optimization where the error in the approximated solution is measured by the projected gradient onto the approximated feasible set, which is obtained from a linearization of the constraints with slack variables to make the current point feasible. We state the AGP condition for variational inequality problems and show that it is necessary for a point being a solution even without constraint qualifications (e.g., Abadie's). Moreover, the AGP condition is sufficient in convex variational inequalities. Sufficiency also holds for variational inequalities involving maximal monotone operators subject to the boundedness of the vectors in the image of the operator (playing the role of the gradients). Since AGP is a condition verified by a sequence, it is particularly interesting for iterative methods. [ABSTRACT FROM AUTHOR]

The notions of upper and lower exhausters were introduced by Demyanov (Optimization 45:13-29, 1999). Upper and lower exhausters can be employed to study a very wide range of positively homogeneous functions, for example, various directional derivatives of nonsmooth functions. Exhausters are not uniquely defined; hence, the problem of minimality arises naturally. This paper describes some techniques for reducing exhausters, both in size and amount of sets. We define also a modified convertor which provides much more flexibility in converting upper exhausters to lower ones and vice versa, and allows us to obtain much smaller sets. [ABSTRACT FROM AUTHOR]

Active constraint set invariancy sensitivity analysis is concerned with finding the range of parameter variation so that the perturbed problem has still an optimal solution with the same support set that the given optimal solution of the unperturbed problem has. However, in an optimization problem with inequality constraints, active constraint set invariancy sensitivity analysis aims to find the range of parameter variation, where the active constraints in a given optimal solution remains invariant. For the sake of simplicity, we consider the primal problem in standard form and consequently its dual may have an optimal solution with some active constraints. In this paper, the following question is answered: ‘what is the range of the parameter, where for each parameter value in this range, a dual optimal solution exists with exactly the same set of positive slack variables as for the current dual optimal solution?’. The differences of the results between the linear and convex quadratic optimization problems are highlighted too. [ABSTRACT FROM AUTHOR]

In this paper we discuss necessary and sufficient conditions for different minimax results to hold using only linear programming duality and the finite intersection property for compact sets. It turns out that these necessary and sufficient conditions have a clear interpretation within zero-sum game theory. We apply these results to derive necessary and sufficient conditions for strong duality for a general class of optimization problems. [ABSTRACT FROM AUTHOR]

This paper extends some theoretical properties of the conjugate gradient-type method FLR (Ref. 1) for iteratively solving indefinite linear systems of equations. The latter algorithm is a generalization of the conjugate gradient method by Hestenes and Stiefel (CG, Ref. 2).We develop a complete relationship between the FLR algorithm and the Lanczos process, in the case of indefinite and possibly singular matrices. Then, we develop simple theoretical results for the FLR algorithm in order to construct an approximation of the Moore-Penrose pseudoinverse of an indefinite matrix. Our approach supplies the theoretical framework for applications within unconstrained optimization. [ABSTRACT FROM AUTHOR]

This paper proposes a line search technique to satisfy a relaxed form of the strong Wolfe conditions in order to guarantee the descent condition at each iteration of the Polak-Ribière-Polyak conjugate gradient algorithm. It is proved that this line search algorithm preserves the usual convergence properties of any descent algorithm. In particular, it is shown that the Zoutendijk condition holds under mild assumptions. It is also proved that the resulting conjugate gradient algorithm is convergent under a strong convexity assumption. For the nonconvex case, a globally convergent modification is proposed. Numerical tests are presented. [ABSTRACT FROM AUTHOR]

In the present paper, we investigate an approximation technique for relaxed optimal control problems. We study control processes governed by ordinary differential equations in the presence of state, target, and integral constraints. A variety of approximation schemes have been recognized as powerful tools for the theoretical studying and practical solving of Infinite-dimensional optimization problems. On the other hand, theoretical approaches to the relaxed optimal control problem with constraints are not sufficiently advanced to yield numerically tractable schemes. The explicit approximation of the compact control set makes it possible to reduce the sophisticated relaxed problem to an auxiliary optimization problem. A given trajectory of the relaxed problem can be approximated by trajectories of the auxiliary problem. An optimal solution of the introduced optimization problem provides a basis for the construction of minimizing sequences for the original optimal control problem. We describe how to carry out the numerical calculations in the context of nonlinear programming and establish the convergence properties of the obtained approximations. [ABSTRACT FROM AUTHOR]

This paper discusses optimization problems with nonlinear inequality constraints and presents a new sequential quadratically-constrained quadratic programming (NSQCQP) method of feasible directions for solving such problems. At each iteration, the NSQCQP method solves only one subproblem which consists of a convex quadratic objective function, convex quadratic equality constraints, as well as a perturbation variable and yields a feasible direction of descent (improved direction). The following results on the NSQCQP are obtained: the subproblem solved at each iteration is feasible and solvable: the NSQCQP is globally convergent under the Mangasarian-Fromovitz constraint qualification (MFCQ); the improved direction can avoid the Maratos effect without the assumption of strict complementarity; the NSQCQP is superlinearly and quasiquadratically convergent under some weak assumptions without the strict complementarity assumption and the linear independence constraint qualification (LICQ). [ABSTRACT FROM AUTHOR]

This paper presents a perturbation approach for performing sensitivity analysis of mathematical programming problems. Contrary to standard methods, the active constraints are not assumed to remain active if the problem data are perturbed, nor the partial derivatives are assumed to exist. In other words, all the elements, variables, parameters, Karush-Kuhn-Tucker multipliers, and objective function values may vary provided that optimality is maintained and the general structure of a feasible perturbation (which is a polyhedral cone) is obtained. This allows determining: (a) the local sensitivities, (b) whether or not partial derivatives exist, and (c) if the directional derivative for a given direction exists. A method for the simultaneous obtention of the sensitivities of the objective function optimal value and the primal and dual variable values with respect to data is given. Three examples illustrate the concepts presented and the proposed methodology. Finally, some relevant conclusions are drawn. [ABSTRACT FROM AUTHOR]

In this paper, we present a new conjugate gradient (CG) based algorithm in the class of planar conjugate gradient methods. These methods aim at solving systems of linear equations whose coefficient matrix is indefinite and nonsingular. This is the case where the application of the standard CG algorithm by Hestenes and Stiefel (Ref. 1) may fail, due to a possible division by zero. We give a complete proof of global convergence for a new planar method endowed with a general structure; furthermore, we describe some important features of our planar algorithm, which will be used within the optimization numerical results are reported. [ABSTRACT FROM AUTHOR]

Several risk management and exotic option pricing models have been proposed in the literature which may price European options correctly. A prerequisite of these models is the interpolation of the market implied volatilities or the European option price function. However, the no-arbitrage principle places shape restrictions on the option price function. In this paper, an interpolation method is developed to preserve the shape of the option price function. The interpolation is optimal in terms of minimizing the distance between the implied risk-neutral density and the prior approximation function in L2-norm, which is important when only a few observations are available. We reformulate the problem into a system of semismooth equations so that it can be solved efficiently. [ABSTRACT FROM AUTHOR]

Multiparametric programming considers optimization problems where the data are functions of a parameter vector and describes the optimal value and an optimizer as explicit functions of the parameters. In this paper, we consider a linear program where the right-hand side is an affine function of a parameter vector; we propose an algorithm for approximating its solution. Given a full-dimensional simplex in the parameter space and an optimizer for each simplex vertex, the algorithm formulates the linear interpolation of the given solutions as an explicit function of the parameters, giving a primal feasible approximation of an optimizer inside the simplex. If the resulting absolute error in the objective exceeds a prescribed tolerance, then the algorithm subdivides the simplex into smaller simplices where it applies recursively. We propose both a basic version and a refined version of the algorithm. The basic version is polynomial in the output size, provided a polynomial LP solver is used; the refined version may give a smaller output. A global error bound for the optimizer is derived and some computational tests are discussed. [ABSTRACT FROM AUTHOR]