This paper addresses the parallel machine scheduling problem in which the jobs have distinct due dates with earliness and tardiness costs. New lower bounds are proposed for the problem, they can be classed into two families. First, two assignment-based lower bounds for the one-machine problem are generalized for the parallel machine case. Second, a time-indexed … Read more
We illustrate the usefulness of Jordan-algebraic technique for nonconvex optimization by considering a potential-reduction algorithm for a nonconvex quadratic function over the domain obtained as the intersection of a symmetric cone with an affine subspace CitationPreprint, September,2004ArticleDownload View PDF
The global convergence properties of a class of penalty methods for nonlinear programming are analyzed. These methods include successive linear programming approaches, and more specifically, the successive linear-quadratic programming approach presented by Byrd, Gould, Nocedal and Waltz (Math. Programming 100(1):27–48, 2004). Every iteration requires the solution of two trust-region subproblems involving piecewise linear and quadratic … Read more
The second-order cone programming problem is reformulated into several new systems of nonlinear equations. Assume the perturbation of the data is in a certain neighborhood of zero. Then starting from a solution to the old problem, the semismooth Newton’s iterates converge Q-quadratically to a solution of the perturbed problem. The algorithm is globalized. Numerical examples … Read more
Based on the Q method for SDP, we develop the Q method for SOCP. A modified Q method is also introduced. Properties of the algorithms are discussed. Convergence proofs are given. Finally, we present numerical results. CitationAdvOl-Report#2004/15 McMaster University, Advanced Optimization LaboratoryArticleDownload View PDF
We extend the Q method to the symmetric cone programming. An infeasible interior point algorithm and a Newton-type algorithm are given. We give convergence results of the interior point algorithm and prove that the Newton-type algorithm is good for CitationAdvOl-Report#2004/18 McMaster University, Advanced Optimization Laboratory Hamilton, Ontario, Canada October 2004ArticleDownload View PDF
There is a natural norm associated with a starting point of the homogeneous self-dual (HSD) embedding model for conic convex optimization. In this norm two measures of the HSD model’s behavior are precisely controlled independent of the problem instance: (i) the sizes of epsilon-optimal solutions, and (ii) the maximum distance of epsilon-optimal solutions to the … Read more
Test problems are generally used to effectively evaluate the algorithms for packing problem. Based on the engineering background of the layout optimization for a retrievable satellite module, this paper describes the test problems for circles packing problem with known optimization solution first. There are N(≦217) circular objects, different in size, packed in a circular container … Read more
This paper studies a new primal-dual interior/exterior-point method for linear programming. We begin with the usual perturbed primal-dual optimality equations $F_\mu(x,y,z)=0$. Under nondegeneracy assumptions, this nonlinear system is well-posed, i.e. it has a nonsingular Jacobian at optimality and is not necessarily ill-conditioned as the iterates approach optimality. We use a simple preprocessing step to eliminate … Read more
The main focus of this paper is discussion of complexity of stochastic programming problems. We argue that two-stage (linear) stochastic programming problems with recourse can be solved with a reasonable accuracy by using Monte Carlo sampling techniques, while multi-stage stochastic programs, in general, are intractable. We also discuss complexity of chance constrained problems and multi-stage … Read more