The modified subgradient algorithm based on feasible values
Authors:
- Refail KasimbeyliRKRefail Kasimbeyli
- Alex M. RubinovARAlex M. Rubinov
- 1 July 2009
- journal article
- research article
- Published by Taylor & Francis in Optimization
- Vol. 58 (5) , 535-560
Abstract
In this article, we continue to study the modified subgradient (MSG) algorithm previously suggested by Gasimov for solving the sharp augmented Lagrangian dual problems. The most important features of this algorithm are those that guarantees a global optimum for a wide class of non-convex optimization problems, generates a strictly increasing sequence of dual values, a property which is not shared by the other subgradient methods and guarantees convergence. The main drawbacks of MSG algorithm, which are typical for many subgradient algorithms, are those that uses an unconstrained global minimum of the augmented Lagrangian function and requires knowing an approximate upper bound of the initial problem to update stepsize parameters. In this study we introduce a new algorithm based on the so-called feasible values and give convergence theorems. The new algorithm does not require to know the optimal value initially and seeks it iteratively beginning with an arbitrary number. It is not necessary to find a global minimum of the augmented Lagrangian for updating the stepsize parameters in the new algorithm. A collection of test problems are used to demonstrate the performance of the new algorithm.Keywords
This publication has 13 references indexed in Scilit:
- Solving the quadratic assignment problem using F-MSG algorithmJournal of Industrial and Management Optimization, 2007
- On a Modified Subgradient Algorithm for Dual Problems via Sharp Augmented Lagrangian*Journal of Global Optimization, 2006
- Mutiobjective Programming2005
- Complete search in continuous global optimization and constraint satisfaction2004
- An MCDM approach to portfolio optimizationEuropean Journal of Operational Research, 2004
- On augmented Lagrangians for Optimization Problems with a Single ConstraintJournal of Global Optimization, 2004
- Strictly Increasing Positively Homogeneous Functions with Application to Exact PenalizationOptimization, 2003
- Characterization of the Benson Proper Efficiency and Scalarization in Nonconvex Vector Optimization2001
- Handbook of Test Problems in Local and Global Optimization1999
- Variational Analysis1998