Robust conjugate duality for convex optimization under uncertainty with application to data classification

In this paper we present a robust conjugate duality theory for convex programming problems in the face of data uncertainty within the framework of robust optimization, extending the powerful conjugate duality technique. We first establish robust strong duality between an uncertain primal parameterized convex programming model problem and its uncertain conjugate dual by proving strong duality between the deterministic robust counterpart of the primal model and the optimistic counterpart of its dual problem under a regularity condition. This regularity condition is not only sufficient for robust duality but also necessary for it whenever robust duality holds for every linear perturbation of the objective function of the primal model problem. More importantly, we show that robust strong duality always holds for partially finite convex programming problems under scenario data uncertainty and that the optimistic counterpart of the dual is a tractable finite dimensional problem. As an application, we also derive a robust conjugate duality theorem for support vector machines which are a class of important convex optimization models for classifying two labelled data sets. The support vector machine has emerged as a powerful modelling tool for machine learning problems of data classification that arise in many areas of application in information and computer sciences.     

Extensions of Dinkelbach's algorithm for solving non-linear fractional programming problems

Dinkelbach's algorithm was developed to solve convex fractinal programming. This method achieves the optimal solution of the optimisation problem by means of solving a sequence of non-linear convex programming subproblems defined by a parameter. In this paper it is shown that Dinkelbach's algorithm can be used to solve general fractional programming. The applicability of the algorithm will depend on the possibility of solving the subproblems. Dinkelbach's extended algorithm is a framework to describe several algorithms which have been proposed to solve linear fractional programming, integer linear fractional programming, convex fractional programming and to generate new algorithms. The applicability of new cases as nondifferentiable fractional programming and quadratic fractional programming has been studied. We have proposed two modifications to improve the speed-up of Dinkelbachs algorithm. One is to use interpolation formulae to update the parameter which defined the subproblem and another truncates the solution of the suproblem. We give sufficient conditions for the convergence of these modifications. Computational experiments in linear fractional programming, integer linear fractional programming and non-linear fractional programming to evaluate the efficiency of these methods have been carried out.     

Some Farkas-type results for fractional programming problems with DC functions

For a kind of fractional programming problem that the objective functions are the ratio of two DC (difference of convex) functions with finitely many convex constraints, in this paper, its dual problems are constructed, weak and strong duality assertions are given, and some sufficient and necessary optimality conditions which characterize their optimal solutions are obtained. Some recently obtained Farkas-type results for fractional programming problems that the objective functions are the ratio of a convex function to a concave function with finitely many convex constraints are the special cases of the general results of this paper.     

Global optimization for sum of generalized fractional functions

This paper considers the solution of generalized fractional programming (GFP) problem which contains various variants such as a sum or product of a finite number of ratios of linear functions, polynomial fractional programming, generalized geometric programming, etc. over a polytope. For such problems, we present an efficient unified method. In this method, by utilizing a transformation and a two-part linearization method, a sequence of linear programming relaxations of the initial nonconvex programming problem are derived which are embedded in a branch-and-bound algorithm. Numerical results are given to show the feasibility and effectiveness of the proposed algorithm.     

Robust duality for generalized convex programming problems under data uncertainty

In this paper we present a robust duality theory for generalized convex programming problems in the face of data uncertainty within the framework of robust optimization. We establish robust strong duality for an uncertain nonlinear programming primal problem and its uncertain Lagrangian dual by showing strong duality between the deterministic counterparts: robust counterpart of the primal model and the optimistic counterpart of its dual problem. A robust strong duality theorem is given whenever the Lagrangian function is convex. We provide classes of uncertain non-convex programming problems for which robust strong duality holds under a constraint qualification. In particular, we show that robust strong duality is guaranteed for non-convex quadratic programming problems with a single quadratic constraint with the spectral norm uncertainty under a generalized Slater condition. Numerical examples are given to illustrate the nature of robust duality for uncertain nonlinear programming problems. We further show that robust duality continues to hold under a weakened convexity condition.     

具有(F,α,ε)-G凸的分式半无限规划问题的ε-最优性

首次引入了（F,α,ε）-G凸函数,（F,α,ε）-G拟凸函数和（F,α,ε）-G伪凸函数等概念,对已有的凸函数进行了推广,研究了涉及这类函数的一类分式半无限规划的ε-最优性条件,得到了一些有意义的结果．这些结果不仅是现有某些结果的推广,而且为诸如资源分配,投资组合等问题的研究提供了依据,也为理论上研究分式规划提供了参考．     

Stability in convex semi-infinite programming and rates of convergence of optimal solutions of discretized finite subproblems

We consider convex semiinfinite programming (SIP) problems with an arbitrary fixed index set T. The article analyzes the relationship between the upper and lower semicontinuity (lsc) of the optimal value function and the optimal set mapping, and the so-called Hadamard well-posedness property (allowing for more than one optimal solution). We consider the family of all functions involved in some fixed optimization problem as one element of a space of data equipped with some topology, and arbitrary perturbations are premitted as long as the perturbed problem continues to be convex semiinfinite. Since no structure is required for T, our results apply to the ordinary convex programming case. We also provide conditions, not involving any second order optimality one, guaranteeing that the distance between optimal solutions of the discretized subproblems and the optimal set of the original problem decreases by a rate which is linear with respect to the discretization mesh-size.     

Some dual characterizations of Farkas-type results for fractional programming problems

In this paper, we present some Farkas-type results for a fractional programming problem. To this end, by using the properties of dualizing parametrization functions, Lagrangian functions and the epigraph of the conjugate functions, we introduce some new notions of regularity conditions and then obtain some dual forms of Farkas-type results for this fractional programming problem. We also obtain sufficient conditions for alternative type theorems. As an application of these results, we obtain the corresponding results for a convex optimization problem.     

Constraint qualifications for optimality conditions and total Lagrange dualities in convex infinite programming

For an inequality system defined by an infinite family of proper convex functions (not necessarily lower semicontinuous), we introduce some new notions of constraint qualifications. Under the new constraint qualifications, we provide necessary and/or sufficient conditions for the KKT rules to hold. Similarly, we provide characterizations for constrained minimization problems to have total Lagrangian dualities. Several known results in the conic programming problem are extended and improved.     

Relations between stochastic and parametric programming for decision problems with a random objective function

In this paper we study the relation between the general concept for an optimal solution for stochastic programming problems with a random objective function-the concept of an £-efficient solution-and the associated parametric problem, We show that it is possible under certain assumptions to obtain some or even all £-efficient solutions of the stochastic problem by solving the parametric problem with respect to a certain parameter set.     

一种新广义凸多目标分式规划的最优性充分条件

提出了（F,α,ρ,θ）-b-凸函数的概念,它是一类新的广义凸函数,并给出了这类广义凸函数的性质.在此基础上,讨论了目标函数和约束函数均为（F,α,ρ,θ）-b-凸函数的多目标分式规划,利用广义K-T条件,得到了这类多目标规划有效解和弱有效解的几个充分条件,推广了已有文献的相关结果.     

Some Randomized Algorithms for Convex Quadratic Programming

We adapt some randomized algorithms of Clarkson [3] for linear programming to the framework of so-called LP-type problems, which was introduced by Sharir and Welzl [10]. This framework is quite general and allows a unified and elegant presentation and analysis. We also show that LP-type problems include minimization of a convex quadratic function subject to convex quadratic constraints as a special case, for which the algorithms can be implemented efficiently, if only linear constraints are present. We show that the expected running times depend only linearly on the number of constraints, and illustrate this by some numerical results. Even though the framework of LP-type problems may appear rather abstract at first, application of the methods considered in this paper to a given problem of that type is easy and efficient. Moreover, our proofs are in fact rather simple, since many technical details of more explicit problem representations are handled in a uniform manner by our approach. In particular, we do not assume boundedness of the feasible set as required in related methods. Accepted 7 May 1997     

Fixed point optimization algorithm and its application to network bandwidth allocation

A convex optimization problem for a strictly convex objective function over the fixed point set of a nonexpansive mapping includes a network bandwidth allocation problem, which is one of the central issues in modern communication networks. We devised an iterative algorithm, called a fixed point optimization algorithm, for solving the convex optimization problem and conducted a convergence analysis on the algorithm. The analysis guarantees that the algorithm, with slowly diminishing step-size sequences, weakly converges to a unique solution to the problem. Moreover, we apply the proposed algorithm to a network bandwidth allocation problem and show its effectiveness.     

Optimality conditions and duality results for nonsmooth vector optimization problems with the multiple interval-valued objective function

In this paper, both Fritz John and Karush-Kuhn-Tucker necessary optimality conditions are established for a (weakly) LU-efficient solution in the considered nonsmooth multiobjective programming problem with the multiple interval-objective function. Further, the sufficient optimality conditions for a (weakly) LU-efficient solution and several duality results in Mond-Weir sense are proved under assumptions that the functions constituting the considered nondifferentiable multiobjective programming problem with the multiple interval-objective function are convex.     

Duality in nonlinear fractional programming

Summary The purpose of the present paper is to introduce, on the lines similar to that ofWolfe [1961], a dual program to a nonlinear fractional program in which the objective function, being the ratio of a convex function to a strictly positive linear function, is a special type of pseudo-convex function and the constraint set is a convex set constrained by convex functions in the form of inequalities. The main results proved are, (i) Weak duality theorem, (ii)Wolfe's (Direct) duality theorem and (iii)Mangasarian's Strict Converse duality theorem.Huard's [1963] andHanson's [1961] converse duality theorems for the present problem have just been stated because they can be obtained as a special case ofMangasarian's theorem [1969, p. 157]. The other important discussion included is to show that the dual program introduced in the present paper can also be obtained throughDinkelbach's Parametric Replacement [1967] of a nonlinear fractional program. Lastly, duality in convex programming is shown to be a special case of the present problem.The present research is partially supported by National Research Council of Canada.     

Minimum norm solution to the positive semidefinite linear complementarity problem

In this article, we present an algorithm to compute the minimum norm solution of the positive semidefinite linear complementarity problem. We show that its solution can be obtained using the alternative theorems and a convenient characterization of the solution set of a convex quadratic programming problem. This problem reduces to an unconstrained minimization problem with once differentiable convex objective function. We propose an extension of Newton's method for solving the unconstrained optimization problem. Computational results show that convergence to high accuracy often occurs in just a few iterations.     

A smoothing Newton method for a type of inverse semi-definite quadratic programming problem

We consider an inverse problem arising from the semi-definite quadratic programming (SDQP) problem. We represent this problem as a cone-constrained minimization problem and its dual (denoted ISDQD) is a semismoothly differentiable (SC¹${\text{SC}}^1$) convex programming problem with fewer variables than the original one. The Karush–Kuhn–Tucker conditions of the dual problem (ISDQD) can be formulated as a system of semismooth equations which involves the projection onto the cone of positive semi-definite matrices. A smoothing Newton method is given for getting a Karush–Kuhn–Tucker point of ISDQD. The proposed method needs to compute the directional derivative of the smoothing projector at the corresponding point and to solve one linear system per iteration. The quadratic convergence of the smoothing Newton method is proved under a suitable condition. Numerical experiments are reported to show that the smoothing Newton method is very effective for solving this type of inverse quadratic programming problems.     

Stability of the intersection of solution sets of semi-infinite systems

Many mathematical programming models arising in practice present a block structure in their constraint systems. Consequently, the feasibility of these problems depends on whether the intersection of the solution sets of each of those blocks is empty or not. The existence theorems allow to decide when the intersection of non-empty sets in the Euclidean space, which are the solution sets of systems of (possibly infinite) inequalities, is empty or not. In those situations where the data (i.e., the constraints) can be affected by some kind of perturbations, the problem consists of determining whether the relative position of the sets is preserved by sufficiently small perturbations or not. This paper focuses on the stability of the non-empty (empty) intersection of the solutions of some given systems, which can be seen as the images of set-valued mappings. We give sufficient conditions for the stability, and necessary ones as well; in particular we consider (semi-infinite) convex systems and also linear systems. In this last case we discuss the distance to ill-posedness.     

Reformulation in mathematical programming: An application to quantum chemistry

This paper concerns the application of reformulation techniques in mathematical programming to a specific problem arising in quantum chemistry, namely the solution of Hartree-Fock systems of equations, which describe atomic and molecular electronic wave functions based on the minimization of a functional of the energy. Their traditional solution method does not provide a guarantee of global optimality and its output depends on a provided initial starting point. We formulate this problem as a multi-extremal nonconvex polynomial programming problem, and solve it with a spatial Branch-and-Bound algorithm for global optimization. The lower bounds at each node are provided by reformulating the problem in such a way that its convex relaxation is tight. The validity of the proposed approach was established by successfully computing the ground-state of the helium and beryllium atoms.     

A decomposition-dualization approach for solving constrained convex minimization problems with applications to discretized obstacle problems

Summary In this paper, we shall be concerned with the solution of constrained convex minimization problems. The constrained convex minimization problems are proposed to be transformable into a convex-additively decomposed and almost separable form, e.g. by decomposition of the objective functional and the restrictions. Unconstrained dual problems are generated by using Fenchel-Rockafellar duality. This decomposition-dualization concept has the advantage that the conjugate functionals occuring in the derived dual problem are easily computable. Moreover, the minimum point of the primal constrained convex minimization problem can be obtained from any maximum point of the corresponding dual unconstrained concave problem via explicit return-formulas. In quadratic programming the decomposition-dualization approach considered here becomes applicable if the quadratic part of the objective functional is generated byH-matrices. Numerical tests for solving obstacle problems in ¹ discretized by using piecewise quadratic finite elements and in ² by using the five-point difference approximation are presented.