# Tag Info

22

"General purpose optimization" is quite broad, so I'll take a step back first, to better identifying the motivation of using ML in optimization settings. To keep things simple, I'll consider a single-objective minimization problem with decision vector $x$, objective function $f$ and some constraints $x \in X$, i.e., \begin{align} (P) \ \ \ \min_{x} ...

18

Local nonlinear optimization solvers, such as IPOPT, are not guaranteed to find a feasible point for problems that are feasible. That is certainly the case for problems with non-convex constraints, and I believe may even occur sometimes for problems having convex nonlinear constraints. The starting (initial) point is often important in determining whether or ...

12

Oh boy. Adding to Mark's great answer, I'll add some fun facts on what can go wrong with IPOPT and feasibility, and provide us with endless nights of entertainment: The linear system solver gets stuck. A timeless classic, especially for MUMPS. It will suddenly slow down to a crawl for no apparent reason. It can also fail outright, which can cascade to ...

11

Yes. But some software may require explicit specification of an objective, which can be a constant. Yes. An optimization solver will attempt to find a feasible solution. Any feasible solution is optimal. Feasibility problem. Some optimization modeling systems or optimization software require an objective to be provided. In such case, you can specify the ...

10

They are equivalent except when $x_{i,g}=x_{j,g}=0$, in which case the second linearization incorrectly contributes $-d_{ij}$ to the objective. Assuming $d_{ij} \ge 0$, I recommend a third linearization (relaxing $z$ and omitting two constraints from linearization 1): \begin{align} z_{ijg}&\ge x_{ig}+x_{jg}-1 \\ z_{ijg}&\ge 0 \end{align}

9

Using the max operator, your objective function has directional derivatives but is not smoothly differentiable. For instance, if $x$ is scalar and $g(x) = x-2$, then at $x=2$ the max term has directional derivative 0 in the direction of decreasing $x$ and $c$ in the direction of increasing $x$. For a gradient-based algorithm, this makes the value of the ...

9

These problems are known as Constraint Satisfaction Problems. In contrast, problems with an objective function are known as Constraint Optimization Problems. Many examples exist. E.g. given some graph with an incomplete edge set, does there exist a closed tour in the graph such that every city is visited exactly once? Or find a schedule that satisfies all ...

8

This answer complements that by @worldsmithhelper . Not only does an objective function not have to include all the decision variables, it need not include any of them. An "optimization" problem having a constant (zero) objective function, which is equivalent to not having an objective function, is called a feasibility problem. Your understanding ...

7

These are called contiguity constraints. See this paper for models and references.

6

This can be handled by transforming this to a bilinear problem, i.e., a problem only involving products of no more than 2 variables at a time. This is accomplished by lifting the problem into a higher dimension, i.e., by introducing new variables and corresponding constraints. For instance, the term $x^3$ can be made bilinear (quadratic), by introducing a ...

6

Surrogate modeling is one of many options. Indeed, it usually does not scale to thousands of variables, unless you can incorporate some domain knowledge in a custom surrogate model. However, you have other options: Surrogate modeling with fewer variables. For example, create a few size groups instead of independent beam sizes A local search or evolutionary ...

6

COUENNE An open-source deterministic global MINLP solver. BONMIN An open-source local MINLP solver. Octeract Engine (our own solver) is a commercial massively parallel deterministic global MINLP solver that is free for academics. What's more interesting is that starting next month the 1-core version of Octeract Engine will also be free for commercial ...

6

I will make the following assumptions: $Q$ is symmetric positive semidefinite $r^Tx \ge 0$ Note that maximizing $\frac{r^Tx}{X^TQx}$ is equivalent to minimizing $\frac{X^TQx}{r^Tx}$ . Under the stated assumptions, this is a convex optimization problem, which can be submitted to and solved by Gurobi. The easiest way of doing so is using a convex ...

6

That IPOPT message means that IPOPT could not find a feasible solution to your problem. The reason could be either that: Once you set that value below 30, IPOPT can no longer find that basin of attraction (or that basin vanishes). Another feasible solution might exist (unless your problem is convex), but IPOPT can't find it. Your problem actually becomes ...

6

Disclaimer: One might want to look for a reformulation or a special structure to apply mathematical tools to find optimal in the feasible set. I am assuming you're already past the possibility that your problem case could be reformulated as a MILP/LP/QP etc. So, with the problem on hand, we're dealing a case where we cannot have a reformulation. Whatever I ...

6

Ipopt seems to have a C# binding. From my own experience WORHP is easy to wrap in high level languages, due a variety of interfaces compatible with different programming styles. Ipopt is a local interior point solver that performs well on quadratic problems. WORHP uses as SQP algorithm, if all constraints and the objective are marked as quadratic or linear ...

5

Indeed, there exists numerous smooth approximations for the max function. One of the most well known approximation is the Kreisselmeier-Steinhauser (KS) functional, that approximates the non-smooth functional $$\max(f_1(x), \cdots, f_n(x))$$ with the smooth functional $$KS(f_1, \cdots, f_n; \rho) = \frac{1}{\rho} \log{\sum_{i=1}^n w_i e^{\rho f_i} } = \... 5 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 both sides by the denominator, which males it a linear constraint.$$\sum_{u=1}^U d_{u,1}L_{u} = \frac{\psi_1}{\psi_2}\sum_{u=1}^U d_{u,2}L_{u}$$Similarly ... 5 I suggest you have a look at LocalSolver to solve your problem. It is free for basic research and teaching. Contrarily to its name suggests, LocalSolver is a global optimization solver. It handles MINLPs. LocaLSolver uses diversification techniques to avoid getting stuck into local optima. Moreover, it allows plugging to your optimization model some external ... 5 NO Not all decision variables need to be present in the objective. They can be often used to handle constraints or express other things. Consider this simple problem:$$\min_{x,y_1,y_2,y_3,y_4,y_5 \in \mathbb{N}} x \text{ subject to }\forall i \in \{1,2,3,4,5\}: \ 0 \leq y_i \leq xy_1+y_2+y_3+y_4+y_5 = 12 Which might answer the question how much ...

4

The notion of NP-hardness relates to whether one class of problems can be solved by a solver for another class of problems where the translation overhead is negligible. The problem you presented is member of many classes of problems. However NP-hardness is the property of a class of problems. So it is impossible to answer whether this particular instance is ...

4

[I'm leaving out constraint 0] I see two levels of decisions in your problem: Group servers into clusters Assign each user to one of these clusters (BTW, this way of seeing the problem is heavily inspired by Facility location problems). The second step is actually the easiest: once the clusters are known, you can just compute each user's gain w.r.t to each ...

4

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}^{n}{x_ic_i^t}\ -L_t + z_t\\ {EP}_{t-1}\leq (1-\delta_t)M, -(1-\delta_t)M \leq z_t - s_t{EP}_{t-1}\leq (1-\delta_t)M\\ ~{EP}_{t-1}\geq -\delta_t M, -\delta_tM \... 4 Rank-one constraints are unfortunately not mixed-integer convex representable, as shown in this paper: https://arxiv.org/abs/1706.05135, although they are quadratically-constrained quadratic representable. If the problem size is not too large, you can try solving it using Gurobi, either directly (for n<=10) or via branch-and-cut (for say n<=50; see ... 4 It is not. Not with the same weights. Regarding general positive coefficients (not necessarily weights) this is a question of existence of a positive solution to the system$Q_{n\times J} w' = q^w_{n\times 1}$, where$Q = [q^1 ... q^J]$collects the horizontally stacked column solution vectors to pure objectives, and$q^w\$ is the column solution vector of ...

4

A common and free NLP solver is IPOPT. IPOPT implements an interior-point line-search filter method, a variation of the interior-point method, these interior point method uses the barrier functions you are aware of. Interior point methods are also useful for large linear systems, as the number of interior steps doesn't depend on the number of constraints. ...

4

This is possible to do in a functional form that preserves all relevant information. As mentioned in the Convex Optimization by Boyd (page 133, Optimizing over some variables): We can always minimize a function by first minimizing over some of the variables, and then minimizing over the remaining ones. This simple and general principle can be used to ...

4

So it seems your strategy (enumerative search on the integer variables) works well, and the issue is solving pure NLP problems. The choice of programming/modeling language you use is dependent on what type of NLPs you solve and that whether you rely on the existing solvers or would be willing to implement your own algorithms. In any case, it is likely that ...

4

You can find non-linear solver binaries here. Also for academic purpose you can use SCIP which is very good. For modelling interface, SCIP has own python interface. Or you can use PYOMO for all of them with jupyter notebook. (I think you have installation problem). Or you can use Google OR-TOOLS but I don't know which solvers supported except SCIP.

3

A commonly used alternative to Interior Point methods is Sequential Quadratic Programming (SQP) https://www.math.uh.edu/~rohop/fall_06/Chapter4.pdf. SQP essentially amounts to iteratively numerically solving the KKT conditions, while "rolling downhill" (for minimization). There are several commercial, as well as free, nonlinear programming solvers ...

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