An iteration of the sequential quadratically constrained quadratic programming method (SQCQP) consists of minimizing a quadratic approximation of the objective function subject to quadratic approximation of the constr...
详细信息
An iteration of the sequential quadratically constrained quadratic programming method (SQCQP) consists of minimizing a quadratic approximation of the objective function subject to quadratic approximation of the constraints, followed by a line search in the obtained direction. Methods of this class are receiving attention due to the development of efficient interior point techniques for solving subproblems with this structure, via formulating them as second-order cone programs. Recently, Fukushima et al. (2003) proposed a SQCQP method for convex minimization with twice continuously differentiable data. Their method possesses global and locally quadratic convergence, and it is free of the Maratos effect. The feasibility of subproblems in their method is enforced by switching between the linear and quadratic approximations of the constraints. This strategy requires computing a strictly feasible point, as well as choosing some further parameters. We propose a SQCQP method where feasibility of subproblems is ensured by introducing a slack variable and, hence, is automatic. In addition, we do not assume convexity of the objective function or twice differentiability of the problem data. While our method has all the desirable convergence properties, it is easier to implement. Among other things, it does not require computing a strictly feasible point, which is a nontrivial task. In addition, its global convergence requires weaker assumptions.
Regularized kernel discriminant analysis (RKDA) performs linear discriminant analysis in the feature space via the kernel trick. Its performance depends on the selection of kernels. In this paper, we consider the prob...
详细信息
Regularized kernel discriminant analysis (RKDA) performs linear discriminant analysis in the feature space via the kernel trick. Its performance depends on the selection of kernels. In this paper, we consider the problem of multiple kernel learning (MKL) for RKDA, in which the optimal kernel matrix is obtained as a linear combination of pre-specified kernel matrices. We show that the kernel learning problem in RKDA can be formulated as convex programs. First, we show that this problem can be formulated as a semidefinite program (SDP). Based on the equivalence relationship between RKDA and least square problems in the binary-class case, we propose a convex quadratically constrained quadratic programming (QCQP) formulation for kernel learning in RKDA. A semi-infinite linear programming (SILP) formulation is derived to further improve the efficiency. We extend these formulations to the multi-class case based on a key result established in this paper. That is, the multi-class RKDA kernel learning problem can be decomposed into a set of binary-class kernel learning problems which are constrained to share a common kernel. Based on this decomposition property, SDP formulations are proposed for the multi-class case. Furthermore, it leads naturally to QCQP and SILP formulations. As the performance of RKDA depends on the regularization parameter, we show that this parameter can also be optimized in a joint framework with the kernel. Extensive experiments have been conducted and analyzed, and connections to other algorithms are discussed.
This paper presents a sequential quadratically constrained quadratic programming (SQCQP) method for solving smooth convex programs. The SQCQP method solves at each iteration a subproblem that involves convex quadratic...
详细信息
This paper presents a sequential quadratically constrained quadratic programming (SQCQP) method for solving smooth convex programs. The SQCQP method solves at each iteration a subproblem that involves convex quadratic inequality constraints as well as a convex quadratic objective function. Such a quadratically constrained quadratic programming problem can be formulated as a second-order cone program, which can be solved efficiently by using interior point methods. We consider the following three fundamental issues on the SQCQP method: the feasibility of subproblems, the global convergence, and the quadratic rate of convergence. In particular, we show that the Maratos effect is avoided without any modification to the search direction, even though we use an ordinary l(1) exact penalty function as the line search merit function.
In this paper we consider optimization problems defined by a quadratic objective function and a finite number of quadratic inequality constraints. Given that the objective function is bounded over the feasible set, we...
详细信息
In this paper we consider optimization problems defined by a quadratic objective function and a finite number of quadratic inequality constraints. Given that the objective function is bounded over the feasible set, we present a comprehensive study of the conditions under which the optimal solution set is nonempty, thus extending the so-called Frank-Wolfe theorem. In particular, we first prove a general continuity result for the solution set defined by a system of convex quadratic inequalities. This result implies immediately that the optimal solution set of the aforementioned problem is nonempty when all the quadratic functions involved are convex. In the absence of the convexity of the objective function, we give examples showing that the optimal solution set may be empty either when there are two or more convex quadratic constraints, or when the Hessian of the objective function has two or more negative eigenvalues. In the case when there exists only one convex quadratic inequality constraint (together with other linear constraints), or when the constraint functions are all convex quadratic and the objective function is quasi-convex (thus allowing one negative eigenvalue in its Hessian matrix), we prove that the optimal solution set is nonempty.
This paper copes with the problem of satisfying input and/or state hard constraints in set-point tracking problems. Stability is guaranteed by synthesizing a Lyapunov quadratic function for the system, and by imposing...
详细信息
This paper copes with the problem of satisfying input and/or state hard constraints in set-point tracking problems. Stability is guaranteed by synthesizing a Lyapunov quadratic function for the system, and by imposing that the terminal state lies within a level set of the function. Procedures to maximize the volume of such an ellipsoidal set are provided, and interior-point methods to solve on-line optimization are considered. (C) 1998 Elsevier Science B.V. All rights reserved.
暂无评论