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
2answers
128 views

Find the minimum possible order at a restaurant for a party of n people

I want to find an efficient algorithm for determining the minimum possible order total for a party of n people at a restaurant, assuming that the items in the order are unique, and they will each ...
0
votes
1answer
156 views

Maximizing a Strictly Convex Quadratic Function Over a Convex Set

I need to solve a special case of non-convex QCQP (Quadratically Constrained Quadratic Programming) with the general form: $$ \begin{align} & \max {x^T}{A_o}x \\ & \text{s.t.}\left\{ ...
1
vote
1answer
59 views

Second order derivation optimization

Recently I am thinking about a problem that might be easy to answer but for me is a big challenge. Assume you have a function $f(x)$ that is second order derivative. So I am looking for a way to ...
1
vote
0answers
21 views

Weierstrass conditions, what does strong mean, and are both conditions required?

I have the Weierstrass condition: In order that the extremal $\bf{C^*}: x = x^*(t)$ give a strong local minimum to $\bf{J[x]}$ it is sufficient that: # ...
2
votes
3answers
543 views

Maximise the volume of an open triangular prism

An open container is to be constructed out of 200 square centimeters of cardboard. The two end pieces are equilateral triangles. The open top is a horizontal rectangle. Find the lengths of the sides ...
1
vote
0answers
32 views

Check my solution for optimization problem

A piece of wire 40 units long is to be cut into two pieces. One piece will be bent to form a circle; the other will be bent to form a square. Find the minimum and maximum values of the area. I found ...
0
votes
2answers
178 views

Spivak “min” notation confusion

Spivak uses a notation: min$(1, \frac{\epsilon}{2|a| + 1})$ What does he mean by this notation? especially by "min"??
0
votes
1answer
34 views

how to differentiate this equation (contains absolute and norm)

how can I differentiate the following wrt $\mathbf{d}_i$? $\frac{|\mathbf{d}_i^T\mathbf{d}_j|}{\|\mathbf{d}_i\|_2\|\mathbf{d}_j\|_2}$ Thanks in advance.
1
vote
1answer
287 views

Find a Square from n given Points.

Given set X of m Integeral Cords. I need to add minimum number of points to set X such that i get atleast one Square. For example: lets say X:{(0,0),(2,2),(3,3)}. Now i will have to add minimum 2 ...
0
votes
0answers
55 views

Finding the shape which gives the max area with constraint.

The problem is: Given $x$ feet of material with one side being $y$ long, what shape gives the maximum area that can be enclosed. My solution is having the $y$ side a straight line, and having ...
1
vote
0answers
50 views

Is there any standard way to handle fractions of bilinear constraints in optimization?

By fractional bilinear constraints, I mean this form: $$\frac{a_1 + a_2 + a_3 + \cdots}{b_1 + b_2 + b_3 + \cdots} \frac{c_1 + c_2 + c_3 + \cdots}{d_1 + d_2 + d_3 + \cdots}$$ Here, $a,b,c,d$ are ...
0
votes
1answer
54 views

Does maximizing an increasing function of two variables in more favorable conditions always increase both inputs?

Consider the problem of maximizing $\sqrt{x}y$ such that $x+y=10$. By basic calculus we can show that the maximum occurs at $x=10/3$, $y=20/3$. If we loosen the constraint to $x+y=12$ then the maximum ...
1
vote
1answer
133 views

Argument to “linearize” an objective function

I have this optimization problem on the variables $\lambda_\ell^+, \lambda_\ell^-$ such that $ \lambda_\ell^+ \geq \lambda_\ell^-$ with $\ell=1,\ldots,n$ , and fixed $P\in [1/(n+1),1]$ \begin{align} ...
3
votes
1answer
107 views

Unconstrained optimal control - $J = \int_0^{t_1} (x^2 + ux + \frac{1}{2} u^2) dt$

I've been given the following problem to solve, and I'm having a lot of difficulty in understanding what I can do. The system $\dot x = x + u$, where $u = u(t)$ is not subject to any constraint, ...
0
votes
1answer
124 views

Simplex method - infeasible basic variables

I am working on an optimization problem right now, and I am using the simplex method on the initial tableau. At first, the basic variables are all non-negative and are equal to the slack variables. ...
0
votes
1answer
176 views

Dual simplex doubt (unrestricted)

I have this two problems and i only want to find the dual form: $\begin{gather} max\hspace{.1cm}z =5x_1+6x_2\\ s.t\hspace{.1cm}x_1+2x_2=5\\ -x_1+5x_2 \ge 3\\ x_2 \ge 0\\ x_1\hspace{.1cm} ...
3
votes
4answers
74 views

Find the maximum of $\frac{1}{1+|x|}+\frac{1}{1+|x-a|}$

Let $a>0$. Show that the maximum value of the function $$f(x)= \frac{1}{1+|x|}+\frac{1}{1+|x-a|}$$ is $$\frac{2+a}{1+a}.$$ really need some help with this thing
0
votes
1answer
68 views

How to find the convex hull of a given set?

$A=\{(0,0),(0,1),(1,0)\}$ $B=\mathbb{Q}^2$ $C=\{(x,\sqrt{x})\in \mathbb{R}^2:x\ge0\}$ I have to find Conv(A), Conv(B) and Conv(C). My attempt Conv(A) is the boundary (correction: obviously it ...
2
votes
1answer
111 views

Strongly minimizing curve optimisation with Weierstrass condition

No idea where to start on this one: Find the strongly minimizing curve and value of $J_{min}$ for cases: $$\int_1^2 (t^2\dot{x}^2 + 2x^2) dt$$ where $x(1)=0,x(2)=7$ Using the Weierstrass ...
0
votes
1answer
415 views

Linear Programming : Is there any other way to solve than graphs?

In my highschool curriculum there's a a chapter on Linear Programming Problems. In the chapter there are bunch of unproved statements and mechanical ways to solve linear problem. But my question is- ...
0
votes
0answers
39 views

is $R^N_{ ++}$ a convex set?

Is $R^N_{ ++}$ a convex set? I'm working on some optimization hw problems that have some functions of the type: $f:\mathbb{R}^2_{++} \rightarrow \mathbb{R}$ And it seems like in general whenever ...
1
vote
1answer
40 views

By minimizing the function $\phi(s,t) = \frac{1}{2} \mid\mid \textbf{b} - (s\textbf{a}_1 + t\textbf{a}_2) \mid\mid^2$, find a for

Suppose $\textbf{a}_1$ and $\textbf{a}_2$ are linearly independent vectors, $L = \text{span} \ \{{\textbf{a}_1, \textbf{a}_2}\}$, and $\textbf{b}$ is a vector not in $L$. By minimizing the function ...
2
votes
1answer
43 views

Maximize $ax + by + cz$ given $x^2 + y^2 + z^2 = k^2$. Write answer as Schwartz inequality for dot products.

Maximize $ax + by + cz$ given $x^2 + y^2 + z^2 = k^2$. Write the answer as the Schwartz inequality for dot products $(a, b, c) \cdot (x, y, z) \le \_\_\_\_\_\_\_\_ \ k$. I'm stuck on this problem. I ...
2
votes
0answers
153 views

Maximize and minimize a function using Lagrange multipliers.

I want to maximize and minimize $$h(a,b) = a + b$$ given the constraint $$g(a,b) = a^{\frac{1}{3}}b^{\frac{2}{3}} = l$$ I'm trying to use Lagrange multipliers. Here's what I did: \begin{align} ...
0
votes
1answer
22 views

Rate of growth of $a$ in $f(x) = \frac{\ln(ax)}{x}$ causing movement of extrema

Problem description Look at the function $f(x) = \frac{\ln(ax)}{x}$ on a cartesian system with steps of 1cm on both axes. a) Show that $f$ has a local maximum for $x = \frac ea$. b) When $a$ ...
1
vote
2answers
85 views

Is a minimum a minimum in every norm? (for finite-dimensional vector spaces)

I have a question regarding the equivalence of the norms in finite-dimensional vector spaces. Basically the question is: if $\hat{x}$ is some minimum-norm solution in a subspace $\mathcal{K}$ under ...
2
votes
0answers
121 views

Saddle point problem (KKT) with block-diagonal matrix

Consider the following saddle point problem originating from an interior-point method algorithm: $$ \begin{bmatrix}\mathbf{H} & \mathbf{A}^{T}\\ \mathbf{A} & \mathbf{0} ...
0
votes
1answer
280 views

Give example of a set which has No Extreme Point !!..

Give example of a set in R^2 , which has no extreme point ?? We were given this question for assignment !!..I thought of a simple line but doing some research i stumbled upon this solution which ...
1
vote
2answers
257 views

Minimize and maximize the function $g(a,b) = a + b$ given the constraint $h(a,b) = \frac{1}{a} + \frac{1}{b} = 1$.

I want to minimize and maximize the function $g(a,b) = a + b$ given the constraint $h(a,b) = \frac{1}{a} + \frac{1}{b} = 1$, and I want to find the values of $a, b,$ and $\lambda$. This is what I've ...
1
vote
0answers
48 views

Minimizing a function using a direct approach (no Lagrange multipliers).

I want to minimize $g = x^2 + y^2$. My constraint is $h = 2x +y = l$. I know that using Lagrange multipliers is unnecessary here. I solved the constraint to get $y = l - 2x$. I then substituted this ...
1
vote
2answers
95 views

Finding minimum on graph for given domain

So I want to find what is the minimum value of a graph on a certain domain. For example, for $y=x^2+1$ between $x=-3$ and $2$, the minimum value is at 1 at x=0. I think I know how to find minimums ...
2
votes
0answers
71 views

Prove circle packing solution is optimal

Background: This is a follow on from this question of how to maximise the area of two non overlapping circles of arbitrary radii packed into a rectangle of arbitrary width and height. I proposed a ...
0
votes
1answer
330 views

Optimization Calculus.. a box/shelter with sides missing..

I'm solving a problem involving calculus optimization. The problem is the following: "We plan to build a boxshaped shelter with no floor and one side open. (Hence we need a roof and three sides). The ...
1
vote
1answer
335 views

How to apply Sherman Morrison formula for rank 2 update?

For obtaining the inverse update in BFGS, Sherman-Morrison needs to be applied twice since it is a rank 2 update. But what does it mean to apply it twice?
0
votes
5answers
4k views

Minimum perimeter of a three-sided rectangular fence with given enclosed area

A three-sided fence is to be built next to a straight section of a river, which forms the fourth side of a rectangular region. The enclosed area is equal to 1800 ft^2. Find the minimum perimeter and ...
0
votes
2answers
27 views

When is $A^t+B^{1-t}$ for $t \in[0,1]$ maximized?

When is $A^t+B^{1-t}$ for $t \in[0,1]$ maximized. Suppose that $A,B \in \mathbb{R}^{+}$. This is very similar to convex combination but only in exponents.
1
vote
1answer
59 views

Proving a point is a local minimum

I have a rather basic question. I have a function $f:R \rightarrow R$, and I want to show a point, $x^*$, is local minimum, i.e., $f(x^*+\delta) \geq f(x^*), \ \delta \to 0$. I can show that: $f(x^* ...
1
vote
1answer
28 views

Modelling problem

i have this problem and i have to model it in a boolean formula. Assuming that variables can have value 0 or 1 and V is OR and ∧ is AND. I have n boolean variables x1,x2......xn. i want a formula ...
1
vote
1answer
38 views

Talyor's Theorem in Nocedal's Numerical Optimization

Please kindly refer to the figure below. I understand that (2.4) is just another formulation of Mean Value Theorem and I understand its geometrical meaning in 1-D case. However, I do not know what ...
1
vote
1answer
54 views

How to approach a minmax problem?

Starting with a certain geometric problem, I have reached this function: $$R(s,t,u,v)=\max(s-u,s+u,t-v,t+v,sX+tY+u, tX-sY+v)$$ where $X\geq0$ and $Y\geq0$ are parameters. I have to find the minimum ...
0
votes
2answers
52 views

Find the maximum points of $f(x)=e^{-x}\sin^2(\pi x) \hspace{0.4cm},0<x<10$

Find the maximum points of $$f(x)=e^{-x}\sin^2(\pi x) \hspace{0.4cm},0<x<10$$ My calculations:I have calculated $f'(x)=\pi e^{-x}\sin(2\pi x)-e^{-x}\sin^2(\pi x)$ $f''(x)=e^{-x}\sin^2(\pi ...
0
votes
0answers
78 views

Monotonically decreasing function for multiplication product?

I have a set of numbers $S = [100,999]$ for which I want the maximum product $p$ such that $p = a \times b$ for all $a,b \in S$ also fulfilling some condition $C$. I would like $p$ to be monotonically ...
1
vote
4answers
59 views

Is $\max\left(\frac{A}{B},\frac{C}{D}\right) \ge \frac{\max(A,C)}{\max(B,D)}$

Is $\max\left(\frac{A}{B},\frac{C}{D}\right) \ge \frac{\max(A,C)}{\max(B,D)}$? Given that $A,B,C,D>0$. What about $\frac{A}{B},\frac{C}{D}>1$. Is there a better bound for the left ...
0
votes
1answer
77 views

Logistic regression maximum likelihood derivation

the following equations are given: $\sum_{j=1}^c\hat{P}_j = 1$ $\sigma_i(\mathbf{z}; \theta) = \frac{exp(\mathbf{\theta}_i^T\mathbf{z})}{\sum_{j=1}^cexp(\mathbf{\theta}_j^T\mathbf{z})}$ $L = ...
0
votes
1answer
137 views

Show running time of algorithm on input of size n is $\Omega$ (f(n))

Basically I'm given this algorithm where I have an array A of integers which outputs an n-by-n array B where B[i,j] contains the sum of the array entries A and asked to give a bound of the form ...
0
votes
1answer
123 views

Derivation of Efficient Frontier (portfolio optimization) question

In Robert Merton's derivation of the efficient frontier of a portfolio, he minimizes $\frac{1}{2}\sigma^2 $ over the investment weights in each asset, where $\sigma^2$ represents portfolio variance. ...
0
votes
1answer
63 views

Lagrange Multipliers for Implicit Functions

How can I find the minimum / maximum of a function for one variable defined implicitly (f(x, y, z) = c) with a constraint g(x, y) = c on the domain? For example, say you wanted to minimize for z: ...
1
vote
1answer
38 views

Designing linear systems to respond to particular kinds of oscillations

Say that I have a linear system which is being perturbed by an oscillating signal of a single frequency, of the form $$ \dot{\vec{x}}(t) = A\vec{x} + B \sin(\alpha t), $$ where $B$ is a vector of 1s ...
0
votes
0answers
194 views

confused between convex and non-linear optimziation

I have an optimization function which contains an objective function which contains sum of decision variables, division of sum of decision variables and also product of sum of decision variables. The ...
0
votes
2answers
50 views

How fast can you split a set of numbers into 2 sets, where the difference of each sum is maximized

How fast can you perform this task? More specifically, if there is a set of 2n elements, how fast could you split those elements into two groups of n elements where the sum of each group is of ...