Abstract:
The $p$-regularized subproblem (p-RS) is a regularisation technique in computing a Newton-like step for unconstrained optimization, which globally minimizes a local quadratic approximation of the objective function while incorporating with a weighted regularisation term $\frac{\sigma}{p} \|x\|^p$. The global solution of the $p$-regularized subproblem for $p=3$, also known as the cubic regularization, has been characterized in literature. In this paper, we resolve both the global and the local non-global minimizers of (p-RS) for $p>2$ with necessary and sufficient optimality conditions. Moreover, we prove a parallel result of Mart\'{\i}nez \cite{Mar} that the (p-RS) for $p>2$, analogous to the trust region subproblem, can have at most one local non-global minimizer. When the (p-RS) is subject to a fixed number $m$ additional linear inequality constraints, we show that the uniqueness of the local solution of the (p-RS) (if exists at all), especially for $p=4$, can be applied to solve such an extension in polynomial time.

Abstract:
We show an improved lower bound for the Fp estimation problem in a data stream setting for p>2. A data stream is a sequence of items from the domain [n] with possible repetitions. The frequency vector x is an n-dimensional non-negative integer vector x such that x(i) is the number of occurrences of i in the sequence. Given an accuracy parameter Omega(n^{-1/p}) < \epsilon < 1, the problem of estimating Fp is to estimate \norm{x}_p^p = \sum_{i \in [n]} \abs{x(i)}^p correctly to within a relative accuracy of 1\pm \epsilon with high constant probability in an online fashion and using as little space as possible. The current space lower bound for this problem is Omega(n^{1-2/p} \epsilon^{-2/p}+ n^{1-2/p}\epsilon^{-4/p}/ \log^{O(1)}(n)+ (\epsilon^{-2} + \log (n))). The first term in the lower bound expression was proved in \cite{B-YJKS:stoc02,cks:ccc03}, the second in \cite{wz:arxiv11} and the third in \cite{wood:soda04}. In this note, we show an Omega(p^2 n^{1-2/p} \epsilon^{-2}/\log (n)) bits space bound, for Omega(pn^{-1/p}) \le \epsilon \le 1/10.

Abstract:
Under the assumption that the encoders’ observations are conditionally independent Markov chains given an unobserved time-invariant random variable, results on the structure of optimal real-time encoding and decoding functions are obtained. The problem with noiseless channels and perfect memory at the receiver is then considered. A new methodology to find the structure of optimal real-time encoders is employed. A sufficient statistic with a time-invariant domain is found for this problem. This methodology exploits the presence of common information between the encoders and the receiver when communication is over noiseless channels. In this paper we estimate the lower bond, upper bond and define the encoder. In the previous design approach they follow Markov Chain approach to estimating the upper bound and define the encoder. In this dissertation we follow poison distribution to finding the lower bound and upper bound. Poisson can be viewed as an approximation to the binomial distribution. The approximation is good enough to be useful even when the sample size (N) is only moderately large (say N > 50) and the probability (p) is only relatively small (p < .2) The advantage of the Poisson distribution, of course, is that if N is large you need only know p to determine the approximate distribution of events. With the binomial distribution you also need to know N.

Abstract:
Image reconstruction in electrical impedance tomography (EIT) is an ill-posed nonlinear inverse problem. Regularization methods are needed to solve this problem. The results of the ill-posed EIT problem strongly depends on noise level in measured data as well as regularization parameter. In this paper we present trust region subproblem (TRS), with the use of Lcurve maximum curvature criteria to find a regularization parameter. Currently Krylov subspace methods especially conjugate gradient least squares (CGLS) are used for large scale 3D problem. CGLS is an efficient technique when the norm of measured noise is exactly known. This paper demonstrates that CGLS and TRS converge to the same point on the L-curve with the same noise level. TRS can be implemented efficiently for large scale inverse EIT problem as CGLS with no need a priori knowledge of the noise level.

Abstract:
With the help of the newly developed S-lemma with interval bounds, we show that strong duality holds for the interval bounded generalized trust region subproblem under some mild assumptions, which answers an open problem raised by Pong and Wolkowicz [Comput. Optim. Appl. 58(2), 273-322, 2014].

Abstract:
In this paper, we study the extended trust region subproblem (eTRS) in which the trust region intersects the unit ball with a single linear inequality constraint. By reformulating the Lagrangian dual of eTRS as a two-parameter linear eigenvalue problem, we state a necessary and sufficient condition for its strong duality in terms of an optimal solution of a linearly constrained bivariate concave maximization problem. This results in an efficient algorithm for solving eTRS of large size whenever the strong duality is detected. Finally, some numerical experiments are given to show the effectiveness of the proposed method.

Abstract:
The trust region subproblem with a fixed number m additional linear inequality constraints, denoted by (Tm), have drawn much attention recently. The question as to whether Problem (Tm) is in Class P or Class NP remains open. So far, the only affirmative general result is that (T1) has an exact SOCP/SDP reformulation and thus is polynomially solvable. By adopting an early result of Martinez on local non-global minimum of the trust region subproblem, we can inductively reduce any instance in (Tm) to a sequence of trust region subproblems (T0). Although the total number of (T0) to be solved takes an exponential order of m, the reduction scheme still provides an argument that the class (Tm) has polynomial complexity for each fixed m. In contrast, we show by a simple example that, solving the class of extended trust region subproblems which contains more linear inequality constraints than the problem dimension; or the class of instances consisting of an arbitrarily number of linear constraints is NP-hard. When m is small such as m = 1,2, our inductive algorithm should be more efficient than the SOCP/SDP reformulation since at most 2 or 5 subproblems of (T0), respectively, are to be handled. In the end of the paper, we improve a very recent dimension condition by Jeyakumar and Li under which (Tm) admits an exact SDP relaxation. Examples show that such an improvement can be strict indeed.

Abstract:
an alternative strategy to solve the subproblems of the method of moving asymptotes (mma) is presented, based on a trust-region scheme applied to the dual of the mma subproblem. at each iteration, the objective function of the dual problem is approximated by a regularized spectral model. a globally convergent modification to the mma is also suggested, in which the conservative condition is relaxed by means of a summable controlled forcing sequence. another modification to the mma previously proposed by the authors [optim. methods softw., 25 (2010), pp. 883-893] is recalled to be used in the numerical tests. this modification is based on the spectral parameter for updating the mma models, so as to improve their quality. the performed numerical experiments confirm the efficiency of the indicated modifications, especially when jointly combined.

Abstract:
A trust-region-based BFGS method is proposed for solving symmetric nonlinear equations. In this given algorithm, if the trial step is unsuccessful, the linesearch technique will be used instead of repeatedly solving the subproblem of the normal trust-region method. We establish the global and superlinear convergence of the method under suitable conditions. Numerical results show that the given method is competitive to the normal trust region method.

Abstract:
We give a lower bound on Walsh figure of merit (WAFOM), which is a parameter to estimate the integration error for quasi-Monte Carlo (QMC) integration by a point set called a digital net. This lower bound is optimal because the existence of point sets attaining the order was proved in [K. Suzuki, An explicit construction of point sets with large minimum Dick weight, Journal of Complexity 30, (2014), 347-354].