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.

learn more… | top users | synonyms (5)

0
votes
0answers
2 views

Rearranging a sequence to minimize a function on its subsequences

Let $Q$ be an arbitrary nonempty sequence of integers with $p$ elements. Let $R$ be a rearrangement of $Q$. Let $A$ be the solution set of $1\leq n\lt m\leq p$, where $n,m\in \mathbb{Z}$. $F(n,m) = ...
0
votes
1answer
12 views

Newtons method for optimization

How can I solve this question? Use Newton's method for a system to write $x^2+y^2=25$ and $x^2-y=2$ in the form $J*\delta=-f$. Define the matrix $J$ and vectors delta, $f$. Dont perform iterations.
2
votes
0answers
37 views

Shortest distance from a point to vertices of a cube

A $d$ dimension cube has vertices $P_1,...,P_{2^d}$, where the coordinates of each vertex are either $0$ or $1$. To find which vertex of $P_1,...P_{2^d}$ is closest to a given point $P=(p_1, ...
1
vote
0answers
20 views

A question about the definition of Lipschitz continuity

Suppose $f(x,y)$ is a function on $R^2$. If $f$ is Lipschitz continuous with respect to $y$, then $|f(x,y_1)-f(x,y_2)|<C|y_1-y_2|$ for some constant $C$. But can anyone tell me whether the ...
1
vote
1answer
19 views

What optimization problem is this?

Minimize $$\sum_{i=1}^{m}w_i x_i$$ with $w_i \in \mathbb{Z}_{\ge0}$, and $x_i \in \{0, 1\}$ subject to a set of $n$ conditions of the form $$\sum_{i\in S_k} x_i \equiv c_k \pmod{2}$$ for $S_k ...
0
votes
0answers
9 views

Eigenvalues and Positive-Definiteness of the Hessian Matrix

Suppose we have a function $f \in C^{2}$ and the Hessian defined as follows: $Hf(x,y)(h) = \displaystyle\frac{1}{2} \begin{pmatrix} h_{1} & h_{2} \\ \end{pmatrix} \begin{pmatrix} f_{xx} ...
1
vote
1answer
25 views

What is the most efficient way of determining a date of birth using yes/no questions?

First question here on StackExchange! Sorry if this question is not quite of the correct style - please let me know if so. Anyway, here's the context. I'm trying to write a program to determine a ...
0
votes
1answer
12 views

Relation between minimum of a function and minimum of the sum of the same function and a linear term

I'd like to know if it's true that if given a function $f(x):X \mapsto \mathbb{R}$ and a vector $c \in X$, then if $$v = \arg\min_x f(x) + x^tc$$ one can say that $$v-c = \arg\min_x f(x)$$ Does this ...
1
vote
0answers
10 views

Evenly divide N items into M groups with constraints

I was wondering if there is a general method for solving the following problem. I have $N$ identical items that I want to divide into $M$ groups in the most equitable/even way possible given that each ...
1
vote
1answer
17 views

Optimization with changing objective function

Is there any theory about (convex) optimization where the objective function is allowed to change during the optimization process? I have a problem where the objective function depends on some ...
0
votes
0answers
5 views

Epi-convergence and normal cones

I have a series of lower semi continuous, eventually level bounded and proper functions $ f^\nu(p)$ that epi-converges to $f(p)$. In this context, it is known from e.g., [7.33, Variational analyis, ...
0
votes
0answers
15 views

Weighting with restrictions, but no clear objective function?

Here is the problem: I have 40 shares in an index and I want to weight them based on their market value, define the known value as $x_i$ In the traditional way, the weight of each share is ...
2
votes
4answers
121 views

Find absolute maximum and minimum with domain

Find absolute maximum and minimum of the function $f(x,y)=3-x^2+y^2$ on the region $R = \{(x,y):1≥x≥0, 2≥y≥0\}$ I found that the gradient is $∇f(x,y)=(2x,2y)$ and that the critical point inside ...
1
vote
0answers
14 views

Maximization over concave subset of variables

Let $f(x_1, \dots, x_N)$ be a concave function in $x_1, \dots, x_N$. For arbitray $n>1$, prove that the (constrained) truncated function defined by $$g(x_1, \dots, x_{n-1}) = \max_{x_n, \dots, x_N ...
0
votes
0answers
8 views

Line search Armijo, Wolfe, Strong Wolfe and Goldstein.

What are the articles (References) who proposed the line search of Armijo, Wolfe, Strong Wolfe, and Goldstein? Articles precursors of unidirectional searches?
0
votes
0answers
19 views

optimization terminology

For the function plotted below, x = 14.5/15 and x = 15.5/15 are two local maximizers. So gradient-based optimization methods could find the global minimum if the initial guess of x is in the range ...
1
vote
1answer
38 views

Algorithms: Maximizing $\Pi \, a^{b}$ (NOTE: Homework)

First I would like to say that this is a homework assignment, so I'm not looking for someone to give me a solution. Just a little guidance if what I have is wrong or inefficient: Given two sets $A$ ...
0
votes
1answer
29 views

Gradient descent for periodic function

Problem: minimize E=$\sum_{t=0}^T [ Y(t)-\sum_{k=0}^K(X(t+k)*cos(k*F+PHI)) ]^2$ where F, PHI - has to be optimized; Y(t), X(t) 1D arrays are given; t=0...T; T=1000; k=0..K; K=10; I can use FFT ...
0
votes
0answers
17 views

Least squares with three quadratic constraints (Ellipse fitting based on algebraic distance)

I would like to fit an ellipse to a given set of scattered data in $\mathcal{R}^2$. The fitting problem is in form least squares, minimizing the sum of squared algebraic distances \begin{equation} ...
1
vote
0answers
9 views

Max flow on undirected graph with constrained edges

I've been trying for a while to develop an algorithm that counts the maximum number of disjoint vertex paths in a graph, but with an addition of "forced paths". Forced paths are here marked with bold ...
1
vote
2answers
24 views

Why does gradient descent make sense?

Suppose I define two functions of $x$ in terms of a convex function $f$ with a unique minimum $x_0$: $$f_1(x) = 1 \times f(x)$$ $$f_2(x) = 2 \times f(x)$$ Suppose I wanted to minimize each of these ...
1
vote
0answers
27 views

Condition for trigonometric inequality

I want to prove the following statement: Suppose $\frac{1}{4}(\cos(\theta_1)+\cos(\theta_2))^2+\lambda^2(a\sin(\theta_1)+b\sin(\theta_2))^2\leq 1$ holds for all $\theta_1,\theta_2\in[-\pi,\pi]$, then ...
0
votes
1answer
30 views

Linear programming and the simplex method

I am trying to solve this system of equations. My approach would be to introduce slack variables and then somehow use the simplex algorithm to solve this. Can anyone show me how this is done?
1
vote
0answers
10 views

Need guidance on a Queuing problem

I can't really go into specifics, I'm more just looking for terms that I can research to get on the right track. Classes of model/processes etc. A close analogy to my problem: I need to optimally ...
0
votes
0answers
2 views

Optimization/Hamiltonian Robinson Crusoe model

Below is a practice problem for a midterm exam in Macroeconomic theory. I'm having a great deal of trouble getting this going as my background is Econ not math so the language transition has been ...
1
vote
1answer
49 views

A problem on positive semi-definite quadratic forms/matrices

Suppose $a+b+c=0$ and (without loss of generality) $a\leq b\leq 0\leq c$, $a^2+b^2+c^2=1$, is the following quadratic form positive semi-definite? Thank you very much. \begin{equation*} \begin{split} ...
0
votes
1answer
25 views

Finding the minimum distance between two lines

I really don't know how to tackle this optimization problem: We consider the two lines $$a(x) = x \begin{pmatrix}1\\2\\3\end{pmatrix}, b(y) = ...
0
votes
0answers
12 views

Projection onto a matrix where the diagonals are identity matrix

I'm trying the understand intersection of convex sets given in "Convex Optimization - Boyd" which I'm also trying to code in cvx. The two convex sets I'm trying to find the intersection are given ...
0
votes
1answer
18 views

Newton Raphson Method in optimiztion.

I understand that Newton Raphson Method is used to find the zero of a function. However when I'm trying to find the maximum or minimum point, why does diving the derivative by the second derivative ...
13
votes
0answers
69 views

Time-optimal control to the origin for two first order ODES - But wait, the node is unstable? Hard-mode active!

I want to find the time optimal control to the origin of the system: $$\dot{x}_1 = 3x_1+ x_2$$ $$\dot{x}_2 = 4x_1 + 3x_2 + u$$ where $|u|\leq 1$ I ran straight into the problem full strength, hit it ...
0
votes
5answers
64 views

Guessing on the SATs, is it ever better to leave it blank than to guess?

On most SAT questions, there are 5 answers of which exactly one is correct and exactly four are wrong. If one answers correctly you get $1$ point. If you answer incorrectly, you receive $-\frac14$ ...
8
votes
0answers
53 views
+50

Largest $n$-vertex polyhedron that fits into a unit sphere

In two dimensions, it is not hard to see that the $n$-vertex polygon of maximum area that fits into a unit circle is the regular $n$-gon whose vertices lie on the circle: For any other vertex ...
1
vote
1answer
25 views

Finding absolute extrema

The function is $f(x,y)=\sin x+\cos y+\sin (xy)$, which on {$(x,y)|0\le x\le 2\pi,~0\le y \le 2\pi$} I want to find the absolute extrema of function $f(x,y)$. I try to find gradient of function $f$, ...
0
votes
1answer
27 views

prove length-like function is convex

I'm trying to prove that $ F(u)= \int\limits_0^1 (1+(du/dx)^2)^{1/2}$ is a convex function of u ; however after squaring both side twice of $(1+(d(tu_1)/dx)^2)^{1/2}+(1+(d((1-t)u_2)/dx)^2)^{1/2} ...
0
votes
0answers
16 views

How to describe contours of a function

$$f(x) = 0.5x^TAx-b^Tx$$ $$A = 2I$$ $$b = (-1, -1, -1,...,-1)^T$$ How can I use this information (or in the general case, just $A$ and $b$) to describe the contours of $f$? I get the feeling that ...
1
vote
0answers
13 views

How to transform equivalent optimization problems

Can somebody either explain how to show the equivalence of the three alternative optimization problems in MPT (or point me to some literature)? I am looking for the necessary "algebraic steps" if at ...
0
votes
0answers
15 views

Regularization of equivalent optimization problems

In portfolio optimization three equivalent optimization problems exist. I am wondering if they are still equivalent when regularized, e.g by ridge regularization. E.g. are the following equivalent ...
2
votes
0answers
19 views

Exercice the converge $r$-superlinearly

Give $x_0 \in \mathbb{R}^*$. Show that $\{x_k\} \subset \mathbb{R}$ converge $r$-superlinearly for $x^∗=0$, where $x_k$ is defined by $x_{k+1}=(1−\beta_k)x_k$ and $\beta_k=1−2^{-k}$ if $k=i^2$ for ...
1
vote
2answers
25 views

Function Maximization

Good day. I have no idea how to solve the following question and will be grateful for any help. Suppose we are given $~n~$ real numbers $~y_1,...,y_n~$. Is there any simple way to minimize function ...
0
votes
0answers
7 views

Help in estimation of unknown parameter not present in the distribution

Question: The unknown parameter to be estimated is the volume of residuals points drawn from a process in multi dimensional space (embedded space after delay embedding) for the following situation : ...
1
vote
0answers
23 views

Help in maximum likelihood estimate of a measure

There is a metric $H$ defined as = $\sum_{i=1, j \neq i}^{N} \min |u_i - u_j| * ..*|u_{i+d-1} - u_{j+d-1}|$ where $u$ is a multi dimensional vector of dimension $d$ and $u_i,u_j$ $\in \mathcal{R}^d$ ...
0
votes
1answer
28 views

How do I plot the following function? [closed]

I need to plot the following function, in order to get the intuition for optimization theory: $$ f(x) = \begin{cases} x , & \text{if $y=x^2$} \\ 0 , & \text{otherwise} \end{cases} $$ How do ...
1
vote
0answers
23 views

Help in deriving Maximum likelihood estimator

The problem is estimating a metric $\operatorname{Vol}(D)$ for the following situation : Given noisy observations the observed data are a random sample $Y_1,\ldots,Y_n$ where $Y_i \in \mathcal{R}^d$. ...
0
votes
2answers
24 views

The maximum volume of Tetrahedron

A optimization problem: Get the maximum volume of a tetrahedron its 4 vertices on the surface of cube whose edge length is 1 . From the geometrical intutition ,we can get : Selecting ...
-1
votes
0answers
19 views

Show that $\{x_k\}$ converge $r$-superlinearly . [closed]

Show that $\{x_k\}$ converge $r$-superlinearly for $x^*=0$, where $x_k$ is defined by $x_{k+1}= (1-\beta_k)x_k$ and $ \beta_k = 1-2^{k}$ if $k=i^2$ for some integer $ i$, ande $ \beta_k=2$ ...
0
votes
0answers
14 views

gradient descent - cost reduces and then increases

I am optimizing a function using Gradient Descent. The learning rate is fixed. First for few iterations the cost decreases after that it starts increases. What is the reason for this?
0
votes
1answer
25 views

Optimization options to select multiple items with different features and values

I'm trying to identify which approach would work best to select a set of elements that have different features that minimise a certain value. To be more specific, I might have a group of elements with ...
2
votes
0answers
39 views

Normalize gradient

I want to minimize a function $f \, : \, \mathbb{R}^{N} \, \longrightarrow \, \mathbb{R}$ (with $N \in \mathbb{N}^{\ast}$. In my problem, $N = 315$). I know that $f$ is differentiable on ...
1
vote
1answer
14 views

Please explain to optimization of maximizing revenue.

I'm finding a hard time understanding optimization. The equation I'm having a hard time figuring out is Maximizing revenue. Suppose the quantity demanded per week of a certain dress to the unit ...
1
vote
1answer
26 views

Taking the dual of this non-standard linear program

I am just beginning to learn linear programming have a question about taking the dual of a non-standard LP specifically the one below: $\min M\\ 2x_1 + 3x_2 + 4x_3 \leq M \\ 2x_1 - x_2 + x_3 \leq M\\ ...