Skip to main content
18 votes
Accepted

Is This Constraint Convex?

Arguments 3 and 4 are incorrect. The Right-Hand Side (RHS) is not convex. Even if it were, setting a nonlinear equality with either side non-affine is non-convex. As the final coup de grace, even if ...
Mark L. Stone's user avatar
16 votes
Accepted

Reference for "expectation preserves convexity"

Reference "Convex Optimization" by Boyd and Vandenberghe https://web.stanford.edu/~boyd/cvxbook/, section 3.2.1, p. 79. These properties extend to infinite sums and integrals. For example if $f(x,...
Mark L. Stone's user avatar
15 votes
Accepted

Convexity of Variance Minimization

It holds $$ \begin{array}{rcl} \operatorname V(x) &= &\dfrac1N\left\| x-\dfrac{e^\top x}{N} e \right\|^2 \\ & = & \dfrac1N\left(x^\top x+\dfrac{(e^\top x)^2 e^\top e}{N^2}-2\dfrac{...
ErlingMOSEK's user avatar
  • 3,206
15 votes

Can an integer optimization problem be convex?

Feels like you are asking two things, tractability of convex problems and convexity of integer problems. A first order approximation is that convex programs are tractable, .i.e., most problems you ...
Johan Löfberg's user avatar
14 votes
Accepted

How to formulate a problem to prove/disprove convexity?

Based on the comment by Ryan Cory-Wright, you could formulate it like this. Verify convexity of the domain $\{x \in X : g(x) \le 0\}$ Solve the following problem, and check the optimal value. \...
Kevin Dalmeijer's user avatar
13 votes

Can an integer optimization problem be convex?

Mathematically, mixed-integer programs (MIPs) are non-convex, for the very reason you stated: the set $x \in \{0,1\}$ is inherently non-convex. In fact, for a convex optimization problem (e.g. linear ...
Richard's user avatar
  • 3,459
13 votes

Dedicated solver for convex problems

Are you formulating your model with nonlinear expressions that just happen to be convex? Or can you provide conic normal forms, maybe using a modeling tool based on displicined convex programming? In ...
Robert Schwarz's user avatar
13 votes

Is This Constraint Convex?

Counterexamples to your arguments: Argument 1: Only affine equality constraints are convex, $x = y^2$ is not convex. Argument 3: Take $f(x) = x^4$ and $g(x) = x$. Both are convex, but the ratio $h(x)...
Michael Feldmeier's user avatar
10 votes
Accepted

Examples of problems with non-convex constraint functions but convex feasible region

Couldn't we use a combination of trigonometric functions ? E.g. \begin{cases} x \in [0, 2\pi] \\ y \le \sin x \\ y \ge -\sin x \end{cases}
fpacaud's user avatar
  • 1,511
10 votes

Convex vs Strictly Quasiconvex Functions in Optimization

Even though I consider "convex is easy" to be a good rule of thumb, there are some important details to consider. Maybe surprisingly: Convex programming is NP-hard in general In this paper, Samuel ...
Kevin Dalmeijer's user avatar
10 votes

Dedicated solver for convex problems

You may want to try out the NLP solver Knitro, which, despite being commercial, is faster than Ipopt: http://plato.asu.edu/ftp/ampl-nlp.html
fpacaud's user avatar
  • 1,511
10 votes
Accepted

KKT inequality conditions

If you want to use the KKT conditions for the solution, you need to test all possible combinations. This is why in most cases, we use the KKT's to validate that something is an optimal solution, since ...
Richard's user avatar
  • 3,459
10 votes
Accepted

how to penalize a shortfall of a sum of absolute values

If the $x$ variables are bounded, you can do this by introducing some binary variables (one for each $x$). Assume that $L_i \le x_i \le U_i$ for all $i$, where $L_i$ and $U_i$ are constants such that $...
prubin's user avatar
  • 39.5k
10 votes

Is upper incomplete gamma function convex?

The incomplete gamma function is not convex with respect to x for fixed a for 0 < x < a, as evidenced by the following counterexample. Counterexample for a = 10, and x = 1, 5, 9: ...
Mark L. Stone's user avatar
10 votes
Accepted

Is upper incomplete gamma function convex?

No, you cannot prove it is convex in $x$ because it is not, as Mark's counterexample indicates. For fixed $a$, $\Gamma$ is concave for $x\in (0, a-1)$ and convex for $x\in (a-1, a).$ Differentiating ...
prubin's user avatar
  • 39.5k
9 votes

Linear Programming with additional "if-then"/"Default to zero" constraints?

You asked several questions at once but these should be answered all at once too. The problem that you describe is no longer convex. An easy way of seeing this is that the linear combination of the ...
David Bernal's user avatar
  • 1,075
9 votes
Accepted

How to determine the convexity of my problem and categorize it?

This is a Linear-Fractional Programming problem. It can be transformed to a Linear Programming problem as shown in section 4.3.2 "Linear-fractional programming" of "Convex Optimization" by Boyd and ...
Mark L. Stone's user avatar
9 votes
Accepted

Bound on the number of constraints to be generated (lazy constraints)

The number of lazy constraints that have to be used, depends on the algorithm that is used. I will discuss two algorithms: The cutting-plane method: solve the problem to optimality for a subset of ...
Kevin Dalmeijer's user avatar
9 votes

Linear Programming with additional "if-then"/"Default to zero" constraints?

An alternative to using binary variables is to use semicontinuous variables, supported by some solvers. You still wind up with a discrete optimization problem (integer program), but the binary "buy/...
prubin's user avatar
  • 39.5k
9 votes
Accepted

Convexity/Concavity of Average Number of Jobs in M/M/1 Queue?

Your calculations (factoring and simplification) are incorrect. $L$ is neither convex nor concave as a function of $\lambda$ and $\mu$. This can be concluded by examining the eigenvalues of the ...
Mark L. Stone's user avatar
9 votes
Accepted

Linear programming convexity

A linear problem is always convex, because anything linear is convex. As pointed out by @Marco L├╝bbecke, any linear function is also concave. But polygons (feasible sets of linear programs) are only ...
Kuifje's user avatar
  • 13.5k
8 votes

Examples of problems with non-convex constraint functions but convex feasible region

+1 for answer by @fpacaud . Here are two non-contrived examples, which commonly arise in modern O.R. optimization. Rotated Second Order Cone, which arises in Second Order Cone Programming. For ...
Mark L. Stone's user avatar
8 votes

How can I linearize or convexify this binary quadratic optimization problem?

Kevin Dalmeijer's answer is correct for the general case. Since $A$ is symmetric, there may be a method that involves fewer constraints. As suggested by Kevin's comment, I'm going to represent a ...
prubin's user avatar
  • 39.5k
8 votes
Accepted

How can I linearize or convexify this binary quadratic optimization problem?

The constraints $${\bf U}(:,m)^T{\bf A}{\bf U}(:,m)=0,m=1,2,\cdots,M$$ can be rewritten as $$\sum_{i=1}^N \sum_{j=1}^N A(i,j) U(i,m)U(j,m)=0,m=1,2,\cdots,M.$$ Next, you can linearize each of the $U(i,...
Kevin Dalmeijer's user avatar
8 votes
Accepted

Problem solvable $\Rightarrow$ subproblems solvable if feasible region closed, convex?

In your question, you call a problem 'solvable' if there exists an $\hat{x} \in M$ such that \begin{align}c^\top\hat{x} = \inf_{x \in \mathbb{R}^n}&\quad c^\intercal x\\\textrm{s.t.}&\quad x \...
Kevin Dalmeijer's user avatar
8 votes

How to make following constraint a convex one?

The constraint is not convex, and is not transformable to a convex constraint without substantively changing it. The additive linear term $dx$ is irrelevant to convexity. So let's ignore it and look ...
Mark L. Stone's user avatar
7 votes

Reference for "expectation preserves convexity"

$\newcommand{\E}{\mathbb{E}}\newcommand{\R}{\mathbb{R}}$Define $\phi(x) = \E[f(x-Y)]$ and assume that for all $x\in\R$, $f(x-Y)$ is measurable and integrable. Then, for $x,x'\in\R$ and $\alpha \in [0,...
Pantelis Sopasakis's user avatar
7 votes

Convex Maximization with Linear Constraints

The location-inventory problem by Shen, et al. and Daskin, et al. has a concave minimization objective. It's related to economies of scale (which you list in your PS 2) but not exactly the same.
LarrySnyder610's user avatar
7 votes

Recovering primal optimal solutions from dual sub gradient ascent using ergodic primal sequences

In general, nonlinear optimization algorithms implemented in finite precision floating point software don't converge exactly to an optimal solution exactly satisfying the optimality conditions. ...
Mark L. Stone's user avatar
7 votes

How to express this constraint?

No. The constraint $a\ge\gamma b$ sets no upper bound on $a$ so it cannot be bounded above by $b$ as your second formulation suggests. There are a few posts here on the linearisation of the product ...
TheSimpliFire's user avatar
  • 5,412

Only top scored, non community-wiki answers of a minimum length are eligible