All Issues

Volume 7, 2017

Volume 6, 2016

Volume 5, 2015

Volume 4, 2014

Volume 3, 2013

Volume 2, 2012

Volume 1, 2011

Numerical Algebra, Control & Optimization

2011 , Volume 1 , Issue 1

A special issue
Dedicated to Professor Masao Fukushima on the occasion of his 60th birthday

Select all articles


Christian Kanzow, Dong-Hui Li and Nobuo Yamashita
2011, 1(1): i-v doi: 10.3934/naco.2011.1.1i +[Abstract](60) +[PDF](582.4KB)
It is our great pleasure and honor to dedicate the first issue of “Numerical Algebra, Control and Optimization” to Professor Masao Fukushima on the occasion of his 60th birthday. The papers contributed to this issue have been written by his old friends, colleagues and former students, and bring up various topics on optimization, which represent Professor Fukushima's wide-ranging interest in all aspects of optimization.

For more information please click the “Full Text” above.
On methods for solving nonlinear semidefinite optimization problems
Jie Sun
2011, 1(1): 1-14 doi: 10.3934/naco.2011.1.1 +[Abstract](149) +[PDF](242.3KB)
The nonlinear semidefinite optimization problem arises from applications in system control, structural design, financial management, and other fields. However, much work is yet to be done to effectively solve this problem. We introduce some new theoretical and algorithmic development in this field. In particular, we discuss first and second-order algorithms that appear to be promising, which include the alternating direction method, the augmented Lagrangian method, and the smoothing Newton method. Convergence theorems are presented and preliminary numerical results are reported.
Recent advances in numerical methods for nonlinear equations and nonlinear least squares
Ya-Xiang Yuan
2011, 1(1): 15-34 doi: 10.3934/naco.2011.1.15 +[Abstract](236) +[PDF](445.3KB)
Nonlinear equations and nonlinear least squares problems have many applications in physics, chemistry, engineering, biology, economics, finance and many other fields. In this paper, we will review some recent results on numerical methods for these two special problems, particularly on Levenberg-Marquardt type methods, quasi-Newton type methods, and trust region algorithms. Discussions on variable projection methods and subspace methods are also given. Some theoretical results about local convergence results of the Levenberg-Marquardt type methods without non-singularity assumption are presented. A few model algorithms based on line searches and trust regions are also given.
CVaR-based formulation and approximation method for stochastic variational inequalities
Xiaojun Chen and Guihua Lin
2011, 1(1): 35-48 doi: 10.3934/naco.2011.1.35 +[Abstract](121) +[PDF](241.6KB)
In this paper, we study the stochastic variational inequality problem (SVIP) from a viewpoint of minimization of conditional value-at-risk. We employ the D-gap residual function for VIPs to define a loss function for SVIPs. In order to reduce the risk of high losses in applications of SVIPs, we use the D-gap function and conditional value-at-risk to present a deterministic minimization reformulation for SVIPs. We show that the new reformulation is a convex program under suitable conditions. Furthermore, by using the smoothing techniques and the Monte Carlo methods, we propose a smoothing approximation method for finding a solution of the new reformulation and show that this method is globally convergent with probability one.
Improved convergence properties of the Lin-Fukushima-Regularization method for mathematical programs with complementarity constraints
Tim Hoheisel, Christian Kanzow and Alexandra Schwartz
2011, 1(1): 49-60 doi: 10.3934/naco.2011.1.49 +[Abstract](122) +[PDF](192.1KB)
We consider a regularization method for the numerical solution of mathematical programs with complementarity constraints (MPCC) introduced by Gui-Hua Lin and Masao Fukushima. Existing convergence results are improved in the sense that the MPCC-LICQ assumption is replaced by the weaker MPCC-MFCQ. Moreover, some preliminary numerical results are presented in order to illustrate the theoretical improvements.
Convergence analysis of sparse quasi-Newton updates with positive definite matrix completion for two-dimensional functions
Yuhong Dai and Nobuo Yamashita
2011, 1(1): 61-69 doi: 10.3934/naco.2011.1.61 +[Abstract](97) +[PDF](161.3KB)
In this paper, we briefly review the extensions of quasi-Newton methods for large-scale optimization. Specially, based on the idea of maximum determinant positive definite matrix completion, Yamashita (2008) proposed a new sparse quasi-Newton update, called MCQN, for unconstrained optimization problems with sparse Hessian structures. In exchange of the relaxation of the secant equation, the MCQN update avoids solving difficult subproblems and overcomes the ill-conditioning of approximate Hessian matrices. A global convergence analysis is given in this paper for the MCQN update with Broyden's convex family assuming that the objective function is uniformly convex and its dimension is only two.
    This paper is dedicated to Professor Masao Fukushima on occasion of his 60th birthday.
A modified Fletcher-Reeves-Type derivative-free method for symmetric nonlinear equations
Dong-Hui Li and Xiao-Lin Wang
2011, 1(1): 71-82 doi: 10.3934/naco.2011.1.71 +[Abstract](129) +[PDF](194.9KB)
In this paper, we propose a descent derivative-free method for solving symmetric nonlinear equations. The method is an extension of the modified Fletcher-Reeves (MFR) method proposed by Zhang, Zhou and Li [25] to symmetric nonlinear equations. It can be applied to solve large-scale symmetric nonlinear equations due to lower storage requirement. An attractive property of the method is that the directions generated by the method are descent for the residual function. By the use of some backtracking line search technique, the generated sequence of function values is decreasing. Under appropriate conditions, we show that the proposed method is globally convergent. The preliminary numerical results show that the method is practically effective.
Celis-Dennis-Tapia based approach to quadratic fractional programming problems with two quadratic constraints
Ailing Zhang and Shunsuke Hayashi
2011, 1(1): 83-98 doi: 10.3934/naco.2011.1.83 +[Abstract](87) +[PDF](235.3KB)
In this paper, we focus on fractional programming problems that minimize the ratio of two indefinite quadratic functions subject to two quadratic constraints. Utilizing the relationship between fractional programming and parametric programming, we transform the original problem into a univariate nonlinear equation. To evaluate the function in the equation, we need to solve a problem of minimizing a nonconvex quadratic function subject to two quadratic constraints. This problem is commonly called a Celis-Dennis-Tapia (CDT) subproblem, which arises in some trust region algorithms for equality constrained optimization. In the outer iterations of the algorithm, we employ the bisection method and/or the generalized Newton method. In the inner iterations, we utilize Yuan's theorem to obtain the global optima of the CDT subproblems. We also show some numerical results to examine the efficiency of the algorithm. Particularly, we will observe that the generalized Newton method is more robust to the erroneous evaluation for the univariate functions than the bisection method.
Filter-based genetic algorithm for mixed variable programming
Abdel-Rahman Hedar and Alaa Fahim
2011, 1(1): 99-116 doi: 10.3934/naco.2011.1.99 +[Abstract](158) +[PDF](224.8KB)
In this paper, Filter Genetic Algorithm (FGA) method is proposed to find the global optimal of the constrained mixed variable programming problem. The considered problem is reformulated to take the form of optimizing two functions, the objective function and the constraint violation function. Then, the filter set methodology [5] is applied within a genetic algorithm framework to solve the reformulated problem. We use pattern search as local search to improve the obtained solutions. Moreover, the gene matrix criteria [10] has been applied to accelerated the search process and to terminate the algorithm. The proposed method FGA is promising compared with some other methods existing in the literature.
A derivative-free trust-region algorithm for unconstrained optimization with controlled error
Jun Takaki and Nobuo Yamashita
2011, 1(1): 117-145 doi: 10.3934/naco.2011.1.117 +[Abstract](91) +[PDF](559.7KB)
In this paper, we consider the unconstrained optimization problem under the following conditions: (S1) The objective function is evaluated with a certain bounded error, (S2) the error is controllable, that is, the objective function can be evaluated to any desired accuracy, and (S3) more accurate evaluation requires a greater computation time. This situation arises in many fields such as engineering and financial problems, where objective function values are obtained from considerable numerical calculation or a simulation. Under (S2) and (S3), it seems reasonable to set the accuracy of the evaluation to be low at points far from a solution, and high at points in the neighborhood of a solution. In this paper, we propose a derivative-free trust-region algorithm based on this idea. For this purpose, we consider (i) how to construct a quadratic model function by exploiting pointwise errors and (ii) how to control the accuracy of function evaluations to reduce the total computation time of the algorithm. For (i), we propose a method based on support vector regression. For (ii), we present an updating formula of the accuracy of which is related to the trust-region radius. We present numerical results for several test problems taken from CUTEr and a financial problem of estimating implied volatilities from option prices.
A nonconvergent example for the iterative water-filling algorithm
Simai He, Min Li, Shuzhong Zhang and Zhi-Quan Luo
2011, 1(1): 147-150 doi: 10.3934/naco.2011.1.147 +[Abstract](77) +[PDF](109.1KB)
Iterative Water-filling Algorithm (IWFA) is a well-known distributed multi-carrier power control method for multi-user communication. It was empirically observed (and conjectured) to be convergent under all channel conditions. In this paper, we present an example showing that IWFA can oscillate, therefore disproving the conjecture.
Performance evaluation of multiobjective multiclass support vector machines maximizing geometric margins
Keiji Tatsumi, Masashi Akao, Ryo Kawachi and Tetsuzo Tanino
2011, 1(1): 151-169 doi: 10.3934/naco.2011.1.151 +[Abstract](88) +[PDF](911.8KB)
The all-together method is one of the support vector machine (SVM) for multiclass classification by using a piece-wise linear function. Recently, we proposed a new hard-margin all-together model maximizing geometric margins in the sense of multiobjective optimization for the high generalization ability, which is called the multiobjective multiclass SVM (MMSVM). Moreover, we derived its solving techniques which can find a Pareto optimal solution for the MMSVM, and verified that classifiers with larger geometric margins were obtained by the proposed techniques through numerical experiments. However, the experiments are not enough to evaluate the classification performance of the proposed model, and the MMSVM is a hard-margin model which can be applied to only piecewise linearly separable data. Therefore, in this paper, we extend the hard-margin model into soft-margin one by introducing penalty functions for the slack margin variables, and derive a single-objective second-order cone programming (SOCP) problem to solve it. Furthermore, through numerical experiments we verify the classification performance of the hard and soft-margin MMSVMs for benchmark problems.
Parametric excitation based bipedal walking: Control method and optimization
Yuji Harata, Yoshihisa Banno and Kouichi Taji
2011, 1(1): 171-190 doi: 10.3934/naco.2011.1.171 +[Abstract](68) +[PDF](1012.7KB)
In parametric excitation walking, energy lost by a heel strike is restored by bending and stretching a swing leg, and then a sustainable gait is generated with only knee torque. In this paper, we first propose the method that combines the parametric excitation method for a swing leg with that for a support leg to improve gait efficiency. Next, we improve gait efficiency of the combined parametric excitation walking by the optimization method for reference trajectories. Numerical results show that the specific resistance of the combined method is reduced to about one tenth of those of the previous results. In addition, the results of multi-objective optimization method are presented by reformulating a single-objective optimization problem.
Genetic algorithm and Tabu search based methods for molecular 3D-structure prediction
Abdel-Rahman Hedar, Ahmed Fouad Ali and Taysir Hassan Abdel-Hamid
2011, 1(1): 191-209 doi: 10.3934/naco.2011.1.191 +[Abstract](83) +[PDF](374.4KB)
The search for the global minimum of a potential energy function is very difficult since the number of local minima grows exponentially with the molecule size. The present work proposes the application of genetic algorithm and tabu search methods, which are called GAMCP (Genetic Algorithm with Matrix Coding Partitioning) [7], and TSVP (Tabu Search with Variable Partitioning) [8], respectively, for minimizing the molecular potential energy function. Computational results for problems with up to 200 degrees of freedom are presented and are favorable compared with other four existing methods from the literature. Numerical results show that the proposed two methods are promising and produce high quality solutions with low computational costs.




Email Alert

[Back to Top]