All Questions
10 questions
0
votes
0
answers
45
views
Generalized envelope theorems
I'm looking for references for two generalizations of Danskin/envelope-type theorems for convex optimization. The first is for when the parameters are functions on a space rather than numbers. A ...
- 4,217
3
votes
1
answer
189
views
Sensitivity of the solution of QP with respect to parameters
Given a quadratic program,
$$\begin{array}{ll} \text{minimize} & \displaystyle \frac12 x^TAx + b^Tx \\ \text{subject to} & Cx \le d \end{array}$$
Suppose $A \succ 0$, so the program strongly ...
- 33
0
votes
0
answers
166
views
Literature request: proving or disproving convexity of the optimal value function of semidefinite program (SDP) or convex optimization in general
Suppose I have a function $f:\mathbb{R}\rightarrow \mathbb{R}$ defined as the following parametric optimization problem:
$$f(p) = \inf_xf_0(x) \quad \text{subject to } \quad G(x,p)\leq 0,$$
where ...
1
vote
0
answers
73
views
Principal component analysis with boundedness constraints
Let $A$ be an $m\times n$ matrix with entries in $F$ ($F=\mathbb{R}$ or $F=\mathbb{C}$).
It is well-known that $A$ has decompositions of the form
$$\displaystyle A = \sum_{k=1}^r\lambda_k\hspace{2mm} ...
- 2,605
1
vote
0
answers
38
views
Solution to dynamic program-type recursion
I have the following dynamic programming principle-type problem.
Suppose that we are given a sequence $\beta_1,\dots,\beta_n\in (0,\infty)$, some target $y\in (0,\infty)$ with $y>\sum_{t=1}^N \...
- 109
0
votes
1
answer
261
views
Non-asymptotic convergence rates for gradient descent
I'd like to know how the number of steps needed for gradient descent depend on properties of the Hessian in non-asymptotic regime.
More specifically, number of gradient descent steps needed to obtain ...
- 2,442
0
votes
1
answer
329
views
Gradient-descent "type" Methods for non-convex and non-smooth functions
Most (stochastic) "gradient descent" type algorithms (such as Nesterov-accelerated gradient-descent or ADAM) seem to be well-defined only for functions which are either:
lower semi-...
- 5,405
0
votes
1
answer
125
views
Are there search algorithms that are competitive against (gradient based) optimization routines for continuous problems?
Suppose that $f: \mathbb{R}^n \to \mathbb{R}$ is a continuous function for which we want to minimize. We may arbitrarily impose good conditions for $f$, such as Lipschitzness, smoothness, convexity, ...
- 479
2
votes
0
answers
98
views
State-of-the-Art algorithms for bilevel optimization
I want to numerically solve a bilevel optimization problem of the form
$$ \min_y f(y, \hat x(y)), \qquad \hat x(y) = \arg\min_x g(x, y) $$
(for simplicity assume that $\min_x g(x, y)$ exists and is ...
- 121
1
vote
0
answers
267
views
Minimum Preserving Transformations [closed]
If $f:X\rightarrow Y$, $g:Y\rightarrow Y$ are functions and $g$ is monotone increasing function then
$$
\operatorname{argmin}_{x \in X} f(x)
=
\operatorname{argmin}_{x \in X} g\circ f(x) .
$$
X and Y ...
- 5,405