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 ...
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,...
user avatar
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 ...
user avatar
14 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{...
user avatar
  • 2,536
13 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. \...
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)...
user avatar
12 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 ...
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}
user avatar
  • 1,391
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 ...
user avatar
10 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 ...
user avatar
  • 3,359
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 ...
user avatar
  • 3,359
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 $...
user avatar
  • 31k
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 ...
user avatar
  • 1,045
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 ...
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 ...
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/...
user avatar
  • 31k
9 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
user avatar
  • 1,391
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 ...
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 ...
user avatar
  • 10.4k
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 ...
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 ...
user avatar
  • 31k
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,...
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 \...
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 ...
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,...
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.
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. ...
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 ...
user avatar
  • 5,191
7 votes

Linear programming convexity

No, linear programming is convex, which you can prove directly from the definition. If $A x \le b$ and $A y \le b$, then for arbitrary $\alpha\in[0,1]$, we have $$A (\alpha x+(1-\alpha)y) = \alpha A ...
user avatar
  • 22.7k
6 votes
Accepted

Convexity of a QP

You can use Singular Value Decomposition or Cholesky Decomposition. I recommend you read this Verification of Positive Definiteness. On page 9 there is an algorithm in MATLAB.
user avatar

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