Cascading: an adjusted exchange method for robust conic programming

It is well known that the robust counterpart introduced by Ben-Tal and Nemirovski (Math Oper Res 23:769–805, 1998) increases the numerical complexity of the solution compared to the original problem. Kočvara, Nemirovski and Zowe therefore introduced in Kočvara et al. (Comput Struct 76:431–442, 2000) an approximation algorithm for the special case of robust material optimization, called cascading. As the title already indicates, we will show that their method can be seen as an adjustment of standard exchange methods to semi-infinite conic programming. We will see that the adjustment can be motivated by a suitable reformulation of the robust conic problem.      

Multi-choice goal programming formulation based on the conic scalarizing function

The multi-choice goal programming allows the decision maker to set multi-choice aspiration levels for each goal to avoid underestimation of the decision. In this paper, we propose an alternative multi-choice goal programming formulation based on the conic scalarizing function with three contributions: (1) the alternative formulation allows the decision maker to set multi-choice aspiration levels for each goal to obtain an efficient solution in the global region, (2) the proposed formulation reduces auxiliary constraints and additional variables, and (3) the proposed model guarantees to obtain a properly efficient (in the sense of Benson) point. Finally, to demonstrate the usefulness of the proposed formulation, illustrative examples and test problems are included.     

On self-concordant barrier functions for conic hulls and fractional programming

Given a self-concordant barrier function for a convex set , we determine a self-concordant barrier function for the conic hull of . As our main result, we derive an “optimal” barrier for based on the barrier function for . Important applications of this result include the conic reformulation of a convex problem, and the solution of fractional programs by interior-point methods. The problem of minimizing a convex-concave fraction over some convex set can be solved by applying an interior-point method directly to the original nonconvex problem, or by applying an interior-point method to an equivalent convex reformulation of the original problem. Our main result allows to analyze the second approach showing that the rate of convergence is of the same order in both cases.     

Risk optimization with p-order conic constraints: A linear programming approach

The paper considers solving of linear programming problems with p-order conic constraints that are related to a certain class of stochastic optimization models with risk objective or constraints. The proposed approach is based on construction of polyhedral approximations for p-order cones, and then invoking a Benders decomposition scheme that allows for efficient solving of the approximating problems. The conducted case study of portfolio optimization with p-order conic constraints demonstrates that the developed computational techniques compare favorably against a number of benchmark methods, including second-order conic programming methods.     

Inverse optimization for linearly constrained convex separable programming problems

In this paper, we study inverse optimization for linearly constrained convex separable programming problems that have wide applications in industrial and managerial areas. For a given feasible point of a convex separable program, the inverse optimization is to determine whether the feasible point can be made optimal by adjusting the parameter values in the problem, and when the answer is positive, find the parameter values that have the smallest adjustments. A sufficient and necessary condition is given for a feasible point to be able to become optimal by adjusting parameter values. Inverse optimization formulations are presented with ℓ₁ and ℓ₂ norms. These inverse optimization problems are either linear programming when ℓ₁ norm is used in the formulation, or convex quadratic separable programming when ℓ₂ norm is used.     

Adjustable robust counterpart of conic quadratic problems

This paper presents an approximate affinely adjustable robust counterpart for conic quadratic constraints. The theory is applied to obtain robust solutions to the problems of subway route design with implementation errors and a supply chain management with uncertain demands. Comparison of the adjustable solutions with the nominal and non-adjustable robust solutions shows that the adjustable (dynamic) robust solution maintains feasibility for all possible realizations, while being less conservative than the usual (static) robust counterpart solution.     

A strong conic quadratic reformulation for machine-job assignment with controllable processing times

We describe a polynomial-size conic quadratic reformulation for a machine-job assignment problem with separable convex cost. Because the conic strengthening is based only on the objective of the problem, it can also be applied to other problems with similar cost functions. Computational results demonstrate the effectiveness of the conic reformulation.     

Quadratic programming for portfolio optimization

Portfolio optimization is a procedure for generating a portfolio composition which yields the highest return for a given level of risk or a minimum risk for given level of return. The problem can be formulated as a quadratic programming problem. We shall present a new and efficient optimization procedure taking advantage of the special structure of the portfolio selection problem. An example of its application to the traditional mean-variance method will be shown. Formulation of the procedure shows that the solution of the problem is vector intensive and fits well with the advanced architecture of recent computers, namely the vector processor.     

Multi-choice goal programming with utility functions

Goal programming (GP) has been, and still is, the most widely used technique for solving multiple-criteria decision problems and multiple-objective decision problems by finding a set of satisfying solutions. However, the major limitation of goal programming is that can only use aspiration levels with scalar value for solving multiple objective problems. In order to solve this problem multi-choice goal programming (MCGP) was proposed by Chang (2007a). Following the idea of MCGP this study proposes a new concept of level achieving in the utility functions to replace the aspiration level with scalar value in classical GP and MCGP for multiple objective problems. According to this idea, it is possible to use the skill of MCGP with utility functions to solve multi-objective problems. The major contribution of using the utility functions of MCGP is that they can be used as measuring instruments to help decision makers make the best/appropriate policy corresponding to their goals with the highest level of utility achieved. In addition, the above properties can improve the practical utility of MCGP in solving more real-world decision/management problems.     

Inverse DEA under inter-temporal dependence using multiple-objective programming

This paper deals with the inverse Data Envelopment Analysis (DEA) under inter-temporal dependence assumption. Both problems, input-estimation and output-estimation, are investigated. Necessary and sufficient conditions for input/output estimation are established utilizing Pareto and weak Pareto solutions of linear multiple-objective programming problems. Furthermore, in this paper we introduce a new optimality notion for multiple-objective programming problems, periodic weak Pareto optimality. These solutions are used in inverse DEA, and it is shown that these can be characterized by a simple modification in weighted sum scalarization tool.     

Cutting plane algorithms for the inverse mixed integer linear programming problem

We present cutting plane algorithms for the inverse mixed integer linear programming problem (InvMILP), which is to minimally perturb the objective function of a mixed integer linear program in order to make a given feasible solution optimal.     

On dynamic programming equations for utility indifference pricing under delta constraints

In this paper we study the problem of utility indifference pricing in a constrained financial market, using a utility function defined over the positive real line. We present a convex risk measure −v(•:y) satisfying q(x,F)=x+v(F:u₀(x)), where u₀(x) is the maximal expected utility of a small investor with the initial wealth x, and q(x,F) is a utility indifference buy price for a European contingent claim with a discounted payoff F. We provide a dynamic programming equation associated with the risk measure (−v), and characterize v as a viscosity solution of this equation.     

Stochastic second-order cone programming: Applications models

Second-order cone programs are a class of convex optimization problems. We refer to them as deterministic second-order cone programs (DSCOPs) since data defining them are deterministic. In DSOCPs we minimize a linear objective function over the intersection of an affine set and a product of second-order (Lorentz) cones. Stochastic programs have been studied since 1950s as a tool for handling uncertainty in data defining classes of optimization problems such as linear and quadratic programs. Stochastic second-order cone programs (SSOCPs) with recourse is a class of optimization problems that defined to handle uncertainty in data defining DSOCPs. In this paper we describe four application models leading to SSOCPs.     

Integer programming approaches in mean-risk models

This paper is concerned with porfolio optimization problems with integer constraints. Such problems include, among others mean-risk problems with nonconvex transaction cost, minimal transaction unit constraints and cardinality constraints on the number of assets in a portfolio. These problems, though practically very important have been considered intractable because we have to solve nonlinear integer programming problems for which there exists no efficient algorithms. We will show that these problems can now be solved by the state- of-the-art integer programming methodologies if we use absolute deviation as the measure of risk.     

A copositive Farkas lemma and minimally exact conic relaxations for robust quadratic optimization with binary and quadratic constraints

We present a new copositive Farkas lemma for a general conic quadratic system with binary constraints under a convexifiability requirement. By employing this Farkas lemma, we establish that a minimally exact conic programming relaxation holds for a convexifiable robust quadratic optimization problem with binary and quadratic constraints under a commonly used ellipsoidal uncertainty set of robust optimization. We then derive a minimally exact copositive relaxation for a robust binary quadratic program with conic linear constraints where the convexifiability easily holds.     

A mixed integer linear programming formulation of the optimal mean/Value-at-Risk portfolio problem

In this paper, we consider an extension of the Markovitz model, in which the variance has been replaced with the Value-at-Risk. So a new portfolio optimization problem is formulated. We showed that the model leads to an NP-hard problem, but if the number of past observation T or the number of assets K are low, e.g. fixed to a constant, polynomial time algorithms exist. Furthermore, we showed that the problem can be formulated as an integer programming instance. When K and T are large and α^VaR is small—as common in financial practice—the computational results show that the problem can be solved in a reasonable amount of time.     

Robust nonlinear optimization with conic representable uncertainty set

The robust optimization methodology is known as a popular method dealing with optimization problems with uncertain data and hard constraints. This methodology has been applied so far to various convex conic optimization problems where only their inequality constraints are subject to uncertainty. In this paper, the robust optimization methodology is applied to the general nonlinear programming (NLP) problem involving both uncertain inequality and equality constraints. The uncertainty set is defined by conic representable sets, the proposed uncertainty set is general enough to include many uncertainty sets, which have been used in literature, as special cases. The robust counterpart (RC) of the general NLP problem is approximated under this uncertainty set. It is shown that the resulting approximate RC of the general NLP problem is valid in a small neighborhood of the nominal value. Furthermore a rather general class of programming problems is posed that the robust counterparts of its problems can be derived exactly under the proposed uncertainty set. Our results show the applicability of robust optimization to a wider area of real applications and theoretical problems with more general uncertainty sets than those considered so far. The resulting robust counterparts which are traditional optimization problems make it possible to use existing algorithms of mathematical optimization to solve more complicated and general robust optimization problems.     

Comments on “A mixed integer linear programming formulation of the optimal mean/Value-at-Risk portfolio problem”

Benati and Rizzi [S. Benati, R. Rizzi, A mixed integer linear programming formulation of the optimal mean/Value-at-Risk portfolio problem, European Journal of Operational Research 176 (2007) 423–434], in a recent proposal of two linear integer programming models for portfolio optimization using Value-at-Risk as the measure of risk, claimed that the two counterpart models are equivalent. This note shows that this claim is only partly true. The second model attempts to minimize the probability of the portfolio return falling below a certain threshold instead of minimizing the Value-at-Risk. However, the discontinuity of real-world probability values makes the second model impractical. An alternative model with Value-at-Risk as the objective is thus proposed.