Interior-Point Lagrangian Decomposition Method for Separable Convex Optimization

In this paper, we propose a distributed algorithm for solving large-scale separable convex problems using Lagrangian dual decomposition and the interior-point framework. By adding self-concordant barrier terms to the ordinary Lagrangian, we prove under mild assumptions that the corresponding family of augmented dual functions is self-concordant. This makes it possible to efficiently use the Newton method for tracing the central path. We show that the new algorithm is globally convergent and highly parallelizable and thus it is suitable for solving large-scale separable convex problems.     

Vaidya’s Method for Convex Stochastic Optimization Problems in Small Dimension

Mathematical Notes - The paper deals with a general problem of convex stochastic optimization in a space of small dimension (for example, 100 variables). It is known that for deterministic problems...     

Recursive Algorithms for Trailing Stop: Stochastic Approximation Approach

Trailing stops are often used in stock trading to limit the maximum of a possible loss and to lock in a profit. This work develops stochastic approximation algorithms to estimate the optimal trailing stop percentage. A stochastic optimization approach is proposed to recursively estimate the desired trailing stop percentage. A modification using projection is developed to ensure that the approximation sequence constructed stays in a reasonable range. Convergence of the algorithm is obtained. Moreover, interval estimates are constructed. Simulation examples are presented to compare our algorithm with Monte Carlo methods. Finally, we use real market data to demonstrate the algorithms.     

On Cone Characterizations of Strong and Lexicographic Optimality in Convex Multiobjective Optimization

Various type of optimal solutions of multiobjective optimization problems can be characterized by means of different cones. Provided the partial objectives are convex, we derive necessary and sufficient geometrical optimality conditions for strongly efficient and lexicographically optimal solutions by using the contingent, feasible and normal cones. Combining new results with previously known ones, we derive two general schemes reflecting the structural properties and the interconnections of five optimality principles: weak and proper Pareto optimality, efficiency and strong efficiency as well as lexicographic optimality.     

Hybrid Conjugate Gradient Method for a Convex Optimization Problem over the Fixed-Point Set of a Nonexpansive Mapping

The main aim of the paper is to accelerate the existing method for a convex optimization problem over the fixed-point set of a nonexpansive mapping. To achieve this goal, we present an algorithm (Algorithm 3.1) by using the conjugate gradient direction. We present also a convergence analysis (Theorem 3.1) under some assumptions. Finally, to demonstrate the effectiveness and performance of the proposed method, we present numerical comparisons of the existing method with the proposed method.     

Convergence of Algorithms in Optimization and Solutions of Nonlinear Equations

It is desirable that an algorithm in unconstrained optimization converges when the guessed initial position is anywhere in a large region containing a minimum point. Furthermore, it is useful to have a measure of the rate of convergence which can easily be computed at every point along a trajectory to a minimum point. The Lyapunov function method provides a powerful tool to study convergence of iterative equations for computing a minimum point of a nonlinear unconstrained function or a solution of a system of nonlinear equations. It is surprising that this popular and powerful tool in the study of dynamical systems is not used directly to analyze the convergence properties of algorithms in optimization. We describe the Lyapunov function method and demonstrate how it can be used to study convergence of algorithms in optimization and in solutions of nonlinear equations. We develop an index which can measure the rate of convergence at all points along a trajectory to a minimum point and not just at points in a small neighborhood of a minimum point. Furthermore this index can be computed when the calculations are being carried out.     

Global Convergence of a Modified Gradient Projection Method for Convex Constrained Problems

In this paper, the continuously differentiable optimization problem min{f（x） ： x∈Ω}, where Ω ∈ R^n is a nonempty closed convex set, the gradient projection method by Calamai and More （Math. Programming, Vol.39. P.93-116, 1987） is modified by memory gradient to improve the convergence rate of the gradient projection method is considered. The convergence of the new method is analyzed without assuming that the iteration sequence {x^k} of bounded. Moreover, it is shown that, when f（x） is pseudo-convex （quasiconvex） function, this new method has strong convergence results. The numerical results show that the method in this paper is more effective than the gradient projection method.     

Beyond Convex? Global Optimization is Feasible Only for Convex Objective Functions: A Theorem

It is known that there are feasible algorithms for minimizing convex functions, and that for general functions, global minimization is a difficult (NP-hard) problem. It is reasonable to ask whether there exists a class of functions that is larger than the class of all convex functions for which we can still solve the corresponding minimization problems feasibly. In this paper, we prove, in essence, that no such more general class exists. In other words, we prove that global optimization is always feasible only for convex objective functions.     

The Million-Variable “March” for Stochastic Combinatorial Optimization

Combinatorial optimization problems have applications in a variety of sciences and engineering. In the presence of data uncertainty, these problems lead to stochastic combinatorial optimization problems which result in very large scale combinatorial optimization problems. In this paper, we report on the solution of some of the largest stochastic combinatorial optimization problems consisting of over a million binary variables. While the methodology is quite general, the specific application with which we conduct our experiments arises in stochastic server location problems. The main observation is that stochastic combinatorial optimization problems are comprised of loosely coupled subsystems. By taking advantage of the loosely coupled structure, we show that decomposition-coordination methods provide highly effective algorithms, and surpass the scalability of even the most efficiently implemented backtracking search algorithms.     

On Optimality Condition for Vector Optimization Based on Convex Set-Valued Mapping

1.IntroductionTheoptimalityconditionsofmathematicalprogrammingisaveryimportantsubjectbecausetLeyprovideausefulanalyticaltoolforstudingthedualitytheoryandnonlinearprogrammingalgoirthms.Inrecelltyears,someauthorshavebeguntostudytheoptimalityconditionsforvectoroptimizationproblemofset-valuedmapping,suchas[4][51.Inthispaperlwedefinetheconceptofcone--weaklyefficientsubdifferentialofset-valuedmappinginthecaseofgeneralpartiallyorderedlocallyconvextopologicalvectorspaces.Thecone-weaklysubdifferential…     

LMI Optimization Approach to Synchronization of Stochastic Delayed Discrete-Time Complex Networks

Complex networks are widespread in real-world systems of engineering, physics, biology, and sociology. This paper is concerned with the problem of synchronization for stochastic discrete-time drive-response networks. A dynamic feedback controller has been proposed to achieve the goal of the paper. Then, based on the Lyapunov second method and LMI (linear matrix inequality) optimization approach, a delay-independent stability criterion is established that guarantees the asymptotical mean-square synchronization of two identical delayed networks with stochastic disturbances. The criterion is expressed in terms of LMIs, which can be easily solved by various convex optimization algorithms. Finally, two numerical examples are given to illustrate the proposed method.     

Switching Time Optimization for Bang-Bang and Singular Controls

Optimal control problems with the control variable appearing linearly are studied. A method for optimization with respect to the switching times of controls containing both bang-bang and singular arcs is presented. This method is based on the transformation of the control problem into a finite-dimensional optimization problem. Therein, first and second-order optimality conditions are thoroughly discussed. Explicit representations of first and second-order variational derivatives of the state trajectory with respect to the switching times are given. These formulas are used to prove that the second-order sufficient conditions can be verified on the basis of only first-order variational derivatives of the state trajectory. The effectiveness of the proposed method is tested with two numerical examples.     

The Projection onto a Direct Product of Convex Cones

ＴｈｅＰｒｏｊｅｃｔｉｏｎｏｎｔｏａＤｉｒｅｃｔｒｏｄｕｃｔｏｆＣｏｎｖｅｘＣｏｎｅｓＬｉｕＷｅｉ（刘维）ａｎｄＳｈｉＮｉｎｇｚｈｏｎｇ（史宁中）（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＮｏｒｔｈｅａｓｔＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｃ...     

Hybrid Conjugate Gradient Algorithm for Unconstrained Optimization

In this paper a new hybrid conjugate gradient algorithm is proposed and analyzed. The parameter β _k is computed as a convex combination of the Polak-Ribière-Polyak and the Dai-Yuan conjugate gradient algorithms, i.e. β _k ^N =(1−θ _k )β _k ^PRP +θ _k β _k ^DY . The parameter θ _k in the convex combination is computed in such a way that the conjugacy condition is satisfied, independently of the line search. The line search uses the standard Wolfe conditions. The algorithm generates descent directions and when the iterates jam the directions satisfy the sufficient descent condition. Numerical comparisons with conjugate gradient algorithms using a set of 750 unconstrained optimization problems, some of them from the CUTE library, show that this hybrid computational scheme outperforms the known hybrid conjugate gradient algorithms. N. Andrei is a member of the Academy of Romanian Scientists, Splaiul Independenţei nr. 54, Sector 5, Bucharest, Romania.     

Weighted Poisson Cells as Models for Random Convex Polytopes

We introduce a parametric family for random convex polytopes in ? ^d which allows for an easy generation of samples for further use, e.g., as random particles in materials modelling and simulation. The basic idea consists in weighting the Poisson cell, which is the typical cell of the stationary and isotropic Poisson hyperplane tessellation, by suitable geometric characteristics. Since this approach results in an exponential family, parameters can be efficiently estimated by maximum likelihood. This work has been motivated by the desire for a flexible model for random convex particles as can be found in many composite materials such as concrete or refractory castables.     

Dual Representations for Convex Risk Measures via Conjugate Duality

The aim of this paper is to give dual representations for different convex risk measures by employing their conjugate functions. To establish the formulas for the conjugates, we use on the one hand some classical results from convex analysis and on the other hand some tools from the conjugate duality theory. Some characterizations of so-called deviation measures recently given in the literature turn out to be direct consequences of our results.     

Algorithms for the Laplace–Stieltjes Transforms of First Return Times for Stochastic Fluid Flows

We derive several algorithms, including quadratically convergent algorithms, which can be used to calculate the Laplace–Stieltjes transforms of the time taken to return to the initial level in the Markovian stochastic fluid flow model. We give physical interpretations of the algorithms and consider their numerical analysis. The numerical performance of the algorithms, which depends on the physical properties of the process, is discussed and illustrated with simple examples. Besides the powerful algorithms, this paper contributes interesting theoretical results. In particular, the methodology for constructing these algorithms is a valuable contribution to the theory of fluid flow models. Moreover, useful physical interpretations of the algorithms, and related expressions, given in terms of the fluid flow model, can assist in further analysis and help in a better understanding of the model. The authors would like to thank the Australian Research Council for funding this research through Discovery Project DP0770388.     

New ODE Methods for Equality Constrained Optimization (2) — Algorithms

As a continuation of [1], this paper considers implementation of ODE approaches. A modified Hamming's algorithm for integration of (ECP)-equation is suggested to obtain a local solution. In addition to the main algorithm, three supporting algorithms are also described: two are for evaluation of the right-hand side of (ECP)-equation, which may be especially suitable for certain kinds of (ECP)-equation when applied to large scale problems; the third one, with a convergence theorem, is for computing an initial feasible point. Our numerical results obtained by executing these algorithms on an example of (ECP)-equation given in [1] on five test problems indicate their remarkable superiority of performance to Tanabe's ODE version that is recently claimed to be much better than some well-known SQP techniques.