Skip to main content
14 votes

Do convex quadratic problems always have sparse solutions?

Consider the convex QP $$\min \lbrace \sum_{i=1}^n x_i^2 : x\in \mathbb{R}^n, \sum_{i=1}^n x_i = 1\rbrace.$$ The solution is $$x = (\frac{1}{n},\dots,\frac{1}{n}),$$which is fully dense.
prubin's user avatar
  • 39.5k
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 ...
ErlingMOSEK's user avatar
  • 3,206
12 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\}&...
Siong Thye Goh's user avatar
12 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-...
Philipp Christophel's user avatar
12 votes
Accepted

Solver for convex optimization with exponent in the objective function

You are missing some details for the claimed convexity of $f(x)$. I will assume that you meant to say convex on the domain $C+mx+\frac{s}{x+t} \geq 0$ and $x+t \geq 0$. In this case the epigraph of $f(...
Henrik Alsing Friberg's 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.
RobPratt's user avatar
  • 32.7k
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 ...
Mark L. Stone's user avatar
10 votes
Accepted

How to solve this linear program with an exponential number of constraints?

For each $k\in\{1,\dots,n\}$, you want the sum of the $k$ smallest $f_i(x)$ to be at least $\sum_{j=1}^k b_j$. Equivalently, you want the sum of the $n-k$ largest $f_i(x)$ to be at most $\sum_{i=1}^n ...
RobPratt's user avatar
  • 32.7k
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

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 ...
Kuifje's user avatar
  • 13.5k
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} & \...
Joris Kinable's 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 ...
Erwin Kalvelagen's user avatar
9 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 ...
worldsmithhelper's user avatar
9 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 ...
Mark L. Stone's user avatar
9 votes
Accepted

Determining the optimize lambda in Multi-Objective Optimization

There is no mathematical way to derive (or justify) a value for $\lambda$. The justification has to be made in the context of a specific problem and a specific (reasonably credible) decision maker. ...
prubin's user avatar
  • 39.5k
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
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$.
Johan Löfberg's 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 ...
RobPratt's user avatar
  • 32.7k
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 ...
Mark L. Stone's user avatar
8 votes
Accepted

How to find the index of the item, the first time appears?

Here's a formulation if at least one $x_i$ must be $1$: \begin{align} \sum_i y_i &= 1 \tag1\label1\\ y_i &\le x_i &&\text{for all $i$} \tag2\label2\\ y_i &\le 1-x_j &&\text{...
RobPratt's user avatar
  • 32.7k
8 votes

Determining the optimize lambda in Multi-Objective Optimization

Another approach could be generating the Pareto Frontier, solving the problem several times for different values of lambda, using a Weighted sum algorithm (see this or this).
Enrique Gabriel Baquela's 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 ...
PeterBe's user avatar
  • 1,652
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

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) \...
Henrik Alsing Friberg's user avatar
7 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 ...
Mark L. Stone's user avatar
7 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 ...
Mark L. Stone's 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 ...
ErlingMOSEK's user avatar
  • 3,206
7 votes

Adding CVXPY abs to optimization problem turns out to be non-DCP

I think you want cp.norm1(beta - s), with no need for abs. This is DCP-compliant. Taking separate norms of ...
Mark L. Stone's user avatar
7 votes

How to find the index of the item, the first time appears?

Suppose the index is 1-based and set constant $u_0 = 0$. With binary variables $u_i, y_i, i=1,\dots,n$ and constraints $$ \begin{align} u_i &\geq x_i\\ u_i &\geq u_{i-1}\\ u_i &\leq x_i + ...
xd y's user avatar
  • 1,196
7 votes

Determining the optimize lambda in Multi-Objective Optimization

In addition to the above answers, there's good deal of discussion here. One of the experts logically breaks down some key questions like avoiding dominating solution by sticking to single combination ...
Sutanu Majumdar's user avatar

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