An extension of Karmarkar's algorithm for linear programming using dual variables

We describe an extension of Karmarkar's algorithm for linear programming that handles problems with unknown optimal value and generates primal and dual solutions with objective values converging to the common optimal primal and dual value. We also describe an implementation for the dense case and show how extreme point solutions can be obtained naturally, with little extra computation.Research supported in part by a fellowship from the Alfred P. Sloan Foundation and by NSF Grant ECS-15361.     

An extension of Karmarkar's algorithm for linear programming using dual variables

We describe an extension of Karmarkar's algorithm for linear programming that handles problems with unknown optimal value and generates primal and dual solutions with objective values converging to the common optimal primal and dual value. We also describe an implementation for the dense case and show how extreme point solutions can be obtained naturally, with little extra computation.     

Asymptotic convergence of constrained primal–dual dynamics

This paper studies the asymptotic convergence properties of the primal–dual dynamics designed for solving constrained concave optimization problems using classical notions from stability analysis. We motivate the need for this study by providing an example that rules out the possibility of employing the invariance principle for hybrid automata to study asymptotic convergence. We understand the solutions of the primal–dual dynamics in the Caratheodory sense and characterize their existence, uniqueness, and continuity with respect to the initial condition. We use the invariance principle for discontinuous Caratheodory systems to establish that the primal–dual optimizers are globally asymptotically stable under the primal–dual dynamics and that each solution of the dynamics converges to an optimizer.     

Scheduling parallel-machine batch operations to maximize on-time delivery performance

In this paper we study the problem of minimizing total weighted tardiness, a proxy for maximizing on-time delivery performance, on parallel nonidentical batch processing machines. We first formulate the (primal) problem as a nonlinear integer programming model. We then show that the primal problem can be solved exactly by solving a corresponding dual problem with a nonlinear relaxation. Since both the primal and the dual problems are NP-hard, we use genetic algorithms, based on random keys and multiple choice encodings, to heuristically solve them. We find that the genetic algorithms consistently outperform a standard mathematical programming package in terms of solution quality and computation time. We also compare the smaller problem instances to a breadth-first tree search algorithm that gives evidence of the quality of the solutions.     

Implementation and analysis of alternative algorithms for generalized shortest path problems

This paper addresses a special class of deterministic dynamic programming problems which can be formulated as a generalized network problem. Because of the similarities between this class of dynamic programming problems and shortest path problems, we are naming it the Generalized Shortest Path problem. A new primal extreme point algorithm and a new special dual algorithm are proposed here. While researchers have presented a variety of algorithms to solve this class of problems, there has been no comuptational analysis of these algorithms. An in-depth computational analysis is performed to determine the most efficient set of rules for implementing the algorithms of this paper.     

Iteration complexity analysis of dual first-order methods for conic convex programming

In this paper we provide a detailed analysis of the iteration complexity of dual first-order methods for solving conic convex problems. When it is difficult to project on the primal feasible set described by conic and convex constraints, we use the Lagrangian relaxation to handle the conic constraints and then, we apply dual first-order algorithms for solving the corresponding dual problem. We give convergence analysis for dual first-order algorithms (dual gradient and fast gradient algorithms): we provide sublinear or linear estimates on the primal suboptimality and feasibility violation of the generated approximate primal solutions. Our analysis relies on the Lipschitz property of the gradient of the dual function or an error bound property of the dual. Furthermore, the iteration complexity analysis is based on two types of approximate primal solutions: the last primal iterate or an average primal sequence.     

A feasible direction algorithm for general nonlinear semidefinite programming

This paper deals with nonlinear smooth optimization problems with equality and inequality constraints, as well as semidefinite constraints on nonlinear symmetric matrix-valued functions. A new semidefinite programming algorithm that takes advantage of the structure of the matrix constraints is presented. This one is relevant in applications where the matrices have a favorable structure, as in the case when finite element models are employed. FDIPA_GSDP is then obtained by integration of this new method with the well known Feasible Direction Interior Point Algorithm for nonlinear smooth optimization, FDIPA. FDIPA_GSDP makes iterations in the primal and dual variables to solve the first order optimality conditions. Given an initial feasible point with respect to the inequality constraints, FDIPA_GSDP generates a feasible descent sequence, converging to a local solution of the problem. At each iteration a feasible descent direction is computed by merely solving two linear systems with the same matrix. A line search along this direction looks for a new feasible point with a lower objective. Global convergence to stationary points is proved. Some structural optimization test problems were solved very efficiently, without need of parameters tuning.     

A primal method for multiple kernel learning

The canonical support vector machines (SVMs) are based on a single kernel, recent publications have shown that using multiple kernels instead of a single one can enhance interpretability of the decision function and promote classification accuracy. However, most of existing approaches mainly reformulate the multiple kernel learning as a saddle point optimization problem which concentrates on solving the dual. In this paper, we show that the multiple kernel learning (MKL) problem can be reformulated as a BiConvex optimization and can also be solved in the primal. While the saddle point method still lacks convergence results, our proposed method exhibits strong optimization convergence properties. To solve the MKL problem, a two-stage algorithm that optimizes canonical SVMs and kernel weights alternately is proposed. Since standard Newton and gradient methods are too time-consuming, we employ the truncated-Newton method to optimize the canonical SVMs. The Hessian matrix need not be stored explicitly, and the Newton direction can be computed using several Preconditioned Conjugate Gradient steps on the Hessian operator equation, the algorithm is shown more efficient than the current primal approaches in this MKL setting. Furthermore, we use the Nesterov’s optimal gradient method to optimize the kernel weights. One remarkable advantage of solving in the primal is that it achieves much faster convergence rate than solving in the dual and does not require a two-stage algorithm even for the single kernel LapSVM. Introducing the Laplacian regularizer, we also extend our primal method to semi-supervised scenario. Extensive experiments on some UCI benchmarks have shown that the proposed algorithm converges rapidly and achieves competitive accuracy.     

A feasible directions algorithm for nonlinear complementarity problems and applications in mechanics

Complementarity problems are involved in mathematical models of several applications in engineering, economy and different branches of physics. We mention contact problems and dynamics of multiple bodies systems in solid mechanics. In this paper we present a new feasible direction algorithm for nonlinear complementarity problems. This one begins at an interior point, strictly satisfying the inequality conditions, and generates a sequence of interior points that converges to a solution of the problem. At each iteration, a feasible direction is obtained and a line search performed, looking for a new interior point with a lower value of an appropriate potential function. We prove global convergence of the present algorithm and present a theoretical study about the asymptotic convergence. Results obtained with several numerical test problems, and also application in mechanics, are described and compared with other well known techniques. All the examples were solved very efficiently with the present algorithm, employing always the same set of parameters.     

基于设施选址问题的费用分配问题的近似算法

许多有着重要理论和应用价值的最优化问题在算法复杂性上都是NP-hard的,其解决方法之一是近似算法。论文研究了与设施选址问题密切相关的费用分配问题,并利用原始与对偶线性规划的思想和无容量设施选址问题的一个1.52-近似算法[1]给出了该问题的一个更好的近似算法。     

Novel artificial neural network with simulation aspects for solving linear and quadratic programming problems

In this paper linear and quadratic programming problems are solved using a novel recurrent artificial neural network. The new model is simpler and converges very fast to the exact primal and dual solutions simultaneously. The model is based on a nonlinear dynamical system, using arbitrary initial conditions. In order to construct an economy model, here we avoid using analog multipliers. The dynamical system is a time dependent system of equations with the gradient of specific Lyapunov energy function in the right hand side. Block diagram of the proposed neural network model is given. Fourth order Runge–Kutta method with controlled step size is used to solve the problem numerically. Global convergence of the new model is proved, both theoretically and numerically. Numerical simulations show the fast convergence of the new model for the problems with a unique solution or infinitely many. This model converges to the exact solution independent of the way that we may choose the starting points, i.e. inside, outside or on the boundaries of the feasible region.     

Inducing strong convergence into the asymptotic behaviour of proximal splitting algorithms in Hilbert spaces

Proximal splitting algorithms for monotone inclusions (and convex optimization problems) in Hilbert spaces share the common feature to guarantee for the generated sequences in general weak convergence to a solution. In order to achieve strong convergence, one usually needs to impose more restrictive properties for the involved operators, like strong monotonicity (respectively, strong convexity for optimization problems). In this paper, we propose a modified Krasnosel'ski?–Mann algorithm in connection with the determination of a fixed point of a nonexpansive mapping and show strong convergence of the iteratively generated sequence to the minimal norm solution of the problem. Relying on this, we derive a forward–backward and a Douglas–Rachford algorithm, both endowed with Tikhonov regularization terms, which generate iterates that strongly converge to the minimal norm solution of the set of zeros of the sum of two maximally monotone operators. Furthermore, we formulate strong convergent primal–dual algorithms of forward–backward and Douglas–Rachford-type for highly structured monotone inclusion problems involving parallel-sums and compositions with linear operators. The resulting iterative schemes are particularized to the solving of convex minimization problems. The theoretical results are illustrated by numerical experiments on the split feasibility problem in infinite dimensional spaces.     

An iterative time‐bucket refinement algorithm for a high‐resolution resource‐constrained project scheduling problem

We consider a resource‐constrained project scheduling problem originating in particle therapy for cancer treatment, in which the scheduling has to be done in high resolution. Traditional mixed integer linear programming techniques such as time‐indexed formulations or discrete‐event formulations are known to have severe limitations in such cases, that is, growing too fast or having weak linear programming relaxations. We suggest a relaxation based on partitioning time into so‐called time‐buckets. This relaxation is iteratively solved and serves as basis for deriving feasible solutions using heuristics. Based on these primal and dual solutions and bounds, the time‐buckets are successively refined. Combining these parts, we obtain an algorithm that provides good approximate solutions soon and eventually converges to an optimal solution. Diverse strategies for performing the time‐bucket refinement are investigated. The approach shows excellent performance in comparison to the traditional formulations and a metaheuristic.     

A primal–dual active set strategy for non-linear multibody contact problems

Non-conforming domain decomposition methods provide a powerful tool for the numerical approximation of partial differential equations. For the discretization of a non-linear multibody contact problem, we use the mortar approach with a dual Lagrange multiplier space. To handle the non-linearity of the contact conditions, we apply a primal–dual active set strategy to find the actual contact zone. The algorithm can be easily generalized to multibody contact problems. A suitable basis transformation guarantees the same algebraic structure in the multibody situation as in the one body case. Using an inexact primal–dual active set strategy in combination with a multigrid method yields an efficient iterative solver. Different numerical examples for one and multibody contact problems illustrate the performance of the method.     

基于集结投影次梯度的机组组合算法研究

针对大规模电力系统机组组合问题,提出了基于集结投影次梯度方法的分解协调算法.首先在上层通过拉格朗日松弛方法将原问题分解为多个子问题,从而减小了求解问题的复杂度,避免了维数灾问题,同时显著降低了计算时间,使得原问题可以在多项式时间内求解,随后下层子问题采用动态规划方法很容易求最优解.算例仿真结果表明,所采用的集结投影次梯度方法调整拉格朗日乘子,避免了传统次梯度方法振荡现象严重的缺点,同时加快了收敛速度,得到了令人满意的机组组合方案.     

L2-SVM: Dependence on the regularization parameter

The goal of this paper is to announce some results dealing with mathematical properties of so-called L2 Soft-Margin Support Vector Machines (L2-SVMs) for data classification. Their dual formulations build a family of quadratic programming problems depending on one regularization parameter. The dependence of the solution on this parameter is examined. Such properties as continuity, differentiability, monotony and convexity are investigated. It is shown that the solution and the objective value of the Hard Margin SVM allow estimating the slack variables of the L2-SVMs. The asymptotic behavior of the solutions of the primal problems in the inseparable case was investigated. An ancillary dual problem is used as investigation tool. It is in reality a dual formulation of a quasi identical L2-SVM primal.     

A majorization-minimization approach to the sparse generalized eigenvalue problem

Generalized eigenvalue (GEV) problems have applications in many areas of science and engineering. For example, principal component analysis (PCA), canonical correlation analysis (CCA) and Fisher discriminant analysis (FDA) are specific instances of GEV problems, that are widely used in statistical data analysis. The main contribution of this work is to formulate a general, efficient algorithm to obtain sparse solutions to a GEV problem. Specific instances of sparse GEV problems can then be solved by specific instances of this algorithm. We achieve this by solving the GEV problem while constraining the cardinality of the solution. Instead of relaxing the cardinality constraint using a ? ₁-norm approximation, we consider a tighter approximation that is related to the negative log-likelihood of a Student??s t-distribution. The problem is then framed as a d.c. (difference of convex functions) program and is solved as a sequence of convex programs by invoking the majorization-minimization method. The resulting algorithm is proved to exhibit global convergence behavior, i.e., for any random initialization, the sequence (subsequence) of iterates generated by the algorithm converges to a stationary point of the d.c. program. Finally, we illustrate the merits of this general sparse GEV algorithm with three specific examples of sparse GEV problems: sparse PCA, sparse CCA and sparse FDA. Empirical evidence for these examples suggests that the proposed sparse GEV algorithm, which offers a general framework to solve any sparse GEV problem, will give rise to competitive algorithms for a variety of applications where specific instances of GEV problems arise.     

Solving scalarized multi‐objective network flow problems using an interior point method

In this paper, we present a primal‐dual interior‐point algorithm to solve a class of multi‐objective network flow problems. More precisely, our algorithm is an extension of the single‐objective primal infeasible dual feasible inexact interior point method for multi‐objective linear network flow problems. Our algorithm is contrasted with standard interior point methods and experimental results on bi‐objective instances are reported. The multi‐objective instances are converted into single objective problems with the aid of an achievement function, which is particularly adequate for interactive decision‐making methods.     

Incremental subgradient method for nonsmooth convex optimization with fixed point constraints

This paper proposes an incremental subgradient method for solving the problem of minimizing the sum of nondifferentiable, convex objective functions over the intersection of fixed point sets of nonexpansive mappings in a real Hilbert space. The proposed algorithm can work in nonsmooth optimization over constraint sets onto which projections cannot be always implemented, whereas the conventional incremental subgradient method can be applied only when a constraint set is simple in the sense that the projection onto it can be easily implemented. We first study its convergence for a constant step size. The analysis indicates that there is a possibility that the algorithm with a small constant step size approximates a solution to the problem. Next, we study its convergence for a diminishing step size and show that there exists a subsequence of the sequence generated by the algorithm which weakly converges to a solution to the problem. Moreover, we show the whole sequence generated by the algorithm with a diminishing step size strongly converges to the solution to the problem under certain assumptions. We also give examples of real applied problems which satisfy the assumptions in the convergence theorems and numerical examples to support the convergence analyses.     

A generalized entropy criterion for Nevanlinna-Pick interpolationwith degree constraint

We present a generalized entropy criterion for solving the rational Nevanlinna-Pick problem for n+1 interpolating conditions and the degree of interpolants bounded by n. The primal problem of maximizing this entropy gain has a very well-behaved dual problem. This dual is a convex optimization problem in a finite-dimensional space and gives rise to an algorithm for finding all interpolants which are positive real and rational of degree at most n. The criterion requires a selection of a monic Schur polynomial of degree n. It follows that this class of monic polynomials completely parameterizes all such rational interpolants, and it therefore provides a set of design parameters for specifying such interpolants. The algorithm is implemented in a state-space form and applied to several illustrative problems in systems and control, namely sensitivity minimization, maximal power transfer and spectral estimation