Steepest ascent algorithms for nonconical multiple objective programming

A steepest ascent family of algorithms suitable for the direct solution of continuous variable unconstrained nonconical multiple objective programming problems is introduced. Nonconical multiple objective problems, unlike standard (conical) vector optimization problems, cannot be easily solved by examining related single objective problems. The concept of a direction of steepest ascent is generalized to the multiple objective context and the question of algorithmic convergence is treated. A computational example involving a nonconical unanimity order is given.     

Degeneracy: Resolve or Avoid?

Two projected gradient algorithms for linear programming are discussed. The first uses a conventional enough steepest edge approach, and implements a version of Wolfe's method for resolving any problems of degeneracy. The second makes use of a steepest descent direction which is calculated by solving a linear least squares problem subject to bound constraints, and avoids problems of degeneracy altogether. They are compared using randomly generated problems which permit the specification of (known) degenerate minima. The results appear to favour the more conventional method as problem sizes get larger.     

The double pivot simplex method

The simplex method, created by George Dantzig, optimally solves a linear program by pivoting. Dantzig’s pivots move from a basic feasible solution to a different basic feasible solution by exchanging exactly one basic variable with a nonbasic variable. This paper introduces the double pivot simplex method, which can transition between basic feasible solutions using two variables instead of one. Double pivots are performed by identifying the optimal basis in a two variable linear program using a new method called the slope algorithm. The slope algorithm is fast and allows an iteration of DPSM to have the same theoretical running time as an iteration of the simplex method. Computational experiments demonstrate that DPSM decreases the average number of pivots by approximately 41% on a small set of benchmark instances.     

Steepest ascent can be exponential in bounded treewidth problems

We investigate the complexity of local search based on steepest ascent. We show that even when all variables have domains of size two and the underlying constraint graph of variable interactions has bounded treewidth (in our construction, treewidth 7), there are fitness landscapes for which an exponential number of steps may be required to reach a local optimum. This is an improvement on prior recursive constructions of long steepest ascents, which we prove to need constraint graphs of unbounded treewidth.     

New efficient shortest path simplex algorithm: pseudo permanent labels instead of permanent labels

We introduce a new network simplex pivot rule for the shortest path simplex algorithm. This new pivot rule chooses a subset of non-basic arcs to simultaneously enter into the basis. We call this operation a multiple pivot. We show that a shortest path simplex algorithm with this pivot rule performs O(n) multiple pivots and runs in O(nm) time. Our pivot rule is based on the new concept of a pseudo permanently labeled node, and it can be adapted to design a new label-correcting algorithm that runs in O(nm). Moreover, this concept lets us introduce new rules to identify negative cycles. Finally, we compare the network simplex algorithm with multiple pivots with other previously proposed efficient network simplex algorithm in a computational experiment.     

Spectral mapping theorem for ascent,essential ascent,descent and essential descent spectrum of linear relations

In [7], Cross showed that the spectrum of a linear relation T on a normed space satisfies the spectral mapping theorem. In this paper, we extend the notion of essential ascent and descent for an operator acting on a vector space to linear relations acting on Banach spaces. We focus to define and study the descent, essential descent, ascent and essential ascent spectrum of a linear relation everywhere defined on a Banach space X. In particular, we show that the corresponding spectrum satisfy the polynomial version of the spectral mapping theorem.     

Successive unconstrained dual optimization method for?rank-one approximation to tensors

A successive unconstrained dual optimization (SUDO) method is developed to solve the high order tensors?? best rank-one approximation problems, in the least-squares sense. The constrained dual program of tensors?? rank-one approximation is transformed into a sequence of unconstrained optimization problems, for where a fast gradient method is proposed. We introduce the steepest ascent direction, a initial step length strategy and a backtracking line search rule for each iteration. A proof of the global convergence of the SUDO algorithm is given. Preliminary numerical experiments show that our method outperforms the alternating least squares (ALS) method.     

Generating lift-and-project cuts from the LP simplex tableau: open source implementation and testing of new variants

Lift-and-project cuts for mixed integer programs (MIP), derived from a disjunction on an integer-constrained fractional variable, were originally (Balas et al. in Math program 58:295–324, 1993) generated by solving a higher-dimensional cut generating linear program (CGLP). Later, a correspondence established (Balas and Perregaard in Math program 94:221–245, 2003) between basic feasible solutions to the CGLP and basic (not necessarily feasible) solutions to the linear programming relaxation LP of the MIP, has made it possible to mimic the process of solving the CGLP through certain pivots in the LP tableau guaranteed to improve the CGLP objective function. This has also led to an alternative interpretation of lift-and-project (L&P) cuts, as mixed integer Gomory cuts from various (in general neither primal nor dual feasible) LP tableaus, guaranteed to be stronger than the one from the optimal tableau. In this paper we analyze the relationship between a pivot in the LP tableau and the (unique) corresponding block pivot (sequence of pivots) in the CGLP tableau. Namely, we show how a single pivot in the LP defines a sequence (potentially as long as the number of variables) of pivots in the CGLP, and we identify this sequence. Also, we give a new procedure for finding in a given LP tableau a pivot that produces the maximum improvement in the CGLP objective (which measures the amount of violation of the resulting cut by the current LP solution). Further, we introduce a procedure called iterative disjunctive modularization. In the standard procedure, pivoting in the LP tableau optimizes the multipliers with which the inequalities on each side of the disjunction are weighted in the resulting cut. Once this solution has been obtained, a strengthening step is applied that uses the integrality constraints (if any) on the variables on each side of the disjunction to improve the cut coefficients by choosing optimal values for the elements of a certain monoid. Iterative disjunctive modularization is a procedure for approximating the simultaneous optimization of both the continuous multipliers and the integer elements of the monoid. All this is discussed in the context of a CGLP with a more general normalization constraint than the standard one used in (Balas and Perregaard in Math program 94:221–245, 2003), and the expressions that describe the above mentioned correspondence are accordingly generalized. Finally, we summarize our extensive computational experience with the above procedures.     

Improvement of extreme controls and the steepest ascent method in the norm maximization problem on the reachable set

The maximization of the terminal state norm of a linear system is considered in the sense of searching for and improving extreme points of the reachable set. A sufficient optimality condition is formulated in terms of a special maximum function. A steepest ascent method for level surfaces of the objective function is constructed, and related procedures for improving extreme controls are described.     

Response surface methodology’s steepest ascent and step size revisited: Correction

This Short Communication corrects Table 1 and Fig. 2, Fig. 3 that were published in a recent article by the same authors, in this journal. The article discussed response surface methodology (RSM), which searches for the input combination maximizing the output of a real or simulated system. RSM uses steepest ascent (SA), which is scale-dependent. The article derived scale-independent ‘adapted’ SA (ASA). The two search directions were explored in Monte Carlo experiments. Unfortunately, the canonical and the non-canonical cases were mixed up. This Communication still shows that—in general—ASA gives a better search direction than SA.     

一个新的求解线性规划最小二乘算法

§1Introduction Currently,therearetwopopularapproachesinlinearprogramming:pivotalgorithm andinterior-pointalgorithm.Manyoftheirvariantsdevelopedbothintheoryand applicationsarestillinprogress.Thepivotmethodobtainstheoptimalsolutionviamoving consecutivelytoabettercorner-pointinthefeasibleregion,anditsmodificationstryto improvethespeedofattainingtheoptimality.Incontrast,theinterior-pointalgorithmis claimedasaninterior-pointapproach,whichgoesfromafeasiblepointtoafeasiblepoint throughtheinterioroft…     

An algorithm for finding the shortest element of a polyhedral set with application to lagrangian duality

An algorithm is developed which finds the point in a compact polyhedral set with smallest Euclidean norm. At each iteration the algorithm requires knowledge of only those vertices of the set which are adjacent to a current reference vertex. This feature is shown to permit the adoption of the technique to find iteratively the shortest subgradient (i.e. the direction of steepest ascent) of the lagrangian dual function for large scale linear programs. Procedures are presented for finding the direction of steepest ascent in both the equality constraint and the inequality constraint cases of lagrangian duality.     

Randomized Simplex Algorithms on Klee-Minty Cubes

The analysis of two most natural randomized pivot rules on the Klee-Minty cubes leads to (nearly) quadratic lower bounds for the complexity of linear programming with random pivots. Thus we disprove two bounds (for the expected running time of the random-edge simplex algorithm on Klee-Minty cubes) conjectured in the literature. At the same time, we establish quadratic upper bounds for the expected length of a path for a simplex algorithm with random pivots on the classes of linear programs under investigation. In contrast to this, we find that the average length of an increasing path in a Klee-Minty cube is exponential when all paths are taken with equal probability. Received: September 2, 1996     

Dual decomposition of a single-machine scheduling problem

We design a fast ascent direction algorithm for the Lagrangian dual problem of the single-machine scheduling problem of minimizing total weighted completion time subject to precedence constraints. We show that designing such an algorithm is relatively simple if a scheduling problem is formulated in terms of the job completion times rather than as an 0–1 linear program. Also, we show that upon termination of such an ascent direction algorithm we get a dual decomposition of the original problem, which can be exploited to develop approximative and enumerative approaches for it. Computational results exhibit that in our application the ascent direction leads to good Lagrangian lower and upper bounds.     

Ergodic,primal convergence in dual subgradient schemes for convex programming,II: the case of inconsistent primal problems

Consider the utilization of a Lagrangian dual method which is convergent for consistent convex optimization problems. When it is used to solve an infeasible optimization problem, its inconsistency will then manifest itself through the divergence of the sequence of dual iterates. Will then the sequence of primal subproblem solutions still yield relevant information regarding the primal program? We answer this question in the affirmative for a convex program and an associated subgradient algorithm for its Lagrange dual. We show that the primal–dual pair of programs corresponding to an associated homogeneous dual function is in turn associated with a saddle-point problem, in which—in the inconsistent case—the primal part amounts to finding a solution in the primal space such that the Euclidean norm of the infeasibility in the relaxed constraints is minimized; the dual part amounts to identifying a feasible steepest ascent direction for the Lagrangian dual function. We present convergence results for a conditional \(\varepsilon \)-subgradient optimization algorithm applied to the Lagrangian dual problem, and the construction of an ergodic sequence of primal subproblem solutions; this composite algorithm yields convergence of the primal–dual sequence to the set of saddle-points of the associated homogeneous Lagrangian function; for linear programs, convergence to the subset in which the primal objective is at minimum is also achieved.     

Degeneracy Subgraph of the Lemke Complementary Pivot Algorithm and Anticycling Rule

In this paper, we use the theory of degeneracy graphs recently developed by Gal et al. to introduce a graph for studying the adjacency of almost complementary feasible bases, some of which may be degenerate, which are of interest in the context of the linear complementarity problem. We study the structure of this graph with particular reference to the possibility of cycling and various anticycling rules in the Lemke complementary pivoting algorithm. We consider the transition node pivot rule introduced by Geue and show that this rule helps in avoiding cycling in the Lemke complementary pivoting algorithm under a suitable assumption.     

Steepest Descent, CG, and Iterative Regularization of Ill-Posed Problems

The state of the art iterative method for solving large linear systems is the conjugate gradient (CG) algorithm. Theoretical convergence analysis suggests that CG converges more rapidly than steepest descent. This paper argues that steepest descent may be an attractive alternative to CG when solving linear systems arising from the discretization of ill-posed problems. Specifically, it is shown that, for ill-posed problems, steepest descent has a more stable convergence behavior than CG, which may be explained by the fact that the filter factors for steepest descent behave much less erratically than those for CG. Moreover, it is shown that, with proper preconditioning, the convergence rate of steepest descent is competitive with that of CG.This revised version was published online in October 2005 with corrections to the Cover Date.     

The relationship between theorems of the alternative,least norm problems,steepest descent directions,and degeneracy: A review

Recently, it has been observed that several nondifferentiable minimization problems share the property that the question of whether a given point is optimal can be answered by solving a certain bounded least squares problem. If the resulting residual vector,r, vanishes then the current point is optimal. Otherwise,r is a descent direction. In fact, as we shall see,r points at the steepest descent direction. On the other hand, it is customary to characterize the optimality conditions (and the steepest descent vector) of a convex nondifferentiable function via its subdifferential. Also, it is well known that optimality conditions are usually related to theorems of the alternative. One aim of our survey is to clarify the relations between these subjects. Another aim is to introduce a new type of theorems of the alternative. The new theorems characterize the optimality conditions of discretel ₁ approximation problems and multifacility location problems, and provide a simple way to obtain the subdifferential and the steepest descent direction in such problems. A further objective of our review is to demonstrate that the ability to compute the steepest descent direction at degenerate dead points opens a new way for handling degeneracy in active set methods.