Skip to main content
12 votes
Accepted

Solvers and saddle points

While iteratively approximately solving the first order Karush-Kuhn-Tucker conditions, many (nonconvex) nonlinear solvers "roll downhill", i.e., enforce descent (for minimization) of the objective ...
Mark L. Stone's user avatar
10 votes

How to determine different gap rates?

MIP solvers such as CPLEX & Gurobi indicate a gap (in %) between the current best solution and the current best dual bound (which is a lower bound for a minimization problem). In general, the ...
mtanneau's user avatar
  • 4,173
8 votes

Optimality in a simultaneous column and row generation procedure

As you are probably aware of, the standard optimality condition for column generation is not valid if not all constraints are included in the master problem, as the dual information of the missing ...
Rolf van Lieshout's user avatar
7 votes

How to determine different gap rates?

Gaps are typically tied to specific models and solution methods. The gap reflects the difference between the best known bound and the objective value of the best solution produced by a particular ...
prubin's user avatar
  • 39.3k
6 votes
Accepted

Optimality in L Shaped or Bender Decomposition

As far as I can see you have binary variables in the first stage and general integer variables in the second stage. This means that classical Benders cuts (based on duality of the subproblems) do not ...
k88074's user avatar
  • 1,671
6 votes

Conditions for minima in calculus of variations

It is possible to apply the notions of stationary points and the second derivative of a function to functionals. For $|\varepsilon|\ll1$ and and a differentiable function $h$, we can write, using ...
TheSimpliFire's user avatar
  • 5,412
6 votes

Conditions for minima in calculus of variations

Coming from the world of optimal control, I tend to view the calculus of variations from a Pontryagin point of view. The conditions stated by Pontryagin are necessary, and sufficient under certain ...
fpacaud's user avatar
  • 1,511
5 votes
Accepted

Existence of Optimal Solution

No, an optimal solution need not exist. Take $f: \mathbb{R} \to \mathbb{R}$ with $f(x) = e^{x}$. However if you restrict $S$ to be compact instead of just closed, then you are guaranteed a solution. ...
Robert Bassett's user avatar
5 votes
Accepted

Minimize $\int_0^\infty g'(x)f(x)\,dx$ where $f(x)$ has a log-normal density

Proposition. There is no minimiser. Proof: An equivalent version of your problem is as follows. Statement. We wish to minimise $$\int_{-\infty}^\infty xe^{q(x)-x^2}\,dx$$ where $q(x)$ is a strictly ...
TheSimpliFire's user avatar
  • 5,412
4 votes

How to determine different gap rates?

A short little note about computing gaps just appeared in 4OR: Laporte, G., Toth, P. A gap in scientific reporting. 4OR-Q J Oper Res (2021). https://doi.org/10.1007/s10288-021-00483-0
Joris Kinable's user avatar
4 votes

Is optimal solution to dual not unique if optimal solution to the primal is degenerate?

If I understand your question correctly, I think you can find your answer by considering the following two primal problems. The first is \begin{alignat*}{2} & \max & x_{1}\\ & \textrm{s....
prubin's user avatar
  • 39.3k
4 votes

Promising regions in optimization

The concept of promising regions (unlike many other concepts in optimization) doesn't have a mathematical definition. It is more an analogy people use to justify why exploring someĀ¹ neighborhood of ...
worldsmithhelper's user avatar
3 votes

Difference between Optimality cuts and Feasibility cuts for L shaped method in stochastic programming?

Given a certain master problem solution, when the subproblem is infeasible, a feasibility cut is added to the master problem. On the other hand, an optimality cut is added to the master problem when ...
Penghui Guo's user avatar
3 votes

Global optimality condition of non-convex quadratic programs

In addition to the references already given in the comments, this paper (DOI link) demonstrates that exact solutions to some non-convex quadratic programs are given by semi-definite programming, and ...
Ryan Cory-Wright's user avatar
3 votes

Local optimum of dual of non-linear program

I guess you are assuming that the dual problem was obtained by only dualizing some of the constraints. The answer below makes sense if I am right about my guess. In general, I believe the answer to ...
batwing's user avatar
  • 1,508
2 votes

Local optimum of dual of non-linear program

From duality theory: At each feasible $x$,$f(x)=\sup_{u>0,v}L(x,u,v)$, and the supremum is taken iff $u\geq 0$ satisfying $u_ih(x)=0,i=1,...,m$. The optimal value of the primal problem, named as $f^...
Nikos Kazazakis's user avatar
2 votes

Global optimality condition of non-convex quadratic programs

With the exception of special cases, this problem is NP-hard. One interesting case is that minimizing a convex or concave function over a simplex can be solved in polynomial time. In other special ...
Nikos Kazazakis's user avatar
2 votes
Accepted

How to prove pseudo-convexity of a discrete function?

For a continuous function, all you need to do is prove that it's (i) non-convex, and (ii) monotonic. (i) can be shown using the eigenvalues of the hessian matrix, and (ii) using the gradient. However, ...
Nikos Kazazakis's user avatar
1 vote

Finding primal feasible solution from optimal dual

When Boyd refers to "regularizing the subproblems," he is likely referring to techniques that improve the numerical stability and convergence properties of the subproblem solvers in the ...
1137h4xor's user avatar
  • 194

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