All Issues

Volume 12, 2022

Volume 11, 2021

Volume 10, 2020

Volume 9, 2019

Volume 8, 2018

Volume 7, 2017

Volume 6, 2016

Volume 5, 2015

Volume 4, 2014

Volume 3, 2013

Volume 2, 2012

Volume 1, 2011

Numerical Algebra, Control and Optimization

2015 , Volume 5 , Issue 2

Select all articles


Yanqin Bai, Duan Li, Hezhi Luo and Guoqiang Wang
2015, 5(2): i-ii doi: 10.3934/naco.2015.5.2i +[Abstract](2413) +[PDF](85.5KB)
We dedicate this Special Issue to the Memory of Professor Xiaoling Sun (1963-2014) who passed away on April 24, 2014. Professor Sun was a leading scholar in optimization and its applications in operations research and financial engineering. He served as Vice-President of both the Chinese Mathematical Programming Society and the Operations Research Society of China.

For more information please click the “Full Text” above.
Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties
Fengmin Wang, Dachuan Xu, Donglei Du and Chenchen Wu
2015, 5(2): 91-100 doi: 10.3934/naco.2015.5.91 +[Abstract](3607) +[PDF](363.7KB)
We introduce two set cover problems with submodular costs and linear/submodular penalties and offer two approximation algorithms of ratios $\eta$ and $2\eta$ respectively via the primal-dual technique, where $\eta$ is the largest number of sets that each element belongs to.
Complexity analysis of primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term
Guoqiang Wang, Zhongchen Wu, Zhongtuan Zheng and Xinzhong Cai
2015, 5(2): 101-113 doi: 10.3934/naco.2015.5.101 +[Abstract](3304) +[PDF](404.7KB)
In this paper, we present a class of large- and small-update primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term. For both versions of the kernel-based interior-point methods, the worst case iteration bounds are established, namely, $O(n^{\frac{2}{3}}\log\frac{n}{\varepsilon})$ and $O(\sqrt{n}\log\frac{n}{\varepsilon})$, respectively. These results match the ones obtained in the linear optimization case.
A smooth QP-free algorithm without a penalty function or a filter for mathematical programs with complementarity constraints
Jianling Li, Chunting Lu and Youfang Zeng
2015, 5(2): 115-126 doi: 10.3934/naco.2015.5.115 +[Abstract](2737) +[PDF](391.3KB)
In this paper, a smooth QP-free algorithm without a penalty function or a filter is proposed for a special kind of mathematical programs with complementarity constraints (MPCC for short). Firstly, the investigated problem is transformed into sequential parametric standard nonlinear programs by perturbed techniques and a generalized complementarity function. Then the trial step, at each iteration, is accepted such that either the value of the objective function or the measure of the constraint violation is sufficiently reduced. Finally, it is shown that every limit point of the iterative sequence is feasible, and there exists a limit point that is a KKT point for the problem under mild conditions.
Rank-one and sparse matrix decomposition for dynamic MRI
Xianchao Xiu and Lingchen Kong
2015, 5(2): 127-134 doi: 10.3934/naco.2015.5.127 +[Abstract](2863) +[PDF](539.2KB)
We introduce a rank-one and sparse matrix decomposition model for dynamic magnetic resonance imaging (MRI). Since $l_p$-norm $(0 < p < 1)$ is generally nonconvex, nonsmooth, non-Lipschitz, we propose reweighted $l_1$-norm to surrogate $l_p$-norm. Based on this, we put forward a modified alternative direction method. Numerical experiments are also given to illustrate the efficiency of our algorithm.
A perturbation-based approach for continuous network design problem with emissions
Robert Ebihart Msigwa, Yue Lu, Xiantao Xiao and Liwei Zhang
2015, 5(2): 135-149 doi: 10.3934/naco.2015.5.135 +[Abstract](2678) +[PDF](415.0KB)
The objective of continuous network design problem (CNDP) is to determine the optimal capacity expansion policy under a limited budget. This transportation system is formulated as a bi-level program where the upper level aims to determine the link capacity expansion vector and emission while taking into account the lower level response. This problem can be solved using various optimization algorithms and software. In this study, the CNDP with environmental considerations is designed and solved using the perturbation based approach. The lower level representing the road users subjected to user equilibrium is solved using the Frank-Wolfe algorithm. The proposed model is tested using a small hypothetical network to show the efficacy of the method. As a contribution of this paper, first it suggests a perturbation based approach for planners to design the capacity expansion, which minimize the total system cost and emission. Second the proposed method solves the nonlinear mathematical program with complementarity constraints (NLMPCC) problem, which overcomes the lack of a suitable set of constraint qualifications, such as Mangasarian Fromovitz constraint qualifications (MFCQ). Although the proposed model illustrated using the CO only and small network, the approach is not limited to large-scale network design problems and other pollutants..
Speeding up a memetic algorithm for the max-bisection problem
Wenxing Zhu, Yanpo Liu and Geng Lin
2015, 5(2): 151-168 doi: 10.3934/naco.2015.5.151 +[Abstract](2510) +[PDF](464.9KB)
Max-bisection of a weighted graph $G = (V, E)$ is to partition the vertex set $V$ into two subsets that have equal cardinality, such that the sum of the weights of the edges connecting vertices in different subsets is maximized. It is an NP-complete problem. Various heuristics have been proposed for solving the max-bisection problem and some of them get very good quality solutions, but are time consuming. In this paper, we propose several techniques to speeding up Lin and Zhu's memetic algorithm for this problem. It consists of a crossover operator with a greedy strategy, a fast modified Kernighan-Lin local search, and a new population updating function. Experiments are performed on 71 well-known G-set benchmark instances. Results show that the memetic algorithm is much faster than Wu and Hao's memetic algorithm, which can get best solutions up to now, on middle-scale and large-scale instances. Specifically, some current best known solutions of the test instances are improved.
A wedge trust region method with self-correcting geometry for derivative-free optimization
Liang Zhang, Wenyu Sun, Raimundo J. B. de Sampaio and Jinyun Yuan
2015, 5(2): 169-184 doi: 10.3934/naco.2015.5.169 +[Abstract](2743) +[PDF](432.2KB)
Recently, some methods for solving optimization problems without derivatives have been proposed. The main part of these methods is to form a suitable model function that can be minimized for obtaining a new iterative point. An important strategy is geometry-improving iteration for a good model, which needs a lot of calculations. Besides, Marazzi and Nocedal (2002) proposed a wedge trust region method for derivative free optimization. In this paper, we propose a new self-correcting geometry procedure with less computational efforts, and combine it with the wedge trust region method. The global convergence of new algorithm is established. The limited numerical experiments show that the new algorithm is efficient and competitive.
A new semidefinite relaxation for $L_{1}$-constrained quadratic optimization and extensions
Yong Xia, Yu-Jun Gong and Sheng-Nan Han
2015, 5(2): 185-195 doi: 10.3934/naco.2015.5.185 +[Abstract](2887) +[PDF](353.8KB)
In this paper, by improving the variable-splitting approach, we propose a new semidefinite programming (SDP) relaxation for the nonconvex quadratic optimization problem over the $\ell_1$ unit ball (QPL1). It dominates the state-of-the-art SDP-based bound for (QPL1). As extensions, we apply the new approach to the relaxation problem of the sparse principal component analysis and the nonconvex quadratic optimization problem over the $\ell_p$ ($1< p<2$) unit ball and then show the dominance of the new relaxation.
Continuity and stability of two-stage stochastic programs with quadratic continuous recourse
Zhiping Chen and Youpan Han
2015, 5(2): 197-209 doi: 10.3934/naco.2015.5.197 +[Abstract](3062) +[PDF](362.0KB)
For two-stage stochastic programs with quadratic continuous recourse where all the coefficients in the objective function and the right-hand side vector in the second-stage constraints vary simultaneously, we firstly show the locally Lipschtiz continuity of the optimal value function of the recourse problem, then under suitable probability metric, we derive the joint Lipschitz continuity of the expected optimal value function with respect to the first-stage variables and the probability distribution. Furthermore, we establish the qualitative and quantitative stability results of the optimal value function and the optimal solution set with respect to the Fortet-Mourier probability metric, when the underlying probability distribution is perturbed. Finally, we show the exponential convergence rate of the optimal value sequence when we solve two-stage quadratic stochastic programs by the sample average approximation method.
Primal-dual interior-point algorithms for convex quadratic circular cone optimization
Yanqin Bai, Xuerui Gao and Guoqiang Wang
2015, 5(2): 211-231 doi: 10.3934/naco.2015.5.211 +[Abstract](3409) +[PDF](520.1KB)
In this paper we focus on a class of special nonsymmetric cone optimization problem called circular cone optimization problem, which has a convex quadratic function as the objective function and an intersection of a non-self-dual circular cone and linear equations as the constraint condition. Firstly we establish the algebraic relationships between the circular cone and the second-order cone and translate the original problem from the circular cone optimization problem to the second-order cone optimization problem. Then we present kernel-function based primal-dual interior-point algorithms for solving this special circular cone optimization and derive the iteration bounds for large- and small-update methods. Finally, some preliminary numerical results are provided to demonstrate the computational performance of the proposed algorithms.

2021 CiteScore: 1.9




Special Issues

Email Alert

[Back to Top]