Johan Löfberg
  • Member for 2 years, 7 months
  • Last seen this week
Can an integer optimization problem be convex?
14 votes

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 ...

View answer
How can I model regression with an asymmetric loss function?
11 votes

I suspect you want to minimize $\sum\limits_i \left[k_1\max(e_i,0)^2 + k_2\max(-e_i,0)^2\right]$. For instance, $a=0.5$ would correspond to $k_1 = 0.25$ and $k_2 = 2.25$). This can be formulated as a ...

View answer
What does nonconvex multilinear mean?
8 votes

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

View answer
How to deal with a decision variable in the objective function that depends on if-else conditions involving other decision variables?
8 votes

Introduce four binary variables indicating which region you are in and the function value. $$\begin{align} \delta_1 &\rightarrow x_2\geq c, ~x_3\geq d, ~x_1 = a\\ \delta_2 &\rightarrow x_2\...

View answer
Modeling floor function exactly
7 votes

As all have mentioned, the problem is intrinsically hard, as it effectively involves a strict inequality. One way to represent it, using no strict inequalities or magic constants, is to use the ...

View answer
Forbid transformation of max(x,y) into MILP
Accepted answer
6 votes

In YALMIP you can use arbitrary black-box operators to circumvent modelling n = 5; c = randn(3*n,1); A = randn(10*n,3*n); b = rand(10*n,1); % MILP model x = sdpvar(2*n,1); Domain= [0 <= x <= 1];...

View answer
How to convexify log(convex) function?
Accepted answer
6 votes

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}})$.

View answer
Linearizing a quadratic function with more variables or not in Gurobi?
6 votes

You can ask Gurobi to do this for you https://www.gurobi.com/documentation/9.1/refman/preqlinearize.html Whether a linearization leads to better or worse performance is almost impossible to know ...

View answer
Index of element in MILP vector decision variable that equals 1
6 votes

My interpretation is that you want $y$ to be $i$ if $p_i=1$. You can do that with a simple multiplication $y=c^Tp$ where the constant vector $c$ is given by $c_i=i$.

View answer
Matrix Singularity Constraint
6 votes

No, it is an intrinsically non-convex constraint. Just take a diagonal matrix, and the feasible set would be the coordinate axes, i.e. nonconvex and highly ill-conditioned as the feasible set has ...

View answer
How do Quadratic Programming solvers handle variables without bounds?
6 votes

Besides simply adding a large bound (which can cause numerical issues and lead to poor branching) or presolve from constraints involving the unbounded variable, the solver might be able to derive ...

View answer
Why does one objective function prove feasibility faster than another?
Accepted answer
5 votes

Consider maximizing $\sum_{i=1}^n x_i$ subject to $x$ binary and $\sum_{i=1}^n i x_i \leq 2$ Solve relaxation and it gives $x_1 = 1, x_2 = 1/2$ with remaining variables 0. Branch on $x_2 = 0$ and the ...

View answer
Multiple If else constraints in Mixed integer programming
Accepted answer
5 votes

You just seem to have hidden a long list of constraints of the form $(x_i=j) \Rightarrow \text{equalities}_{ij}$ Introduce a binary matrix $C_{ij}$ with $\sum_j C_{ij}= 1$ and $C_{ij} \Rightarrow \{...

View answer
MILP modelling on minimal disturbance of right-hand-side to make a linear system infeasible
5 votes

By Farkas lemma, infeasibility of $Ax\leq b$ is equivalent to feasibility of $A^Ty = 0, y^Tb < 0, y\geq 0$, or more practically useful $A^Ty=0, y^Tb \leq -1, y\geq 0$. Unfortunately, this will lead ...

View answer
How to reformulate a discontinuous piecewise-quadratic functions
Accepted answer
5 votes

Although focused on implementing the model in YALMIP instead of CVX (converting the code should be trivial), precisely this case is described in the following tutorial https://yalmip.github.io/...

View answer
Non-linear optimization local or global solution
Accepted answer
4 votes

Introduce a binary variable $\delta_t$ to represent which case it is and $z_t$ to represent the modelled product, and your MILP model of the piecewise-affine dynamics would be ${EP}_t\ =\ \sum_{i=1}^{...

View answer
Eliminating Variables in Semidefinite Programs Using Equality Constraints
3 votes

Are you talking about doing it in some particularly clever way? If you simply intend to solve the problem in the original dual space (i.e. seeing $X$ as a matrix parameterized by its elements and ...

View answer
When is a formulation with min function an ILP problem?
3 votes

Extending Robs answer slightly, taking into account that you asked about ILP (which I interpret as mixed-integer linear program), the constraint is MILP-representable as long as $f$ is MILP-...

View answer
How to deal with log0 in optimization problem
Accepted answer
3 votes

You are not going to be able to add these logs and quadratic terms to the model via simple double-sided big-M constraints, as they generate non-convex use of convex quadratics and logs, and CVX does ...

View answer
Hyperbolic constraint as second-order cone
3 votes

No, the product is indefinite so it can neither be bounded from above using an tight convex epigraph representation, nor from below using a convex hypograph representation. If you cannot accept a ...

View answer
How to transform this problem with logarithmic objective function into an approximated convex optimization problem?
Accepted answer
3 votes

Introduce a term $y_m$ to replace and lower bound the terms inside the logarithm. Those lower bound constraints simplify to $\sum_{n=1}^{N}(1-x_{m,n})\omega_{m,n}+z\ge y_m(\sum_{n=1}^{N}x_{m,n}\omega_{...

View answer
CPLEX non-convex Quadratic Programming algorithms
3 votes

When you call optimize without any options set, the default values will be used, and those are created by the function baronset.

View answer
Integral of PWL-Constraint in Gurobi (Java)
Accepted answer
2 votes

Integrating a piecewise linear function means you end up with a piecewise quadratic function. Unless there is come convex structure in the resulting piecewise quadratic function (i.e. the PWL is non-...

View answer
How can I model this Hyperbolic constraint?
2 votes

You are asking about representations of $\sqrt{a^2 + b^2} \leq b$. It is trivially only feasible for $a = 0$ and $b\geq 0$. The constraint $b\geq 0$ term will be problematic in your new model as it ...

View answer
Linearizing a constraint with square root of a variable
Accepted answer
2 votes

Define $\mu_i = \sqrt{\lambda_i}$ and the problem is a convex quadratically constrained problem in $(b,\mu)$

View answer
How to convert an element of a variable to a convex constraint using binary variables?
1 votes

Impossible in cvx since absolute value of a complex expression effectively is something represented using second-order cones/quadratics, and you thus have a nonconvex quadratic constraints since you ...

View answer