Projective-Dual Method for Solving Systems of Linear Equations with Nonnegative Variables

In order to solve an underdetermined system of linear equations with nonnegative variables, the projection of a given point onto its solutions set is sought. The dual of this problem—the problem of unconstrained maximization of a piecewise-quadratic function—is solved by Newton’s method. The problem of unconstrained optimization dual of the regularized problem of finding the projection onto the solution set of the system is considered. A connection of duality theory and Newton’s method with some known algorithms of projecting onto a standard simplex is shown. On the example of taking into account the specifics of the constraints of the transport linear programming problem, the possibility to increase the efficiency of calculating the generalized Hessian matrix is demonstrated. Some examples of numerical calculations using MATLAB are presented.     

New algorithms for linear programming

The problem of solving a linear programming is converted into that of solving an unconstrained maximization problem in which the objective function is concave. Two algorithms are proposed. These two algorithms have very simple structure and can be implemented easily. For any given precision, the algorithms will terminate in a finite number of steps.     

Some duality relationships for the generalized Neyman-Pearson problem

In 1963, Kuhn presented a dual problem to a relatively well-known location problem, variously referred to as the generalized Fermat problem and the Steiner-Weber problem. The purpose of this paper is to point out how Kuhn's results can be adapted to provide a dual to the generalized Neyman-Pearson problem, a problem of fundamental interest in statistics, which has applications in control theory and a number of other areas. The Neyman-Pearson problem, termed the dual problem, is a constrained maximization problem and may be considered to be a calculus-of-variations analog to the bounded-variable problem of linear programming. When the dual problem has equality constraints, the primal problem is an unconstrained minimization problem. Duality results are also obtained for the case where the dual problem has inequality constraints.This work was partially supported by the National Science Foundation, Grant Nos. NSF-GK-1571 and NSF-GK-3038. The authors would like to acknowledge the very useful comments of one of the referees, which led to more direct and general proofs of Properties 2.3 and 2.6.     

An entire space polynomial-time algorithm for linear programming

We propose an entire space polynomial-time algorithm for linear programming. First, we give a class of penalty functions on entire space for linear programming by which the dual of a linear program of standard form can be converted into an unconstrained optimization problem. The relevant properties on the unconstrained optimization problem such as the duality, the boundedness of the solution and the path-following lemma, etc, are proved. Second, a self-concordant function on entire space which can be used as penalty for linear programming is constructed. For this specific function, more results are obtained. In particular, we show that, by taking a parameter large enough, the optimal solution for the unconstrained optimization problem is located in the increasing interval of the self-concordant function, which ensures the feasibility of solutions. Then by means of the self-concordant penalty function on entire space, a path-following algorithm on entire space for linear programming is presented. The number of Newton steps of the algorithm is no more than $O(nL\log (nL/ {\varepsilon }))$ , and moreover, in short step, it is no more than $O(\sqrt{n}\log (nL/{\varepsilon }))$ .     

An unconstrained dual approach to solving Karmarkar-type linear programs using conventional barrier functions

This paper proposes an unconstrained dual approach and an efficient algorithm for solving Karmarkar-type linear programming problems. Conventional barrier functions are incorporated as a perturbation term in the derivation of the associated duality theory. An optimal solution of the original linear program can be obtained by solving a sequence of unconstrained concave programs, or be approximated by solving one such dual program with a sufficiently small perturbation parameter. A globally convergent curved-search algorithm with a quadratic rate of convergence is designed for this purpose. Based on our testing results, we find that the computational procedure is very efficient and can be a viable approach for solving linear programming problems.     

Solutions to quadratic minimization problems with box and integer constraints

This paper presents a canonical duality theory for solving quadratic minimization problems subjected to either box or integer constraints. Results show that under Gao and Strang’s general global optimality condition, these well-known nonconvex and discrete problems can be converted into smooth concave maximization dual problems over closed convex feasible spaces without duality gap, and can be solved by well-developed optimization methods. Both existence and uniqueness of these canonical dual solutions are presented. Based on a second-order canonical dual perturbation, the discrete integer programming problem is equivalent to a continuous unconstrained Lipschitzian optimization problem, which can be solved by certain deterministic technique. Particularly, an analytical solution is obtained under certain condition. A fourth-order canonical dual perturbation algorithm is presented and applications are illustrated. Finally, implication of the canonical duality theory for the popular semi-definite programming method is revealed.     

Deriving an unconstrained convex program for linear programming

Consider a linear programming problem in Karmarkar's standard form. By perturbing its linear objective function with an entropic barrier function and applying generalized geometric programming theory to it, Fang recently proposed an unconstrained convex programming approach to finding an epsilon-optimal solution. In this paper, we show that Fang's derivation of an unconstrained convex dual program can be greatly simplified by using only one simple geometric inequality. In addition, a system of nonlinear equations, which leads to a pair of primal and dual epsilon-optimal solutions, is proposed for further investigation.This work was partially supported by the North Carolina Supercomputing Center and a 1990 Cray Research Grant. The authors are indebted to Professors E. L. Peterson and R. Saigal for stimulating discussions.     

Interior penalty functions and duality in linear programming

Logarithmic additive terms of barrier type with a penalty parameter are included in the Lagrange function of a linear programming problem. As a result, the problem of searching for saddle points of the modified Lagrangian becomes unconstrained (the saddle point is sought with respect to the whole space of primal and dual variables). Theorems on the asymptotic convergence to the desired solution and analogs of the duality theorems for the arising optimization minimax and maximin problems are formulated.     

Lagrangian duality and saddle points for sparse linear programming

The sparse linear programming(SLP) is a linear programming problem equipped with a sparsity constraint, which is nonconvex, discontinuous and generally NP-hard due to the combinatorial property involved.In this paper, by rewriting the sparsity constraint into a disjunctive form, we present an explicit formula of the Lagrangian dual problem for the SLP, in terms of an unconstrained piecewise-linear convex programming problem which admits a strong duality under bi-dual sparsity consistency. Furthermore, we show a saddle point theorem based on the strong duality and analyze two classes of stationary points for the saddle point problem. At last,we extend these results to SLP with the lower bound zero replaced by a certain negative constant.     

Using a factored dual in augmented Lagrangian methods for semidefinite programming

In the context of augmented Lagrangian approaches for solving semidefinite programming problems, we investigate the possibility of eliminating the positive semidefinite constraint on the dual matrix by employing a factorization. Hints on how to deal with the resulting unconstrained maximization of the augmented Lagrangian are given. We further use the approximate maximum of the augmented Lagrangian with the aim of improving the convergence rate of alternating direction augmented Lagrangian frameworks. Numerical results are reported, showing the benefits of the approach.     

Nonlinear complementarity as unconstrained and constrained minimization

The nonlinear complementarity problem is cast as an unconstrained minimization problem that is obtained from an augmented Lagrangian formulation. The dimensionality of the unconstrained problem is the same as that of the original problem, and the penalty parameter need only be greater than one. Another feature of the unconstrained problem is that it has global minima of zero at precisely all the solution points of the complementarity problem without any monotonicity assumption. If the mapping of the complementarity problem is differentiable, then so is the objective of the unconstrained problem, and its gradient vanishes at all solution points of the complementarity problem. Under assumptions of nondegeneracy and linear independence of gradients of active constraints at a complementarity problem solution, the corresponding global unconstrained minimum point is locally unique. A Wolfe dual to a standard constrained optimization problem associated with the nonlinear complementarity problem is also formulated under a monotonicity and differentiability assumption. Most of the standard duality results are established even though the underlying constrained optimization problem may be nonconvex. Preliminary numerical tests on two small nonmonotone problems from the published literature converged to degenerate or nondegenerate solutions from all attempted starting points in 7 to 28 steps of a BFGS quasi-Newton method for unconstrained optimization.Dedicated to Phil Wolfe on his 65th birthday, in appreciation of his major contributions to mathematical programming.This material is based on research supported by Air Force Office of Scientific Research Grant AFOSR-89-0410 and National Science Foundation Grant CCR-9101801.     

A Convergence Proof for Constrained Finite Element Solutions

A convergence proof is given for the finite-element solutionof the infinite dimensional quadratic programming problem ofminimizing a quadratic functional subject to linear constraints.The proof for the unconstrained problem is briefly reviewed,and then extended to the constrained case. Only the first partof the proof is given, in which necessary conditions for convergenceare derived for the specific problem and its finite-elementapproximation. The final step of proving that any problem doesobey these conditions will depend on the specific problem, butit is shown that if the finite element formulation is pointwiseconvergent and the unconstrained problem is convergent, thenso too will be the constrained problem.     

Parallel bundle-based decomposition for large-scale structured mathematical programming problems

In this paper, we present parallel bundle-based decomposition algorithms to solve a class of structured large-scale convex optimization problems. An example in this class of problems is the block-angular linear programming problem. By dualizing, we transform the original problem to an unconstrained nonsmooth concave optimization problem which is in turn solved by using a modified bundle method. Further, this dual problem consists of a collection of smaller independent subproblems which give rise to the parallel algorithms. We discuss the implementation on the CRYSTAL multi-computer. Finally, we present computational experience with block-angular linear programming problems and observe that more than 70% efficiency can be obtained using up to eleven processors for one group of test problems, and more than 60% efficiency can be obtained for relatively smaller problems using up to five processors for another group of problems.     

An exact penalty function method for nonlinear mixed discrete programming problems

In this paper, we consider a general class of nonlinear mixed discrete programming problems. By introducing continuous variables to replace the discrete variables, the problem is first transformed into an equivalent nonlinear continuous optimization problem subject to original constraints and additional linear and quadratic constraints. Then, an exact penalty function is employed to construct a sequence of unconstrained optimization problems, each of which can be solved effectively by unconstrained optimization techniques, such as conjugate gradient or quasi-Newton methods. It is shown that any local optimal solution of the unconstrained optimization problem is a local optimal solution of the transformed nonlinear constrained continuous optimization problem when the penalty parameter is sufficiently large. Numerical experiments are carried out to test the efficiency of the proposed method.     

The convergence of a dual algorithm for nonlinear programming

A dual algorithm based on the smooth function proposed by Polyak (1988) is constructed for solving nonlinear programming problems with inequality constraints. It generates a sequence of points converging locally to a Kuhn-Tucker point by solving an unconstrained minimizer of a smooth potential function with a parameter. We study the relationship between eigenvalues of the Hessian of this smooth potential function and the parameter, which is useful for analyzing the effectiveness of the dual algorithm.     

Dijkstra’s algorithm and L-concave function maximization

Dijkstra’s algorithm is a well-known algorithm for the single-source shortest path problem in a directed graph with nonnegative edge length. We discuss Dijkstra’s algorithm from the viewpoint of discrete convex analysis, where the concept of discrete convexity called L-convexity plays a central role. We observe first that the dual of the linear programming (LP) formulation of the shortest path problem can be seen as a special case of L-concave function maximization. We then point out that the steepest ascent algorithm for L-concave function maximization, when applied to the LP dual of the shortest path problem and implemented with some auxiliary variables, coincides exactly with Dijkstra’s algorithm.     

An algorithm for large scale 0–1 integer programming with application to airline crew scheduling

We present an approximation algorithm for solving large 0–1 integer programming problems whereA is 0–1 and whereb is integer. The method can be viewed as a dual coordinate search for solving the LP-relaxation, reformulated as an unconstrained nonlinear problem, and an approximation scheme working together with this method. The approximation scheme works by adjusting the costs as little as possible so that the new problem has an integer solution. The degree of approximation is determined by a parameter, and for different levels of approximation the resulting algorithm can be interpreted in terms of linear programming, dynamic programming, and as a greedy algorithm. The algorithm is used in the CARMEN system for airline crew scheduling used by several major airlines, and we show that the algorithm performs well for large set covering problems, in comparison to the CPLEX system, in terms of both time and quality. We also present results on some well known difficult set covering problems that have appeared in the literature.     

On the Continuity of the Optimal Value in Parametric Linear Optimization: Stable Discretization of the Lagrangian Dual of Nonlinear Problems

This paper is focused on the stability of the optimal value, and its immediate repercussion on the stability of the optimal set, for a general parametric family of linear optimization problems in ⁿ. In our approach, the parameter ranges over an arbitrary metric space, and each parameter determines directly a set of coefficient vectors describing the linear system of constraints. Thus, systems associated with different parameters are not required to have the same number (cardinality) of inequalities. In this way, discretization techniques for solving a nominal linear semi-infinite optimization problem may be modeled in terms of suitable parametrized problems. The stability results given in the paper are applied to the stability analysis of the Lagrangian dual associated with a parametric family of nonlinear programming problems. This dual problem is translated into a linear (semi-infinite) programming problem and, then, we prove that the lower semicontinuity of the corresponding feasible set mapping, the continuity of the optimal value function, and the upper semicontinuity of the optimal set mapping are satisfied. Then, the paper shows how these stability properties for the dual problem entail a nice behavior of parametric approximation and discretization strategies (in which an ordinary linear programming problem may be considered in each step). This approximation–discretization process is formalized by means of considering a double parameter: the original one and the finite subset of indices (grid) itself. Finally, the convex case is analyzed, showing that the referred process also allows us to approach the primal problem.Mathematics Subject Classifications (2000) Primary 90C34, 90C31; secondary 90C25, 90C05.     

一个新的解线性规划的神经网络

本文提出一个新的解线性规划的Hopfields-型网络。该网络基于线性规划的对偶理论,并使用了Sigmoid函数,但不需要预先给定的罚参数和乘法模拟器,我们证明该网络不仅全局收敛到线性规划的精确解,而且能同时解原规划和对偶规划。由于在该网络中没有使用乘法模拟器而利用了Sigmoid函数,因此该模型是很容易用硬件实现的。     

Calculating risk neutral probabilities and optimal portfolio policies in a dynamic investment model with downside risk control

This paper presents a method for solving multiperiod investment models with downside risk control characterized by the portfolio’s worst outcome. The stochastic programming problem is decomposed into two subproblems: a nonlinear optimization model identifying the optimal terminal wealth distribution and a stochastic linear programming model replicating the identified optimal portfolio wealth. The replicating portfolio coincides with the optimal solution to the investor’s problem if the market is frictionless. The multiperiod stochastic linear programming model tests for the absence of arbitrage opportunities and its dual feasible solutions generate all risk neutral probability measures. When there are constraints such as liquidity or position requirements, the method yields approximate portfolio policies by minimizing the initial cost of the replication portfolio. A numerical example illustrates the difference between the replicating result and the optimal unconstrained portfolio.