13 votes
Accepted

Why does some solvers can only solve conic optimization problems?

The fundamental algorithm employed by Mosek and SeDuMi is a primal-dual interior-point algorithm based on the work of Nesterov and Todd (NT). See for instance my paper and the references therein. This ...
user avatar
  • 2,451
11 votes
Accepted

How to check for convexity of the inequality constraint $−x^2+y−1\ge0$ for a minimization objective function?

I think you are trying to use the following property: $\{x:g(x) \le 0\}$ is convex if $g$ is convex. Note the direction of the inequality. Notice that \begin{align}\{(x,y): -x^2+y-1 \ge 0\}&...
user avatar
11 votes
Accepted

Solving Quadratically Constrained Quadratic Program with Cross Product Terms Only

Rather than solving this directly as MIQCQP, you might consider linearizing the products $y_{ij} x_{ij}$, as shown here, yielding instead an MILP problem.
user avatar
  • 22.2k
11 votes
Accepted

Express equality constraint involving exponentials cones

Q: "How do i write $\text{exp}(a) = b$ using cone programming?" A You don't. $\text{exp}(a) = b$ is a nonlinear equality constraint, and is therefore non-convex. $\text{exp}(a) \le b$ is ...
user avatar
10 votes

What is the best open source solver for large scale LP optimization in pyomo?

There is a new open source solver that looks quite promising, HiGHS: https://www.maths.ed.ac.uk/hall/HiGHS/ But as pointed out by others, for mixed-integer programming problems, at the moment, open-...
user avatar
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

How to solve this convex problem heuristically?

This is a minimum cost flow problem in the bipartite graph $G=(V,A)$ with $V=N_U \cup N_B$. Add a source node and link it to each vertex $v\in N_U$. On each of these arcs, constrain the flow to be in ...
user avatar
  • 10.2k
9 votes

How can I express this max-min in CPLEX?

You can model this as a maxmin problem by introducing an auxiliary variable $\theta$: \begin{align} \max&\quad\theta &\\ \text{s.t.}&\quad\theta \leq \sum_{c=1}^C x_{uc}d_{uc} & \...
user avatar
9 votes
Accepted

Non-symmetric Positive Definite/Semidefinite Matrix in Quadratic Program

Yes, a real PSD matrix $M$ is a symmetric matrix with $$x^TMx\ge 0$$ for any $x$ (see e.g. https://en.wikipedia.org/wiki/Definite_matrix). However, this is not a real restriction. (We have two ...
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
8 votes
Accepted

Inverse of weighted sum of positive definite matrices

This is a convex optimization problem, which can easily be formed (and solved), in CVX, among other convex optimization tools. Let $A = x_1I_1 + x_2I_2 + ... + x_nI_n$, where the $I_i$ are m by m ...
user avatar
8 votes

What does nonconvex multilinear mean?

Non-convex means not convex, which could mean concave but also neither convex nor concave, such as a bilinear term $xy$.
user avatar
8 votes

Fast way to repeatedly solve many similar LPs/QPs in parallel

The OPTMODEL modeling language in SAS (disclaimer: I work at SAS) supports two features for solving independent optimization (LP or otherwise) problems concurrently: The COFOR loop, which ...
user avatar
  • 22.2k
8 votes

Maximize correlation subject to nonconvex correlation constraints

You could add the non-convex constraint $z^Tz = 1$. That would make the objective function and other constraints linear. So this would be a Linear Programming problem, but for a single non-convex ...
user avatar
7 votes

Difference between exploration and exploitation in Simulated Annealing algorithm

I personally see it as follows. In simulated annealing the likelihood of choosing a solution from the neighborhood is quite high at the beginning. This phase could be regarded as exploration as the ...
user avatar
  • 1,546
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

Disciplined convex programming representation of $x\sqrt{1-x}$

I think in convex functions and epigraphs, so I hope you don't mind me deriving a DCP representation of the inequality $$t \geq -x \sqrt{1-x},$$ on $x \in (-∞, 1]$, which I rewrite to $$t \geq (1-x) \...
user avatar
7 votes

Are there any parallel methods for solving multiple general nonlinear convex optimization problems?

Almost all convex optimization problems can be formulated as a conic optimization problem using only the cone types we can handle in practice. See the Mosek modeling cookbook for details. This often ...
user avatar
  • 2,451
6 votes

Disciplined convex programming representation of $x\sqrt{1-x}$

This is possible purely under DCP. As you are interested in the interval $[0,1]$, rewrite your function as $$x\sqrt{1-x}=\exp\left(\ln x+\frac12\ln(1-x)\right),\quad x\in[0,1].$$ Then the following ...
user avatar
  • 5,185
6 votes

Disciplined convex programming representation of $x\sqrt{1-x}$

I don't think you can represent this as a concave function in the (cvxpy-)DCP sense: import cvxpy as cp x=cp.Variable() a=x*cp.sqrt(1-x) a.curvature 'UNKNOWN' ...
user avatar
  • 543
6 votes
Accepted

Approximation methods for a mixed integer convex optimization problem

Mosek 9.x can natively solve mixed-integer exponential cone problems. Formulate the problem in YALMIP, specifying the binary variables as binvar, and Mosek as the solver. YALMIP will call Mosek to ...
user avatar
6 votes

Difference between exploration and exploitation in Simulated Annealing algorithm

Those two are also called Diversification (Exploration) and Intensification (Exploitation). In SA, Diversification relates to the larger values of the probability of accepting an inferior neighbor ...
user avatar
  • 2,044
6 votes

Find the farthest point in hypercube to an exterior point

This answers a comment by the OP, to explain why the other answers are correct. It is due to the following standard result. A concave objective subject to compact convex constraints has a global ...
user avatar
6 votes

Should I process the data or add a new constraint to achieve the target?

Neither. You should delete $d_{u,c}$ from the model whenever $\omega_{u,c} < t_\min$.
user avatar
  • 29.7k
6 votes
Accepted

How can I linearise this nonlinear proportional relation constraint?

Based on the comments (thanks @RobPratt), C4 looks like $$\frac{\sum_{u=1}^U d_{u,1}L_{u}}{\sum_{u=1}^U d_{u,2}L_{u}} = \frac{\psi_1}{\psi_2}$$ with similar constraints for other ratios. Just multiply ...
user avatar
6 votes

How can I express this max-min in CPLEX?

Maximize an auxiliary variable $z$ subject to the constraints $z\le \sum_{c=1}^C d_{u,c}x_{u,c}\ \forall u$.
user avatar
  • 29.7k
6 votes
Accepted

Is $\min \ x^3 \ \mathrm{s.t.}\ x \geq 0$ a convex problem?

An objective function which is convex on only part of its unconstrained domain, but which is convex on the constraint set (i.e.., for any feasible point), can be 'convexified" by modifying the ...
user avatar
6 votes
Accepted

How to convexify log(convex) function?

You are maximizing a convex quadratic (the monotonic log is irrelevant) so the maximum is attained at the border, i.e. either $0$ or $\min(1,\sqrt{1-\text{constant}})$.
user avatar
6 votes

What is a good way to penalise LP relaxation?

You can't quite create a penalty function to enforce integrality and keep your problem linear, at best it would be quadratic (which could indeed be easier to solve sometimes). The closest thing that ...
user avatar
6 votes
Accepted

What is the best open source solver for large scale LP optimization in pyomo?

The Mittlemann benchmarks are an excellent benchmark as ever in particular these two: Benchmark of Barrier LP solvers Large Network-LP Benchmark (commercial vs free) Note that Pyomo doesn't have ...
user avatar

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