Questions tagged [optimization]

Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.

Filter by
Sorted by
Tagged with
0
votes
0answers
2 views

Multi-Stage Combinatorial Optimization

I am not sure if I used the corret terminology. I think the problem is a multi-stage combinatorial optimization problem. The problem is like this: There is a dynamic equation $$ S_{k+1} = f(S_k,\pi_k) ...
2
votes
0answers
9 views

Understanding Karush-Kuhn-Tucker conditions

Suppose we may want to use the K–T conditions to find the optimal solution to: \begin{array}{cc} \max & (\text { or } \min ) z=f\left(x_{1}, x_{2}, \ldots, x_{n}\right) \\ \text { s.t. } & g_{...
1
vote
0answers
18 views

Determining the number of switching times in a bang-bang control with nonlinear switching function

In optimal control, if the Hamiltonian $H$ is linear in the control $u$, then the optimality condition $$\frac{\partial H}{\partial u}$$ gives no information about the optimal control $u^*$. The way ...
0
votes
1answer
50 views

Can we tell if ANY Function is Convex or Non-Convex?

Reading the mathematical definition of convexity (https://en.wikipedia.org/wiki/Convex_function), it seems that there is a relatively clear definition as to what makes a function "convex": ...
0
votes
1answer
26 views

Why is this symmetric rank one update "the symmetric solution that is closest?"

Trying to understand symmetric rank one updates and there is this like in the Wikipedia page that says... A twice continuously differentiable function $x\mapsto f(x)$ has a gradient ($\nabla f$) and ...
1
vote
0answers
16 views

Discretization of the Optimization Problem

Say that $g:[0,1] \rightarrow \mathbb{R}$ is a smooth function that has a unique maximizer. Let $x_1,\cdots,x_n$ be a set of equally spaced points on $[0,1]$. Question: How close does the discretized ...
0
votes
0answers
18 views

Lipschitz Continuity of the Value Function [duplicate]

Suppose that $g:[0,1]^2 \rightarrow \mathbb{R}$ is a smooth function. Define the value function $$ g^*(x) = \max_{t \in [0,1]} g(x,t). $$ Question: Under what conditions would $g^*$ be a Lipschitz ...
2
votes
2answers
146 views

Can this Minimization Problem be Proved through Induction?

Consider the following function (this function has $n$ dimensions): $f(x_1,...,x_n)=10n+\sum_{i=1}^n(x_i^2-10\cos(2\pi x_i));\quad -5.12\leq x_i\leq 5.12$, $\text{minimum at }f(0,...,0)=0$. Using ...
2
votes
0answers
17 views

Interpretation of "Noise" in Function Optimization

I am trying to better understand the meaning of "noise" with regards to function optimization - specifically, why "Noisy" functions are more difficult to optimize compared to "...
0
votes
1answer
25 views

Minimization of basis pursuit using ADMM

This note describes how to perform Basis Pursuit using the ADMM method. I am confused about how to map the general algorithm given in the note for this particular context. Can someone explain how it ...
4
votes
0answers
35 views

Optimization with inner product condition

I designed an optimization problem to improve the performance of the neural network learning process on the gradients. I spent hours, but unfortunately it did not work out. Given vectors ${\bf a}_1, {\...
0
votes
0answers
22 views

How to adjust a probability over time while gaining more information? (bayesian statistics)

I'm struggling with a probability problem at work, which I need to understand more in order to devise an algorithm. It seems like a problem typically suited for a bayesian approach, but after hours on ...
1
vote
2answers
79 views

Simply Put - Are Most Functions in the "Real World" Non-Convex?

Is it "safe" to say that natural phenomena in the real world are often characterized and modelled by functions exhibiting irregular and complicated behaviors, and such functions are almost ...
1
vote
0answers
40 views

Is there a such thing called the "Classic Convergence Theorem"?

Has anyone heard of the "classical convergence theorem" before? I tried searching online for this theorem but couldn't really find anything. My Question: Does this theorem have a different ...
5
votes
1answer
94 views

Do we have any way of knowing if natural phenomena in the real world follow the "Lipschitz Condition"?

Recently, I keep coming across terms containing "Lipschitz" pertaining to statistical models and machine learning. This includes terms such as "p-lipschitz (rho), lipschitz convexity, ...
-1
votes
1answer
34 views

simple linear programming problem with integer constraints

Given positive numbers $a, b, c, d, e$, how do I find the maximum value of $ax + by$ such that $cx + dy \leq e$ and $x, y$ are non-negative integers?
0
votes
0answers
35 views

Identification Problem

I want to find the parameters $A_{n\times n}$ and $B_{n\times m}$ of this model: $$x(k+1) = Ax(k) + Bu(k),$$ $\textbf{what I know}:$ $x_{n\times1}(k)$ is a vector of theoretical data, $u_{m\times 1}(k)...
3
votes
0answers
75 views
+50

Uniform convergence of objective function implies convergence of minimizers

Let $A,A_h\in M_{n\times m}(\mathbb{R})$ be $n\times m$ matrices with $\Vert (A-A_h)x\Vert\leq h^2 \Vert x\Vert$ for $h\in (0,1)$ and $e\in \mathbb{R}^n$. Now consider for a fixed $\lambda>0$ the ...
0
votes
0answers
39 views

Newton-Raphson method convergence criteria for a system of two equation with two unknowns

I am having a system of two non-linear equations and I want to compute the root. For example the system is $$f_1(x,y)=0 \tag{1}$$ $$f_2(x,y)=0.\tag{2}$$ In this post, it is shown that the root of the ...
0
votes
2answers
32 views

Convergence of Optimization Algorithms on Non-Convex Functions

Have any major results been established on the use of gradient descent for optimizing non-convex and noisy functions? It seems like the majority of the desirable properties of gradient based ...
-1
votes
0answers
22 views

Lagrange multipliers - 3 constraints for Max and Min [closed]

Can anyone help me on this topic, please! Find the maximum and minimum values of the function f(x,y)=2x^2+2y^2 subject to the constraints x≥0,y≥3 and x+y≤8. Thank you in advance !!
2
votes
3answers
53 views

Find $a$ such that ${x_1}^2+{x_2}^2$ takes the minimal value where $x_1, x_2$ are solutions to $x^2-ax+(a-1)=0$ DO NOT USE CALCULUS

My thinking: Let $x_1 = \frac{a+\sqrt{a^2-4a+4}}{2}$ and $x_2 = \frac{a-\sqrt{a^2-4a+4}}{2}$ By the AGM (Arithmetic-Geometric Mean Inequality): We have $x_1\cdot x_2\le \left(\frac{x_1\cdot \:x_2}{2}\...
1
vote
0answers
29 views

Finding $\max_{0\leq x\leq3} |f'(x)|$, $\max_{0\leq x\leq3} |f''(x)|$, and $\max_{0\leq x\leq3} |f^{(4)}(x)|$ numerically

In an numerical analysis project I need as an intermediate step to calculate the following: $$\max_{0\leq x\leq3} |f'(x)|,\ \ \max_{0\leq x\leq3} |f''(x)|\ \ \text{and}\ \ \max_{0\leq x\leq3} |f^{(4)}...
0
votes
0answers
8 views

Finding Hilbert Basis of a cone

This is more of a general question, I don't necessarily have a specific question I've been given. Part of one of my modules includes finding Hilbert Basis of cones; a question I'm given might look ...
2
votes
1answer
55 views

If $\ z_k\ $ are complex numbers, sort of uniformly spread out on the unit circle, then what is $\ \sup \{\ \vert z_0 + \ldots + z_{n-1} \vert\ \}\ ?$

Let $\ n\in\mathbb{N}\ $ and suppose $\ z_k = x_k + iy_k,\ $ where $ \vert z_k \vert = 1\ $ and $\ \frac{2k\pi}{n} < \arg(z_k) < \frac{2(k+1)\pi}{n}\quad $ for all $\ k\in \{ 0,\ \ldots,\ n-1 \}....
0
votes
1answer
25 views

Convex function inequality with eigenvalues of Hessian matrix are bounded above and away from zero

We have a twice continuously differentiable function $f:\mathbb{R}^d\to\mathbb{R}$ and $\mu,L>0$ constants We have $\mu\cdot E\preccurlyeq\nabla^2f(x)\preccurlyeq L\cdot E$. that means that the ...
0
votes
1answer
25 views

How to show that an optimization problem is equivalent to the Least Squares problem?

I hope you guys can lend me a hand with this one. Let $A\in \mathbb{R}^{m\times{n}}$ and $b\in \mathbb{R}^{m}$, and consider the following optimization problem: $\min_{x\in\mathbb{R}^{n}} \max_{y\in\...
0
votes
1answer
31 views

Why do the derivatives of a function lead towards the extremum of the function?

Is there some theorem in mathematics that formalizes the idea that "for some function, at a given point, moving in the negative direction of the gradient leads you to some (local) extremum point&...
1
vote
0answers
21 views

Minimum of the Rastrigin Function

In the context of Optimization, the Rastrigin Function is used as a popular example to the test the ability of different Optimization Algorithms to find the global minimum of this function. This ...
0
votes
0answers
4 views

Can you check if a boundary point is a local constrained maxima with SO sufficient conditions?

Consider the problem of maximizing some continous $f(x,y)$ subject to the following two non-negativity constraints $g_1,g_2$ and an equality constraint $h$: $g_1=-x\leqslant0,g_2=-y\leqslant0,h(x,y)=...
1
vote
2answers
91 views

Let $a,b\in \mathbb{R}$ such that $ab=2$. Find the max value of $\frac{3}{2\left(a+b\right)^2}$ and $a, b$ where max is attained, without calculus.

My thinking: By Arithmetic and Geometric mean inequality (AGM): $ab\le \left(\frac{a+b}{2}\right)^2$ We know $ab=2$ $\rightarrow$ $2\le \left(\frac{a+b}{2}\right)^2$ $\rightarrow$ $2\le \frac{a^2+b^2}...
0
votes
0answers
26 views

Bounded convex function on a non-compact set

Let $f : A \rightarrow \mathbb R$ where $A \subset \mathbb{R}^n$ is an unbounded (but closed) convex set. If $f$ is bounded and convex, can we say anything about the extremum of it? For $n=1$ and $A=\...
0
votes
0answers
11 views

Generators of a polyhedral cone and half spaces

I'm told that $A = \begin{pmatrix} -6 & 1 & 5\\ 0 & 0 & -1 \\ 1 & -5 & 4 \end{pmatrix} $ and I want to find the generator of the polyhedral cone: $C=${$x \in \mathbb{R}^3: Ax\...
0
votes
1answer
22 views

Optimization problem for competition design

My question is about a particular constrained optimization problem, but the problem is motivated by a hypothetical. Motivating story: I'm organizing a competition where $n$ players will play $d$ ...
-1
votes
1answer
29 views

Supporting hyperplance theorem proof. [closed]

I've read the proof of supporting hyperplane theorem here (page 5 in pdf) I have some questions regarding the proof, that are not clear for me now. Also I include the proof image here: Why $\{x_k\} ...
1
vote
0answers
14 views

Constrained Calculus of Variations: minimise surface area given volume enclosed

I wish to find a curve $u(x)$ (symmetrical about the y-axis), such that the surface area of revolution about the x-axis: $$A[u]=2\pi \int_{x_1}^{x_2} u(x) \sqrt{1+u'(x)^2} dx$$ is minimised. The ...
1
vote
0answers
17 views

Convex Relaxation Problem (theory )

I was wondering if any of you folks could help me with this optimization problem. I want to show if I find a solution $X^*$ for $(P'')$ for which $rank(X ^* ) = 2$, then $X ^* = uu^T $. Here is the ...
1
vote
0answers
22 views

Closed form solution for an $\ell{1}$ optimization problem with a quadratic constraint and bounded variables

Consider the following optimization problem $$ \min \lVert{x}\rVert_{1} \quad\text{s.t} \quad \lVert{y - Ax}\rVert_2 \leq \varepsilon \quad \text{and} \quad x \in [0,1]^n, $$ where $A \in \mathbb{R}^{...
0
votes
0answers
20 views

Find scale factors to maximize images size

I have two images with dimensions $w_1 \times h_1$ and $w_2 \times h_2$ respectively. I want to display them in a screen of size $w_{screen} \times h_{screen}$. My goal is to resize those images with ...
0
votes
0answers
16 views

Orthogonality leading to a simpler optimization problem (procrustes, Stiefel manifold)

I have seen somewhere doing the following "trick" to simplify an optimization problem. I would like to understand the logic behind it. Take two matrices $A$ and $B$ of dimension $N \times N$ ...
4
votes
1answer
64 views

Derivative of Mahalanobis pairwise distance matrix respect to transformation matrix

For a set of vectorial observations $x_i$ stored in the matrix $X$, I would like to obtain the gradient of the pairwise Mahalanobis distance matrix $D$ with respect to the Mahalanobis transformation ...
0
votes
0answers
58 views

Finding minimizer of sum of quadratic matrix form minus log(det(X))

I am looking to solve the following problem. The first task is to comment on the convexity/concavity of the problem and then I need to compute minimizer of the problem. $$\min f \left( \Psi \right) = ​...
0
votes
1answer
26 views

Importance of the KKT Conditions

Does anyone know why the KKT Conditions are considered such a fundamental result in optimization? As far as I understand, the KKT Conditions appear to be a set of conditions that if satisfied - ...
0
votes
1answer
15 views

Solving linear equation with max min function

For a particular problem, I got some equations of the form $a = \min(1-b,0.9)$ $b = \max(\min(1-a,0.7)$, $\min(c, 0.8))$ $c = \max(\min(1-a,0.9)$, $\min(1-c, 0.9)) a,b,c \in [0,1]$ The system has a ...
1
vote
0answers
26 views

Using repeated/higher-order prefix sums (cumulative sum/scan) to calculate fast linear combinations

A few years ago, I learned certain algorithms that use "prefix sums" (also called cumulative sums) for calculating certain array operations in a faster way. For example, if your input array $...
0
votes
0answers
20 views

finding the range in which a function is positive

I have the functions $ f(v) = w-\frac{wz}{z+v}$ and $g(v) = \frac{xy}{y-v}-x$ where all the variables are constants except $v$. I need to find the range of values of $v$ in which $g(v)-f(v) >0$ how ...
1
vote
0answers
9 views

Notating an (arg)max relative to some ordering

Suppose we want to write an expression stating that $x$ satisfies the property $f(x) \geq f(x'), \forall x' \in X$. A fairly common way of doing this in optimization and economics literature is $$ x \...
3
votes
1answer
52 views

Minimum Distance between a kitten and a puppy moving on a coordinate plane

At time $t= 0$, the kitten is at $(1,0)$ and the puppy is at $(-1,0)$. The kitten starts walking counterclockwise along the unit circle, and the puppy runs right along the $x$-axis. If the puppy's ...
0
votes
0answers
12 views

How to implement waiting time in objective function time violation?

I would like to build an objective function for the vehicle platoon problem. the objective function called minimize time violation. vehicle platoon means trucks travelling in a straight line to reduce ...
0
votes
4answers
70 views

Why does $df(x,y)=0$ imply that $\frac{\partial f}{\partial x}=0$ and $\frac{\partial f}{\partial y}=0$?

When finding "critical points" of a multivariable function, we look for the argument of the function where the function's derivative is zero, e.g. $\arg_{x,y \ \in \ \mathbb{R}} \min{f(x, y)}...

1
2 3 4 5
390