Questions tagged [optimality-conditions]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
19 votes
1 answer
280 views

Optimality in a simultaneous column and row generation procedure

What is the optimality argument in a simultaneous column and row generation procedure? By column and row generation procedure I mean a procedure in which every time a column in generated, several ...
Daniel Duque's user avatar
  • 1,355
11 votes
1 answer
565 views

Solvers and saddle points

It seems like most solvers that can tackle nonlinear nonconvex optimization problems (e.g. IPOPT) operate on ultimately solving for the first-order optimality conditions. Can it therefore be assumed ...
Josh Allen's user avatar
11 votes
1 answer
318 views

Finding primal feasible solution from optimal dual

I'm reading Boyd's notes on forming the dual problem in order to decompose the primal problem. On page 4, right before the start of the next section, he talks about how given the optimal dual solution,...
George Chang's user avatar
10 votes
2 answers
227 views

Global optimality condition of non-convex quadratic programs

We know that a convex quadratic maximization (not minimization!) on a polyhedron has its global optimal value on a vertex. Also, I have read in some papers that checking whether a vertex is globally ...
independentvariable's user avatar
8 votes
3 answers
2k views

How to determine different gap rates?

I found in the literature different gaps: a gap between a random solution and an exact solution a gap between the exact solution and a lower bound a gap between the exact solution and a lower bound a ...
fathese's user avatar
  • 423
8 votes
2 answers
204 views

Conditions for minima in calculus of variations

In the calculus of variations (unconstrained), one applies a first-order variation on a general functional of the form $$\int_{a}^{b}F(x,y,y')\,dx$$ to obtain the first-order necessary condition for ...
Josh Allen's user avatar
6 votes
1 answer
88 views

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

I would like to optimize (minimize) the following expression in order to find the functional minimizer $g$ (which should be at least once differentiable): $$ \int_0^\infty g'(x) f(x) \ dx $$ where $f(...
Jay's user avatar
  • 63
6 votes
2 answers
835 views

Existence of Optimal Solution

Assume we are solving $\min\{f(x) \ | \ x \in S \}$. If $f: \mathbb{R}^n \mapsto \mathbb{R}$ is a proper closed convex function, and $S$ is a non-empty closed convex set, does this imply that the ...
independentvariable's user avatar
5 votes
1 answer
405 views

Optimality in L Shaped or Bender Decomposition

I was working on solving a two-stage stochastic problem using L Shaped method (Benders Decomposition). I have discussed the model here: Stochastic Facility Location Model. Do the single-cut/ multi-cut ...
mars's user avatar
  • 629
5 votes
2 answers
193 views

Local optimum of dual of non-linear program

In general, suppose you have a non-convex optimization problem with constraints and you form the dual problem. If you find a local optimum for the dual problem, will the corresponding primal solution ...
George Chang's user avatar
4 votes
1 answer
88 views

How to prove pseudo-convexity of a discrete function?

Given a general function $f:\Bbb Z\to\Bbb R$ is there a simple way to verify whether $f(x)$ is pseudo-convex or not?
Lici's user avatar
  • 43
3 votes
0 answers
29 views

How to establish the optimal value functions and optimal control policy for a controlled random walk problem?

Question: How to establish an explicit characterization of both the optimal value functions and the optimal control policy for a controlled random walk? Background: Assume our system is a perfectly-...
Jxson99's user avatar
  • 141
2 votes
1 answer
151 views

Promising regions in optimization

I have investigated the literature, but I could not find proper explanations. As we know, (meta-)heuristics try to explore promising regions of optimality. The regions are then exploited. What is the ...
YcK's user avatar
  • 79
2 votes
1 answer
191 views

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

What is the difference between Optimality cuts and Feasibility cuts for L shaped method in stochastic programming? Like for the following problem they used Optimality cuts, $$ \begin{aligned} & z=\...
falamiw's user avatar
  • 157
2 votes
0 answers
66 views

FOC point vs Stationary point in local optimization

In this SIAM Review paper the authors are giving the following necessary condition for a point being a local maximum of a convex function: Let $F: \mathbb{R}^n \mapsto \mathbb{R}$ be convex. If $x$ ...
independentvariable's user avatar
0 votes
1 answer
2k views

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

If optimal solution to the primal is degenerate, does it necessarily follow that optimal solution to dual not unique? That is, is uniqueness an unnecessary assumption? Spin-off from here. In my ...
BCLC's user avatar
  • 59
0 votes
0 answers
37 views

How to check optimality of conic optimization problem

I'm trying to solve this problem, but I'm not sure if it is possible to check the optimality of this problem. $$\min_{K,L} \quad Tr(L^\top L)\qquad\\ \text{s.t.} \quad K^\top L = A^\top Q\\ \qquad \...
Jisun Lee's user avatar