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)

1
vote
0answers
4 views

Minimize distance to a given point subject to a number of linear inequities

I'm trying to find a point that has minimal distance to a known point and satisfies a number of linear inequities. Example in two dimensions and one inequity: $min\{$distance to $(50,70)$ | ...
0
votes
0answers
12 views

Deleting 0's from a random mod 2 matrix

I am fairly new to optimization problems, so please forgive my lack of knowledge. That said, I'm trying to write a program that takes an NxM matrix randomly filled with 0's and 1's, then reduces this ...
1
vote
0answers
24 views

Mixed-Integer Linear Programing : get the maximum constant associated to a non null variable

Does anyone know a way get the maximum constant associated to a non null variable using Mixed-Integer Linear Programing ? For example, supposed that there is 3 variables in the problem : $x$, $y$ and ...
1
vote
0answers
14 views

Can this specific Linear Program constraint be expressed? [duplicate]

Thanks for your time. I have a linear program and no idea how I could express a form of constraint and even if it's possible. Maybe someone here know a solution. A company assembly and sells a ...
0
votes
1answer
13 views

What is the difference between a local maximum and an unconstrained local maximum?

I can see that the definition of local maximum and unconstrained local maximum is written differently, but to me they look like they are defining the same thing. Furthermore, based on Fig 4.1, it ...
1
vote
0answers
61 views

Can this specific Linear Programming constraint be expressed? [on hold]

Thanks for your time. I have a linear program and no idea how I could express a form of constraint and even if it's possible. Maybe someone here know a solution. A company assembly and sells a ...
-1
votes
1answer
19 views

What are the minimum and maximum of $x$ and $y$ within the set $ 0 \le x \le 2$, $x - 2 \le y \le x$?

Given a set, how do I calculate what it's minimum and maximum is for x and y? $$ 0 \le x \le 2 \ , \ x - 2 \le y \le x$$ I informally look at it and think "if x is 0, then y is at most 0, and least ...
0
votes
1answer
30 views

A question on a nonnegative quadratic form

Denote $x,y,z$ as variables, and $a,b,c$ as coefficients. Suppose $a\leq b\leq 0\leq c$ and $a+b+c=0$. Could anyone help me prove whether the following quadratic form positive semi-definite? ...
2
votes
2answers
26 views

maximum, complex quadratic function, Is my solutions correct?

I'm trying to compute $\max_{|z| \le 1} |(z+2)(z-1)|$. Here's how I do it: $\{z \in \mathbb{C} \ | \ |z| \le 1 \}$ is compact and $f(z) = (z+2)(z-1)$ is continuous, so it suffices to look for ...
0
votes
0answers
18 views

Gradient and hessian of square of quadratic form

I'm trying to differentiate a term of the form $(x^TA x)^2$ where $x$ is a vector and $A$ is a symmetric square matrix. Can anyone please tell me what the gradient and Hessian matrix of this term ...
1
vote
1answer
34 views

Optimization problem: rowing across a lake

A woman at a point A on the shore of a circular lake with radius $r=3$ wants to arrive at the point $C$ diametrically opposite $A$ on the other side of the lake in the shortest possible time. She ...
0
votes
1answer
22 views

Finding maximum of the basic Bernstein Polynomials

The basic Bernstein Polynomials $B_{n, k}$ are defined for all integers $n, k$ with $0 \leq k \leq n$ by $B_{n, k} = {n \choose k} x^k (1 - x)^{n-k}$ for $x \in [0,1]$. I want to prove that the ...
0
votes
0answers
22 views

Rearranging a sequence to minimize a series function on its subsequences

Given an arbitrary nonempty sequence of integers $Q$ 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
23 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
58 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
21 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
28 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
10 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
34 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
13 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
1answer
24 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
8 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
131 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
21 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
9 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
20 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
33 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
20 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
41 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
29 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
32 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
11 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
52 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
26 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
13 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 ...
14
votes
0answers
75 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
65 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$ ...
11
votes
1answer
99 views

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
26 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 ...